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;
020import static com.google.common.collect.Iterators.singletonIterator;
021
022import com.google.common.annotations.Beta;
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.base.Function;
025import java.util.ArrayDeque;
026import java.util.Deque;
027import java.util.Iterator;
028import java.util.Queue;
029import java.util.function.Consumer;
030import javax.annotation.CheckForNull;
031
032/**
033 * Views elements of a type {@code T} as nodes in a tree, and provides methods to traverse the trees
034 * induced by this traverser.
035 *
036 * <p>For example, the tree
037 *
038 * <pre>{@code
039 *        h
040 *      / | \
041 *     /  e  \
042 *    d       g
043 *   /|\      |
044 *  / | \     f
045 * a  b  c
046 * }</pre>
047 *
048 * <p>can be iterated over in preorder (hdabcegf), postorder (abcdefgh), or breadth-first order
049 * (hdegabcf).
050 *
051 * <p>Null nodes are strictly forbidden.
052 *
053 * <p>Because this is an abstract class, not an interface, you can't use a lambda expression to
054 * implement it:
055 *
056 * <pre>{@code
057 * // won't work
058 * TreeTraverser<NodeType> traverser = node -> node.getChildNodes();
059 * }</pre>
060 *
061 * Instead, you can pass a lambda expression to the {@code using} factory method:
062 *
063 * <pre>{@code
064 * TreeTraverser<NodeType> traverser = TreeTraverser.using(node -> node.getChildNodes());
065 * }</pre>
066 *
067 * @author Louis Wasserman
068 * @since 15.0
069 * @deprecated Use {@link com.google.common.graph.Traverser} instead. All instance methods have
070 *     their equivalent on the result of {@code Traverser.forTree(tree)} where {@code tree}
071 *     implements {@code SuccessorsFunction}, which has a similar API as {@link #children} or can be
072 *     the same lambda function as passed into {@link #using(Function)}.
073 *     <p>This class is scheduled to be removed in October 2019.
074 */
075// TODO(b/68134636): Remove by 2019-10
076@Deprecated
077@Beta
078@GwtCompatible
079@ElementTypesAreNonnullByDefault
080public abstract class TreeTraverser<T> {
081  /** Constructor for use by subclasses. */
082  public TreeTraverser() {}
083
084  /**
085   * Returns a tree traverser that uses the given function to navigate from a node to its children.
086   * This is useful if the function instance already exists, or so that you can supply a lambda
087   * expressions. If those circumstances don't apply, you probably don't need to use this; subclass
088   * {@code TreeTraverser} and implement its {@link #children} method directly.
089   *
090   * @since 20.0
091   * @deprecated Use {@link com.google.common.graph.Traverser#forTree} instead. If you are using a
092   *     lambda, these methods have exactly the same signature.
093   */
094  @Deprecated
095  public static <T> TreeTraverser<T> using(
096      final Function<T, ? extends Iterable<T>> nodeToChildrenFunction) {
097    checkNotNull(nodeToChildrenFunction);
098    return new TreeTraverser<T>() {
099      @Override
100      public Iterable<T> children(T root) {
101        return nodeToChildrenFunction.apply(root);
102      }
103    };
104  }
105
106  /** Returns the children of the specified node. Must not contain null. */
107  public abstract Iterable<T> children(T root);
108
109  /**
110   * Returns an unmodifiable iterable over the nodes in a tree structure, using pre-order traversal.
111   * That is, each node's subtrees are traversed after the node itself is returned.
112   *
113   * <p>No guarantees are made about the behavior of the traversal when nodes change while iteration
114   * is in progress or when the iterators generated by {@link #children} are advanced.
115   *
116   * @deprecated Use {@link com.google.common.graph.Traverser#depthFirstPreOrder} instead, which has
117   *     the same behavior.
118   */
119  @Deprecated
120  public final FluentIterable<T> preOrderTraversal(final T root) {
121    checkNotNull(root);
122    return new FluentIterable<T>() {
123      @Override
124      public UnmodifiableIterator<T> iterator() {
125        return preOrderIterator(root);
126      }
127
128      @Override
129      public void forEach(Consumer<? super T> action) {
130        checkNotNull(action);
131        new Consumer<T>() {
132          @Override
133          public void accept(T t) {
134            action.accept(t);
135            children(t).forEach(this);
136          }
137        }.accept(root);
138      }
139    };
140  }
141
142  UnmodifiableIterator<T> preOrderIterator(T root) {
143    return new PreOrderIterator(root);
144  }
145
146  private final class PreOrderIterator extends UnmodifiableIterator<T> {
147    private final Deque<Iterator<T>> stack;
148
149    PreOrderIterator(T root) {
150      this.stack = new ArrayDeque<>();
151      stack.addLast(singletonIterator(checkNotNull(root)));
152    }
153
154    @Override
155    public boolean hasNext() {
156      return !stack.isEmpty();
157    }
158
159    @Override
160    public T next() {
161      Iterator<T> itr = stack.getLast(); // throws NSEE if empty
162      T result = checkNotNull(itr.next());
163      if (!itr.hasNext()) {
164        stack.removeLast();
165      }
166      Iterator<T> childItr = children(result).iterator();
167      if (childItr.hasNext()) {
168        stack.addLast(childItr);
169      }
170      return result;
171    }
172  }
173
174  /**
175   * Returns an unmodifiable iterable over the nodes in a tree structure, using post-order
176   * traversal. That is, each node's subtrees are traversed before the node itself is returned.
177   *
178   * <p>No guarantees are made about the behavior of the traversal when nodes change while iteration
179   * is in progress or when the iterators generated by {@link #children} are advanced.
180   *
181   * @deprecated Use {@link com.google.common.graph.Traverser#depthFirstPostOrder} instead, which
182   *     has the same behavior.
183   */
184  @Deprecated
185  public final FluentIterable<T> postOrderTraversal(final T root) {
186    checkNotNull(root);
187    return new FluentIterable<T>() {
188      @Override
189      public UnmodifiableIterator<T> iterator() {
190        return postOrderIterator(root);
191      }
192
193      @Override
194      public void forEach(Consumer<? super T> action) {
195        checkNotNull(action);
196        new Consumer<T>() {
197          @Override
198          public void accept(T t) {
199            children(t).forEach(this);
200            action.accept(t);
201          }
202        }.accept(root);
203      }
204    };
205  }
206
207  UnmodifiableIterator<T> postOrderIterator(T root) {
208    return new PostOrderIterator(root);
209  }
210
211  private static final class PostOrderNode<T> {
212    final T root;
213    final Iterator<T> childIterator;
214
215    PostOrderNode(T root, Iterator<T> childIterator) {
216      this.root = checkNotNull(root);
217      this.childIterator = checkNotNull(childIterator);
218    }
219  }
220
221  private final class PostOrderIterator extends AbstractIterator<T> {
222    private final ArrayDeque<PostOrderNode<T>> stack;
223
224    PostOrderIterator(T root) {
225      this.stack = new ArrayDeque<>();
226      stack.addLast(expand(root));
227    }
228
229    @Override
230    @CheckForNull
231    protected T computeNext() {
232      while (!stack.isEmpty()) {
233        PostOrderNode<T> top = stack.getLast();
234        if (top.childIterator.hasNext()) {
235          T child = top.childIterator.next();
236          stack.addLast(expand(child));
237        } else {
238          stack.removeLast();
239          return top.root;
240        }
241      }
242      return endOfData();
243    }
244
245    private PostOrderNode<T> expand(T t) {
246      return new PostOrderNode<>(t, children(t).iterator());
247    }
248  }
249
250  /**
251   * Returns an unmodifiable iterable over the nodes in a tree structure, using breadth-first
252   * traversal. That is, all the nodes of depth 0 are returned, then depth 1, then 2, and so on.
253   *
254   * <p>No guarantees are made about the behavior of the traversal when nodes change while iteration
255   * is in progress or when the iterators generated by {@link #children} are advanced.
256   *
257   * @deprecated Use {@link com.google.common.graph.Traverser#breadthFirst} instead, which has the
258   *     same behavior.
259   */
260  @Deprecated
261  public final FluentIterable<T> breadthFirstTraversal(final T root) {
262    checkNotNull(root);
263    return new FluentIterable<T>() {
264      @Override
265      public UnmodifiableIterator<T> iterator() {
266        return new BreadthFirstIterator(root);
267      }
268    };
269  }
270
271  private final class BreadthFirstIterator extends UnmodifiableIterator<T>
272      implements PeekingIterator<T> {
273    private final Queue<T> queue;
274
275    BreadthFirstIterator(T root) {
276      this.queue = new ArrayDeque<>();
277      queue.add(root);
278    }
279
280    @Override
281    public boolean hasNext() {
282      return !queue.isEmpty();
283    }
284
285    @Override
286    public T peek() {
287      return queue.element();
288    }
289
290    @Override
291    public T next() {
292      T result = queue.remove();
293      Iterables.addAll(queue, children(result));
294      return result;
295    }
296  }
297}