com.inxar.syntacs.util
Class BubbleTree
java.lang.Object
|
+--com.inxar.syntacs.util.BubbleTree
- public class BubbleTree
- extends Object
BubbleTree
is a binary tree (interval tree) data
structure which maintains a IntSet
of integers at each
node in the tree. The unique feature of is that adjacent nodes
which 'abut' each other (the low endpoint of I1
is one
greater than the high endpoint of I2
) will merge into
a single node when their bitsets are equal. This can be envisioned
like two oil bubbles floating in water suddenly merging onto one
larger oil bubble. This is the origin of 'bubble' in
'BubbleTree
'.
Two bubbles in the tree may merge in four different ways. Each
interval (node) in the tree may at some point find that its IntSet is
equal to one or more of its four "neighbors". Thus, merging may
occur with the left upper node, the right upper node, the left down
node, or the right down node.
This data structure is exceedingly cool.
Inner Class Summary |
static class |
BubbleTree.Bubble
A Bubble is a single node in a BubbleTree interval tree. |
Constructor Summary |
BubbleTree()
Zero-argument constructor creates a new empty
BubbleTree . |
Method Summary |
IntSet |
get(int key)
Returns the IntSet maintained at the interval which
includes the given key. |
boolean |
isEmpty()
Returns true if this is an empty tree. |
void |
put(int lo,
int hi,
IntSet other)
Puts the given value across the given interval <lo,hi>. |
String |
toString()
|
root
public BubbleTree.Bubble root
BubbleTree
public BubbleTree()
- Zero-argument constructor creates a new empty
BubbleTree
.
put
public void put(int lo,
int hi,
IntSet other)
- Puts the given value across the given interval <lo,hi>.
get
public IntSet get(int key)
- Returns the
IntSet
maintained at the interval which
includes the given key.
isEmpty
public boolean isEmpty()
- Returns
true
if this is an empty tree.
toString
public String toString()
- Overrides:
toString
in class Object