All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class collections.RBTree

java.lang.Object
   |
   +----collections.UpdatableImpl
           |
           +----collections.UpdatableBagImpl
                   |
                   +----collections.RBTree

public class RBTree

extends UpdatableBagImpl

implements UpdatableBag, ElementSortedCollection

cmp_

The comparator to use for ordering.

tree_

The root of the tree.

RBTree()

Make an empty tree.

RBTree(Comparator)

Make an empty tree, using the supplied element comparator for ordering.

RBTree(Predicate)

Make an empty tree, using the supplied element screener.

RBTree(Predicate, Comparator)

Make an empty tree, using the supplied element screener and comparator

RBTree(Predicate, Comparator, RBCell, int)

Special version of constructor needed by clone()

add(Object)

Implements collections.UpdatableBag.add.

addIfAbsent(Object)

Implements collections.UpdatableBag.addIfAbsent Time complexity: O(log n).

checkImplementation()

Implements collections.ImplementationCheckable.checkImplementation.

clear()

Implements collections.UpdatableCollection.clear.

clone()

Make an indepenent copy of the tree.

elementComparator()

Implements collections.ElementSortedCollection.elementComparator Time complexity: O(1).

elementComparator(Comparator)

Reset the comparator.

elements()

Implements collections.Collection.elements.

exclude(Object)

Implements collections.UpdatableCollection.exclude.

includes(Object)

Implements collections.Collection.includes.

occurrencesOf(Object)

Implements collections.Collection.occurrencesOf.

removeOneOf(Object)

Implements collections.UpdatableCollection.removeOneOf.

replaceAllOf(Object, Object)

Implements collections.UpdatableCollection.replaceAllOf.

replaceOneOf(Object, Object)

Implements collections.UpdatableCollection.replaceOneOf Time complexity: O(log n).

take()

Implements collections.UpdatableCollection.take.

 protected RBCell tree_

The root of the tree. Null if empty.

 protected Comparator cmp_

The comparator to use for ordering.

 public RBTree()

Make an empty tree. Initialize to use DefaultComparator for ordering

 public RBTree(Predicate s)

Make an empty tree, using the supplied element screener. Initialize to use DefaultComparator for ordering

 public RBTree(Comparator c)

Make an empty tree, using the supplied element comparator for ordering.

 public RBTree(Predicate s,
               Comparator c)

Make an empty tree, using the supplied element screener and comparator

 protected RBTree(Predicate s,
                  Comparator cmp,
                  RBCell t,
                  int n)

Special version of constructor needed by clone()

 protected Object clone() throws CloneNotSupportedException

Make an indepenent copy of the tree. Does not clone elements.

Overrides:

clone in class Object

 public synchronized boolean includes(Object element)

Implements collections.Collection.includes. Time complexity: O(log n).

Overrides:

includes in class UpdatableImpl

See Also:

includes

 public synchronized int occurrencesOf(Object element)

Implements collections.Collection.occurrencesOf. Time complexity: O(log n).

Overrides:

occurrencesOf in class UpdatableImpl

See Also:

occurrencesOf

 public synchronized CollectionEnumeration elements()

Implements collections.Collection.elements. Time complexity: O(1).

Overrides:

elements in class UpdatableImpl

See Also:

elements

 public synchronized Comparator elementComparator()

Implements collections.ElementSortedCollection.elementComparator Time complexity: O(1).

See Also:

elementComparator

 public synchronized void elementComparator(Comparator cmp)

Reset the comparator. Will cause a reorganization of the tree. Time complexity: O(n log n).

 public synchronized void clear()

Implements collections.UpdatableCollection.clear. Time complexity: O(1).

Overrides:

clear in class UpdatableImpl

See Also:

clear

 public synchronized void exclude(Object element)

Implements collections.UpdatableCollection.exclude. Time complexity: O(log n * occurrencesOf(element)).

Overrides:

exclude in class UpdatableImpl

See Also:

exclude

 public synchronized void removeOneOf(Object element)

Implements collections.UpdatableCollection.removeOneOf. Time complexity: O(log n).

Overrides:

removeOneOf in class UpdatableImpl

See Also:

removeOneOf

 public synchronized void replaceOneOf(Object oldElement,
                                       Object newElement) throws IllegalElementException

Implements collections.UpdatableCollection.replaceOneOf Time complexity: O(log n).

Overrides:

replaceOneOf in class UpdatableImpl

See Also:

replaceOneOf

 public synchronized void replaceAllOf(Object oldElement,
                                       Object newElement) throws IllegalElementException

Implements collections.UpdatableCollection.replaceAllOf. Time complexity: O(log n * occurrencesOf(oldElement)).

Overrides:

replaceAllOf in class UpdatableImpl

See Also:

replaceAllOf

 public synchronized Object take() throws NoSuchElementException

Implements collections.UpdatableCollection.take. Time complexity: O(log n). Takes the least element.

Overrides:

take in class UpdatableImpl

See Also:

take

 public synchronized void addIfAbsent(Object element) throws IllegalElementException

Implements collections.UpdatableBag.addIfAbsent Time complexity: O(log n).

Overrides:

addIfAbsent in class UpdatableBagImpl

See Also:

addIfAbsent

 public synchronized void add(Object element) throws IllegalElementException

Implements collections.UpdatableBag.add. Time complexity: O(log n).

Overrides:

add in class UpdatableBagImpl

See Also:

add

 public void checkImplementation() throws ImplementationError

Implements collections.ImplementationCheckable.checkImplementation.

Overrides:

checkImplementation in class UpdatableImpl

See Also:

checkImplementation

All Packages  Class Hierarchy  This Package  Previous  Next  Index