All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class jdsl.core.ref.RBTree

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

public class RBTree
extends Object
implements OrderedDictionary, ComparatorBased, RBColorConstants
A Red Black tree. Implemented using a RestructurableNodeBinaryTree.


Constructor Index

 o RBTree(Comparator)
The class's constructor.

Method Index

 o after(Locator)
Finds the locator after the passed in Locator.
 o before(Locator)
Finds the locator before the passed in Locator
 o case1(Position)
take care of case 1 after deletion: sib is red
 o case2(Position)
 o case3(Position)
 o case4(Position)
 o closestAfter(Object)
Finds the Locator that comes right after a Locator with the given key
 o closestBefore(Object)
Finds the Locator that comes right before a Locator with the given key in the tree.
 o colorPromotion(Position)
handy color promotion method.....promotes the red up
 o comparator()
Retrieves the Comparator.
 o elements()
Produces an Enumeration of the elements of all the Locators in the tree
 o find(Object)
Finds the Locator with the given key
 o findAll(Object)
Finds all of the locators in the tree with the given key
 o findInSubtree(Object, Position)
a helper method that will return the position is key is found or the position where the key would be (i.e.
 o getCInfo()
 o getTree()
Returns the underlying tree.
 o insert(Locator)
Inserts a locator into the tree.
 o insert(Object, Object)
Inserts a new key element pair into the tree.
 o isEmpty()
 o keys()
Returns an Enumeration of all the keys within this Container.
 o locators()
Returns an enumeration of colors
 o makeLocator(Object, Object)
Produces a Locator that is ready to be inserted.
 o newContainer()
 o recolor(Position)
 o recolorAfterRemove(Position)
 o remove(Locator)
 o replaceElement(Locator, Object)
Replaces the element of the passed in locator
 o replaceKey(Locator, Object)
Replaces the key of the passed in locator
 o rotation(Position)
silly method that just calls restructure on the restructurable BT
 o setComparator(Comparator)
Sets the Comparator to be used in this container.
 o size()

Constructors

 o 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

Methods

 o comparator
 public Comparator comparator()
Retrieves the Comparator.

Returns:
the Comparator that is used by this PriorityQueue.
 o find
 public Locator find(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.
 o findAll
 public Enumeration findAll(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.
 o closestBefore
 public Locator closestBefore(Object key) throws InvalidKeyException
Finds the Locator that comes right before a Locator with the given key in the tree.

Parameters:
key - The key to search for
Returns:
The Locator if it exists.
Throws: InvalidKeyException
If the key is not compatible with this container.
 o closestAfter
 public Locator closestAfter(Object key) throws InvalidKeyException
Finds the Locator that comes right after a Locator with the given key

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.
 o after
 public Locator after(Locator locator) throws InvalidLocatorException
Finds the locator after the passed in Locator.

Returns:
The Locator after locator, or BOUNDARY_VIOLATION if it doesn't exist.
Throws: InvalidLocatorException
if locator is incompatible with this container
 o before
 public Locator before(Locator locator) throws InvalidLocatorException
Finds the locator before the passed in Locator

Returns:
The Locator before locator, or BOUNDARY_VIOLATION if it doesn't exist.
Throws: InvalidLocatorException
if locator is incompatible with this container
 o findInSubtree
 public Position findInSubtree(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
 o 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.
Throws: InvalidLocatorException
if the given locator is invalid
Throws: ContainedLocatorException
if the given locator is already contained
 o insert
 public Locator insert(Object key,
                       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.
Throws: InvalidLocatorException
if the given locator is invalid
Throws: ContainedLocatorException
if the given locator is already contained
 o remove
 public void remove(Locator locator) throws InvalidLocatorException
 o recolorAfterRemove
 protected void recolorAfterRemove(Position child)
 o case1
 protected void case1(Position sibling)
take care of case 1 after deletion: sib is red

 o case2
 protected void case2(Position child)
 o case3
 protected Position case3(Position sibling)
 o case4
 protected void case4(Position position)
 o replaceKey
 public Object replaceKey(Locator locator,
                          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.
Throws: InvalidKeyException
if the key is not comparable
 o replaceElement
 public Object replaceElement(Locator loc,
                              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.
 o colorPromotion
 protected void colorPromotion(Position parent)
handy color promotion method.....promotes the red up

Parameters:
parent - The position to promote
 o rotation
 protected Position rotation(Position grandchild)
silly method that just calls restructure on the restructurable BT

Parameters:
grandchild - The position to rotate
 o recolor
 protected void recolor(Position root)
 o locators
 public Enumeration locators()
Returns an enumeration of colors

Returns:
an Enumeration
 o keys
 public 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
 o makeLocator
 public Locator makeLocator(Object key,
                            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
 o elements
 public Enumeration elements()
Produces an Enumeration of the elements of all the Locators in the tree

Returns:
An Enumeration
 o newContainer
 public Container newContainer()
 o size
 public int size()
 o isEmpty
 public boolean isEmpty()
 o getTree
 public InspectableBinaryTree getTree()
Returns the underlying tree.

 o getCInfo
 protected RBColorInfo getCInfo()
 o setComparator
 public Comparator setComparator(Comparator c)
Sets the Comparator to be used in this container.

Parameters:
c - The comparator to use.
Returns:
The old Comparator

All Packages  Class Hierarchy  This Package  Previous  Next  Index