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

for the record: region splay

Abstract: I think I came up with an algorithm for region splay
(necessary for ND, for example).  Rather than pursue it now, I'll just
post it so it makes it into our records.  Warning: this will be arcane!

Right now, the splay.Region operation only works for regions with one
or two distinctions.  The distinctions of a simple region are the
inequality regions that *intersect* to form the region.  The current
splay.Region gets the distinction regions from the simple region and
splays each of them down the otree.  The intention is to force all the
rangeElements within the region to be in a single subtree, somewhere
in the otree.  

I think the new algorithm just splays the incoming region down the
tree once for every distinction in the region.  The rotation
operations might take an extra argument to ensure that subLoaves in
the region get brought next to each other.  Since each splay
effectively forces the tree to represent one distinction, splaying
once for each distinction will force every distinction on the tree
(assuming the rotate operation maintains grouping).

Clear?  :-)