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 January 2019. 072 */ 073// TODO(b/68134636): Remove by 2019-01 074@Deprecated 075@Beta 076@GwtCompatible 077public abstract class TreeTraverser<T> { 078 079 /** 080 * Returns a tree traverser that uses the given function to navigate from a node to its children. 081 * This is useful if the function instance already exists, or so that you can supply a lambda 082 * expressions. If those circumstances don't apply, you probably don't need to use this; subclass 083 * {@code TreeTraverser} and implement its {@link #children} method directly. 084 * 085 * @since 20.0 086 * @deprecated Use {@link com.google.common.graph.Traverser#forTree} instead. If you are using a 087 * lambda, these methods have exactly the same signature. 088 */ 089 @Deprecated 090 public static <T> TreeTraverser<T> using( 091 final Function<T, ? extends Iterable<T>> nodeToChildrenFunction) { 092 checkNotNull(nodeToChildrenFunction); 093 return new TreeTraverser<T>() { 094 @Override 095 public Iterable<T> children(T root) { 096 return nodeToChildrenFunction.apply(root); 097 } 098 }; 099 } 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}