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