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.
 
Field Summary
 BubbleTree.Bubble root
           
 
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()
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

root

public BubbleTree.Bubble root
Constructor Detail

BubbleTree

public BubbleTree()
Zero-argument constructor creates a new empty BubbleTree.
Method Detail

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