Region splay

[Eric Dean Tribble <tribble>]

MarkM observed when I first started thinking about a region splay
operation that we should just get a simply splay operation working
because once the structure existed and we all had time to bounce the
spaly stuff around (bby February, say), it would all be much easier to
think about.  Congratulations, you're right on time!

	   - isolates the region in its own subtree and brings it to the top
	   - groups the tree according to the kind of regions it gets
	   as requests (hence does not require any external grouping heuristic)
	   - does extra search only if the requests (hence grouping)
	   don't correspond well to the simple regions in the space
	   - works fine in the presence of overlapping subtree regions,
	   but it may do some extra searching

These are exactly the properties I started with for a region splay
operation, and they are sufficient to be wonderful.  While discussing
my algorithm sketch with Markm, we noticed that enfilades needed
grouping heuristics and overlap in order to maintain balance.  With
splay trees, we can probably transform the tree during splay
operations from one non-overlapping tree to another.  Your approach
using tables of transformation rules should easily extend to figure
out if this makes sense.  non-overlapping issues only make sense for
simple regions, however.  More on this later.

It's going to be fun proving that any of these algorithms are still
amortized log-bounded.  It might even be easy....

   Return 0, 1, or 2 according to the number of my children that
   are in the region. If 1, then the left child is in the region, and the
   right child outside."

This by itself would simplify the algorithm.

   0	2	(A B*) -> (B* A)			1
Cute!

   Virtual and partial loaves need to replace themselves with an actual
   subtree in which the leaves are all in or all out of the region, and
   return the result from splaying it.

   It's sufficiently complicated that I don't
   see any need to implement the algorithm right away, but it's nice to
   know it'll be there when we need it.

How much different is it from the algorithm that you already coded?
The algorithm looks correct, and your approach to the algorithm
certainly is a clarifying way to think about it and understand it..
After FM I'll wrap it around the hard cases.  If it still looks
correct, I'll add this algorithm when I next revamp the ent (to get
rid of SpatialBehaviors).

   P.S. Dean: the algorithm you posted will work fine for the
   multi-dimensional case, but not for a region splay of, say, every
   fifth element, where the grouping algorithm has no way to know how to
   keep things in the region together across distinction splays. For
   arbitrary regions, you really need to do the splay all at once.

The first sketch of the algorithm I posted used the count of
distinctions only as a count.  Further discussion with MarkM
immediately eliminated the use of distinctions.  It used the full
region for grouping, so would result in similar tree structures
(assuming it worked!).  Your algorithm is abstractly similar, but much
simpler and clearer.  Great Work!

dean

PS: Ravi:  where would you like to go for dinner?  :-)