Deprecated

Use com.google.common.graph.Traverser instead. All instance methods have their equivalent on the result of Traverser.forTree(tree) where tree implements SuccessorsFunction, which has a similar API as children or can be the same lambda function as passed into using(Function).

This class is scheduled to be removed in October 2019.

Views elements of a type T as nodes in a tree, and provides methods to traverse the trees induced by this traverser.

For example, the tree

h
     / | \
    /  e  \
   d       g
  /|\      |
 / | \     f
a  b  c

can be iterated over in preorder (hdabcegf), postorder (abcdefgh), or breadth-first order (hdegabcf).

Null nodes are strictly forbidden.

For Java 8 users: Because this is an abstract class, not an interface, you can't use a lambda expression to extend it:

// won't work
TreeTraverser<NodeType> traverser = node -> node.getChildNodes();

Instead, you can pass a lambda expression to the using factory method:

TreeTraverser<NodeType> traverser = TreeTraverser.using(node -> node.getChildNodes());

Nested and Inner Type Summary

Modifier and Type	Class and Description
private class	TreeTraverser.BreadthFirstIterator
private class	TreeTraverser.PostOrderIterator
private static class	TreeTraverser.PostOrderNode<T>
private class	TreeTraverser.PreOrderIterator

Access	Constructor and Description
public	TreeTraverser()

Method Summary

Modifier and Type	Method and Description
public final FluentIterable<T>	breadthFirstTraversal(final T root) Deprecated Use `com.google.common.graph.Traverser#breadthFirst` instead, which has the same behavior. Returns an unmodifiable iterable over the nodes in a tree structure, using breadth-first traversal.
public abstract Iterable<T>	children(T root) Returns the children of the specified node.
pack-priv UnmodifiableIterator<T>	postOrderIterator(T root)
public final FluentIterable<T>	postOrderTraversal(final T root) Deprecated Use `com.google.common.graph.Traverser#depthFirstPostOrder` instead, which has the same behavior. Returns an unmodifiable iterable over the nodes in a tree structure, using post-order traversal.
pack-priv UnmodifiableIterator<T>	preOrderIterator(T root)
public final FluentIterable<T>	preOrderTraversal(final T root) Deprecated Use `com.google.common.graph.Traverser#depthFirstPreOrder` instead, which has the same behavior. Returns an unmodifiable iterable over the nodes in a tree structure, using pre-order traversal.
public static <T> TreeTraverser<T>	using(final Function<T, ? extends Iterable<T>> nodeToChildrenFunction) Deprecated Use `com.google.common.graph.Traverser#forTree` instead. Returns a tree traverser that uses the given function to navigate from a node to its children.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

TreeTraverser	back to summary
public TreeTraverser()

Method Detail

breadthFirstTraversal back to summary

breadthFirstTraversal	back to summary
public final FluentIterable<T> breadthFirstTraversal(final T root) Deprecated Use `com.google.common.graph.Traverser#breadthFirst` instead, which has the same behavior. Returns an unmodifiable iterable over the nodes in a tree structure, using breadth-first traversal. That is, all the nodes of depth 0 are returned, then depth 1, then 2, and so on. No guarantees are made about the behavior of the traversal when nodes change while iteration is in progress or when the iterators generated by `children` are advanced. Annotations @Deprecated

public final FluentIterable<T> breadthFirstTraversal(final T root)

Deprecated

Use com.google.common.graph.Traverser#breadthFirst instead, which has the same behavior.

Returns an unmodifiable iterable over the nodes in a tree structure, using breadth-first traversal. That is, all the nodes of depth 0 are returned, then depth 1, then 2, and so on.

No guarantees are made about the behavior of the traversal when nodes change while iteration is in progress or when the iterators generated by children are advanced.

Annotations

@Deprecated

children	back to summary
public abstract Iterable<T> children(T root) Returns the children of the specified node. Must not contain null.

postOrderIterator	back to summary
pack-priv UnmodifiableIterator<T> postOrderIterator(T root)

postOrderTraversal back to summary

postOrderTraversal	back to summary
public final FluentIterable<T> postOrderTraversal(final T root) Deprecated Use `com.google.common.graph.Traverser#depthFirstPostOrder` instead, which has the same behavior. Returns an unmodifiable iterable over the nodes in a tree structure, using post-order traversal. That is, each node's subtrees are traversed before the node itself is returned. No guarantees are made about the behavior of the traversal when nodes change while iteration is in progress or when the iterators generated by `children` are advanced. Annotations @Deprecated

public final FluentIterable<T> postOrderTraversal(final T root)

Deprecated

Use com.google.common.graph.Traverser#depthFirstPostOrder instead, which has the same behavior.

Returns an unmodifiable iterable over the nodes in a tree structure, using post-order traversal. That is, each node's subtrees are traversed before the node itself is returned.

No guarantees are made about the behavior of the traversal when nodes change while iteration is in progress or when the iterators generated by children are advanced.

Annotations

@Deprecated

preOrderIterator	back to summary
pack-priv UnmodifiableIterator<T> preOrderIterator(T root)

preOrderTraversal back to summary

preOrderTraversal	back to summary
public final FluentIterable<T> preOrderTraversal(final T root) Deprecated Use `com.google.common.graph.Traverser#depthFirstPreOrder` instead, which has the same behavior. Returns an unmodifiable iterable over the nodes in a tree structure, using pre-order traversal. That is, each node's subtrees are traversed after the node itself is returned. No guarantees are made about the behavior of the traversal when nodes change while iteration is in progress or when the iterators generated by `children` are advanced. Annotations @Deprecated

public final FluentIterable<T> preOrderTraversal(final T root)

Deprecated

Use com.google.common.graph.Traverser#depthFirstPreOrder instead, which has the same behavior.

Returns an unmodifiable iterable over the nodes in a tree structure, using pre-order traversal. That is, each node's subtrees are traversed after the node itself is returned.

No guarantees are made about the behavior of the traversal when nodes change while iteration is in progress or when the iterators generated by children are advanced.

Annotations

@Deprecated

using back to summary

using	back to summary
public static <T> TreeTraverser<T> using(final Function<T, ? extends Iterable<T>> nodeToChildrenFunction) Deprecated Use `com.google.common.graph.Traverser#forTree` instead. If you are using a lambda, these methods have exactly the same signature. Returns a tree traverser that uses the given function to navigate from a node to its children. This is useful if the function instance already exists, or so that you can supply a lambda expressions. If those circumstances don't apply, you probably don't need to use this; subclass `TreeTraverser` and implement its `children` method directly. Annotations @Deprecated Since 20.0

public static <T> TreeTraverser<T> using(final Function<T, ? extends Iterable<T>> nodeToChildrenFunction)

Deprecated

Use com.google.common.graph.Traverser#forTree instead. If you are using a lambda, these methods have exactly the same signature.

Returns a tree traverser that uses the given function to navigate from a node to its children. This is useful if the function instance already exists, or so that you can supply a lambda expressions. If those circumstances don't apply, you probably don't need to use this; subclass TreeTraverser and implement its children method directly.

Annotations

@Deprecated

Since

20.0

com.google.common.collect back to summary

private final Class TreeTraverser.BreadthFirstIterator

Class Inheritance

extends UnmodifiableIterator<T>
implements PeekingIterator<T>

java.lang.Object
com.google.common.collect.UnmodifiableIterator
com.google.common.collect.TreeTraverser.BreadthFirstIterator

All Implemented Interfaces

com.google.common.collect.PeekingIterator, java.util.Iterator

Field Summary

Modifier and Type	Field and Description
private final Queue<T>	queue

Constructor Summary

Access	Constructor and Description
pack-priv	BreadthFirstIterator(T root)

Method Summary

Modifier and Type	Method and Description
public boolean	hasNext() Implements java.util.Iterator.hasNext. Returns `true` if the iteration has more elements.
public T	next() Implements com.google.common.collect.PeekingIterator.next, java.util.Iterator.next. Returns the next element in the iteration.
public T	peek() Implements com.google.common.collect.PeekingIterator.peek. Returns the next element in the iteration, without advancing the iteration.

Inherited from com.google.common.collect.UnmodifiableIterator:: remove

Field Detail

queue	back to summary
private final Queue<T> queue

Constructor Detail

BreadthFirstIterator	back to summary
pack-priv BreadthFirstIterator(T root)

Method Detail

hasNext back to summary

hasNext	back to summary
public boolean hasNext() Implements java.util.Iterator.hasNext. Doc from java.util.Iterator.hasNext. Returns `true` if the iteration has more elements. (In other words, returns `true` if `next` would return an element rather than throwing an exception.) Returns:boolean `true` if the iteration has more elements Annotations @Override

public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

Returns:boolean

true if the iteration has more elements

Annotations

@Override

next back to summary

next	back to summary
public T next() Implements com.google.common.collect.PeekingIterator.next, java.util.Iterator.next. Doc from com.google.common.collect.PeekingIterator.next. Returns the next element in the iteration. The objects returned by consecutive calls to `peek()` then `next()` are guaranteed to be equal to each other. Returns:T Doc from java.util.Iterator.next. the next element in the iteration Annotations @Override

public T next()

Implements com.google.common.collect.PeekingIterator.next, java.util.Iterator.next.

Doc from com.google.common.collect.PeekingIterator.next.

Returns the next element in the iteration.

The objects returned by consecutive calls to peek() then next() are guaranteed to be equal to each other.

Returns:T

Doc from java.util.Iterator.next.

the next element in the iteration

Annotations

@Override

peek back to summary

peek	back to summary
public T peek() Implements com.google.common.collect.PeekingIterator.peek. Doc from com.google.common.collect.PeekingIterator.peek. Returns the next element in the iteration, without advancing the iteration. Calls to `peek()` should not change the state of the iteration, except that it may prevent removal of the most recent element via `remove()`. Annotations @Override

public T peek()

Implements com.google.common.collect.PeekingIterator.peek.

Doc from com.google.common.collect.PeekingIterator.peek.

Returns the next element in the iteration, without advancing the iteration.

Calls to peek() should not change the state of the iteration, except that it may prevent removal of the most recent element via remove().

Annotations

@Override

com.google.common.collect back to summary

private final Class TreeTraverser.PostOrderIterator

Class Inheritance

extends AbstractIterator<T>

java.lang.Object
com.google.common.collect.UnmodifiableIterator
com.google.common.collect.AbstractIterator
com.google.common.collect.TreeTraverser.PostOrderIterator

Field Summary

Modifier and Type	Field and Description
private final ArrayDeque<TreeTraverser.PostOrderNode<T>>	stack

Constructor Summary

Access	Constructor and Description
pack-priv	PostOrderIterator(T root)

Method Summary

Modifier and Type	Method and Description
protected T	computeNext() Implements abstract com.google.common.collect.AbstractIterator.computeNext. Returns the next element Note the implementation must call `endOfData()` when there are no elements left in the iteration.
private TreeTraverser.PostOrderNode<T>	expand(T t)

Inherited from com.google.common.collect.AbstractIterator:: endOfData hasNext next peek

Field Detail

stack	back to summary
private final ArrayDeque<TreeTraverser.PostOrderNode<T>> stack

Constructor Detail

PostOrderIterator	back to summary
pack-priv PostOrderIterator(T root)

Method Detail

computeNext back to summary

computeNext	back to summary
protected T computeNext() Implements abstract com.google.common.collect.AbstractIterator.computeNext. Doc from com.google.common.collect.AbstractIterator.computeNext. Returns the next element Note the implementation must call `endOfData()` when there are no elements left in the iteration. Failure to do so could result in an infinite loop. The initial invocation of `hasNext()` or `next()` calls this method, as does the first invocation of `hasNext` or `next` following each successful call to `next`. Once the implementation either invokes `endOfData` or throws an exception, `computeNext` is guaranteed to never be called again. If this method throws an exception, it will propagate outward to the `hasNext` or `next` invocation that invoked this method. Any further attempts to use the iterator will result in an `IllegalStateException`. The implementation of this method may not invoke the `hasNext`, `next`, or `peek()` methods on this instance; if it does, an `IllegalStateException` will result. Returns:T the next element if there was one. If `endOfData` was called during execution, the return value will be ignored. Annotations @Override @CheckForNull

protected T computeNext()

Implements abstract com.google.common.collect.AbstractIterator.computeNext.

Doc from com.google.common.collect.AbstractIterator.computeNext.

Returns the next element

Note

the implementation must call endOfData() when there are no elements left in the iteration. Failure to do so could result in an infinite loop.

The initial invocation of hasNext() or next() calls this method, as does the first invocation of hasNext or next following each successful call to next. Once the implementation either invokes endOfData or throws an exception, computeNext is guaranteed to never be called again.

If this method throws an exception, it will propagate outward to the hasNext or next invocation that invoked this method. Any further attempts to use the iterator will result in an IllegalStateException.

The implementation of this method may not invoke the hasNext, next, or peek() methods on this instance; if it does, an IllegalStateException will result.

Returns:T

the next element if there was one. If endOfData was called during execution, the return value will be ignored.

Annotations

@Override
@CheckForNull

expand	back to summary
private TreeTraverser.PostOrderNode<T> expand(T t)

com.google.common.collect back to summary

private final Class TreeTraverser.PostOrderNode<T>

Class Inheritance

extends Object

java.lang.Object
com.google.common.collect.TreeTraverser.PostOrderNode

Field Summary

Modifier and Type	Field and Description
pack-priv final Iterator<T>	childIterator
pack-priv final T	root

Constructor Summary

Access	Constructor and Description
pack-priv	PostOrderNode(T root, Iterator<T> childIterator)

Method Summary

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

childIterator	back to summary
pack-priv final Iterator<T> childIterator

root	back to summary
pack-priv final T root

Constructor Detail

PostOrderNode	back to summary
pack-priv PostOrderNode(T root, Iterator<T> childIterator)

com.google.common.collect back to summary

private final Class TreeTraverser.PreOrderIterator

Class Inheritance

extends UnmodifiableIterator<T>

java.lang.Object
com.google.common.collect.UnmodifiableIterator
com.google.common.collect.TreeTraverser.PreOrderIterator

Field Summary

Modifier and Type	Field and Description
private final Deque<Iterator<T>>	stack

Constructor Summary

Access	Constructor and Description
pack-priv	PreOrderIterator(T root)

Method Summary

Modifier and Type	Method and Description
public boolean	hasNext() Implements java.util.Iterator.hasNext. Returns `true` if the iteration has more elements.
public T	next() Implements java.util.Iterator.next. Returns the next element in the iteration.

Inherited from com.google.common.collect.UnmodifiableIterator:: remove

Field Detail

stack	back to summary
private final Deque<Iterator<T>> stack

Constructor Detail

PreOrderIterator	back to summary
pack-priv PreOrderIterator(T root)

Method Detail

hasNext back to summary

hasNext	back to summary
public boolean hasNext() Implements java.util.Iterator.hasNext. Doc from java.util.Iterator.hasNext. Returns `true` if the iteration has more elements. (In other words, returns `true` if `next` would return an element rather than throwing an exception.) Returns:boolean `true` if the iteration has more elements Annotations @Override

public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

Returns:boolean

true if the iteration has more elements

Annotations

@Override

next	back to summary
public T next() Implements java.util.Iterator.next. Doc from java.util.Iterator.next. Returns the next element in the iteration. Returns:T the next element in the iteration Annotations @Override

back to summary

public T next()

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

Returns:T

the next element in the iteration

Annotations

@Override

public abstract Class TreeTraverser<T>

Nested and Inner Type Summary

Constructor Summary

Method Summary

Constructor Detail

Method Detail

private final Class TreeTraverser.BreadthFirstIterator

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private final Class TreeTraverser.PostOrderIterator

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private final Class TreeTraverser.PostOrderNode<T>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

private final Class TreeTraverser.PreOrderIterator

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail