001/*
002 * Copyright (C) 2012 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020
021import com.google.common.annotations.Beta;
022import com.google.common.annotations.GwtCompatible;
023import com.google.common.base.Optional;
024import java.util.ArrayDeque;
025import java.util.BitSet;
026import java.util.Deque;
027import java.util.Iterator;
028
029/**
030 * A variant of {@link TreeTraverser} for binary trees, providing additional traversals specific to
031 * binary trees.
032 *
033 * @author Louis Wasserman
034 * @since 15.0
035 */
036@Beta
037@GwtCompatible
038public abstract class BinaryTreeTraverser<T> extends TreeTraverser<T> {
039
040  /**
041   * Returns the left child of the specified node, or {@link Optional#absent()} if the specified
042   * node has no left child.
043   */
044  public abstract Optional<T> leftChild(T root);
045
046  /**
047   * Returns the right child of the specified node, or {@link Optional#absent()} if the specified
048   * node has no right child.
049   */
050  public abstract Optional<T> rightChild(T root);
051
052  /**
053   * Returns the children of this node, in left-to-right order.
054   */
055  @Override
056  public final Iterable<T> children(final T root) {
057    checkNotNull(root);
058    return new FluentIterable<T>() {
059      @Override
060      public Iterator<T> iterator() {
061        return new AbstractIterator<T>() {
062          boolean doneLeft;
063          boolean doneRight;
064
065          @Override
066          protected T computeNext() {
067            if (!doneLeft) {
068              doneLeft = true;
069              Optional<T> left = leftChild(root);
070              if (left.isPresent()) {
071                return left.get();
072              }
073            }
074            if (!doneRight) {
075              doneRight = true;
076              Optional<T> right = rightChild(root);
077              if (right.isPresent()) {
078                return right.get();
079              }
080            }
081            return endOfData();
082          }
083        };
084      }
085    };
086  }
087
088  @Override
089  UnmodifiableIterator<T> preOrderIterator(T root) {
090    return new PreOrderIterator(root);
091  }
092
093  /*
094   * Optimized implementation of preOrderIterator for binary trees.
095   */
096  private final class PreOrderIterator extends UnmodifiableIterator<T>
097      implements PeekingIterator<T> {
098    private final Deque<T> stack;
099
100    PreOrderIterator(T root) {
101      this.stack = new ArrayDeque<T>(8);
102      stack.addLast(root);
103    }
104
105    @Override
106    public boolean hasNext() {
107      return !stack.isEmpty();
108    }
109
110    @Override
111    public T next() {
112      T result = stack.removeLast();
113      pushIfPresent(stack, rightChild(result));
114      pushIfPresent(stack, leftChild(result));
115      return result;
116    }
117
118    @Override
119    public T peek() {
120      return stack.getLast();
121    }
122  }
123
124  @Override
125  UnmodifiableIterator<T> postOrderIterator(T root) {
126    return new PostOrderIterator(root);
127  }
128
129  /*
130   * Optimized implementation of postOrderIterator for binary trees.
131   */
132  private final class PostOrderIterator extends UnmodifiableIterator<T> {
133    private final Deque<T> stack;
134    private final BitSet hasExpanded;
135
136    PostOrderIterator(T root) {
137      this.stack = new ArrayDeque<T>(8);
138      stack.addLast(root);
139      this.hasExpanded = new BitSet();
140    }
141
142    @Override
143    public boolean hasNext() {
144      return !stack.isEmpty();
145    }
146
147    @Override
148    public T next() {
149      while (true) {
150        T node = stack.getLast();
151        boolean expandedNode = hasExpanded.get(stack.size() - 1);
152        if (expandedNode) {
153          stack.removeLast();
154          hasExpanded.clear(stack.size());
155          return node;
156        } else {
157          hasExpanded.set(stack.size() - 1);
158          pushIfPresent(stack, rightChild(node));
159          pushIfPresent(stack, leftChild(node));
160        }
161      }
162    }
163  }
164
165  // TODO(lowasser): see if any significant optimizations are possible for breadthFirstIterator
166
167  public final FluentIterable<T> inOrderTraversal(final T root) {
168    checkNotNull(root);
169    return new FluentIterable<T>() {
170      @Override
171      public UnmodifiableIterator<T> iterator() {
172        return new InOrderIterator(root);
173      }
174    };
175  }
176
177  private final class InOrderIterator extends AbstractIterator<T> {
178    private final Deque<T> stack;
179    private final BitSet hasExpandedLeft;
180
181    InOrderIterator(T root) {
182      this.stack = new ArrayDeque<T>(8);
183      this.hasExpandedLeft = new BitSet();
184      stack.addLast(root);
185    }
186
187    @Override
188    protected T computeNext() {
189      while (!stack.isEmpty()) {
190        T node = stack.getLast();
191        if (hasExpandedLeft.get(stack.size() - 1)) {
192          stack.removeLast();
193          hasExpandedLeft.clear(stack.size());
194          pushIfPresent(stack, rightChild(node));
195          return node;
196        } else {
197          hasExpandedLeft.set(stack.size() - 1);
198          pushIfPresent(stack, leftChild(node));
199        }
200      }
201      return endOfData();
202    }
203  }
204
205  private static <T> void pushIfPresent(Deque<T> stack, Optional<T> node) {
206    if (node.isPresent()) {
207      stack.addLast(node.get());
208    }
209  }
210}