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