alvinalexander.com | career | drupal | java | mac | mysql | perl | scala | uml | unix  

Java example source code file (TreeTraverser.java)

This example Java source code file (TreeTraverser.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

abstractiterator, arraydeque, beta, breadthfirstiterator, fluentiterable, gwtcompatible, override, postorderiterator, postordernode, preorderiterator, queue, treetraverser, unmodifiableiterator, util

The TreeTraverser.java Java example source code

/*
 * Copyright (C) 2012 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.Queue;

/**
 * Views elements of a type {@code T} as nodes in a tree, and provides methods to traverse the trees
 * induced by this traverser.
 *
 * <p>For example, the tree
 *
 * <pre>          {@code
 *          h
 *        / | \
 *       /  e  \
 *      d       g
 *     /|\      |
 *    / | \     f
 *   a  b  c       }</pre>
 *
 * <p>can be iterated over in preorder (hdabcegf), postorder (abcdefgh), or breadth-first order
 * (hdegabcf).
 *
 * <p>Null nodes are strictly forbidden.
 *
 * @author Louis Wasserman
 * @since 15.0
 */
@Beta
@GwtCompatible(emulated = true)
public abstract class TreeTraverser<T> {
  // TODO(lowasser): make this GWT-compatible when we've checked in ArrayDeque emulation

  /**
   * Returns the children of the specified node.  Must not contain null.
   */
  public abstract Iterable<T> children(T root);

  /**
   * 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.
   *
   * <p>No guarantees are made about the behavior of the traversal when nodes change while
   * iteration is in progress or when the iterators generated by {@link #children} are advanced.
   */
  public final FluentIterable<T> preOrderTraversal(final T root) {
    checkNotNull(root);
    return new FluentIterable<T>() {
      @Override
      public UnmodifiableIterator<T> iterator() {
        return preOrderIterator(root);
      }
    };
  }

  // overridden in BinaryTreeTraverser
  UnmodifiableIterator<T> preOrderIterator(T root) {
    return new PreOrderIterator(root);
  }

  private final class PreOrderIterator extends UnmodifiableIterator<T> {
    private final Deque<Iterator stack;

    PreOrderIterator(T root) {
      this.stack = new ArrayDeque<Iterator();
      stack.addLast(Iterators.singletonIterator(checkNotNull(root)));
    }

    @Override
    public boolean hasNext() {
      return !stack.isEmpty();
    }

    @Override
    public T next() {
      Iterator<T> itr = stack.getLast(); // throws NSEE if empty
      T result = checkNotNull(itr.next());
      if (!itr.hasNext()) {
        stack.removeLast();
      }
      Iterator<T> childItr = children(result).iterator();
      if (childItr.hasNext()) {
        stack.addLast(childItr);
      }
      return result;
    }
  }

  /**
   * 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.
   *
   * <p>No guarantees are made about the behavior of the traversal when nodes change while
   * iteration is in progress or when the iterators generated by {@link #children} are advanced.
   */
  public final FluentIterable<T> postOrderTraversal(final T root) {
    checkNotNull(root);
    return new FluentIterable<T>() {
      @Override
      public UnmodifiableIterator<T> iterator() {
        return postOrderIterator(root);
      }
    };
  }

  // overridden in BinaryTreeTraverser
  UnmodifiableIterator<T> postOrderIterator(T root) {
    return new PostOrderIterator(root);
  }

  private static final class PostOrderNode<T> {
    final T root;
    final Iterator<T> childIterator;

    PostOrderNode(T root, Iterator<T> childIterator) {
      this.root = checkNotNull(root);
      this.childIterator = checkNotNull(childIterator);
    }
  }

  private final class PostOrderIterator extends AbstractIterator<T> {
    private final ArrayDeque<PostOrderNode stack;

    PostOrderIterator(T root) {
      this.stack = new ArrayDeque<PostOrderNode();
      stack.addLast(expand(root));
    }

    @Override
    protected T computeNext() {
      while (!stack.isEmpty()) {
        PostOrderNode<T> top = stack.getLast();
        if (top.childIterator.hasNext()) {
          T child = top.childIterator.next();
          stack.addLast(expand(child));
        } else {
          stack.removeLast();
          return top.root;
        }
      }
      return endOfData();
    }

    private PostOrderNode<T> expand(T t) {
      return new PostOrderNode<T>(t, children(t).iterator());
    }
  }

  /**
   * 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.
   *
   * <p>No guarantees are made about the behavior of the traversal when nodes change while
   * iteration is in progress or when the iterators generated by {@link #children} are advanced.
   */
  public final FluentIterable<T> breadthFirstTraversal(final T root) {
    checkNotNull(root);
    return new FluentIterable<T>() {
      @Override
      public UnmodifiableIterator<T> iterator() {
        return new BreadthFirstIterator(root);
      }
    };
  }

  private final class BreadthFirstIterator extends UnmodifiableIterator<T>
      implements PeekingIterator<T> {
    private final Queue<T> queue;

    BreadthFirstIterator(T root) {
      this.queue = new ArrayDeque<T>();
      queue.add(root);
    }

    @Override
    public boolean hasNext() {
      return !queue.isEmpty();
    }

    @Override
    public T peek() {
      return queue.element();
    }

    @Override
    public T next() {
      T result = queue.remove();
      Iterables.addAll(queue, children(result));
      return result;
    }
  }
}

Other Java examples (source code examples)

Here is a short list of links related to this Java TreeTraverser.java source code file:

... this post is sponsored by my books ...

#1 New Release!

FP Best Seller

 

new blog posts

 

Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.