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;
024
025import java.util.ArrayDeque;
026import java.util.BitSet;
027import java.util.Deque;
028import java.util.Iterator;
029
030/**
031 * A variant of {@link TreeTraverser} for binary trees, providing additional traversals specific to
032 * binary trees.
033 *
034 * @author Louis Wasserman
035 * @since 15.0
036 */
037@Beta
038@GwtCompatible(emulated = true)
039public abstract class BinaryTreeTraverser<T> extends TreeTraverser<T> {
040  // TODO(lowasser): make this GWT-compatible when we've checked in ArrayDeque and BitSet emulation
041
042  /**
043   * Returns the left child of the specified node, or {@link Optional#absent()} if the specified
044   * node has no left child.
045   */
046  public abstract Optional<T> leftChild(T root);
047
048  /**
049   * Returns the right child of the specified node, or {@link Optional#absent()} if the specified
050   * node has no right child.
051   */
052  public abstract Optional<T> rightChild(T root);
053
054  /**
055   * Returns the children of this node, in left-to-right order.
056   */
057  @Override
058  public final Iterable<T> children(final T root) {
059    checkNotNull(root);
060    return new FluentIterable<T>() {
061      @Override
062      public Iterator<T> iterator() {
063        return new AbstractIterator<T>() {
064          boolean doneLeft;
065          boolean doneRight;
066
067          @Override
068          protected T computeNext() {
069            if (!doneLeft) {
070              doneLeft = true;
071              Optional<T> left = leftChild(root);
072              if (left.isPresent()) {
073                return left.get();
074              }
075            }
076            if (!doneRight) {
077              doneRight = true;
078              Optional<T> right = rightChild(root);
079              if (right.isPresent()) {
080                return right.get();
081              }
082            }
083            return endOfData();
084          }
085        };
086      }
087    };
088  }
089
090  @Override
091  UnmodifiableIterator<T> preOrderIterator(T root) {
092    return new PreOrderIterator(root);
093  }
094
095  /*
096   * Optimized implementation of preOrderIterator for binary trees.
097   */
098  private final class PreOrderIterator extends UnmodifiableIterator<T>
099      implements PeekingIterator<T> {
100    private final Deque<T> stack;
101
102    PreOrderIterator(T root) {
103      this.stack = new ArrayDeque<T>();
104      stack.addLast(root);
105    }
106
107    @Override
108    public boolean hasNext() {
109      return !stack.isEmpty();
110    }
111
112    @Override
113    public T next() {
114      T result = stack.removeLast();
115      pushIfPresent(stack, rightChild(result));
116      pushIfPresent(stack, leftChild(result));
117      return result;
118    }
119
120    @Override
121    public T peek() {
122      return stack.getLast();
123    }
124  }
125
126  @Override
127  UnmodifiableIterator<T> postOrderIterator(T root) {
128    return new PostOrderIterator(root);
129  }
130
131  /*
132   * Optimized implementation of postOrderIterator for binary trees.
133   */
134  private final class PostOrderIterator extends UnmodifiableIterator<T> {
135    private final Deque<T> stack;
136    private final BitSet hasExpanded;
137
138    PostOrderIterator(T root) {
139      this.stack = new ArrayDeque<T>();
140      stack.addLast(root);
141      this.hasExpanded = new BitSet();
142    }
143
144    @Override
145    public boolean hasNext() {
146      return !stack.isEmpty();
147    }
148
149    @Override
150    public T next() {
151      while (true) {
152        T node = stack.getLast();
153        boolean expandedNode = hasExpanded.get(stack.size() - 1);
154        if (expandedNode) {
155          stack.removeLast();
156          hasExpanded.clear(stack.size());
157          return node;
158        } else {
159          hasExpanded.set(stack.size() - 1);
160          pushIfPresent(stack, rightChild(node));
161          pushIfPresent(stack, leftChild(node));
162        }
163      }
164    }
165  }
166
167  // TODO(lowasser): see if any significant optimizations are possible for breadthFirstIterator
168
169  public final FluentIterable<T> inOrderTraversal(final T root) {
170    checkNotNull(root);
171    return new FluentIterable<T>() {
172      @Override
173      public UnmodifiableIterator<T> iterator() {
174        return new InOrderIterator(root);
175      }
176    };
177  }
178
179  private final class InOrderIterator extends AbstractIterator<T> {
180    private final Deque<T> stack;
181    private final BitSet hasExpandedLeft;
182
183    InOrderIterator(T root) {
184      this.stack = new ArrayDeque<T>();
185      this.hasExpandedLeft = new BitSet();
186      stack.addLast(root);
187    }
188
189    @Override
190    protected T computeNext() {
191      while (!stack.isEmpty()) {
192        T node = stack.getLast();
193        if (hasExpandedLeft.get(stack.size() - 1)) {
194          stack.removeLast();
195          hasExpandedLeft.clear(stack.size());
196          pushIfPresent(stack, rightChild(node));
197          return node;
198        } else {
199          hasExpandedLeft.set(stack.size() - 1);
200          pushIfPresent(stack, leftChild(node));
201        }
202      }
203      return endOfData();
204    }
205  }
206
207  private static <T> void pushIfPresent(Deque<T> stack, Optional<T> node) {
208    if (node.isPresent()) {
209      stack.addLast(node.get());
210    }
211  }
212}