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;
 
 
A variant of TreeTraverser for binary trees, providing additional traversals specific to binary trees.

Author(s):
Louis Wasserman
Since:
15.0
 
 @GwtCompatible(emulated = true)
 public abstract class BinaryTreeTraverser<T> extends TreeTraverser<T> {
   // TODO(user): make this GWT-compatible when we've checked in ArrayDeque and BitSet emulation
 
  
Returns the left child of the specified node, or com.google.common.base.Optional.absent() if the specified node has no left child.
 
   public abstract Optional<T> leftChild(T root);

  
Returns the right child of the specified node, or com.google.common.base.Optional.absent() if the specified node has no right child.
 
   public abstract Optional<T> rightChild(T root);

  
Returns the children of this node, in left-to-right order.
 
   @Override
   public final Iterable<T> children(final T root) {
     checkNotNull(root);
     return new FluentIterable<T>() {
       @Override
       public Iterator<T> iterator() {
         return new AbstractIterator<T>() {
           boolean doneLeft;
           boolean doneRight;
 
           @Override
           protected T computeNext() {
             if (!) {
                = true;
               Optional<T> left = leftChild(root);
               if (left.isPresent()) {
                 return left.get();
               }
             }
             if (!) {
                = true;
               Optional<T> right = rightChild(root);
               if (right.isPresent()) {
                 return right.get();
               }
             }
             return endOfData();
           }
         };
       }
     };
   }
 
   @Override
     return new PreOrderIterator(root);
   }
 
   /*
    * Optimized implementation of preOrderIterator for binary trees.
    */
   private final class PreOrderIterator extends UnmodifiableIterator<T>
       implements PeekingIterator<T> {
    private final Deque<T> stack;
    PreOrderIterator(T root) {
      this. = new ArrayDeque<T>();
      .addLast(root);
    }
    @Override
    public boolean hasNext() {
      return !.isEmpty();
    }
    @Override
    public T next() {
      T result = .removeLast();
      pushIfPresent(rightChild(result));
      pushIfPresent(leftChild(result));
      return result;
    }
    @Override
    public T peek() {
      return .getLast();
    }
  }
    return new PostOrderIterator(root);
  }
  /*
   * Optimized implementation of postOrderIterator for binary trees.
   */
  private final class PostOrderIterator extends UnmodifiableIterator<T> {
    private final Deque<T> stack;
    private final BitSet hasExpanded;
    PostOrderIterator(T root) {
      this. = new ArrayDeque<T>();
      .addLast(root);
      this. = new BitSet();
    }
    @Override
    public boolean hasNext() {
      return !.isEmpty();
    }
    @Override
    public T next() {
      while (true) {
        T node = .getLast();
        boolean expandedNode = .get(.size() - 1);
        if (expandedNode) {
          .removeLast();
          .clear(.size());
          return node;
        } else {
          .set(.size() - 1);
          pushIfPresent(rightChild(node));
          pushIfPresent(leftChild(node));
        }
      }
    }
  }
  // TODO(user): see if any significant optimizations are possible for breadthFirstIterator
  public final FluentIterable<T> inOrderTraversal(final T root) {
    checkNotNull(root);
    return new FluentIterable<T>() {
      @Override
      public UnmodifiableIterator<T> iterator() {
        return new InOrderIterator(root);
      }
    };
  }
  private final class InOrderIterator extends AbstractIterator<T> {
    private final Deque<T> stack;
    private final BitSet hasExpandedLeft;
    InOrderIterator(T root) {
      this. = new ArrayDeque<T>();
      this. = new BitSet();
      .addLast(root);
    }
    @Override
    protected T computeNext() {
      while (!.isEmpty()) {
        T node = .getLast();
        if (.get(.size() - 1)) {
          .removeLast();
          .clear(.size());
          pushIfPresent(rightChild(node));
          return node;
        } else {
          .set(.size() - 1);
          pushIfPresent(leftChild(node));
        }
      }
      return endOfData();
    }
  }
  private static <T> void pushIfPresent(Deque<T> stackOptional<T> node) {
    if (node.isPresent()) {
      stack.addLast(node.get());
    }
  }
New to GrepCode? Check out our FAQ X