Region splay

[Ravi Pandya <ravi>]

I ran into a bug in the splay algorithm last night. Because the
grouping was hidden inside the rotate operations, I thought the
problem was more fundamental than it was, so I rewrote the splay
algorithm to maintain grouping between splays of the left and right
ends of a region. In designing the algorithm, I had made the
simplifying assumption that we had fully ordered spaces, and that the
tree was kept in ordered form (left < right). It turns out that the
algorithm doesn't require full ordering if proper grouping is built
into the rotate operations. My algorithm is much simpler than the old
algorithm, mostly because the (later unnecessary) ordering assumption
caused me to take a different perspective on the problem.

>From this perspective, it looked like it ought to be possible to do a
Status: RO

region splay algorithm, and I couldn't fall asleep last night until
I'd worked out the details. A simple extension of the new algorithm
gives a region splay with the following properties:

	- 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

The algorithm is:

SplayEntLoaf >> {IntegerVar} splay: region {Region}

"Ensure that each of my children is either all in or all out of the
region. 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."

Inner loaf:

"optimization: use external regions to avoid splaying children if possible"
left := myLeftOCrum splay: left transformed region.
right := myRightOCrum splay: right transformed region.

Rearrange the subtree according to the following table:

left	right	rearrange subtree from -> to		return
------	------	--------------------------------------	------
0	0	no change				0
0	1	(A (B* C)) -> (B* (A C))		1
0	2	(A B*) -> (B* A)			1
1	0	((A* B) C) -> (A* (B C))		1
1	1	((A* B) (C* D)) -> ((A* C*) (B D))	1
1	2	((A* B) C*) -> ((A* C*) B)		1
2	0	no change				1
2	1	(A* (B* C)) -> ((A* B*) C)		1
2	2	no change				2

* indicates a subtree that is all in the region, as opposed to
one that is all outside the region (one or the other is guaranteed,
because the children have already been splayed)

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.

Enforcing that left is inside and right is outside rather than vice
versa is not necessary, but it simplifies the book-keeping, which is
complicated enough already. 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.
	--ravi

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.