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 org.checkerframework.checker.nullness.qual.Nullable;
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
078public abstract class TreeTraverser<T> {
079  /** Constructor for use by subclasses. */
080  public TreeTraverser() {}
081
082  /**
083   * Returns a tree traverser that uses the given function to navigate from a node to its children.
084   * This is useful if the function instance already exists, or so that you can supply a lambda
085   * expressions. If those circumstances don't apply, you probably don't need to use this; subclass
086   * {@code TreeTraverser} and implement its {@link #children} method directly.
087   *
088   * @since 20.0
089   * @deprecated Use {@link com.google.common.graph.Traverser#forTree} instead. If you are using a
090   *     lambda, these methods have exactly the same signature.
091   */
092  @Deprecated
093  public static <T> TreeTraverser<T> using(
094      final Function<T, ? extends Iterable<T>> nodeToChildrenFunction) {
095    checkNotNull(nodeToChildrenFunction);
096    return new TreeTraverser<T>() {
097      @Override
098      public Iterable<T> children(T root) {
099        return nodeToChildrenFunction.apply(root);
100      }
101    };
102  }
103
104  /** Returns the children of the specified node. Must not contain null. */
105  public abstract Iterable<T> children(T root);
106
107  /**
108   * Returns an unmodifiable iterable over the nodes in a tree structure, using pre-order traversal.
109   * That is, each node's subtrees are traversed after the node itself is returned.
110   *
111   * <p>No guarantees are made about the behavior of the traversal when nodes change while iteration
112   * is in progress or when the iterators generated by {@link #children} are advanced.
113   *
114   * @deprecated Use {@link com.google.common.graph.Traverser#depthFirstPreOrder} instead, which has
115   *     the same behavior.
116   */
117  @Deprecated
118  public final FluentIterable<T> preOrderTraversal(final T root) {
119    checkNotNull(root);
120    return new FluentIterable<T>() {
121      @Override
122      public UnmodifiableIterator<T> iterator() {
123        return preOrderIterator(root);
124      }
125    };
126  }
127
128  UnmodifiableIterator<T> preOrderIterator(T root) {
129    return new PreOrderIterator(root);
130  }
131
132  private final class PreOrderIterator extends UnmodifiableIterator<T> {
133    private final Deque<Iterator<T>> stack;
134
135    PreOrderIterator(T root) {
136      this.stack = new ArrayDeque<>();
137      stack.addLast(singletonIterator(checkNotNull(root)));
138    }
139
140    @Override
141    public boolean hasNext() {
142      return !stack.isEmpty();
143    }
144
145    @Override
146    public T next() {
147      Iterator<T> itr = stack.getLast(); // throws NSEE if empty
148      T result = checkNotNull(itr.next());
149      if (!itr.hasNext()) {
150        stack.removeLast();
151      }
152      Iterator<T> childItr = children(result).iterator();
153      if (childItr.hasNext()) {
154        stack.addLast(childItr);
155      }
156      return result;
157    }
158  }
159
160  /**
161   * Returns an unmodifiable iterable over the nodes in a tree structure, using post-order
162   * traversal. That is, each node's subtrees are traversed before the node itself is returned.
163   *
164   * <p>No guarantees are made about the behavior of the traversal when nodes change while iteration
165   * is in progress or when the iterators generated by {@link #children} are advanced.
166   *
167   * @deprecated Use {@link com.google.common.graph.Traverser#depthFirstPostOrder} instead, which
168   *     has the same behavior.
169   */
170  @Deprecated
171  public final FluentIterable<T> postOrderTraversal(final T root) {
172    checkNotNull(root);
173    return new FluentIterable<T>() {
174      @Override
175      public UnmodifiableIterator<T> iterator() {
176        return postOrderIterator(root);
177      }
178    };
179  }
180
181  UnmodifiableIterator<T> postOrderIterator(T root) {
182    return new PostOrderIterator(root);
183  }
184
185  private static final class PostOrderNode<T> {
186    final T root;
187    final Iterator<T> childIterator;
188
189    PostOrderNode(T root, Iterator<T> childIterator) {
190      this.root = checkNotNull(root);
191      this.childIterator = checkNotNull(childIterator);
192    }
193  }
194
195  private final class PostOrderIterator extends AbstractIterator<T> {
196    private final ArrayDeque<PostOrderNode<T>> stack;
197
198    PostOrderIterator(T root) {
199      this.stack = new ArrayDeque<>();
200      stack.addLast(expand(root));
201    }
202
203    @Override
204    protected @Nullable T computeNext() {
205      while (!stack.isEmpty()) {
206        PostOrderNode<T> top = stack.getLast();
207        if (top.childIterator.hasNext()) {
208          T child = top.childIterator.next();
209          stack.addLast(expand(child));
210        } else {
211          stack.removeLast();
212          return top.root;
213        }
214      }
215      return endOfData();
216    }
217
218    private PostOrderNode<T> expand(T t) {
219      return new PostOrderNode<>(t, children(t).iterator());
220    }
221  }
222
223  /**
224   * Returns an unmodifiable iterable over the nodes in a tree structure, using breadth-first
225   * traversal. That is, all the nodes of depth 0 are returned, then depth 1, then 2, and so on.
226   *
227   * <p>No guarantees are made about the behavior of the traversal when nodes change while iteration
228   * is in progress or when the iterators generated by {@link #children} are advanced.
229   *
230   * @deprecated Use {@link com.google.common.graph.Traverser#breadthFirst} instead, which has the
231   *     same behavior.
232   */
233  @Deprecated
234  public final FluentIterable<T> breadthFirstTraversal(final T root) {
235    checkNotNull(root);
236    return new FluentIterable<T>() {
237      @Override
238      public UnmodifiableIterator<T> iterator() {
239        return new BreadthFirstIterator(root);
240      }
241    };
242  }
243
244  private final class BreadthFirstIterator extends UnmodifiableIterator<T>
245      implements PeekingIterator<T> {
246    private final Queue<T> queue;
247
248    BreadthFirstIterator(T root) {
249      this.queue = new ArrayDeque<>();
250      queue.add(root);
251    }
252
253    @Override
254    public boolean hasNext() {
255      return !queue.isEmpty();
256    }
257
258    @Override
259    public T peek() {
260      return queue.element();
261    }
262
263    @Override
264    public T next() {
265      T result = queue.remove();
266      Iterables.addAll(queue, children(result));
267      return result;
268    }
269  }
270}