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    
006    package fc.util;
007    
008    import java.util.*;
009    
010    /** 
011    Implements a simple Tree data structure. The tree is made up of nodes. Each
012    node has an associated object holding the data for that node and has zero
013    (0) or arbitrary more children. 
014    <p>
015    Depending on the application, leaf data can be collectively stored as part
016    of the data for a node or spread out among child (leaf) nodes. For example,
017    if the tree represents a directory structure, files (leaf data) for a
018    directory can be stored as part of that directory's node itself or as part
019    of additional child nodes under that directory node (1 file per child
020    node). Such additional child nodes should be used for leaf data if there is
021    some chance/need of converting those leaf nodes to non-leaf nodes in the
022    future.
023    <p>
024    This class provides operations common to all trees. Tree based data structures 
025    can be built on top of this class.
026    
027    @author hursh jain
028    **/
029    public class Tree
030    {
031    //private static final boolean dbg = true;
032    private static final boolean dbg = false;
033    
034    String name;
035    Node root;
036    
037    /** Constructs a new tree **/
038    public Tree() {
039      this(null);
040      }
041    
042    /** 
043    Constructs a new tree with the specified name
044    
045    @param  name  the name of this tree
046    **/
047    public Tree(String name) {
048      this.name = name;
049      } 
050    
051    /**
052    Creates and returns the root node for this tree.
053    
054    @param  data the data object associated with this node
055    **/
056    public Node createRootNode(Object data) {
057      root = new Node(data);
058      return root;
059      }
060    
061    /** 
062    Returns the root node of this tree. If no root node has been created 
063    returns <tt>null</tt>.
064    **/
065    public Tree.Node getRootNode() {
066      return root;
067      }
068    
069    
070    public String toString() {
071      return name + "; maximum depth=" + root.getMaxDepth() + "; total # of nodes=" + root.recursiveSize(); 
072      }
073    
074    static 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      
364    static 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    
651    public 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    
688    private 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      
730    private 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    
749    private 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