/*
 *  This code is from the book:
 *
 *    Winder, R and Roberts, G (2000) Developing Java
 *    Software, second edition, John Wiley & Sons.
 *
 *  It is copyright (c) 2000 Russel Winder and Graham Roberts.
 */

package ADS ;
/**
 *  The simplest instantiatable <CODE>BinaryTree</CODE>.  This class
 *  inherit from <CODE>AbstractBinaryTree</CODE> adding the
 *  <CODE>add</CODE>, <CODE>remove</CODE> and <CODE>clone</CODE>
 *  methods.  The insertion policy is to use an order relation
 *  provided by the <CODE>Comparator</CODE> method objects.
 *
 *  @version 1.5 2001.04.23
 *  @author Russel Winder
 */
public class OrderedBinaryTree extends AbstractBinaryTree {
  /**
   *  The order relation that provides the insertion and deletion
   *  policy for this binary tree.  We have to have an order relation
   *  in order to be able to insert and search for items in the tree!
   */
  protected final Comparator order ;
  /**
   *  The Comparator that defines the equality relation between data
   *  items.
   *
   *  <P> We use this technique (using a <CODE>Comparator</CODE>)
   *  rather than using <CODE>equals</CODE> directly so that clients
   *  of this class can define equality however they want.</P>
   */
  protected final Comparator equal ;
  /**
   *  The <CODE>boolean</CODE> that determines whether the tree
   *  accepts duplicate entries (the default) or whether duplicates
   *  are forbidden.
   */
  protected final boolean duplicatesAllowed ;
  /**
   *  Construct an <CODE>OrderedBinaryTree</CODE>.  We insist on being
   *  given a valid <CODE>Comparator</CODE> to implement the insertion
   *  policy.  Duplicate entries are allowed.
   */
  public OrderedBinaryTree(final Comparator o) {
    this(o, new EqualToComparator (), true) ;
  }
  /**
   *  Construct an <CODE>OrderedBinaryTree</CODE>.  We insist on being
   *  given a valid <CODE>Comparator</CODE> to implement the insertion
   *  policy.  Specify whether duplicates are allowed.
   */
  public OrderedBinaryTree(final Comparator o, final boolean dups) {
    this(o, new EqualToComparator (), dups) ;
  }
  /**
   *  Construct an <CODE>OrderedBinaryTree</CODE>.  We insist on being
   *  given a valid <CODE>Comparator</CODE> to implement the insertion
   *  policy.  Duplicate entries are allowed.  Specify an equality
   *  relation.
   */
  public OrderedBinaryTree(final Comparator o, final Comparator e) {
    this(o, e, true) ;
  }
  /**
   *  Construct an <CODE>OrderedBinaryTree</CODE>.  We insist on being
   *  given a valid <CODE>Comparator</CODE> to implement the insertion
   *  policy.  Specify whether duplicates are allowed.  Specify an
   *  equality relation.
   */
  public OrderedBinaryTree(final Comparator o,
                           final Comparator e,
                           final boolean dups) {
    order = o ;
    equal = e ;
    duplicatesAllowed = dups ;
  }
  /**
   *  Insert a value into the <CODE>OrderedBinaryTree</CODE>.
   */
  public void add(final Object o) {
    SearchIterator si = (SearchIterator)searchFor(o) ;
    if (si.atEnd()) {
      si.set(o) ;
    } else {
      if (duplicatesAllowed) {
        si.add(o) ;
      }
    }
  }
  /**
   *  Remove an item from the <CODE>OrderedBinaryTree</CODE>.
   */
  public boolean remove(final Object o) {
    SearchIterator si = (SearchIterator)searchFor(o) ;
    if (!si.atEnd()) {
      si.remove() ;
      return true ;
    }
    return false ;
  }
  /**
   *  Search the tree looking for a given element.
   */
  public final boolean contains(final Object o) {
    return ! ((SearchIterator)searchFor(o)).atEnd() ;
  }
  /**
   *  Cloning is actually easy since everything has been prepared for
   *  in <CODE>BinaryTree</CODE>, in particular the <CODE>Node</CODE>s
   *  know how to recursively clone themselves.  NB
   *  <CODE>CloneNotSupportedException</CODE> is caught in
   *  <CODE>AbstractContainer</CODE> so we don't need to worry about
   *  it here.
   */
  public Object clone() {
    OrderedBinaryTree t = (OrderedBinaryTree)super.clone() ;
    //  Have to clone the dummy node as well as the actual data nodes
    //  otherwise we end up with an element of sharing that ruins the
    //  cloning.
    t.root = new Node (null, null, null, null) ;
    if (! isEmpty()) {
      t.root.left = (Node)root.left.clone(t.root) ;
    }
    return t ;
  }
  /**
   *  A special iterator to handle the searching (usually for adding
   *  or removing an item).  NB This is not a subclass of
   *  <CODE>AbstractIterator</CODE> since that iterator was about
   *  iterating over the values in the data structure whereas this
   *  iterator is about iterating over the <CODE>Node</CODE>s of the
   *  data structure.
   */
  //  This is an inner class because it needs access to the data items
  //  held in the enclosing class.
  protected class SearchIterator implements Iterator {
    /**
     *  The item to be delivered up by the iterator.
     */
    protected Node theItem = root.left ;
    /**
     *  The parent of the item to be delivered up by the iterator.
     */
    protected Node theParent = root ;
    /**
     *  A variable to keep track of whether the child is the left or
     *  right child of the parent.  Cannot avoid use of this variable
     *  since an integral part of the algorithm is ending up with the
     *  child reference being null at which point left and right can
     *  be indistinguishable.
     *
     *  <P> The default stems from the root node of the tree being the
     *  left child of the dummy root hook.</P>
     */
    protected boolean isLeft = true ;
    /**
     *  The value we are given at the outset.
     */
    protected final Object theValue ;
    /**
     *  The constructor.  We must have an item to search for.  This
     *  constructor allows us to use an alternate equality relation.
     *
     *  @return a reference to the node that has the given value or
     *  null if it is not in the tree.
     */
    public SearchIterator(final Object o) {
      theValue = o ;
      search(theValue) ;
    }
    /**
     *  Deliver up the next <CODE>Node</CODE> in the iteration.  NB
     *  This is a different approach to the normal iterators since it
     *  may, correctly, deliver null.
     */
    public Object get() {
      if (theParent == null)
        throw new InvalidIteratorOperationException() ;
      return theItem ;
    }
    /**
     *  Set the datum of the current <CODE>Node</CODE> to be the
     *  proferred object.  If <CODE>theItem</CODE> is null then attach
     *  to the parent as a new <CODE>Node</CODE>.
     */
    //  TODO: This operation could leave the tree in an inconsistent
    //  state since the new item could be out of sorted sequence.
    //  There really ought to be some sort of protection so as to
    //  guarantee the order relation.  Of course the whole
    //  SearchIterator/searchFor mechanism is protected so they should
    //  not get used improperly, nothing wrong with a bit of paranoia
    //  though.
    public void set(final Object o) {
      if (theParent == null)
        throw new InvalidIteratorOperationException() ;    
      if (theItem == null) {
        Node n = new Node (o, null, null, theParent) ;
        if (isLeft) {
          theParent.left = n ;
        } else {
          theParent.right = n ;
        }
      } else {
        theItem.datum = o ;
      }
    }
    /**
     *  Move the iterator on one.
     */
    public void advance() {
      if (theParent == null)
        throw new InvalidIteratorOperationException() ;
      theParent = theItem ;
      if (theItem != null) {
        //  If there are duplicates then they are to be found in the
        //  left child.  See add.
        theItem = theItem.left ; 
        isLeft = true ;
        search(theValue) ;
      }
    }   
    /**
     *  Move the iterator on n or until the end is reached.
     *
     *  @exception InvalidIteratorOperationException if the increment
     *  is negative
     */
    public void advance(int increment) {
      if (increment < 0)
        throw new InvalidIteratorOperationException() ;
      for ( ; increment > 0 ; --increment) {
        if (atEnd())
          break ;
        advance() ;
      }
    }   
    /**
     *  Determine whether we are positioned at the beginning.
     */            
    public boolean atBegin() {
      return theItem == root.left ;
    }
    /**
     *  Determine whether we have iterated over all the elements.
     */            
    public boolean atEnd() {
      return theItem == null ;
    }
    /**
     *  Are two iterators equal, i.e. do two iterators refer to the
     *  same item in the same data structure.
     */
    public boolean equals(final ADS.Iterator i) {
      if (!(i instanceof SearchIterator))
        return false ;
      return theItem == ((SearchIterator)i).theItem ;
    }
    /**
     *  Return a reference to the <CODE>Container</CODE> of this
     *  <CODE>Iterator</CODE>.
     */
    public Container getContainer() {
      return OrderedBinaryTree.this ;
    }
    /**
     *  Clone this <CODE>Iterator</CODE>.
     */
    public final Object clone() {
      try {
        return super.clone() ;
      } catch (CloneNotSupportedException e) {
        throw new InternalError ()  ;
      }
    }
    /**
     *  Add an item.
     */
    public void add(final Object o) {
      while (theItem != null) {
        search(o) ;
        if ((theItem != null) && ! duplicatesAllowed)
          throw new InvalidIteratorOperationException () ;
        if (theItem == null)
          break ;
        //  If there are duplicates then they are to be found in the
        //  left child.  See advance.
        theParent = theItem ;
        theItem = theItem.left ;
        isLeft = true ;
      }
      set(o) ;
    }
    /**
     *  Remove this item.  Advance the iterator first.
     */
    public void remove() {
      if (theItem != null) {
        Node toGo = theItem ;
        advance() ;
        toGo.remove() ;
      }
    }
    /**
     *  Go searching for an item.
     */
    private void search(final Object o) {
      while (theItem != null) {
        if (equal.relation(o, theItem.datum))
          return ;
        theParent = theItem ;
        if (order.relation(o, theItem.datum)) {
          theItem = theItem.left ;
          isLeft = true ;
        } else {
          theItem = theItem.right ;
          isLeft = false ;
        }
      }
    }
  }
  /**
   *  The method to find a particular node in the tree.  This is the
   *  factory method for <CODE>SearchIterator</CODE>s.
   */
  protected Iterator searchFor(final Object o) {
    return new SearchIterator (o) ;
  }  
}