1/*
2 * Copyright (C) 2012 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkNotNull;
20
21import com.google.common.base.Optional;
22
23import java.util.LinkedList;
24import java.util.Iterator;
25
26/**
27 * A variant of {@link TreeTraverser} for binary trees, providing additional traversals specific to
28 * binary trees.
29 *
30 * @author Louis Wasserman
31 */
32public abstract class BinaryTreeTraverser<T> extends TreeTraverser<T> {
33  // TODO(user): make this GWT-compatible when we've checked in ArrayDeque and BitSet emulation
34
35  /**
36   * Returns the left child of the specified node, or {@link Optional#absent()} if the specified
37   * node has no left child.
38   */
39  public abstract Optional<T> leftChild(T root);
40
41  /**
42   * Returns the right child of the specified node, or {@link Optional#absent()} if the specified
43   * node has no right child.
44   */
45  public abstract Optional<T> rightChild(T root);
46
47  /**
48   * Returns the children of this node, in left-to-right order.
49   */
50  @Override
51  public final Iterable<T> children(final T root) {
52    checkNotNull(root);
53    return new FluentIterable<T>() {
54      @Override
55      public Iterator<T> iterator() {
56        return new AbstractIterator<T>() {
57          boolean doneLeft;
58          boolean doneRight;
59
60          @Override
61          protected T computeNext() {
62            if (!doneLeft) {
63              doneLeft = true;
64              Optional<T> left = leftChild(root);
65              if (left.isPresent()) {
66                return left.get();
67              }
68            }
69            if (!doneRight) {
70              doneRight = true;
71              Optional<T> right = rightChild(root);
72              if (right.isPresent()) {
73                return right.get();
74              }
75            }
76            return endOfData();
77          }
78        };
79      }
80    };
81  }
82
83  // TODO(user): see if any significant optimizations are possible for breadthFirstIterator
84
85  public final FluentIterable<T> inOrderTraversal(final T root) {
86    checkNotNull(root);
87    return new FluentIterable<T>() {
88      @Override
89      public UnmodifiableIterator<T> iterator() {
90        return new InOrderIterator(root);
91      }
92    };
93  }
94
95  private static final class InOrderNode<T> {
96    final T node;
97    boolean hasExpandedLeft;
98
99    InOrderNode(T node) {
100      this.node = checkNotNull(node);
101      this.hasExpandedLeft = false;
102    }
103  }
104
105  private final class InOrderIterator extends AbstractIterator<T> {
106    private final LinkedList<InOrderNode<T>> stack;
107
108    InOrderIterator(T root) {
109      this.stack = Lists.newLinkedList();
110      stack.addLast(new InOrderNode<T>(root));
111    }
112
113    @Override
114    protected T computeNext() {
115      while (!stack.isEmpty()) {
116        InOrderNode<T> inOrderNode = stack.getLast();
117        if (inOrderNode.hasExpandedLeft) {
118          stack.removeLast();
119          pushIfPresent(rightChild(inOrderNode.node));
120          return inOrderNode.node;
121        } else {
122          inOrderNode.hasExpandedLeft = true;
123          pushIfPresent(leftChild(inOrderNode.node));
124        }
125      }
126      return endOfData();
127    }
128
129    private void pushIfPresent(Optional<T> node) {
130      if (node.isPresent()) {
131        stack.addLast(new InOrderNode<T>(node.get()));
132      }
133    }
134  }
135}
136