redblacktree.java

Java数据结构开发包

/*
  Copyright (c) 1999, 2000 Brown University, Providence, RI
  
                            All Rights Reserved
  
  Permission to use, copy, modify, and distribute this software and its
  documentation for any purpose other than its incorporation into a
  commercial product is hereby granted without fee, provided that the
  above copyright notice appear in all copies and that both that
  copyright notice and this permission notice appear in supporting
  documentation, and that the name of Brown University not be used in
  advertising or publicity pertaining to distribution of the software
  without specific, written prior permission.
  
  BROWN UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR ANY PARTICULAR PURPOSE.  IN NO EVENT SHALL BROWN
  UNIVERSITY BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  PERFORMANCE OF THIS SOFTWARE.
*/

package jdsl.core.ref;

import jdsl.core.api.*;



/**
 * A Dictionary implemented as a red-black tree.  (A red-black tree is
 * a balanced search tree that maintains its balance through coloring
 * its nodes. See "Data Structures and Algorithms in Java", Goodrich,
 * Tamassia, 2nd Ed., Ch.9.)  The red-black tree, in turn, is
 * implemented on top of a subclass of BinaryTree that has the ability
 * to rotate (restructure).
 *
 * This RB tree begins empty, and its internal structure can be accessed
 * with the inspectableBinaryTree method. Once the comparator is set,
 * it can never be changed.
 *
 * Leaf nodes contain locators with a null key; this separates them
 * from data nodes, which are internal and have locators with
 * legitimate, user's keys.
 * A position's color is represented in the locator it holds rather
 * than through a decoration, for faster access.
 *
 * The iterator-returning methods are not cached.
 *
 * This OrderedDictionary is a multi-map, meaning that it is possible
 * for two elements to have the same key.
 *
 * Currently has RestructurableNodeBinaryTree as a nested class while
 * waiting for a test for RNBT.
 *
 * @author Ming En Cho
 * @author Michael Boilen
 * @author Mark Handy
 * @author Ryan Shaun Baker
 * @author Luca Vismara
 * @version JDSL 2.1.1 
 *
 */
public class RedBlackTree implements OrderedDictionary {

  public static final int RED = 0;
  public static final int BLACK = 1;
  public static final int DOUBLEBLACK = 2;

  /**
   * Underlying tree
   */
  private RestructurableNodeBinaryTree tree_;

  /**
   * The comparator for the Dictionary
   */
  private Comparator comparator_;

  /**
   * The size (cached for O(1) access)
   */
  private int size_;
    
  /**
   * The one instance of a BlackColorHolder; held by
   * all black external nodes
   */
  private BlackColorHolder bch_ = new BlackColorHolder();

  /**
   * The one instance of a DoubleBlackColorHolder; held by
   * all double- black external nodes
   * (should only be one at a time)
   */
  private DoubleBlackColorHolder dbch_ = new DoubleBlackColorHolder();

  
  /**
   *  Takes O(1) time
   *  This constructor creates the tree with a single 
   *  no-element-stored-here locator. (null key)
   */
  public RedBlackTree (Comparator comparator) {
    tree_ = new RestructurableNodeBinaryTree();
    comparator_ = comparator;
    tree_.replaceElement(tree_.root(), bch_);
  }

  
  // Container/InspectableContainer methods

  /** 
   * Takes O(1) time
   */
  public Container newContainer() {
    return new RedBlackTree(comparator_);
  }

  
  /** 
   * Takes O(1) time
   */
  public int size() { return size_; }

  
  /** 
   * Takes O(1) time
   */
  public boolean isEmpty() { return size_==0; }

  
  /** 
   * Takes O(1) time
   */
  public boolean contains (Accessor a) throws InvalidAccessorException{
    if (a == null)
      throw new InvalidAccessorException
	("No container contains a null accessor");
    if ((!(a instanceof RBTLocator)) || (((RBTLocator)a).container() != this))
      return false;
    return true;
  }

  
  /** 
   * Takes O(1) time
   */
  public Object replaceElement (Accessor loc, Object newElement) throws
  InvalidAccessorException {
    RBTLocator ul = checkLocator (loc);
    Object oldel = ul.element();
    ul.setElement(newElement);
    return oldel;
  }


  // IKBC/KBC methods  

  /** 
   * Takes O(N) time from the need to iterate through the tree during 
   * snapshot -- where N= the number of locators in the tree
   *
   * Could very easily be cached; not sure that would be useful
   *
   * @return LocatorIterator of the container inorder
   */
  public LocatorIterator locators() {
    PositionIterator pi = new InOrderIterator(tree_);

    Locator[] locarray = new Locator[size()];

    int i = 0;
    while (pi.hasNext()){
      pi.nextPosition();
      if (pi.element() instanceof Locator){
	locarray[i++] = (Locator)(pi.element());
      }
    }
    ArrayLocatorIterator akbi = new ArrayLocatorIterator(locarray,i);

    return akbi;
  }

  
  /** 
   * Takes O(N) time from the need to iterate through the tree during 
   * snapshot -- where N= the number of locators in the tree
   *
   * Could very easily be cached; not sure that would be useful
   *
   * @return an iterator over the container elements inorder
   */
  public ObjectIterator elements() {
    LocatorIterator akbi = locators();

    Object elements[] = new Object[size()];
    int elt = 0;
    while (akbi.hasNext())
      elements[elt++] = akbi.nextLocator().element();
    return new ArrayObjectIterator(elements);

  }

  
  /** 
   * Takes O(N) time from the need to iterate through the tree during 
   * snapshot -- where N= the number of locators in the tree
   *
   * Could very easily be cached; not sure that would be useful
   *
   * @return an iterator over the container keys inorder
   */
  public ObjectIterator keys() {
    LocatorIterator akbi = locators();

    Object keys[] = new Object[size()];
    int key = 0;
    while (akbi.hasNext()){
      akbi.nextLocator();
      keys[key++] = akbi.key();
    }
    return new ArrayObjectIterator(keys);

  }

  
  /** 
   * Takes O(logN) time -- where N = the number of locators in the tree
   * and O(logN) = the height of the tree
   *
   * Takes the running time it would take to execute
   * both remove and insert.
   */
  public Object replaceKey(Locator locator, Object key) throws
  InvalidAccessorException, InvalidKeyException {
    if (!comparator_.isComparable(key))
      throw new InvalidKeyException("replacement key is not comparable");
    RBTLocator ul = checkLocator (locator);
    Object oldKey = ul.key();
    remove(locator);
    ul.setKey(key);
    insertLoc (locator);
    return oldKey;
  }

  
  /** 
   * Takes O(logN) time  -- where N = the number of locators in the tree
   * and O(logN) = the height of the tree
   *
   * Takes the time to traverse the tree's height, which is O(logN)
   */
  public Locator find(Object key) throws InvalidKeyException {
    if ( ! comparator_.isComparable(key))
      throw new InvalidKeyException
	("Key requested not comparable with existing keys");
    Position found = findInSubtree(key, tree_.root());
    if (tree_.isExternal(found))
      return NO_SUCH_KEY;
//     return checkLocator(found.element());
    return (RBTLocator)found.element();
  }

  
  /** 
   * Takes O(logN+R) time -- where N = the number of locators in the tree
   * and O(logN) = the height of the tree, and R = the number of 
   * instances of key in the tree
   *
   * O(log N) for one element; in theory, for each element, taking its inorder
   * prev or next may take up to O(log N). In practice, the O(log N) case
   * can only occur twice, and every other case is O(1).
   */
  public LocatorIterator findAll(Object key) throws InvalidKeyException {
    Locator[] toret = new Locator[size()]; // accumulate results
    int actualnum = 0;
	
    if ( ! comparator_.isComparable(key))
      throw new InvalidKeyException
	("Key requested not comparable with existing keys");

    // first try to find a matching key (the one at the root of the subtree
    // containing all the keys), then traverse backward and forward
    // from there until we exit the range of matching keys
    Position p = findInSubtree (key, tree_.root());
    if (tree_.isExternal(p))
      return new ArrayLocatorIterator(toret,actualnum);// key not found
	
    Position first = tree_.leftChild(((RBTLocator)first()).treePosition()); // a leaf node
    Position last = tree_.rightChild(((RBTLocator)last()).treePosition()); // a leaf node
//     RBTLocator h = checkLocator(p.element());
    RBTLocator h = (RBTLocator)p.element();

    Position save = p; //save where we started from

    //first check to the right
    while (comparator_.isEqualTo(h.key(),key)){
      toret[actualnum++] = h;
      // next() alternates between leaves and internals
      p = next(p);
      if (p==last) break;
      p = next(p);
//       h = checkLocator (p.element());
      h = (RBTLocator)p.element();
    }
    // now check to the left
    p = prev(save);
    if (p==first) return new ArrayLocatorIterator(toret,actualnum);
    p = prev(p);
//     h = checkLocator (p.element());
    h = (RBTLocator)p.element();
    while (comparator_.isEqualTo(h.key(),key)){
      toret[actualnum++] = h;
      p = prev(p);
      if (p==first) return new ArrayLocatorIterator(toret,actualnum);
      p = prev(p);
//       h = checkLocator (p.element());
      h = (RBTLocator)p.element();
    }
    return new ArrayLocatorIterator(toret,actualnum);
  }

  
  /**
   * Takes O(logN) time  -- traverses the height of the tree once.
   */
  public Locator closestBefore(Object key) throws InvalidKeyException { 
    if (!comparator_.isComparable(key))
      throw new InvalidKeyException
	("This key is inappropriate for this structure's comparator");
    if(isEmpty()) return BOUNDARY_VIOLATION;
    Position found=findInSubtree(key, tree_.root());
    if (tree_.isInternal(found))
//       return checkLocator(found.element());
      return (RBTLocator)found.element();
//     if (found==(tree_.leftChild(checkLocator(first()).treePosition())))
    if (found == tree_.leftChild(((RBTLocator)first()).treePosition()))
      return BOUNDARY_VIOLATION;
//     return checkLocator(prev(found).element());
    return (RBTLocator)prev(found).element();
  }

  
  /**
   * Takes O(logN) time  -- traverses the height of the tree once.
   */
  public Locator closestAfter(Object key) throws InvalidKeyException {
    if (!comparator_.isComparable(key))
      throw new InvalidKeyException
	("This key is inappropriate for this structure's comparator");
    if(isEmpty()) return BOUNDARY_VIOLATION;
    Position found=findInSubtree(key, tree_.root());
    if (tree_.isInternal(found))
//       return checkLocator(found.element());
      return (RBTLocator)found.element();
//     if (found==(tree_.rightChild(checkLocator(last()).treePosition())))
    if (found == tree_.rightChild(((RBTLocator)last()).treePosition()))
      return BOUNDARY_VIOLATION;
//     return checkLocator(next(found).element());
    return (RBTLocator)next(found).element();
  }

  
  /**
   * Takes O(logN) time -- may need to traverse the height of the tree
   * to find the next note that we do not return color-locators in the
   * leaves -- we only return key locators.
   */
  public Locator after(Locator locator) throws InvalidAccessorException {    
    Position p = checkLocator(locator).treePosition();
    // p is an internal (if there are no bugs...)
    p = next(p); // now points to a leaf
    try {
//       return checkLocator(next(p).element());
      return (RBTLocator)next(p).element();
    }
    catch (BoundaryViolationException bve) {