[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

Regions



I just thought of a neat representation for fully ordered regions. A
region has a Boolean startsInside, telling whether negative infinity
is inside or outside the set, and an array of (Position,
TransitionType) pairs, arranged by ascending positions. The Transition
type is either Before, After, or Both, to tell whether the boundary of
the set is crossed before, after, or on both sides of the position
(one is assumed to be travelling from smaller to larger positions. A
couple of examples: (assumed to be on the real line because for
integers we could arrange for all transitions to be Before).

	[3,5) : False, {(3, Before), (5, Before)}
	(-Inf, +Inf) : True, {}
	{} : False, {}
	(-Inf, 0] U [6] U [8, 9) U (9, 20] : True, {(0, After),
		(6, Both), (8, Before), (9, Both), (20, After)}

To complement, just invert the startsInside flag. Union and
intersection operations are O(m+n) state machine algorithms merging
two sorted lists of transitions. This single representation covers all
cases with neither the hideous conditionals in the old OrderedRegion
code nor the jungle of classes in the new FORegion system. I'd like to
keep this on the back burner for performance engineering phase, as I
have a feeling we're going to need to give regions a boost. (Some
small attention to efficiency in C++ would really make it scream --
bit operations on the flags and such).
	--ravi