Regions

[Ravi Pandya <acad!xanadu!ravi>]

Date: Thu, 12 Apr 90 20:57:05 PDT
   From: acad!alce!greg (Greg Lutz)

   Your representation is quite equivalent to the other notation in your
   examples ("(-Inf, 0] U [6] U [8, 9) U (9, 20]"), which is more
   literally translatable as an array of triples (start, end, eflags),
   where eflags is a pair of Booleans telling whether the two brackets are
   round or square.

This is the representation we used to use, along with another pair of
booleans saying whether each side was infinite or not.

		  Does your representation have any advantage other
   than easy invertibility?  Well, on consideration, maybe another small
   one:  a member of the array used in your representation can't be
   invalid in itself, whereas in "mine" it could have the "start" and
   "end" out of order.

In the transition representation, the only error is for the array to
be unsorted. There are many more possible wrong formats for the array
of intervals (intervals overlap, start > end, one side is infinite but
closed, etc.) The old code had many *very* ugly conditional expressions
to check all the cases.

	  Oh yes: yours also doesn't require any literal
   representation for -Inf and +Inf.  I bet that's the big one.

Yea verily! The big advantage of this representation is that all of
the special cases (half- and fully-infinite regions, empty regions)
are just one case of the general format, and handled by the general
algorithms.
	--ravi