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 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkNotNull; 20 21import com.google.common.annotations.Beta; 22import com.google.common.annotations.GwtCompatible; 23 24import java.util.Iterator; 25import java.util.LinkedList; 26import java.util.Queue; 27 28/** 29 * Views elements of a type {@code T} as nodes in a tree, and provides methods to traverse the trees 30 * induced by this traverser. 31 * 32 * <p>For example, the tree 33 * 34 * <pre> {@code 35 * h 36 * / | \ 37 * / e \ 38 * d g 39 * /|\ | 40 * / | \ f 41 * a b c }</pre> 42 * 43 * <p>can be iterated over in preorder (hdabcegf), postorder (abcdefgh), or breadth-first order 44 * (hdegabcf). 45 * 46 * <p>Null nodes are strictly forbidden. 47 * 48 * @author Louis Wasserman 49 * @since 15.0 50 */ 51@Beta 52@GwtCompatible(emulated = true) 53public abstract class TreeTraverser<T> { 54 // TODO(user): make this GWT-compatible when we've checked in LinkedList emulation 55 56 /** 57 * Returns the children of the specified node. Must not contain null. 58 */ 59 public abstract Iterable<T> children(T root); 60 61 /** 62 * Returns an unmodifiable iterable over the nodes in a tree structure, using pre-order 63 * traversal. That is, each node's subtrees are traversed after the node itself is returned. 64 * 65 * <p>No guarantees are made about the behavior of the traversal when nodes change while 66 * iteration is in progress or when the iterators generated by {@link #children} are advanced. 67 */ 68 public final FluentIterable<T> preOrderTraversal(final T root) { 69 checkNotNull(root); 70 return new FluentIterable<T>() { 71 @Override 72 public UnmodifiableIterator<T> iterator() { 73 return preOrderIterator(root); 74 } 75 }; 76 } 77 78 // overridden in BinaryTreeTraverser 79 UnmodifiableIterator<T> preOrderIterator(T root) { 80 return new PreOrderIterator(root); 81 } 82 83 private final class PreOrderIterator extends UnmodifiableIterator<T> { 84 private final LinkedList<Iterator<T>> stack; 85 86 PreOrderIterator(T root) { 87 this.stack = new LinkedList<Iterator<T>>(); 88 stack.addLast(Iterators.singletonIterator(checkNotNull(root))); 89 } 90 91 @Override 92 public boolean hasNext() { 93 return !stack.isEmpty(); 94 } 95 96 @Override 97 public T next() { 98 Iterator<T> itr = stack.getLast(); // throws NSEE if empty 99 T result = checkNotNull(itr.next()); 100 if (!itr.hasNext()) { 101 stack.removeLast(); 102 } 103 Iterator<T> childItr = children(result).iterator(); 104 if (childItr.hasNext()) { 105 stack.addLast(childItr); 106 } 107 return result; 108 } 109 } 110 111 /** 112 * Returns an unmodifiable iterable over the nodes in a tree structure, using post-order 113 * traversal. That is, each node's subtrees are traversed before the node itself is returned. 114 * 115 * <p>No guarantees are made about the behavior of the traversal when nodes change while 116 * iteration is in progress or when the iterators generated by {@link #children} are advanced. 117 */ 118 public final FluentIterable<T> postOrderTraversal(final T root) { 119 checkNotNull(root); 120 return new FluentIterable<T>() { 121 @Override 122 public UnmodifiableIterator<T> iterator() { 123 return postOrderIterator(root); 124 } 125 }; 126 } 127 128 // overridden in BinaryTreeTraverser 129 UnmodifiableIterator<T> postOrderIterator(T root) { 130 return new PostOrderIterator(root); 131 } 132 133 private static final class PostOrderNode<T> { 134 final T root; 135 final Iterator<T> childIterator; 136 137 PostOrderNode(T root, Iterator<T> childIterator) { 138 this.root = checkNotNull(root); 139 this.childIterator = checkNotNull(childIterator); 140 } 141 } 142 143 private final class PostOrderIterator extends AbstractIterator<T> { 144 private final LinkedList<PostOrderNode<T>> stack; 145 146 PostOrderIterator(T root) { 147 this.stack = new LinkedList<PostOrderNode<T>>(); 148 stack.addLast(expand(root)); 149 } 150 151 @Override 152 protected T computeNext() { 153 while (!stack.isEmpty()) { 154 PostOrderNode<T> top = stack.getLast(); 155 if (top.childIterator.hasNext()) { 156 T child = top.childIterator.next(); 157 stack.addLast(expand(child)); 158 } else { 159 stack.removeLast(); 160 return top.root; 161 } 162 } 163 return endOfData(); 164 } 165 166 private PostOrderNode<T> expand(T t) { 167 return new PostOrderNode<T>(t, children(t).iterator()); 168 } 169 } 170 171 /** 172 * Returns an unmodifiable iterable over the nodes in a tree structure, using breadth-first 173 * traversal. That is, all the nodes of depth 0 are returned, then depth 1, then 2, and so on. 174 * 175 * <p>No guarantees are made about the behavior of the traversal when nodes change while 176 * iteration is in progress or when the iterators generated by {@link #children} are advanced. 177 */ 178 public final FluentIterable<T> breadthFirstTraversal(final T root) { 179 checkNotNull(root); 180 return new FluentIterable<T>() { 181 @Override 182 public UnmodifiableIterator<T> iterator() { 183 return new BreadthFirstIterator(root); 184 } 185 }; 186 } 187 188 private final class BreadthFirstIterator extends UnmodifiableIterator<T> 189 implements PeekingIterator<T> { 190 private final Queue<T> queue; 191 192 BreadthFirstIterator(T root) { 193 this.queue = new LinkedList<T>(); 194 queue.add(root); 195 } 196 197 @Override 198 public boolean hasNext() { 199 return !queue.isEmpty(); 200 } 201 202 @Override 203 public T peek() { 204 return queue.element(); 205 } 206 207 @Override 208 public T next() { 209 T result = queue.remove(); 210 Iterables.addAll(queue, children(result)); 211 return result; 212 } 213 } 214} 215