Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright (C) 2012 The Guava Authors
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 package com.google.common.collect;
 
 import static com.google.common.base.Preconditions.checkNotNull;
 
 
Views elements of a type T as nodes in a tree, and provides methods to traverse the trees induced by this traverser.

For example, the tree

          h
        / | \
       /  e  \
      d       g
     /|\      |
    / | \     f
   a  b  c       

can be iterated over in preorder (hdabcegf), postorder (abcdefgh), or breadth-first order (hdegabcf).

Null nodes are strictly forbidden.

Author(s):
Louis Wasserman
Since:
15.0
 
 @GwtCompatible(emulated = true)
 public abstract class TreeTraverser<T> {
   // TODO(user): make this GWT-compatible when we've checked in ArrayDeque emulation
 
  
Returns the children of the specified node. Must not contain null.
 
   public abstract Iterable<T> children(T root);

  
Returns an unmodifiable iterable over the nodes in a tree structure, using pre-order traversal. That is, each node's subtrees are traversed after the node itself is returned.

No guarantees are made about the behavior of the traversal when nodes change while iteration is in progress or when the iterators generated by children(java.lang.Object) are advanced.

 
   public final FluentIterable<T> preOrderTraversal(final T root) {
     checkNotNull(root);
     return new FluentIterable<T>() {
       @Override
       public UnmodifiableIterator<T> iterator() {
         return preOrderIterator(root);
       }
     };
   }
 
   // overridden in BinaryTreeTraverser
     return new PreOrderIterator(root);
   }
 
   private final class PreOrderIterator extends UnmodifiableIterator<T> {
     private final Deque<Iterator<T>> stack;
 
     PreOrderIterator(T root) {
       this. = new ArrayDeque<Iterator<T>>();
       .addLast(Iterators.singletonIterator(checkNotNull(root)));
     }
 
     @Override
     public boolean hasNext() {
       return !.isEmpty();
     }
 
     @Override
     public T next() {
       Iterator<T> itr = .getLast(); // throws NSEE if empty
      T result = checkNotNull(itr.next());
      if (!itr.hasNext()) {
        .removeLast();
      }
      Iterator<T> childItr = children(result).iterator();
      if (childItr.hasNext()) {
        .addLast(childItr);
      }
      return result;
    }
  }

  
Returns an unmodifiable iterable over the nodes in a tree structure, using post-order traversal. That is, each node's subtrees are traversed before the node itself is returned.

No guarantees are made about the behavior of the traversal when nodes change while iteration is in progress or when the iterators generated by children(java.lang.Object) are advanced.

  public final FluentIterable<T> postOrderTraversal(final T root) {
    checkNotNull(root);
    return new FluentIterable<T>() {
      @Override
      public UnmodifiableIterator<T> iterator() {
        return postOrderIterator(root);
      }
    };
  }
  // overridden in BinaryTreeTraverser
    return new PostOrderIterator(root);
  }
  private static final class PostOrderNode<T> {
    final T root;
    final Iterator<T> childIterator;
    PostOrderNode(T rootIterator<T> childIterator) {
      this. = checkNotNull(root);
      this. = checkNotNull(childIterator);
    }
  }
  private final class PostOrderIterator extends AbstractIterator<T> {
    private final ArrayDeque<PostOrderNode<T>> stack;
    PostOrderIterator(T root) {
      this. = new ArrayDeque<PostOrderNode<T>>();
      .addLast(expand(root));
    }
    @Override
    protected T computeNext() {
      while (!.isEmpty()) {
        PostOrderNode<T> top = .getLast();
        if (top.childIterator.hasNext()) {
          T child = top.childIterator.next();
          .addLast(expand(child));
        } else {
          .removeLast();
          return top.root;
        }
      }
      return endOfData();
    }
    private PostOrderNode<T> expand(T t) {
      return new PostOrderNode<T>(tchildren(t).iterator());
    }
  }

  
Returns an unmodifiable iterable over the nodes in a tree structure, using breadth-first traversal. That is, all the nodes of depth 0 are returned, then depth 1, then 2, and so on.

No guarantees are made about the behavior of the traversal when nodes change while iteration is in progress or when the iterators generated by children(java.lang.Object) are advanced.

  public final FluentIterable<T> breadthFirstTraversal(final T root) {
    checkNotNull(root);
    return new FluentIterable<T>() {
      @Override
      public UnmodifiableIterator<T> iterator() {
        return new BreadthFirstIterator(root);
      }
    };
  }
  private final class BreadthFirstIterator extends UnmodifiableIterator<T>
      implements PeekingIterator<T> {
    private final Queue<T> queue;
    BreadthFirstIterator(T root) {
      this. = new ArrayDeque<T>();
      .add(root);
    }
    @Override
    public boolean hasNext() {
      return !.isEmpty();
    }
    @Override
    public T peek() {
      return .element();
    }
    @Override
    public T next() {
      T result = .remove();
      Iterables.addAll(children(result));
      return result;
    }
  }
New to GrepCode? Check out our FAQ X