Home > Guava, Java, Softwareentwicklung > Hierarchical Iterator

Hierarchical Iterator

Thursday, 17. November 2011 Leave a comment Go to comments

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);

:)

About these ads
  1. Saturday, 19. November 2011 at 17:11

    Some questions.
    a) The variable “stack” is a LinkedList, why not a real “Stack”?
    b) In which order will the children be processed? In-, pre- or post-order? It is not configurable nor documented :P

    Greetings, Ben

  2. Tuesday, 22. November 2011 at 1:24

    Hi Ben,

    a) what class do you mean? Vector?
    b) this iterator will do it with http://en.wikipedia.org/wiki/Breadth-first_search, this simple code doesn’t need any documentation ;) … you are right … a next step could be the usage of the strategy pattern, in combination with the builder pattern it would be quite easy to support all aspects of traversing a hierarchical data-structure.

    cya
    höhmi

    • xaerxess
      Monday, 20. August 2012 at 20:23

      ad. a) ArrayDeque is superior to LinkedList (and Stack of course) if you use Java 6 and don’t need List interface goodies (positional get mainly). It even outperforms ArrayList; see this benchmark.

  1. No trackbacks yet.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: