// Copyright (c) 2001 Hursh Jain (http://www.mollypages.org) 
// The Molly framework is freely distributable under the terms of an
// MIT-style license. For details, see the molly pages web site at:
// http://www.mollypages.org/. Use, modify, have fun !

package fc.util;

import java.util.*;

/** 
Implements a simple Tree data structure. The tree is made up of nodes. Each
node has an associated object holding the data for that node and has zero
(0) or arbitrary more children. 
<p>
Depending on the application, leaf data can be collectively stored as part
of the data for a node or spread out among child (leaf) nodes. For example,
if the tree represents a directory structure, files (leaf data) for a
directory can be stored as part of that directory's node itself or as part
of additional child nodes under that directory node (1 file per child
node). Such additional child nodes should be used for leaf data if there is
some chance/need of converting those leaf nodes to non-leaf nodes in the
future.
<p>
This class provides operations common to all trees. Tree based data structures 
can be built on top of this class.

@author hursh jain
**/
public class Tree
{
//private static final boolean dbg = true;
private static final boolean dbg = false;

String name;
Node root;

/** Constructs a new tree **/
public Tree() {
  this(null);
  }

/** 
Constructs a new tree with the specified name

@param  name  the name of this tree
**/
public Tree(String name) {
  this.name = name;
  } 

/**
Creates and returns the root node for this tree.

@param  data the data object associated with this node
**/
public Node createRootNode(Object data) {
  root = new Node(data);
  return root;
  }

/** 
Returns the root node of this tree. If no root node has been created 
returns <tt>null</tt>.
**/
public Tree.Node getRootNode() {
  return root;
  }


public String toString() {
  return name + "; maximum depth=" + root.getMaxDepth() + "; total # of nodes=" + root.recursiveSize(); 
  }

static public class Node
  {
    Node parent;
    List children;
    Object data;

    /**
    Creates a new Node. The created Node is not attached to any other node in the
    tree and must be manually attached via the {@link #setParent(TreeNode)}
    method.
  
  @param  data  the data object associated with this node.
  **/
    public Node(Object data) {
      this(null, data);
      }

    /**
    Creates a new Node and adds it as a child of the specified Node
  
  @param  parent  the parent of this node
  @param  data  the data object associated with this node
    **/
    public Node(Node parent, Object data) {
    this.parent = parent;
      this.data = data;
      this.children = new ArrayList();
    if (parent != null) { //could be for root nodes
      parent.add(this);
      }
    }

      
    /** Adds the specified node as a new child node to this node.
  **/
    public void add(Node child) {
      children.add(child);
      }

  /**
    Removes a single instance of the specified element from this node's children, 
  if it is present. More formally, removes an element e such that
    (o==null ? e==null : o.equals(e)), if this node contains one or more such
    elements. Returns <tt>true</tt> if this node contained the specified element (or
    equivalently, if this collection changed as a result of the call).

  @param   child  child element to be removed from this node if present.
  @return true  if this node changed as a result of the call
  **/
  public boolean remove(Node child) {
      return children.remove(child);
      }
  
    /** 
    Returns the children of this node. The returned list is <b>not</b> a copy
    of this node's trees therefore any modification made to the returned
    object will be seen by this node. This is useful for reordering nodes etc.
    **/
    public List getChildren() {
      return children;
      }

  /**
  Returns the first child node whose data object equals the specified
  argument. That is, returns child node where <tt>childnode.data.equals(obj)
  == true</tt>. Returns <tt>null</tt> is no matching child node is found.
  
  @param  obj   the object against which the child nodes will be compared
  **/
  public Node getChildContaining(Object obj) {
    if (children == null)
      return null;
    Node result = null;
    for (Iterator it = children.iterator(); it.hasNext(); /*empty*/) 
      {
      Node item = (Node) it.next();
      Object itemdata = item.data;
      if ( itemdata != null && itemdata.equals(obj) ) {
        result = item;
        break;
        }
      } 
    return result;  
    }

  /**
    Returns true if this node contains the specified element. Follows the
  contract of {@link java.util.Collection#contains(Object)}
  
  @param  child node whose presence in this collection is to be tested.
  @return true if this node contains the specified child element
  **/
    public boolean containsChild(Node child) {
      return children.contains(child);
      }

    /**
  Returns the parent of the TreeNode, <tt>null</tt> if there is no parent 
  **/
    public Node getParent() {
      return parent;
      }
      
  /** 
  Returns the siblings of this node. A sibling is any node that is a child
  of this node's parent and is not the same as this node. 
  <p>
    Returns an iterator with no elements if there are no siblings or if this is 
  the root node (which can have no siblings). 
  **/ 
    public Iterator getSiblings() 
    {
    List list = new ArrayList();
    if (parent == null)
      return list.iterator();
    Node parent = getParent();
    Iterator it = parent.children.iterator(); 
    while(it.hasNext()) {
      Node item = (Node) it.next();
      // 'this' makes sure it's a reference test, not an equals() test
      // because conceivably equals() could be redefined by some subclass
      // to have non reference (data based) equality. For a list of
      // siblings, we want reference equality
      if (item == this) 
        continue;
      list.add(item);
      } 
    return list.iterator();     
      }

    /**
    Returns the Object representing the data for this node, <tt>null</tt> if
    no data has been assigned.
    **/
    public Object getData() {
      return data;
      }

  /** 
    Returns the total number of all nodes reachable under this node. If there
    are no children, this method returns 1 (this node itself is of size 1) 
  **/
  public int recursiveSize() {
    int size = 1;
    for (Iterator it = children.iterator(); it.hasNext(); /*empty*/) {
      Node item = (Node) it.next();
      size += item.recursiveSize();
      } 
    return size;  
    }   
      
  /** 
    Returns <tt>true</tt> if this node is the root node of the tree,
    <tt>false</tt> otherwise. 
    **/
    public boolean isRoot() {
      return (parent == null);
      }
  
  /**  
  Returns <tt>true</tt> if the specified node is an ancestor of this node
  <tt>false</tt> otherwise. An ancestor is any node between thre root node
  and this node, not including this node itself.
  **/
  public boolean isNodeAncestor(Node ancestor) {
    if (ancestor == this) {
      return false; //not needed for correctness, short-circuit for speed
      }
    boolean result = false;
    Node p = parent;  //this means we don't consider ourselves anyway
    while (p != null) {
      p = p.getParent();
      if (p.equals(ancestor)) {
        result = true;
        break;
        }     
      }
    return result;
    }
  
  /** 
  Returns <tt>true</tt> if the specified node is a child of this node
  <tt>false</tt> otherwise. A node is not a child of itself.
  **/
  public boolean isNodeChild(Node child) {
    return children.contains(child);
    }
  
  /**
  Returns <tt>true</tt> if the specified node is a descendent of this node
  <tt>false</tt> otherwise. A node is not a descendent of itself.
  **/
  public boolean isNodeDescendant(Node descendent) {
    return descendent.isNodeAncestor(this);  
    }
  
  /**  
  Returns <tt>true</tt> if the specified node is a sibling of this node
  <tt>false</tt> otherwise. A node is not a sibling of itself.
  **/
  public boolean isNodeSibling(Node node) {
    return ( node != this && parent.children.contains(node) );
    }
  
  /** Returns <tt>true</tt> is this node has no children, <tt>false</tt> otherwise**/
  public boolean isLeaf() {
    if (children.size() == 0)
      return true;
    else return false;
    }
  
  /** 
  Gets the level of this node starting from the root (the root node is
  at level 0) 
  **/
  public int getLevel() {
    int level = 0;
    Node p = parent;
    while (p != null) {
      level++;
      p = p.parent;
      } 
    return level;
    }

  /** 
    Returns the maximum depth of the tree starting from this node and following
    the deepest branch. The ending depth is a node that contains only data
    (leaves) and no children. If this node has no children, this method returns
    0 (i.e., this node itself is at depth 0).
  **/ 
    public int getMaxDepth() {
    int childrensize = children.size();
    if (childrensize == 0) {
      return 0;
      }
    List depthlist = new ArrayList(childrensize);
    for (Iterator it = children.iterator(); it.hasNext(); /*empty*/) {
      Node item = (Node) it.next();
      depthlist.add(new Integer(item.getMaxDepth())); 
      } 
    return ((Integer)Collections.max(depthlist)).intValue() + 1;
    }
  
  
  /** 
  Returns an iterator for all the nodes in the tree, starting from this node
  onwards. 
  @parem  order the tree transveral order for the iteration
  **/
  public Iterator iterator(IterationOrder order) {
    return order.iterator(this);
    }
  
  /** 
    Calls super.equals(), i.e, reference equality. java.util.Collection
    operations like add/remove nodes etc., are defined in terms of equals(). It
    becomes very inefficient to have a full-fledged equals that compares both
    the data of this node and the exact number and structure of the children of
    this node. Subclasses can optionally redefine this method if necessary.
  **/
  public boolean equals(Object obj) {
      return super.equals(obj);
    }
  
  /** 
  Compares the values of 2 nodes. Only the data associated with the
  nodes is compared; the number/structure of any child nodes is ignored
  by this method
  **/
  public boolean valEquals(Node one, Node other) 
    {
    if (one == null || other == null) 
      return false;
    Object obj = one.data;
    if ( obj == null || ! obj.equals(other.data) )
      return false;
    return true;
    }
      
  public String toString() {
    if (data == null)
      return "Node[no data]";
    else
      return data.toString();
    }
    
  } //~class Node 
  
  
static abstract public class IterationOrder 
  {
  private IterationOrder() { /* */ }
  public abstract Iterator iterator(Node startnode);
  
  /** A breadth first iteration of the tree, starting from the specified startnode. **/ 
  public static final IterationOrder BreadthFirst = new IterationOrder() {
    public Iterator iterator(Node startnode) {
      return new BreadthFirstIterator(startnode);
      }
    };
    
  /** A depth first, left to right, pre order iteration starting from the specified startnode. **/
  public static final IterationOrder PreOrder = new IterationOrder() {
    public Iterator iterator(Node startnode) {
      return new PreOrderIterator(startnode);
      }
    };

  /** 
  A depth first, left to right, in order iteration starting from the specified startnode.
  In order iteration only makes sense when each node has a maximum of 2 child
  nodes (since the parent node is visited between the left and right children).
  Therefore this iteration will throw a runtime exception if more than 2 children
  are encountered for any node.
  **/
  public static final IterationOrder InOrder = new IterationOrder() {
    public Iterator iterator(Node startnode) {
      return new InOrderIterator(startnode);
      }
    };

  /** A depth first, left to right, post order iteration starting from the specified startnode **/
  public static final IterationOrder PostOrder = new IterationOrder() {
    public Iterator iterator(Node startnode) {
      return new PostOrderIterator(startnode);
      }
    };
    
  } //~class IterationOrder

  //-------------------- Iterators --------------------------------

  private static class BreadthFirstIterator implements Iterator 
    {
    Queue q;
    
    BreadthFirstIterator(Node startnode) {
      q = new Queue();  
      q.enque(startnode);
      }

    public boolean hasNext() {
      return (! q.empty());
      }
    
    public Object next() {
      if (! hasNext()) {
        throw new NoSuchElementException("No more elements");
        }   
      Node node = (Node) q.deque();
      /*
      we don't iterate the q and add the children of _all_
      current nodes because that way successive removals
      might result in children of following nodes getting
      added more than once.
      */
      if (! node.isLeaf()) {
        // addAll adds all elements in the child list, enque will add
        // the child list itself and later cause a classcastexception
        // between List and Node
        q.addAll(node.getChildren()); 
        }
      return node;
      }
    
    public void remove() {
      throw new UnsupportedOperationException("Not supported");
      } 
    }   //~BreadthFirstIterator
  
  //we use a stack to recursively push child nodes, with the left most
  //child being the top most item on the stack.  
  private static class PreOrderIterator implements Iterator 
    {
    Stack stack;
    
    PreOrderIterator(Node startnode) {
      Argcheck.notnull(startnode, "specified node was null");
      stack = new Stack();
      stack.push(startnode);
      } 

    public boolean hasNext() {
      return (! stack.empty());
      }
    
    public Object next() 
      {
      if (! hasNext()) {
        throw new NoSuchElementException("No more elements");
        }   
      Node node = (Node) stack.pop();
      List childlist = node.children;
      //push children in reverse (right to left) order
      ListIterator it = childlist.listIterator(childlist.size());
      while(it.hasPrevious()) {
        Node item = (Node) it.previous();
        stack.push(item);
        } 
      return node;  
      }
    
    public void remove() {
      throw new UnsupportedOperationException("Not supported");
      } 
      
    } //~PreOrderIterator

  /*
  A simply Stack based approach does not work because we have
  to push the parent before pushing the children (parents come
  first). When the children are popped, we are back to the
  parent (post order) but at this point our algorithm has to
  keep track that this particular parent's child nodes were
  already visited, otherwise we go into a never ending loop.
  We can keep track of the parent node's state via a separate
  data structure (i.e., already visited this node or not, a
  property called "node color" is canonically used for this
  purpose). Another way is to use multiple stacks, where if
  any parent has children, then those children are pushed into
  a separate stack and so on. This way we finish popping the
  child stack and then move back to the parent stack and pop
  the parent. 
  This method owes a lot to the similar method found in 
  javax.swing.Tree.*
  */
  private static class PostOrderIterator implements Iterator 
    {
    Node startnode;
    Stack childstack;
    Iterator child_it;
    
    PostOrderIterator(Node startnode) 
      {
      Argcheck.notnull(startnode, "specified node was null");
      childstack = new Stack();
      this.startnode = startnode;
      
      if (! startnode.isLeaf()) 
        {
        //push children in reverse order
        List childlist = startnode.children;
        ListIterator it = childlist.listIterator(childlist.size());
        while(it.hasPrevious()) {
          Node item = (Node) it.previous();
          childstack.push(item);
          } 
        }
      
      Iterator empty = new ArrayList().iterator();
      child_it = empty;
      }

    public boolean hasNext() {
      return startnode != null;
      }
      
    //the child_it will return all nodes below a child node including
    //the child node itself
    public Object next() 
      {
      if (dbg) System.out.println("ENTER PostOrderIterator[@" + System.identityHashCode(this) + "].next(); rootnode=" + startnode + "; stack=" + childstack);
    
      if (! hasNext()) {
        throw new NoSuchElementException("No more elements");
        }   
      if (child_it.hasNext()) {
        Object obj = child_it.next();
        if (dbg) System.out.println("PostOrderIterator[@" + System.identityHashCode(this) + "].child_it.hasNext()=true; returning obj=" + obj);
        return obj;
        }
      else if (! childstack.empty()) {
        child_it = new PostOrderIterator((Node)childstack.pop());
        Object obj = child_it.next();
        if (dbg) System.out.println("PostOrderIterator[@" + System.identityHashCode(this) + "]; stack not empty; returning obj=" + obj);
        return obj;
        }
      else { //children processed, return this node
        Object node = startnode;
        startnode = null;
        if (dbg) System.out.println("PostOrderIterator[@" + System.identityHashCode(this) + "]; returning rootnode=" + node);
        return node;
        }
      }   //~next
    
    public void remove() {
      throw new UnsupportedOperationException("Not supported");
      } 
      
    } //~PostOrderIterator


  private static class InOrderIterator implements Iterator 
    {
    Node startnode;
    //we are only interested in que'ing/deq'uing nodes since each
    //node's subtree is handled via a recursive call. We could use
    //a stack as a que by reverse pushing and then popping but a 
    //queue is simpler. 
    Queue q;
    Iterator child_it;    //the iterator for child subtrees
    
    InOrderIterator(Node startnode) 
      {
      Argcheck.notnull(startnode, "specified node was null");
      List childlist = startnode.children;
      int size = childlist.size();
      
      if (size > 2) 
        throw new IllegalArgumentException("This iterator only supports 2 children per node. Encountered node has children = " + childlist);
      
      q = new Queue();
      this.startnode = startnode;
  
      if (size == 2) {
        q.enque(childlist.get(0)); //first element
        q.enque(startnode);
        q.enque(childlist.get(1)); //second element
        }
      else if (size == 1) {
        q.enque(startnode);
        q.enque(childlist.get(0)); 
        }
      else {
        q.enque(startnode);
        }
          
      Iterator empty = new ArrayList().iterator();
      child_it = empty;
      }

    public boolean hasNext() 
      {
    // cannot just test q.empty() because this queue may be empty after 
    // removing the last item, yet the subtree created by the last element
    // may not be empty.
      //return ! q.empty(); 
      return (! q.empty() || child_it.hasNext());
      }
      
    public Object next() 
      {
      if (dbg) System.out.println("ENTER: InOrderIterator[@" + System.identityHashCode(this) + "].next(): current queue=" + q);
    
      //1. our own queue has more children or a subtree has more children ?
      if (! hasNext()) {
        throw new NoSuchElementException("No more elements");
        }
  
      //2. child subtree (for a given child) has more items ?
      if (child_it.hasNext()) {
        Object obj = child_it.next();
        if (dbg) System.out.println("InOrderIterator[@" + System.identityHashCode(this) + "].next(): child_it.hasNext()=true; returning: " + obj);
        return obj;
        }
                    
      Node node = (Node) q.deque();
      
      if (node == startnode) {  //the startnode itself
        if (dbg) System.out.println("InOrderIterator[@" + System.identityHashCode(this) + "] returning rootnode: " + startnode);
        return node;
        }
      else {
        child_it = new InOrderIterator(node);
        Object obj = child_it.next();
        if (dbg) System.out.println("InOrderIterator[@" + System.identityHashCode(this) + "], returning InOrderIterator[@" + System.identityHashCode(child_it) + "].next()=" + obj); 
        return obj;
        }
      }   //~next
    
    public void remove() {
      throw new UnsupportedOperationException("Not supported");
      } 
      
    } //~InOrderIterator

public static void main(String[] args) throws Exception
  {
  Tree tree = new Tree("My_Test_Tree");
  Tree.Node root = tree.createRootNode("1");
  Tree.Node node1 = new Tree.Node(root, "2");
  Tree.Node node2 = new Tree.Node(node1, "3");
  node2 = new Tree.Node(node1, "4");
  
  node1 = new Tree.Node(root, "5");
  node2 = new Tree.Node(node1, "6");
  
  System.out.println("Tree=" + tree);
  iterateTest(root);
  structTest(root);
  
  root = tree.createRootNode("1");
  node2 = new Node("2");
  Tree.Node node3 = new Node("3");
  Tree.Node node4 = new Node("4");
  root.add(node2);
  node2.add(node3);
  node3.add(node4); 
  System.out.println("Tree=" + tree);
  System.out.println("Note: when a node has only 1 child, in-order should print the parent before that child"); 
  iterateTest(root);

  root = tree.createRootNode("1");
  node2 = new Node("2");
  node3 = new Node("3");
  node4 = new Node("4");
  root.add(node2);
  root.add(node3);
  root.add(node4);
  System.out.println("Tree=" + tree);
  iterateTest(root);
  }

private static void iterateTest(Node node) {
  Iterator it = null;

  System.out.print("Breadth First iteration: ");
  it = node.iterator(Tree.IterationOrder.BreadthFirst);
  while(it.hasNext()) {
    Node item = (Node) it.next();
    System.out.print(item + " ");
    } 
  System.out.println("");       

  System.out.print("PreOrder iteration: ");
  it = node.iterator(Tree.IterationOrder.PreOrder);
  while(it.hasNext()) {
    Node item = (Node) it.next();
    System.out.print(item + " ");
    } 
  System.out.println("");       

  try {
  System.out.print("InOrderIteration: ");
  it = node.iterator(Tree.IterationOrder.InOrder);
  while(it.hasNext()) {
    Node item = (Node) it.next();
    System.out.print(item + " ");
    } 
  System.out.println("");       
  }
  catch (Exception e) {
    e.printStackTrace(); 
    }
    
  System.out.print("PostOrder iteration: ");
  it = node.iterator(Tree.IterationOrder.PostOrder);
  while(it.hasNext()) {
    Node item = (Node) it.next();
    System.out.print(item + " ");
    } 
  System.out.println("");       
  System.out.println("");       
  }
  
private static void structTest(Node node) {
  System.out.println("PreOrder iteration, methods test");
  Iterator it = node.iterator(Tree.IterationOrder.PreOrder);
  while(it.hasNext()) {
    Node item = (Node) it.next();
    System.out.print(item);
    System.out.print(" ; isRoot=" + item.isRoot() );
    System.out.print(" ; isleaf=" + item.isLeaf() );
    System.out.print(" ; level=" + item.getLevel() );
    System.out.print(" ; data=" + item.getData() );
    System.out.print(" ; maxdepth=" + item.getMaxDepth() );
    System.out.print(" ; parent=" + item.getParent() );
    System.out.print(" ; siblings=");
    printIterator(item.getSiblings()); 
    System.out.println("");   
    } 
  System.out.println("");   
  }

private static void printIterator(Iterator it) {
  if (it == null)
    System.out.print(it);
  else
  while(it.hasNext()) {
    System.out.print(it.next());
    }     
  }


}   //~class Tree