1 /*
2 * Copyright (C) 2012 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20
21 import com.google.common.annotations.Beta;
22 import com.google.common.annotations.GwtCompatible;
23 import com.google.common.base.Function;
24 import java.util.ArrayDeque;
25 import java.util.Deque;
26 import java.util.Iterator;
27 import java.util.Queue;
28 import java.util.function.Consumer;
29
30 /**
31 * Views elements of a type {@code T} as nodes in a tree, and provides methods to traverse the trees
32 * induced by this traverser.
33 *
34 * <p>For example, the tree
35 *
36 * <pre>{@code
37 * h
38 * / | \
39 * / e \
40 * d g
41 * /|\ |
42 * / | \ f
43 * a b c
44 * }</pre>
45 *
46 * <p>can be iterated over in preorder (hdabcegf), postorder (abcdefgh), or breadth-first order
47 * (hdegabcf).
48 *
49 * <p>Null nodes are strictly forbidden.
50 *
51 * <p><b>For Java 8 users:</b> Because this is an abstract class, not an interface, you can't use a
52 * lambda expression to extend it:
53 *
54 * <pre>{@code
55 * // won't work
56 * TreeTraverser<NodeType> traverser = node -> node.getChildNodes();
57 * }</pre>
58 *
59 * Instead, you can pass a lambda expression to the {@code using} factory method:
60 *
61 * <pre>{@code
62 * TreeTraverser<NodeType> traverser = TreeTraverser.using(node -> node.getChildNodes());
63 * }</pre>
64 *
65 * @author Louis Wasserman
66 * @since 15.0
67 * @deprecated Use {@link com.google.common.graph.Traverser} instead. All instance methods have
68 * their equivalent on the result of {@code Traverser.forTree(tree)} where {@code tree}
69 * implements {@code SuccessorsFunction}, which has a similar API as {@link #children} or can be
70 * the same lambda function as passed into {@link #using(Function)}.
71 * <p>This class is scheduled to be removed in October 2019.
72 */
73 // TODO(b/68134636): Remove by 2019-10
74 @Deprecated
75 @Beta
76 @GwtCompatible
77 public abstract class TreeTraverser<T> {
78
79 /**
80 * Returns a tree traverser that uses the given function to navigate from a node to its children.
81 * This is useful if the function instance already exists, or so that you can supply a lambda
82 * expressions. If those circumstances don't apply, you probably don't need to use this; subclass
83 * {@code TreeTraverser} and implement its {@link #children} method directly.
84 *
85 * @since 20.0
86 * @deprecated Use {@link com.google.common.graph.Traverser#forTree} instead. If you are using a
87 * lambda, these methods have exactly the same signature.
88 */
89 @Deprecated
90 public static <T> TreeTraverser<T> using(
91 final Function<T, ? extends Iterable<T>> nodeToChildrenFunction) {
92 checkNotNull(nodeToChildrenFunction);
93 return new TreeTraverser<T>() {
94 @Override
95 public Iterable<T> children(T root) {
96 return nodeToChildrenFunction.apply(root);
97 }
98 };
99 }
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 }