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