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.Iterator;
   8 import java.util.LinkedList;
   9
  10 /**
  11  * @author afflux
  12  *
  13  * @param <T> the type of the tree node
  14  */
  15 public class TreeIterator<T> implements Iterator<T> {
  16         /**
  17          * @author afflux
  18          *
  19          * @param <T> the type of the tree node
  20          */
  21         public interface ChildrenAccessor<T> {
  22                 /**
  23                  * @param node
  24                  * @return the children of the node
  25                  */
  26                 Iterator<T> getChildren(T node);
  27         }
  28
  29         private final ChildrenAccessor<T> childrenAccessor;
  30
  31         private final LinkedList<Iterator<T>> iteratorStack = new LinkedList<Iterator<T>>();
  32
  33         /**
  34          * @param rootNode COMMENT
  35          * @param childrenAccessor COMMENT
  36          */
  37         public TreeIterator(final T rootNode, final ChildrenAccessor<T> childrenAccessor) {
  38                 this.childrenAccessor = childrenAccessor;
  39                 this.iteratorStack.add(Collections.singleton(rootNode).iterator());
  40         }
  41
  42         /**
  43          * @see java.util.Iterator#hasNext()
  44          * @return x
  45          */
  46         @Override
  47         public boolean hasNext() {
  48                 for (final Iterator<T> iterator : this.iteratorStack)
  49                         if (iterator.hasNext())
  50                                 return true;
  51                 return false;
  52         }
  53
  54         /**
  55          * @see java.util.Iterator#next()
  56          * @return x
  57          */
  58         @Override
  59         public T next() {
  60                 while (!this.last().hasNext())
  61                         this.iteratorStack.removeLast(); // will throw a NSEE if hasNext() is false
  62                 final T nextNode = this.last().next();
  63
  64                 final Iterator<T> children = this.childrenAccessor.getChildren(nextNode);
  65                 if (children.hasNext())
  66                         this.iteratorStack.addLast(children);
  67
  68                 return nextNode;
  69         }
  70
  71         private Iterator<T> last() {
  72                 return this.iteratorStack.peekLast();
  73         }
  74
  75         /**
  76          * @see java.util.Iterator#remove()
  77          */
  78         @Override
  79         public void remove() {
  80                 this.iteratorStack.peekLast().remove();
  81         }
  82
  83 }