/*
  File: RBTree.java

  Originally written by Doug Lea and released into the public domain. 
  Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  Inc, Loral, and everyone contributing, testing, and using this code.

  History:
  Date     Who                What
  24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  13Oct95  dl                 Changed protection statuses

*/
  
package cnslab.cnsmath;
import cnslab.cnsnetwork.*;
import java.util.Map;
import java.io.PrintStream;

/**
 *
 * RedBlack trees.
 * @author Doug Lea
 * @version 0.93
 *
 * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
**/
public class RBTree<T extends Comparable >
{

        // instance variables

        /**
         * The root of the tree. Null if empty.
         *
         **/
        /**
         * Returns the root of the tree.
         *
         * @return      The root of the tree.
         */

        public RBCell<T> root()
        {
                return this.root;
        }

        private RBCell<T> root;

  protected int count_;

  /** 
   *make iterate exit 
   */
  public boolean iterExit;

  /** 
   * save time for noTillInputEvent iteration 
   */
  public FireEvent firstFire;

  /** 
   * save time for noTillFireEvent iteration 
   */
  public InputEvent firstInput;

  public Map flags; 


  protected final void incCount() { count_++; }
  protected final void decCount() { count_--; }

  // constructors
  /**
   * Constructs a new empty tree.
   */
  public RBTree()
  {
          root = null;
  }

  /**
   * Constructs a new tree with a root node x.
   *
   * @param x           The root node of the tree.
   */
  public RBTree(RBCell<T> x)
  {
          root = x;
  }


/**
 * set the element count and update version_ if changed
**/
  protected final void setCount(int c) { 
    if (c != count_) { count_ = c; }
  }



// Collection methods  
        
/**
 * Implements collections.Collection.includes.
 * Time complexity: O(log n).
 * @see collections.Collection#includes
**/
  public synchronized boolean includes(T element) {
    if (element == null || count_ == 0) return false;
    return root.find(element) != null;
  }

/**
 * Implements collections.Collection.occurrencesOf.
 * Time complexity: O(log n).
 * @see collections.Collection#occurrencesOf
**/
  public synchronized int occurrencesOf(T element) {
    if (element == null || count_ == 0) return 0;
    return root.count(element);
  }


// UpdatableCollection methods

/**
 * Implements collections.UpdatableCollection.clear.
 * Time complexity: O(1).
 * @see collections.UpdatableCollection#clear
**/
  public synchronized void clear() { 
    setCount(0);
    root = null;
  }

/**
 * Implements collections.UpdatableCollection.exclude.
 * Time complexity: O(log n * occurrencesOf(element)).
 * @see collections.UpdatableCollection#exclude
**/
  public synchronized void exclude(T element) {
    remove_(element, true);
  }


/**
 * Implements collections.UpdatableCollection.removeOneOf.
 * Time complexity: O(log n).
 * @see collections.UpdatableCollection#removeOneOf
**/
  public synchronized void removeOneOf(T element) {
    remove_(element, false);
  }

/**
 * Implements collections.UpdatableCollection.replaceOneOf
 * Time complexity: O(log n).
 * @see collections.UpdatableCollection#replaceOneOf
**/
  public synchronized void replaceOneOf(T oldElement, T newElement) { 
    replace_(oldElement, newElement, false);
  }

/**
 * Implements collections.UpdatableCollection.replaceAllOf.
 * Time complexity: O(log n * occurrencesOf(oldElement)).
 * @see collections.UpdatableCollection#replaceAllOf
**/
  public synchronized void replaceAllOf(T oldElement, T newElement)  {
    replace_(oldElement, newElement, true);
  }

/**
 * Implements collections.UpdatableCollection.take.
 * Time complexity: O(log n).
 * Takes the least element.
 * @see collections.UpdatableCollection#take
**/
  public synchronized T take() {
    if (count_ != 0) {
      RBCell<T> p = root.leftmost();
      T v = p.element();
      root = p.delete(root);
      decCount();
      return v;
    }
    return null; // not reached
  }


// UpdatableBag methods

/**
 * Implements collections.UpdatableBag.addIfAbsent
 * Time complexity: O(log n).
 * @see collections.UpdatableBag#addIfAbsent
**/
  public synchronized void addIfAbsent(T element)  {
    add_(element, true);
  }


/**
 * Implements collections.UpdatableBag.add.
 * Time complexity: O(log n).
 * @see collections.UpdatableBag#add
**/
  public synchronized void add(T element)  {
    add_(element, false);
  }


// helper methods

  private void add_(T element, boolean checkOccurrence)  {
    if (root == null) {
      root = new RBCell<T>(element);
      incCount();
    }
    else {
      RBCell<T> t = root;
      for (;;) {
        int diff = element.compareTo(t.element());
        if (diff == 0 && checkOccurrence) return;
        else if (diff <= 0) {
          if (t.left() != null) 
            t = t.left();
          else {
            root = t.insertLeft(new RBCell<T>(element), root);
            incCount();
            return;
          }
        }
        else {
          if (t.right() != null) 
            t = t.right();
          else {
            root = t.insertRight(new RBCell<T>(element), root);
            incCount();
            return;
          }
        }
      }
    }
  }


  private void remove_(T element, boolean allOccurrences) {
    if (element == null) return;
    while (count_ > 0) {
      RBCell<T> p = root.find(element);
      if (p != null) {
        root = p.delete(root);
        decCount();
        if (!allOccurrences) return;
      }
      else 
      { 
//      throw new RuntimeException(" delete null");
        break;
      }
    }
  }

  private void replace_(T oldElement, T newElement, boolean allOccurrences) {
    if (oldElement == null || count_ == 0 || oldElement.equals(newElement)) 
      return;
    while (includes(oldElement)) {
      removeOneOf(oldElement);
      add(newElement);
      if (!allOccurrences) return;
    }
  }

// ImplementationCheckable methods
//

        public boolean treeNoTillFireEvent(RBCell<T> x)
        {
                return true;
        }

        public boolean treeNoTillFireEvent2(RBCell<T> x)
        {
                return true;
        }

        public boolean treeNoTillInputEvent(RBCell<T> x)
        {
                return true;
        }

         /**
         * Prints the keys of current tree in inorder (ascending).
         * Runs in Theta(n) time.
         *
         * @param       x       The node from which to start.
         */
        public void inorderTreeWalk(RBCell<T> x, PrintStream p)
        {
                if (!(x==null))
                {
                        inorderTreeWalk(x.left(), p);
                        //System.out.println(x.key());
                        p.println(x.element_);
                        inorderTreeWalk(x.right(), p);
                }

        }

        public void inorderTreeWalk(RBCell<T> x, StringWrap p)
        {
                if (!(x==null))
                {
                        inorderTreeWalk(x.left(),p);
                        //System.out.println(x.key());
                        p.out=p.out+x.element_+" | ";
                        inorderTreeWalk(x.right(),p);
                }
        }

}