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