jdsl.core.ref
Class RBTree

java.lang.Object
  |
  +--jdsl.core.ref.RBTree

public class RBTree
extends java.lang.Object
implements OrderedDictionary, ComparatorBased, RBColorConstants

A Red Black tree. Implemented using a RestructurableNodeBinaryTree.

Author:
Ming En Cho, Ryan Shaun Baker, Michael Boilen

Constructor Summary
RBTree(Comparator comparator)
          The class's constructor.
 
Method Summary
 Locator after(Locator locator)
          Finds the locator after the passed in Locator.
 Locator before(Locator locator)
          Finds the locator before the passed in Locator
 Locator closestAfter(java.lang.Object key)
          Finds the Locator that comes right after a Locator with the given key
 Locator closestBefore(java.lang.Object key)
          Finds the Locator that comes right before a Locator with the given key in the tree.
 Comparator comparator()
          Retrieves the Comparator.
 java.util.Enumeration elements()
          Produces an Enumeration of the elements of all the Locators in the tree
 Locator find(java.lang.Object key)
          Finds the Locator with the given key
 java.util.Enumeration findAll(java.lang.Object key)
          Finds all of the locators in the tree with the given key
 Position findInSubtree(java.lang.Object key, Position subtreeRoot)
          a helper method that will return the position is key is found or the position where the key would be (i.e.
 InspectableBinaryTree getTree()
          Returns the underlying tree.
 void insert(Locator locator)
          Inserts a locator into the tree.
 Locator insert(java.lang.Object key, java.lang.Object element)
          Inserts a new key element pair into the tree.
 boolean isEmpty()
           
 java.util.Enumeration keys()
          Returns an Enumeration of all the keys within this Container.
 java.util.Enumeration locators()
          Returns an enumeration of colors
 Locator makeLocator(java.lang.Object key, java.lang.Object element)
          Produces a Locator that is ready to be inserted.
 Container newContainer()
           
 void remove(Locator locator)
           
 java.lang.Object replaceElement(Locator loc, java.lang.Object newElement)
          Replaces the element of the passed in locator
 java.lang.Object replaceKey(Locator locator, java.lang.Object key)
          Replaces the key of the passed in locator
 Comparator setComparator(Comparator c)
          Sets the Comparator to be used in this container.
 int size()
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

RBTree

public RBTree(Comparator comparator)
The class's constructor. * Also, sets the binary tree's root to hold a RBTLocator which is black.
Parameters:
comparator - the comparator for this dictionary
Method Detail

comparator

public Comparator comparator()
Retrieves the Comparator.
Specified by:
comparator in interface ComparatorBased
Returns:
the Comparator that is used by this PriorityQueue.

find

public Locator find(java.lang.Object key)
             throws InvalidKeyException
Finds the Locator with the given key
Parameters:
key - The search key.
Returns:
The found Locator(NO_SUCH_KEY if one wasn't found)
Throws:
InvalidKeyException - If the key is not compatible with this container.

findAll

public java.util.Enumeration findAll(java.lang.Object key)
                              throws InvalidKeyException
Finds all of the locators in the tree with the given key
Parameters:
key - The search key.
Returns:
An Enumeration of the found locators
Throws:
InvalidKeyException - If the key is not compatible with this container.

closestBefore

public Locator closestBefore(java.lang.Object key)
                      throws InvalidKeyException
Finds the Locator that comes right before a Locator with the given key in the tree.
Specified by:
closestBefore in interface OrderedDictionary
Parameters:
key - The key to search for
Returns:
The Locator if it exists.
Throws:
InvalidKeyException - If the key is not compatible with this container.

closestAfter

public Locator closestAfter(java.lang.Object key)
                     throws InvalidKeyException
Finds the Locator that comes right after a Locator with the given key
Specified by:
closestAfter in interface OrderedDictionary
Parameters:
key - The key of the Locator to find the closestAfter
Returns:
The Locator if it exists
Throws:
InvalidKeyException - If the key is not compatible with this container.

after

public Locator after(Locator locator)
              throws InvalidLocatorException
Finds the locator after the passed in Locator.
Specified by:
after in interface OrderedDictionary
Parameters:
locator -  
Returns:
The Locator after locator, or BOUNDARY_VIOLATION if it doesn't exist.
Throws:
InvalidLocatorException - if locator is incompatible with this container

before

public Locator before(Locator locator)
               throws InvalidLocatorException
Finds the locator before the passed in Locator
Specified by:
before in interface OrderedDictionary
Parameters:
locator -  
Returns:
The Locator before locator, or BOUNDARY_VIOLATION if it doesn't exist.
Throws:
InvalidLocatorException - if locator is incompatible with this container

findInSubtree

public Position findInSubtree(java.lang.Object key,
                              Position subtreeRoot)
                       throws InvalidKeyException
a helper method that will return the position is key is found or the position where the key would be (i.e. an external)
Parameters:
key - The search key.
subtreeRoot - Where the search will start.
Returns:
The found Position
Throws:
InvalidKeyException - if key is incompatible with this container

insert

public void insert(Locator locator)
            throws InvalidKeyException,
                   InvalidLocatorException,
                   ContainedLocatorException
Inserts a locator into the tree.
Parameters:
locator - The Locator to insert.
Throws:
InvalidKeyException - if the key of the given locator is incompatible with the container.
InvalidLocatorException - if the given locator is invalid
ContainedLocatorException - if the given locator is already contained

insert

public Locator insert(java.lang.Object key,
                      java.lang.Object element)
               throws InvalidKeyException,
                      ContainedLocatorException
Inserts a new key element pair into the tree.
Parameters:
locator - The Locator to insert.
Throws:
InvalidKeyException - if the key of the given locator is incompatible with the container.
InvalidLocatorException - if the given locator is invalid
ContainedLocatorException - if the given locator is already contained

remove

public void remove(Locator locator)
            throws InvalidLocatorException

replaceKey

public java.lang.Object replaceKey(Locator locator,
                                   java.lang.Object key)
                            throws InvalidLocatorException,
                                   InvalidKeyException
Replaces the key of the passed in locator
Parameters:
locator - The Locator whose key will be replaced.
key - The new key
Returns:
The old key
Throws:
InvalidLocatorException - if the locator's key is not valid or the container is empty.
InvalidKeyException - if the key is not comparable

replaceElement

public java.lang.Object replaceElement(Locator loc,
                                       java.lang.Object newElement)
                                throws InvalidLocatorException
Replaces the element of the passed in locator
Parameters:
locator - The Locator whose element will be replaced.
newElement - The new element
Returns:
The old element
Throws:
InvalidLocatorException - if the locator's key is not valid or the container is empty.

locators

public java.util.Enumeration locators()
Returns an enumeration of colors
Returns:
an Enumeration

keys

public java.util.Enumeration keys()
Returns an Enumeration of all the keys within this Container. If this Container is empty then an empty Enumeration is returned.
Returns:
An Enumeration of all the keys stored in the container. Note: this Enumeration may be empty.
See Also:
elements, Enumeration

makeLocator

public Locator makeLocator(java.lang.Object key,
                           java.lang.Object element)
Produces a Locator that is ready to be inserted.
Parameters:
key - The new Locator's key.
element - The new Locator's element.
Returns:
The newly created Locator

elements

public java.util.Enumeration elements()
Produces an Enumeration of the elements of all the Locators in the tree
Returns:
An Enumeration

newContainer

public Container newContainer()

size

public int size()

isEmpty

public boolean isEmpty()

getTree

public InspectableBinaryTree getTree()
Returns the underlying tree.

setComparator

public Comparator setComparator(Comparator c)
Sets the Comparator to be used in this container.
Specified by:
setComparator in interface ComparatorBased
Parameters:
c - The comparator to use.
Returns:
The old Comparator