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