/******************************************************************************
    Binary Tree
----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.

Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted. 
*******************************************************************************/

package FlexOr.container;
import java.util.*;

/** Binary Tree is an abstract class implementing container.  It is abstract
because the following methods which depend upon different policies on node
ordering.<BR>
-- add <BR>
-- contains <BR>
-- remove <BR>
-- clone -- needs a non abstract class to create an instance.
<P>
@author Gunnar Gotshalks
@version 1.0 1999 Jan 15
*/

public abstract class BinaryTree implements Container {

/******************************************************************************
Defining the component objects
*******************************************************************************/
/** The tree itself. */

  protected Node tree = null;

/** Number of nodes in the tree */

  protected int count = 0;
  
/*******************************************************************************
   Access Methods -- not enumeration
*******************************************************************************/

/** Determines whether an element is in the tree.  Default uses the O(size)
<CODE>levelOrderLRtraversal</CODE> to search the tree.  Subclasses may want to
override this method.

<P><PRE><B>Requires:</B> True
<B>Ensures:</B> contains(obj) => result = true
            not contains(obj) => result = false
</PRE>
*/

  public boolean contains(Object obj) {
    Enumeration <Object> e = levelOrderLRtraversal();
    while (e.hasMoreElements()) {
      if (e.nextElement().equals(obj)) return true;
    }
    return false;
  }


/** Check if the container is empty.
<P><PRE><B>Requires:</B> True
<B>Ensures:</B> isEmpty = (count = 0)
</PRE>
 */

  public boolean isEmpty() { return count == 0; }

/** Check if the container is full.  Binary trees cannot be full.
<P><PRE><B>Requires:</B> True
<B>Ensures:</B> isFull = false
</PRE>
 */

  public boolean isFull() { return false; }

/** Returns the number of elements in the container.
<P><PRE><B>Requires:</B> True
<B>Ensures:</B> result = size
</PRE>
*/
  
  public int size() {  return count; }

/*******************************************************************************
   Access Methods -- enumeration
   --  Each of the eight possible traversal orders.
*******************************************************************************/
/** Returns an enumerator using inorder traversal -- left subtree first.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/
  
  public Enumeration<Object> elements() { return inOrderLRtraversal(); }

/** Return an enumerator using preorder traversal -- left subtree first.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/

  public Enumeration<Object> preOrderLRtraversal() {
    return new Enumeration<Object>() {
      public boolean hasMoreElements() { return !btStack.isEmpty(); }

/** Simulate the recursive version by stacking the two subtrees to be processed
after the current node. */

      public Object nextElement() {
        if (btStack.isEmpty()) throw new NoSuchElementException();
        Node node = (Node) btStack.remove();
        if (node.right != null) { btStack.add(node.right); }        
        if (node.left != null) { btStack.add(node.left); }
        return node.datum;
      }

      private Stack btStack = new Stack(); {
        if (tree != null) btStack.add(tree);
      }
    };
  }
  
/** Return an enumerator using preorder traversal -- right subtree first.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/

  public Enumeration<Object> preOrderRLtraversal() {
    return new Enumeration<Object> () {
      public boolean hasMoreElements() { return !btStack.isEmpty(); }

/** Simulate the recursive version by stacking the two subtrees to be processed
after the current node. */

      public Object nextElement() {
        if (btStack.isEmpty()) throw new NoSuchElementException();
        Node node = (Node) btStack.remove();
        if (node.left != null) { btStack.add(node.left); }        
        if (node.right != null) { btStack.add(node.right); }
        return node.datum;
      }
      
      private Stack btStack = new Stack(); {
        if (tree != null) btStack.add(tree);
      }
    };
  }
  
/** Return an enumerator using inorder traversal -- left subtree first.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/

  public Enumeration<Object> inOrderLRtraversal() {
    return new Enumeration<Object> () {
      public boolean hasMoreElements() { return !btStack.isEmpty(); }

/** Simulate the recursive version by stacking the left subtree nodes
until we reach the node to be processed. */
      
      public Object nextElement() {
        if (btStack.isEmpty()) throw new NoSuchElementException();
        Node node = (Node) btStack.remove();
        Object result = node.datum;
        if (node.right != null) {
          node = node.right;
          do { btStack.add(node);
            node = node.left;
          } while (node != null);
        }
        return result;
      }
      
      private Stack btStack = new Stack(); {
        Node node = tree;
        while (node != null) {
            btStack.add(node);
            node = node.left;
        }
      }
    };
  }
  
/** Return an enumerator using inorder traversal -- right subtree first.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/

  public Enumeration<Object> inOrderRLtraversal() {
    return new Enumeration<Object> () {
      public boolean hasMoreElements() { return !btStack.isEmpty(); }

/** Simulate the recursive version by stacking the right subtree nodes
until we reach the node to be processed. */

      public Object nextElement() {
        if (btStack.isEmpty()) throw new NoSuchElementException();
        Node node = (Node) btStack.remove();
        Object result = node.datum;
        if (node.left != null) {
          node = node.left;
          do { btStack.add(node);
            node = node.right;
          } while (node != null);
        }
        return result;
      }
      
      private Stack btStack = new Stack(); {
        Node node = tree;
        while (node != null) {
            btStack.add(node);
            node = node.right;
        }
      }
    };
  }
  
/** Return an enumerator using postorder traversal -- left subtree first.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/

  public Enumeration<Object> postOrderLRtraversal() {
    return new Enumeration<Object> () {
      public boolean hasMoreElements() { return !btStack.isEmpty(); }

/** Simulate the recursive version by stacking left branch nodes until we
reach the end, then stack the datum in the last node in a left path for
laster processing.  If a datum is popped it is the next element to return.
If a node is popped, it means the left branch has been processed, so go to the
first node on the right and repeat until we get to a leaf node.  Its datum is
the element to return. */

      public Object nextElement() {
        if (btStack.isEmpty()) throw new NoSuchElementException();
        Object tmp = btStack.remove();
        if (tmp instanceof Node) {
          Node node = (Node) tmp;
          while (node.right != null) {
            btStack.add(node.datum);
            node = node.right;
            while (node.left !=null) {
              btStack.add(node);
              node = node.left;
            }
          }
          return node.datum;
        }
        else return tmp;
      }
      
      private Stack btStack = new Stack(); {
        Node node = tree;
        while (node != null) {
            btStack.add(node);
            node = node.left;
        }
      }
    };
  }
   
/** Return an enumerator using postorder traversal -- right subtree first.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/

  public Enumeration<Object> postOrderRLtraversal() {
    return new Enumeration<Object> () {
      public boolean hasMoreElements() { return !btStack.isEmpty(); }

/** Simulate the recursive version by stacking right branch nodes until we
reach the end, then stack the datum in the last node in a right path for
laster processing.  If a datum is popped it is the next element to return.
If a node is popped, it means the right branch has been processed, so go to the
first node on the left and repeat until we get to a leaf node.  Its datum is
the element to return. */

      public Object nextElement() {
        if (btStack.isEmpty()) throw new NoSuchElementException();
        Object tmp = btStack.remove();
        if (tmp instanceof Node) {
          Node node = (Node) tmp;
          while (node.left != null) {
            btStack.add(node.datum);
            node = node.left;
            while (node.right !=null) {
              btStack.add(node);
              node = node.right;
            }
          }
          return node.datum;
        }
        else return tmp;
      }
      
      private Stack btStack = new Stack(); {
        Node node = tree;
        while (node != null) {
            btStack.add(node);
            node = node.right;
        }
      }
    };
  }

/** Return an enumerator using levelorder traversal -- left subtree first.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/

  public Enumeration<Object> levelOrderLRtraversal() {
    return new Enumeration<Object> () {
      public boolean hasMoreElements() { return !btQueue.isEmpty(); }

      public Object nextElement() {
        if (btQueue.isEmpty()) throw new NoSuchElementException();
        Node node = (Node) btQueue.remove();
        if (node.left != null) { btQueue.add(node.left); }
        if (node.right != null) { btQueue.add(node.right); }
        return node.datum;
      }
      
      private Queue btQueue = new Queue(); {
        if (tree!= null) btQueue.add(tree);
      }
    };
  }
  
/** Return an enumerator using levelorder traversal -- right subtree first.
@exception NoSuchElementException when nextElement is called with an empty
enumeration sequence.
*/

  public Enumeration<Object> levelOrderRLtraversal() {
    return new Enumeration<Object> () {
      public boolean hasMoreElements() { return !btQueue.isEmpty(); }

      public Object nextElement() {
        if (btQueue.isEmpty()) throw new NoSuchElementException();
        Node node = (Node) btQueue.remove();
        if (node.right != null) { btQueue.add(node.right); }
        if (node.left != null) { btQueue.add(node.left); }
        return node.datum;
      }
      
      private Queue btQueue = new Queue(); {
        if (tree!= null) btQueue.add(tree);
      }
    };
  }

/*******************************************************************************
   Update Methods
*******************************************************************************/

/** Adds <CODE>obj</CODE> at the default location.
<P><PRE><B>Requires:</B> True
<B>Ensures:</B> contains(obj) = true
                size = old size + 1
</PRE>
@exception ContainerFullException if container already contains MaxLength
elements for finite size containers.
*/

  public abstract void add(Object obj);
  
/** Empty the container.
<P><PRE><B>Requires:</B> True
<B>Ensures:</B> size = 0
</PRE>
*/

  public void removeAll() {
    tree = null;
    count = 0;
  }
  
/**
Remove the first element based on an inorder traversal of the tree contents.

<P><PRE><B>Requires:</B> size >= 0
<B>Ensures:</B> size = old size - 1
                old inorderSequence = obj ^ inorderSequence
</PRE>
@exception ContainerEmptyException if removing from an empty container.
*/

  public Object remove() {
    if (tree == null) { throw new ContainerEmptyException(); }

    Object result;
    Node node = tree;
    
    if (node.left == null) { result = node.datum; tree = node.right; }
    else {    
      while (node.left.left != null) { node = node.left; }
      result = node.left.datum;
      node.left = node.left.right;
    }
    count--;
    return result;
  }


/** Remove the specified element.
<P><PRE><B>Requires:</B> size >= 0
<B>Ensures:</B> 
    old binaryTree.contains(obj) =>
        binaryTree = old binaryTree / obj and result = true 
not old binaryTree.contains(obj) =>
        binaryTree = old binaryTree and result = false
</PRE>
@exception ContainerEmptyException if removing from an empty container.
*/

  public abstract boolean remove(Object obj);

/*******************************************************************************
   Object Methods
*******************************************************************************/

/** Return a copy of the tree that points to the same objects as in the original
tree.  Part way between a shallow and deep copy.  This is equivalent to how a
Vector is cloned.

<P><PRE><B>Requires:</B> True
<B>Ensures:</B> result = copy of BinaryTree
</PRE>
*/

  public abstract Object clone();  

/** Return a string representation of the contents of the tree.  Shows the
structure.

<P><PRE><B>Requires:</B> true
<B>Ensures:</B> result = string representation of tree
</PRE>
*/
  
  public String toString() {
    if (tree == null) return "[]";
    else return tree.toString();
  }

/** Check for equality of contents of two containers.  By equality we mean an
equal sequence of elements as returned by an inorder traversal.
<P><PRE><B>Requires:</B> True
<B>Ensures:</B> result = true => container contents are equal
                result = false => container contents are not equal
</PRE>
 */

  public boolean equals(Object container) {
    if (container == null) return false;
    if (! (container instanceof BinaryTree)) return false;
    if (count != ((BinaryTree) container).count) return false;
    return tree.equals(((BinaryTree) container).tree); 
  }

/*******************************************************************************
  Support classes and methods
*******************************************************************************/
/** Define a Node as an inner class.  Users of binary trees should not have to
know the structure of a node, they are only interested in the objects stored in
the tree.
*/

  protected class Node implements Cloneable {

/** Create a node with null subtrees. */

    protected Node(final Object obj) { this(obj, null, null); }

/** Create a node with specified subtrees. */
    
    protected Node(final Object obj, final Node left, final Node right) {
      datum = obj;
      this.left = left;
      this.right = right;
    }
    
/** Stores the object. */
 
    protected Object datum = null;

/* Point to the left subtree. */

    protected Node left = null;

/* Point to the right subtree. */

    protected Node right = null;

/*********************************
The toString and equals methods for a binary tree require helper functions to
recurse over the nodes in the tree.  It makes sense to have these methods be
a part of the definition of a node.
*/

/** Return a string representation of the contents of a Node and all its
descendents as defined by an inorder traversal

<P><PRE><B>Requires:</B> True
<B>Ensures:</B> result = string representation as described.
</PRE>
*/
  
    public String toString() {
      return new String("[" +
          (left == null ? "" : left.toString()) +
          datum.toString() +
          (right == null ? "" : right.toString()) +
          "]");
    }

/** Check for equality of contents of two nodes and all their descendents
as defined by an inorder traversal.

<P><PRE><B>Requires:</B> True
<B>Ensures:</B> result = true => nodes and descendents are equal
                result = false => nodes and descendents are not equal
</PRE>
 */

    public boolean equals(Node node) {
      if (node == null) return false;
      return datum == node.datum
         &&  ( left == null ? node.left == null
                            : left.equals(node.left) )
         &&  ( right == null ? node.right == null
                             : right.equals(node.right) ) ;
    }
 
 /** Clone the node and all of its descendents.  This is part way between a
 shallow and a deep copy.
 */
 
    public Object clone() {
      return new Node( datum,
                       (Node)(left == null ? null : left.clone()),
                       (Node)(right == null ? null : right.clone()));
    }

  } // End of class Node

} // End of class BinaryTree