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><b>For Java 8 users:</b> Because this is an abstract class, not an interface, you can't use a 053 * lambda expression to extend 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>(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<T>(); 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}