brutil
Class RBSet

java.lang.Object
  |
  +--brutil.RBSet

All Implemented Interfaces:

Collection, Set, SortedSet

public class RBSet

extends java.lang.Object

implements SortedSet

An implementation of the Set interface based on RBTree. Add, contains, remove take logarithmic time.

Inner Class Summary

protected class	RBSet.RBIterator
class	RBSet.RBNode

Field Summary

int	colorCount
int	rotateCount

Constructor Summary

RBSet()
Creates an empty tree

Method Summary

java.lang.Object	add(java.lang.Object elt) Add the specified object to the Set.
void	clear() Clears all the items out of this tree
boolean	contains(java.lang.Object elt) Tells if the specified object is contained within this set.
java.lang.Object	find(java.lang.Object elt) Returns the object that is mapped to the given key.
protected void	initMemory() Associates the given key with the given value.
boolean	isEmpty() Returns true if the Tree is empty, false otherwise
java.util.Iterator	iterator() Returns an Iterator for this tree.
java.lang.Object	maxElement() Returns the maximum key in the tree.
java.lang.Object	minElement() Returns the minimum key in the tree.
java.lang.Object	nextElement(java.lang.Object elt) Returns the lowest key that is greater that the specified key.
java.lang.Object	prevElement(java.lang.Object elt) Returns the greatest key that is less that the specified key.
java.lang.Object	remove(java.lang.Object key) Removes the mapping associated with the specified key from the tree.
int	size() Returns the number of mappings in the tree.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

rotateCount

public int rotateCount

colorCount

public int colorCount

Constructor Detail

RBSet

public RBSet()

Creates an empty tree

Method Detail

find

public java.lang.Object find(java.lang.Object elt)

Returns the object that is mapped to the given key. Use the #containsKey(Object) method to determine if null return values indicate no mapping for this key or a mapping to null.

Specified by:

find in interface Set

Parameters:

key - The Comparable Object for associated return value

Returns:

the value which is associated with the given key, and null if no mapping to this key exists.

Throws:

ClassCastException - key does not implement Comparable

contains

public boolean contains(java.lang.Object elt)

Tells if the specified object is contained within this set.

Specified by:

contains in interface Set

Parameters:

o - The object to search for in the Set.

Returns:

true if the object is contained in the set, false otherwise.

initMemory

protected void initMemory()

Associates the given key with the given value. If there is already a mapping to the given key, it will be replaced, and the old value will be returned.

Parameters:

key - The Comparable Object to associate this value with.

value - The Object to associate with this key.

Returns:

The Object that was previously associated with the specified key, and null if there was no previous mapping.

Throws:

ClassCastException - key does not implement Comparable

add

public java.lang.Object add(java.lang.Object elt)

Description copied from interface: Set

Add the specified object to the Set. Unless the implementing class is also a MultiSet, there may only be one instance of the object in the set.

Specified by:

add in interface Set

Following copied from interface: brutil.Set

Parameters:

o - The object to add to the Set.

Returns:

Object pointer that was replaced by this add, null otherwise.

remove

public java.lang.Object remove(java.lang.Object key)

Removes the mapping associated with the specified key from the tree.

Specified by:

remove in interface Set

Parameters:

key - The Comparable Object which will be removed from the tree.

Returns:

The value which was removed.

Throws:

ClassCastException - key does not implement Comparable

size

public int size()

Returns the number of mappings in the tree.

Specified by:

size in interface Collection

Returns:

the number of nodes in the tree

isEmpty

public boolean isEmpty()

Returns true if the Tree is empty, false otherwise

Specified by:

isEmpty in interface Set

Following copied from interface: brutil.Set

Returns:

true if the Set is empty, false otherwise.

clear

public void clear()

Clears all the items out of this tree

Specified by:

clear in interface Collection

minElement

public java.lang.Object minElement()

Returns the minimum key in the tree.

Specified by:

minElement in interface SortedSet

Returns:

the minimum key

maxElement

public java.lang.Object maxElement()

Returns the maximum key in the tree.

Specified by:

maxElement in interface SortedSet

Returns:

the maximum key

prevElement

public java.lang.Object prevElement(java.lang.Object elt)

Returns the greatest key that is less that the specified key.

Specified by:

prevElement in interface SortedSet

Parameters:

key - Comparable object for which to find the previous key.

Returns:

the greatest key that is less that the specified key.

Throws:

ClassCastException - key is not Comparable

nextElement

public java.lang.Object nextElement(java.lang.Object elt)

Returns the lowest key that is greater that the specified key.

Specified by:

nextElement in interface SortedSet

Parameters:

key - Comparable object for which to find the next key.

Returns:

the lowest key that is greater that the specified key.

Throws:

ClassCastException - key is not Comparable

iterator

public java.util.Iterator iterator()

Returns an Iterator for this tree. Creating the Iterator and next() take logarithmic time; remove() and hasNext() take constant time. Right now, we do nothing about modifications to the tree that are not done through the iterators.

Specified by:

iterator in interface Set

Returns:

an iterator over this tree

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object