    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

RedBlack trees.

##

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.

##

tree_

     protected RBCell tree_

  The root of the tree. Null if empty.

cmp_

     protected Comparator cmp_

  The comparator to use for ordering.

##

RBTree

     public RBTree()

  Make an empty tree. Initialize to use DefaultComparator for ordering

RBTree

     public RBTree(Predicate s)

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

RBTree

     public RBTree(Comparator c)

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

RBTree

     public RBTree(Predicate s,
                   Comparator c)

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

RBTree

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

  Special version of constructor needed by clone()

##

clone

     protected Object clone() throws CloneNotSupportedException

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

  Overrides:
    clone in class Object

includes

     public synchronized boolean includes(Object element)

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

  Overrides:
    includes in class UpdatableImpl
  See Also:
    includes

occurrencesOf

     public synchronized int occurrencesOf(Object element)

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

  Overrides:
    occurrencesOf in class UpdatableImpl
  See Also:
    occurrencesOf

elements

     public synchronized CollectionEnumeration elements()

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

  Overrides:
    elements in class UpdatableImpl
  See Also:
    elements

elementComparator

     public synchronized Comparator elementComparator()

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

  See Also:
    elementComparator

elementComparator

     public synchronized void elementComparator(Comparator cmp)

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

clear

     public synchronized void clear()

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

  Overrides:
    clear in class UpdatableImpl
  See Also:
    clear

exclude

     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

removeOneOf

     public synchronized void removeOneOf(Object element)

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

  Overrides:
    removeOneOf in class UpdatableImpl
  See Also:
    removeOneOf

replaceOneOf

     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

replaceAllOf

     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

take

     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

addIfAbsent

     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

add

     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

checkImplementation

     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