KezvhLib/src-lib/net/kezvh/collections/TreeIterator.java

   1 /**
   2  *
   3  */
   4 package net.kezvh.collections;
   5
   6 import java.util.Collections;
   7 import java.util.Deque;
   8 import java.util.Iterator;
   9 import java.util.LinkedList;
  10 import java.util.List;
  11 import java.util.Set;
  12
  13 /**
  14  * @author afflux
  15  *
  16  * @param <T> the type of the tree node
  17  */
  18 public class TreeIterator<T> implements Iterator<T> {
  19         /**
  20          * @author afflux
  21          *
  22          * @param <T> the type of the tree node
  23          */
  24         public interface ChildrenAccessor<T> {
  25                 /**
  26                  * @param node
  27                  * @return the children of the node
  28                  */
  29                 Set<T> getChildren(T node);
  30         }
  31
  32         private final ChildrenAccessor<T> childrenAccessor;
  33
  34         private final Deque<Iterator<T>> iteratorStack = new LinkedList<Iterator<T>>();
  35         private final LinkedList<T> stack = new LinkedList<T>() {
  36                 {
  37                         this.add(null);
  38                 }
  39         };
  40         private final List<T> unmodifiableStack = Collections.unmodifiableList(this.stack);
  41
  42         /**
  43          * @param rootNode FIXME comment
  44          * @param childrenAccessor FIXME comment
  45          */
  46         public TreeIterator(final T rootNode, final ChildrenAccessor<T> childrenAccessor) {
  47                 this.childrenAccessor = childrenAccessor;
  48                 this.iteratorStack.add(Collections.singleton(rootNode).iterator());
  49         }
  50
  51         /**
  52          * @see java.util.Iterator#hasNext()
  53          * @return x
  54          */
  55         @Override
  56         public boolean hasNext() {
  57                 for (final Iterator<T> iterator : this.iteratorStack)
  58                         if (iterator.hasNext())
  59                                 return true;
  60                 return false;
  61         }
  62
  63         /**
  64          * @see java.util.Iterator#next()
  65          * @return x
  66          */
  67         @Override
  68         public T next() {
  69                 while (!this.last().hasNext()) {
  70                         this.iteratorStack.removeLast(); // will throw a NSEE if hasNext() is false
  71                         this.stack.removeLast();
  72                 }
  73                 final T nextNode = this.last().next();
  74                 this.stack.set(this.stack.size() - 1, nextNode);
  75                 final Set<T> children = this.childrenAccessor.getChildren(nextNode);
  76                 if (!children.isEmpty()) {
  77                         this.iteratorStack.addLast(children.iterator());
  78                         this.stack.add(null);
  79                 }
  80                 return nextNode;
  81         }
  82
  83         private Iterator<T> last() {
  84                 return this.iteratorStack.peekLast();
  85         }
  86
  87         /**
  88          * @see java.util.Iterator#remove()
  89          */
  90         @Override
  91         public void remove() {
  92                 this.iteratorStack.peekLast().remove();
  93         }
  94
  95         /**
  96          * @return the stack
  97          */
  98         public List<T> getStack() {
  99                 return this.unmodifiableStack;
 100         }
 101
 102 }