001// Copyright (c) 2001 Hursh Jain (http://www.mollypages.org) 
002// The Molly framework is freely distributable under the terms of an
003// MIT-style license. For details, see the molly pages web site at:
004// http://www.mollypages.org/. Use, modify, have fun !
005
006package fc.util;
007
008import java.util.*;
009
010/** 
011Implements a simple Tree data structure. The tree is made up of nodes. Each
012node has an associated object holding the data for that node and has zero
013(0) or arbitrary more children. 
014<p>
015Depending on the application, leaf data can be collectively stored as part
016of the data for a node or spread out among child (leaf) nodes. For example,
017if the tree represents a directory structure, files (leaf data) for a
018directory can be stored as part of that directory's node itself or as part
019of additional child nodes under that directory node (1 file per child
020node). Such additional child nodes should be used for leaf data if there is
021some chance/need of converting those leaf nodes to non-leaf nodes in the
022future.
023<p>
024This class provides operations common to all trees. Tree based data structures 
025can be built on top of this class.
026
027@author hursh jain
028**/
029public class Tree
030{
031//private static final boolean dbg = true;
032private static final boolean dbg = false;
033
034String name;
035Node root;
036
037/** Constructs a new tree **/
038public Tree() {
039  this(null);
040  }
041
042/** 
043Constructs a new tree with the specified name
044
045@param  name  the name of this tree
046**/
047public Tree(String name) {
048  this.name = name;
049  } 
050
051/**
052Creates and returns the root node for this tree.
053
054@param  data the data object associated with this node
055**/
056public Node createRootNode(Object data) {
057  root = new Node(data);
058  return root;
059  }
060
061/** 
062Returns the root node of this tree. If no root node has been created 
063returns <tt>null</tt>.
064**/
065public Tree.Node getRootNode() {
066  return root;
067  }
068
069
070public String toString() {
071  return name + "; maximum depth=" + root.getMaxDepth() + "; total # of nodes=" + root.recursiveSize(); 
072  }
073
074static public class Node
075  {
076    Node parent;
077    List children;
078    Object data;
079
080    /**
081    Creates a new Node. The created Node is not attached to any other node in the
082    tree and must be manually attached via the {@link #setParent(TreeNode)}
083    method.
084  
085  @param  data  the data object associated with this node.
086  **/
087    public Node(Object data) {
088      this(null, data);
089      }
090
091    /**
092    Creates a new Node and adds it as a child of the specified Node
093  
094  @param  parent  the parent of this node
095  @param  data  the data object associated with this node
096    **/
097    public Node(Node parent, Object data) {
098    this.parent = parent;
099      this.data = data;
100      this.children = new ArrayList();
101    if (parent != null) { //could be for root nodes
102      parent.add(this);
103      }
104    }
105
106      
107    /** Adds the specified node as a new child node to this node.
108  **/
109    public void add(Node child) {
110      children.add(child);
111      }
112
113  /**
114    Removes a single instance of the specified element from this node's children, 
115  if it is present. More formally, removes an element e such that
116    (o==null ? e==null : o.equals(e)), if this node contains one or more such
117    elements. Returns <tt>true</tt> if this node contained the specified element (or
118    equivalently, if this collection changed as a result of the call).
119
120  @param   child  child element to be removed from this node if present.
121  @return true  if this node changed as a result of the call
122  **/
123  public boolean remove(Node child) {
124      return children.remove(child);
125      }
126  
127    /** 
128    Returns the children of this node. The returned list is <b>not</b> a copy
129    of this node's trees therefore any modification made to the returned
130    object will be seen by this node. This is useful for reordering nodes etc.
131    **/
132    public List getChildren() {
133      return children;
134      }
135
136  /**
137  Returns the first child node whose data object equals the specified
138  argument. That is, returns child node where <tt>childnode.data.equals(obj)
139  == true</tt>. Returns <tt>null</tt> is no matching child node is found.
140  
141  @param  obj   the object against which the child nodes will be compared
142  **/
143  public Node getChildContaining(Object obj) {
144    if (children == null)
145      return null;
146    Node result = null;
147    for (Iterator it = children.iterator(); it.hasNext(); /*empty*/) 
148      {
149      Node item = (Node) it.next();
150      Object itemdata = item.data;
151      if ( itemdata != null && itemdata.equals(obj) ) {
152        result = item;
153        break;
154        }
155      } 
156    return result;  
157    }
158
159  /**
160    Returns true if this node contains the specified element. Follows the
161  contract of {@link java.util.Collection#contains(Object)}
162  
163  @param  child node whose presence in this collection is to be tested.
164  @return true if this node contains the specified child element
165  **/
166    public boolean containsChild(Node child) {
167      return children.contains(child);
168      }
169
170    /**
171  Returns the parent of the TreeNode, <tt>null</tt> if there is no parent 
172  **/
173    public Node getParent() {
174      return parent;
175      }
176      
177  /** 
178  Returns the siblings of this node. A sibling is any node that is a child
179  of this node's parent and is not the same as this node. 
180  <p>
181    Returns an iterator with no elements if there are no siblings or if this is 
182  the root node (which can have no siblings). 
183  **/ 
184    public Iterator getSiblings() 
185    {
186    List list = new ArrayList();
187    if (parent == null)
188      return list.iterator();
189    Node parent = getParent();
190    Iterator it = parent.children.iterator(); 
191    while(it.hasNext()) {
192      Node item = (Node) it.next();
193      // 'this' makes sure it's a reference test, not an equals() test
194      // because conceivably equals() could be redefined by some subclass
195      // to have non reference (data based) equality. For a list of
196      // siblings, we want reference equality
197      if (item == this) 
198        continue;
199      list.add(item);
200      } 
201    return list.iterator();     
202      }
203
204    /**
205    Returns the Object representing the data for this node, <tt>null</tt> if
206    no data has been assigned.
207    **/
208    public Object getData() {
209      return data;
210      }
211
212  /** 
213    Returns the total number of all nodes reachable under this node. If there
214    are no children, this method returns 1 (this node itself is of size 1) 
215  **/
216  public int recursiveSize() {
217    int size = 1;
218    for (Iterator it = children.iterator(); it.hasNext(); /*empty*/) {
219      Node item = (Node) it.next();
220      size += item.recursiveSize();
221      } 
222    return size;  
223    }   
224      
225  /** 
226    Returns <tt>true</tt> if this node is the root node of the tree,
227    <tt>false</tt> otherwise. 
228    **/
229    public boolean isRoot() {
230      return (parent == null);
231      }
232  
233  /**  
234  Returns <tt>true</tt> if the specified node is an ancestor of this node
235  <tt>false</tt> otherwise. An ancestor is any node between thre root node
236  and this node, not including this node itself.
237  **/
238  public boolean isNodeAncestor(Node ancestor) {
239    if (ancestor == this) {
240      return false; //not needed for correctness, short-circuit for speed
241      }
242    boolean result = false;
243    Node p = parent;  //this means we don't consider ourselves anyway
244    while (p != null) {
245      p = p.getParent();
246      if (p.equals(ancestor)) {
247        result = true;
248        break;
249        }     
250      }
251    return result;
252    }
253  
254  /** 
255  Returns <tt>true</tt> if the specified node is a child of this node
256  <tt>false</tt> otherwise. A node is not a child of itself.
257  **/
258  public boolean isNodeChild(Node child) {
259    return children.contains(child);
260    }
261  
262  /**
263  Returns <tt>true</tt> if the specified node is a descendent of this node
264  <tt>false</tt> otherwise. A node is not a descendent of itself.
265  **/
266  public boolean isNodeDescendant(Node descendent) {
267    return descendent.isNodeAncestor(this);  
268    }
269  
270  /**  
271  Returns <tt>true</tt> if the specified node is a sibling of this node
272  <tt>false</tt> otherwise. A node is not a sibling of itself.
273  **/
274  public boolean isNodeSibling(Node node) {
275    return ( node != this && parent.children.contains(node) );
276    }
277  
278  /** Returns <tt>true</tt> is this node has no children, <tt>false</tt> otherwise**/
279  public boolean isLeaf() {
280    if (children.size() == 0)
281      return true;
282    else return false;
283    }
284  
285  /** 
286  Gets the level of this node starting from the root (the root node is
287  at level 0) 
288  **/
289  public int getLevel() {
290    int level = 0;
291    Node p = parent;
292    while (p != null) {
293      level++;
294      p = p.parent;
295      } 
296    return level;
297    }
298
299  /** 
300    Returns the maximum depth of the tree starting from this node and following
301    the deepest branch. The ending depth is a node that contains only data
302    (leaves) and no children. If this node has no children, this method returns
303    0 (i.e., this node itself is at depth 0).
304  **/ 
305    public int getMaxDepth() {
306    int childrensize = children.size();
307    if (childrensize == 0) {
308      return 0;
309      }
310    List depthlist = new ArrayList(childrensize);
311    for (Iterator it = children.iterator(); it.hasNext(); /*empty*/) {
312      Node item = (Node) it.next();
313      depthlist.add(new Integer(item.getMaxDepth())); 
314      } 
315    return ((Integer)Collections.max(depthlist)).intValue() + 1;
316    }
317  
318  
319  /** 
320  Returns an iterator for all the nodes in the tree, starting from this node
321  onwards. 
322  @parem  order the tree transveral order for the iteration
323  **/
324  public Iterator iterator(IterationOrder order) {
325    return order.iterator(this);
326    }
327  
328  /** 
329    Calls super.equals(), i.e, reference equality. java.util.Collection
330    operations like add/remove nodes etc., are defined in terms of equals(). It
331    becomes very inefficient to have a full-fledged equals that compares both
332    the data of this node and the exact number and structure of the children of
333    this node. Subclasses can optionally redefine this method if necessary.
334  **/
335  public boolean equals(Object obj) {
336      return super.equals(obj);
337    }
338  
339  /** 
340  Compares the values of 2 nodes. Only the data associated with the
341  nodes is compared; the number/structure of any child nodes is ignored
342  by this method
343  **/
344  public boolean valEquals(Node one, Node other) 
345    {
346    if (one == null || other == null) 
347      return false;
348    Object obj = one.data;
349    if ( obj == null || ! obj.equals(other.data) )
350      return false;
351    return true;
352    }
353      
354  public String toString() {
355    if (data == null)
356      return "Node[no data]";
357    else
358      return data.toString();
359    }
360    
361  } //~class Node 
362  
363  
364static abstract public class IterationOrder 
365  {
366  private IterationOrder() { /* */ }
367  public abstract Iterator iterator(Node startnode);
368  
369  /** A breadth first iteration of the tree, starting from the specified startnode. **/ 
370  public static final IterationOrder BreadthFirst = new IterationOrder() {
371    public Iterator iterator(Node startnode) {
372      return new BreadthFirstIterator(startnode);
373      }
374    };
375    
376  /** A depth first, left to right, pre order iteration starting from the specified startnode. **/
377  public static final IterationOrder PreOrder = new IterationOrder() {
378    public Iterator iterator(Node startnode) {
379      return new PreOrderIterator(startnode);
380      }
381    };
382
383  /** 
384  A depth first, left to right, in order iteration starting from the specified startnode.
385  In order iteration only makes sense when each node has a maximum of 2 child
386  nodes (since the parent node is visited between the left and right children).
387  Therefore this iteration will throw a runtime exception if more than 2 children
388  are encountered for any node.
389  **/
390  public static final IterationOrder InOrder = new IterationOrder() {
391    public Iterator iterator(Node startnode) {
392      return new InOrderIterator(startnode);
393      }
394    };
395
396  /** A depth first, left to right, post order iteration starting from the specified startnode **/
397  public static final IterationOrder PostOrder = new IterationOrder() {
398    public Iterator iterator(Node startnode) {
399      return new PostOrderIterator(startnode);
400      }
401    };
402    
403  } //~class IterationOrder
404
405  //-------------------- Iterators --------------------------------
406
407  private static class BreadthFirstIterator implements Iterator 
408    {
409    Queue q;
410    
411    BreadthFirstIterator(Node startnode) {
412      q = new Queue();  
413      q.enque(startnode);
414      }
415
416    public boolean hasNext() {
417      return (! q.empty());
418      }
419    
420    public Object next() {
421      if (! hasNext()) {
422        throw new NoSuchElementException("No more elements");
423        }   
424      Node node = (Node) q.deque();
425      /*
426      we don't iterate the q and add the children of _all_
427      current nodes because that way successive removals
428      might result in children of following nodes getting
429      added more than once.
430      */
431      if (! node.isLeaf()) {
432        // addAll adds all elements in the child list, enque will add
433        // the child list itself and later cause a classcastexception
434        // between List and Node
435        q.addAll(node.getChildren()); 
436        }
437      return node;
438      }
439    
440    public void remove() {
441      throw new UnsupportedOperationException("Not supported");
442      } 
443    }   //~BreadthFirstIterator
444  
445  //we use a stack to recursively push child nodes, with the left most
446  //child being the top most item on the stack.  
447  private static class PreOrderIterator implements Iterator 
448    {
449    Stack stack;
450    
451    PreOrderIterator(Node startnode) {
452      Argcheck.notnull(startnode, "specified node was null");
453      stack = new Stack();
454      stack.push(startnode);
455      } 
456
457    public boolean hasNext() {
458      return (! stack.empty());
459      }
460    
461    public Object next() 
462      {
463      if (! hasNext()) {
464        throw new NoSuchElementException("No more elements");
465        }   
466      Node node = (Node) stack.pop();
467      List childlist = node.children;
468      //push children in reverse (right to left) order
469      ListIterator it = childlist.listIterator(childlist.size());
470      while(it.hasPrevious()) {
471        Node item = (Node) it.previous();
472        stack.push(item);
473        } 
474      return node;  
475      }
476    
477    public void remove() {
478      throw new UnsupportedOperationException("Not supported");
479      } 
480      
481    } //~PreOrderIterator
482
483  /*
484  A simply Stack based approach does not work because we have
485  to push the parent before pushing the children (parents come
486  first). When the children are popped, we are back to the
487  parent (post order) but at this point our algorithm has to
488  keep track that this particular parent's child nodes were
489  already visited, otherwise we go into a never ending loop.
490  We can keep track of the parent node's state via a separate
491  data structure (i.e., already visited this node or not, a
492  property called "node color" is canonically used for this
493  purpose). Another way is to use multiple stacks, where if
494  any parent has children, then those children are pushed into
495  a separate stack and so on. This way we finish popping the
496  child stack and then move back to the parent stack and pop
497  the parent. 
498  This method owes a lot to the similar method found in 
499  javax.swing.Tree.*
500  */
501  private static class PostOrderIterator implements Iterator 
502    {
503    Node startnode;
504    Stack childstack;
505    Iterator child_it;
506    
507    PostOrderIterator(Node startnode) 
508      {
509      Argcheck.notnull(startnode, "specified node was null");
510      childstack = new Stack();
511      this.startnode = startnode;
512      
513      if (! startnode.isLeaf()) 
514        {
515        //push children in reverse order
516        List childlist = startnode.children;
517        ListIterator it = childlist.listIterator(childlist.size());
518        while(it.hasPrevious()) {
519          Node item = (Node) it.previous();
520          childstack.push(item);
521          } 
522        }
523      
524      Iterator empty = new ArrayList().iterator();
525      child_it = empty;
526      }
527
528    public boolean hasNext() {
529      return startnode != null;
530      }
531      
532    //the child_it will return all nodes below a child node including
533    //the child node itself
534    public Object next() 
535      {
536      if (dbg) System.out.println("ENTER PostOrderIterator[@" + System.identityHashCode(this) + "].next(); rootnode=" + startnode + "; stack=" + childstack);
537    
538      if (! hasNext()) {
539        throw new NoSuchElementException("No more elements");
540        }   
541      if (child_it.hasNext()) {
542        Object obj = child_it.next();
543        if (dbg) System.out.println("PostOrderIterator[@" + System.identityHashCode(this) + "].child_it.hasNext()=true; returning obj=" + obj);
544        return obj;
545        }
546      else if (! childstack.empty()) {
547        child_it = new PostOrderIterator((Node)childstack.pop());
548        Object obj = child_it.next();
549        if (dbg) System.out.println("PostOrderIterator[@" + System.identityHashCode(this) + "]; stack not empty; returning obj=" + obj);
550        return obj;
551        }
552      else { //children processed, return this node
553        Object node = startnode;
554        startnode = null;
555        if (dbg) System.out.println("PostOrderIterator[@" + System.identityHashCode(this) + "]; returning rootnode=" + node);
556        return node;
557        }
558      }   //~next
559    
560    public void remove() {
561      throw new UnsupportedOperationException("Not supported");
562      } 
563      
564    } //~PostOrderIterator
565
566
567  private static class InOrderIterator implements Iterator 
568    {
569    Node startnode;
570    //we are only interested in que'ing/deq'uing nodes since each
571    //node's subtree is handled via a recursive call. We could use
572    //a stack as a que by reverse pushing and then popping but a 
573    //queue is simpler. 
574    Queue q;
575    Iterator child_it;    //the iterator for child subtrees
576    
577    InOrderIterator(Node startnode) 
578      {
579      Argcheck.notnull(startnode, "specified node was null");
580      List childlist = startnode.children;
581      int size = childlist.size();
582      
583      if (size > 2) 
584        throw new IllegalArgumentException("This iterator only supports 2 children per node. Encountered node has children = " + childlist);
585      
586      q = new Queue();
587      this.startnode = startnode;
588  
589      if (size == 2) {
590        q.enque(childlist.get(0)); //first element
591        q.enque(startnode);
592        q.enque(childlist.get(1)); //second element
593        }
594      else if (size == 1) {
595        q.enque(startnode);
596        q.enque(childlist.get(0)); 
597        }
598      else {
599        q.enque(startnode);
600        }
601          
602      Iterator empty = new ArrayList().iterator();
603      child_it = empty;
604      }
605
606    public boolean hasNext() 
607      {
608    // cannot just test q.empty() because this queue may be empty after 
609    // removing the last item, yet the subtree created by the last element
610    // may not be empty.
611      //return ! q.empty(); 
612      return (! q.empty() || child_it.hasNext());
613      }
614      
615    public Object next() 
616      {
617      if (dbg) System.out.println("ENTER: InOrderIterator[@" + System.identityHashCode(this) + "].next(): current queue=" + q);
618    
619      //1. our own queue has more children or a subtree has more children ?
620      if (! hasNext()) {
621        throw new NoSuchElementException("No more elements");
622        }
623  
624      //2. child subtree (for a given child) has more items ?
625      if (child_it.hasNext()) {
626        Object obj = child_it.next();
627        if (dbg) System.out.println("InOrderIterator[@" + System.identityHashCode(this) + "].next(): child_it.hasNext()=true; returning: " + obj);
628        return obj;
629        }
630                    
631      Node node = (Node) q.deque();
632      
633      if (node == startnode) {  //the startnode itself
634        if (dbg) System.out.println("InOrderIterator[@" + System.identityHashCode(this) + "] returning rootnode: " + startnode);
635        return node;
636        }
637      else {
638        child_it = new InOrderIterator(node);
639        Object obj = child_it.next();
640        if (dbg) System.out.println("InOrderIterator[@" + System.identityHashCode(this) + "], returning InOrderIterator[@" + System.identityHashCode(child_it) + "].next()=" + obj); 
641        return obj;
642        }
643      }   //~next
644    
645    public void remove() {
646      throw new UnsupportedOperationException("Not supported");
647      } 
648      
649    } //~InOrderIterator
650
651public static void main(String[] args) throws Exception
652  {
653  Tree tree = new Tree("My_Test_Tree");
654  Tree.Node root = tree.createRootNode("1");
655  Tree.Node node1 = new Tree.Node(root, "2");
656  Tree.Node node2 = new Tree.Node(node1, "3");
657  node2 = new Tree.Node(node1, "4");
658  
659  node1 = new Tree.Node(root, "5");
660  node2 = new Tree.Node(node1, "6");
661  
662  System.out.println("Tree=" + tree);
663  iterateTest(root);
664  structTest(root);
665  
666  root = tree.createRootNode("1");
667  node2 = new Node("2");
668  Tree.Node node3 = new Node("3");
669  Tree.Node node4 = new Node("4");
670  root.add(node2);
671  node2.add(node3);
672  node3.add(node4); 
673  System.out.println("Tree=" + tree);
674  System.out.println("Note: when a node has only 1 child, in-order should print the parent before that child"); 
675  iterateTest(root);
676
677  root = tree.createRootNode("1");
678  node2 = new Node("2");
679  node3 = new Node("3");
680  node4 = new Node("4");
681  root.add(node2);
682  root.add(node3);
683  root.add(node4);
684  System.out.println("Tree=" + tree);
685  iterateTest(root);
686  }
687
688private static void iterateTest(Node node) {
689  Iterator it = null;
690
691  System.out.print("Breadth First iteration: ");
692  it = node.iterator(Tree.IterationOrder.BreadthFirst);
693  while(it.hasNext()) {
694    Node item = (Node) it.next();
695    System.out.print(item + " ");
696    } 
697  System.out.println("");       
698
699  System.out.print("PreOrder iteration: ");
700  it = node.iterator(Tree.IterationOrder.PreOrder);
701  while(it.hasNext()) {
702    Node item = (Node) it.next();
703    System.out.print(item + " ");
704    } 
705  System.out.println("");       
706
707  try {
708  System.out.print("InOrderIteration: ");
709  it = node.iterator(Tree.IterationOrder.InOrder);
710  while(it.hasNext()) {
711    Node item = (Node) it.next();
712    System.out.print(item + " ");
713    } 
714  System.out.println("");       
715  }
716  catch (Exception e) {
717    e.printStackTrace(); 
718    }
719    
720  System.out.print("PostOrder iteration: ");
721  it = node.iterator(Tree.IterationOrder.PostOrder);
722  while(it.hasNext()) {
723    Node item = (Node) it.next();
724    System.out.print(item + " ");
725    } 
726  System.out.println("");       
727  System.out.println("");       
728  }
729  
730private static void structTest(Node node) {
731  System.out.println("PreOrder iteration, methods test");
732  Iterator it = node.iterator(Tree.IterationOrder.PreOrder);
733  while(it.hasNext()) {
734    Node item = (Node) it.next();
735    System.out.print(item);
736    System.out.print(" ; isRoot=" + item.isRoot() );
737    System.out.print(" ; isleaf=" + item.isLeaf() );
738    System.out.print(" ; level=" + item.getLevel() );
739    System.out.print(" ; data=" + item.getData() );
740    System.out.print(" ; maxdepth=" + item.getMaxDepth() );
741    System.out.print(" ; parent=" + item.getParent() );
742    System.out.print(" ; siblings=");
743    printIterator(item.getSiblings()); 
744    System.out.println("");   
745    } 
746  System.out.println("");   
747  }
748
749private static void printIterator(Iterator it) {
750  if (it == null)
751    System.out.print(it);
752  else
753  while(it.hasNext()) {
754    System.out.print(it.next());
755    }     
756  }
757
758
759}   //~class Tree