Hierarchical Iterator

import static com.google.common.collect.ImmutableList.of;

import java.util.Iterator;
import java.util.LinkedList;

import com.google.common.collect.AbstractIterator;
import com.google.common.collect.Lists;

/**
 * This Iterator could be used for hierarchical data structure (e.g. Trees).
 *
 * @author Andreas Höhmann
 * @param <T>
 */
public abstract class AbstractHierarchialIterator<T> extends AbstractIterator<T> {

   private final LinkedList<Iterable<T>> stack = Lists.newLinkedList();
   private Iterator<T> current;

   public AbstractHierarchialIterator(final T start) {
      this(of(start));
   }

   private AbstractHierarchialIterator(final Iterable<T> start) {
      current = start.iterator();
   }

   /**
    * An concrete hierarchical iterator has to implement a method to 
    * visit the children of an element.
    *
    * @param currentElement
    * @return never <code>null</code>
    */
   protected abstract Iterable<T> childrenOf(T currentElement);

   @Override
   protected T computeNext() {
      while (true) {
         if (current.hasNext()) {
            final T next = current.next();
            stack.add(childrenOf(next));
            return next;
         }
         if (stack.isEmpty()) {
            break;
         }
         current = stack.removeFirst().iterator();
      }
      return endOfData();
   }
}

Examples

AbstractHierarchialIterator<Foobar> i = 
    new AbstractHierarchialIterator<Foobar>(foobarStart) {

    @Override
    protected Iterable<Foobar> childrenOf(final Foobar currentElement) {
        // <--- here you have to implement something
        return currentElement.getFoobarChildren(); 
    }
};

// example 1 - show all foobars
while (i.hasNext()) {
    System.out.println(i.next());
}

// example 2 - search the first "foo"
Foobar foo = com.google.common.collect.Iterators.find(i, new Predicate<Foobar>() {

      @Override
      public boolean apply(final Foobar input) {
        return "foo".equals(input.getName());
      }
    }, null);

Advertisement