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;
023
024import java.util.ArrayDeque;
025import java.util.Deque;
026import java.util.Iterator;
027import java.util.Queue;
028
029/**
030 * Views elements of a type {@code T} as nodes in a tree, and provides methods to traverse the trees
031 * induced by this traverser.
032 *
033 * <p>For example, the tree
034 *
035 * <pre>          {@code
036 *          h
037 *        / | \
038 *       /  e  \
039 *      d       g
040 *     /|\      |
041 *    / | \     f
042 *   a  b  c       }</pre>
043 *
044 * <p>can be iterated over in preorder (hdabcegf), postorder (abcdefgh), or breadth-first order
045 * (hdegabcf).
046 *
047 * <p>Null nodes are strictly forbidden.
048 *
049 * @author Louis Wasserman
050 * @since 15.0
051 */
052@Beta
053@GwtCompatible(emulated = true)
054public abstract class TreeTraverser<T> {
055  // TODO(lowasser): make this GWT-compatible when we've checked in ArrayDeque emulation
056
057  /**
058   * Returns the children of the specified node.  Must not contain null.
059   */
060  public abstract Iterable<T> children(T root);
061
062  /**
063   * Returns an unmodifiable iterable over the nodes in a tree structure, using pre-order
064   * traversal. That is, each node's subtrees are traversed after the node itself is returned.
065   *
066   * <p>No guarantees are made about the behavior of the traversal when nodes change while
067   * iteration is in progress or when the iterators generated by {@link #children} are advanced.
068   */
069  public final FluentIterable<T> preOrderTraversal(final T root) {
070    checkNotNull(root);
071    return new FluentIterable<T>() {
072      @Override
073      public UnmodifiableIterator<T> iterator() {
074        return preOrderIterator(root);
075      }
076    };
077  }
078
079  // overridden in BinaryTreeTraverser
080  UnmodifiableIterator<T> preOrderIterator(T root) {
081    return new PreOrderIterator(root);
082  }
083
084  private final class PreOrderIterator extends UnmodifiableIterator<T> {
085    private final Deque<Iterator<T>> stack;
086
087    PreOrderIterator(T root) {
088      this.stack = new ArrayDeque<Iterator<T>>();
089      stack.addLast(Iterators.singletonIterator(checkNotNull(root)));
090    }
091
092    @Override
093    public boolean hasNext() {
094      return !stack.isEmpty();
095    }
096
097    @Override
098    public T next() {
099      Iterator<T> itr = stack.getLast(); // throws NSEE if empty
100      T result = checkNotNull(itr.next());
101      if (!itr.hasNext()) {
102        stack.removeLast();
103      }
104      Iterator<T> childItr = children(result).iterator();
105      if (childItr.hasNext()) {
106        stack.addLast(childItr);
107      }
108      return result;
109    }
110  }
111
112  /**
113   * Returns an unmodifiable iterable over the nodes in a tree structure, using post-order
114   * traversal. That is, each node's subtrees are traversed before the node itself is returned.
115   *
116   * <p>No guarantees are made about the behavior of the traversal when nodes change while
117   * iteration is in progress or when the iterators generated by {@link #children} are advanced.
118   */
119  public final FluentIterable<T> postOrderTraversal(final T root) {
120    checkNotNull(root);
121    return new FluentIterable<T>() {
122      @Override
123      public UnmodifiableIterator<T> iterator() {
124        return postOrderIterator(root);
125      }
126    };
127  }
128
129  // overridden in BinaryTreeTraverser
130  UnmodifiableIterator<T> postOrderIterator(T root) {
131    return new PostOrderIterator(root);
132  }
133
134  private static final class PostOrderNode<T> {
135    final T root;
136    final Iterator<T> childIterator;
137
138    PostOrderNode(T root, Iterator<T> childIterator) {
139      this.root = checkNotNull(root);
140      this.childIterator = checkNotNull(childIterator);
141    }
142  }
143
144  private final class PostOrderIterator extends AbstractIterator<T> {
145    private final ArrayDeque<PostOrderNode<T>> stack;
146
147    PostOrderIterator(T root) {
148      this.stack = new ArrayDeque<PostOrderNode<T>>();
149      stack.addLast(expand(root));
150    }
151
152    @Override
153    protected T computeNext() {
154      while (!stack.isEmpty()) {
155        PostOrderNode<T> top = stack.getLast();
156        if (top.childIterator.hasNext()) {
157          T child = top.childIterator.next();
158          stack.addLast(expand(child));
159        } else {
160          stack.removeLast();
161          return top.root;
162        }
163      }
164      return endOfData();
165    }
166
167    private PostOrderNode<T> expand(T t) {
168      return new PostOrderNode<T>(t, children(t).iterator());
169    }
170  }
171
172  /**
173   * Returns an unmodifiable iterable over the nodes in a tree structure, using breadth-first
174   * traversal. That is, all the nodes of depth 0 are returned, then depth 1, then 2, and so on.
175   *
176   * <p>No guarantees are made about the behavior of the traversal when nodes change while
177   * iteration is in progress or when the iterators generated by {@link #children} are advanced.
178   */
179  public final FluentIterable<T> breadthFirstTraversal(final T root) {
180    checkNotNull(root);
181    return new FluentIterable<T>() {
182      @Override
183      public UnmodifiableIterator<T> iterator() {
184        return new BreadthFirstIterator(root);
185      }
186    };
187  }
188
189  private final class BreadthFirstIterator extends UnmodifiableIterator<T>
190      implements PeekingIterator<T> {
191    private final Queue<T> queue;
192
193    BreadthFirstIterator(T root) {
194      this.queue = new ArrayDeque<T>();
195      queue.add(root);
196    }
197
198    @Override
199    public boolean hasNext() {
200      return !queue.isEmpty();
201    }
202
203    @Override
204    public T peek() {
205      return queue.element();
206    }
207
208    @Override
209    public T next() {
210      T result = queue.remove();
211      Iterables.addAll(queue, children(result));
212      return result;
213    }
214  }
215}