View Javadoc

1   package net.sf.tacos.components.tree;
2   
3   import java.util.ArrayList;
4   import java.util.Collection;
5   import java.util.Collections;
6   import java.util.Iterator;
7   import java.util.List;
8   import java.util.Stack;
9   
10  /**
11   * @author phraktle
12   */
13  public abstract class TreeIterator implements Iterator {
14  
15      private final Stack todo = new Stack();
16      private int depth = 0;
17      private int previousDepth = 0;
18      private int markers = 0;
19  
20      /**
21       * New tree
22       * @param rootElement
23       */
24      public TreeIterator(Object rootElement)
25      {
26          todo.push(rootElement);
27      }
28  
29      /**
30       * Tree iterator
31       * @param rootElements
32       */
33      public TreeIterator(Collection rootElements)
34      {
35          push(rootElements);
36      }
37  
38      /**
39       * Depth
40       * @return
41       */
42      public int getDepth()
43      {
44          return depth;
45      }
46  
47      /**
48       * Previous depth
49       * @return
50       */
51      public int getPreviousDepth()
52      {
53          return previousDepth;
54      }
55  
56      /**
57       * 
58       * {@inheritDoc}
59       */
60      public boolean hasNext()
61      {
62          return !todo.isEmpty() && todo.size() != markers;
63      }
64  
65      /**
66       * 
67       * {@inheritDoc}
68       */
69      public Object next()
70      {
71          Object node;
72          do {
73              node = todo.pop();
74              if (node == MARKER) {
75                  markers--;
76              }
77          } while(node == MARKER);
78          previousDepth = depth;
79          depth = markers;
80          Collection children = getChildren(node);
81          if (!children.isEmpty()) {
82              todo.push(MARKER);
83              markers++;
84              push(children);
85          }
86          return node;
87      }
88  
89      /**
90       * Push set of elements
91       * @param elements
92       */
93      private void push(Collection elements)
94      {
95          List rev = new ArrayList(elements);
96          Collections.reverse(rev);
97          todo.addAll(rev);
98      }
99  
100     /**
101      * Gets children
102      * @param node
103      * @return
104      */
105     protected abstract Collection getChildren(Object node);
106 
107     /**
108      * 
109      * {@inheritDoc}
110      */
111     public void remove()
112     {
113         throw new UnsupportedOperationException();
114     }
115 
116     private final static Object MARKER = new Object();
117 
118 }