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

Author:

Ming En Cho, Ryan Shaun Baker, Michael Boilen

RBTree(Comparator)

The class's constructor.

after(Locator)

Finds the locator after the passed in Locator.

before(Locator)

Finds the locator before the passed in Locator

case1(Position)

take care of case 1 after deletion: sib is red

case2(Position)

case3(Position)

case4(Position)

closestAfter(Object)

Finds the Locator that comes right after a Locator with the given key

closestBefore(Object)

Finds the Locator that comes right before a Locator with the given key in the tree.

colorPromotion(Position)

handy color promotion method.....promotes the red up

comparator()

Retrieves the Comparator.

elements()

Produces an Enumeration of the elements of all the Locators in the tree

find(Object)

Finds the Locator with the given key

findAll(Object)

Finds all of the locators in the tree with the given key

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.

getCInfo()

getTree()

Returns the underlying tree.

insert(Locator)

Inserts a locator into the tree.

insert(Object, Object)

Inserts a new key element pair into the tree.

isEmpty()

keys()

Returns an Enumeration of all the keys within this Container.

locators()

Returns an enumeration of colors

makeLocator(Object, Object)

Produces a Locator that is ready to be inserted.

newContainer()

recolor(Position)

recolorAfterRemove(Position)

remove(Locator)

replaceElement(Locator, Object)

Replaces the element of the passed in locator

replaceKey(Locator, Object)

Replaces the key of the passed in locator

rotation(Position)

silly method that just calls restructure on the restructurable BT

setComparator(Comparator)

Sets the Comparator to be used in this container.

size()

 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

 public Comparator comparator()

Retrieves the Comparator.

Returns:

the Comparator that is used by this PriorityQueue.

 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.

 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.

 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.

 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.

 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

 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

 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

 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

 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

 public void remove(Locator locator) throws InvalidLocatorException

 protected void recolorAfterRemove(Position child)

 protected void case1(Position sibling)

take care of case 1 after deletion: sib is red

 protected void case2(Position child)

 protected Position case3(Position sibling)

 protected void case4(Position position)

 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

 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.

 protected void colorPromotion(Position parent)

handy color promotion method.....promotes the red up

Parameters:

parent - The position to promote

 protected Position rotation(Position grandchild)

silly method that just calls restructure on the restructurable BT

Parameters:

grandchild - The position to rotate

 protected void recolor(Position root)

 public Enumeration locators()

Returns an enumeration of colors

Returns:

an Enumeration

 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

 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

 public Enumeration elements()

Produces an Enumeration of the elements of all the Locators in the tree

Returns:

An Enumeration

 public Container newContainer()

 public int size()

 public boolean isEmpty()

 public InspectableBinaryTree getTree()

Returns the underlying tree.

 protected RBColorInfo getCInfo()

 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