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.base.Optional; 22 23import java.util.LinkedList; 24import java.util.Iterator; 25 26/** 27 * A variant of {@link TreeTraverser} for binary trees, providing additional traversals specific to 28 * binary trees. 29 * 30 * @author Louis Wasserman 31 */ 32public abstract class BinaryTreeTraverser<T> extends TreeTraverser<T> { 33 // TODO(user): make this GWT-compatible when we've checked in ArrayDeque and BitSet emulation 34 35 /** 36 * Returns the left child of the specified node, or {@link Optional#absent()} if the specified 37 * node has no left child. 38 */ 39 public abstract Optional<T> leftChild(T root); 40 41 /** 42 * Returns the right child of the specified node, or {@link Optional#absent()} if the specified 43 * node has no right child. 44 */ 45 public abstract Optional<T> rightChild(T root); 46 47 /** 48 * Returns the children of this node, in left-to-right order. 49 */ 50 @Override 51 public final Iterable<T> children(final T root) { 52 checkNotNull(root); 53 return new FluentIterable<T>() { 54 @Override 55 public Iterator<T> iterator() { 56 return new AbstractIterator<T>() { 57 boolean doneLeft; 58 boolean doneRight; 59 60 @Override 61 protected T computeNext() { 62 if (!doneLeft) { 63 doneLeft = true; 64 Optional<T> left = leftChild(root); 65 if (left.isPresent()) { 66 return left.get(); 67 } 68 } 69 if (!doneRight) { 70 doneRight = true; 71 Optional<T> right = rightChild(root); 72 if (right.isPresent()) { 73 return right.get(); 74 } 75 } 76 return endOfData(); 77 } 78 }; 79 } 80 }; 81 } 82 83 // TODO(user): see if any significant optimizations are possible for breadthFirstIterator 84 85 public final FluentIterable<T> inOrderTraversal(final T root) { 86 checkNotNull(root); 87 return new FluentIterable<T>() { 88 @Override 89 public UnmodifiableIterator<T> iterator() { 90 return new InOrderIterator(root); 91 } 92 }; 93 } 94 95 private static final class InOrderNode<T> { 96 final T node; 97 boolean hasExpandedLeft; 98 99 InOrderNode(T node) { 100 this.node = checkNotNull(node); 101 this.hasExpandedLeft = false; 102 } 103 } 104 105 private final class InOrderIterator extends AbstractIterator<T> { 106 private final LinkedList<InOrderNode<T>> stack; 107 108 InOrderIterator(T root) { 109 this.stack = Lists.newLinkedList(); 110 stack.addLast(new InOrderNode<T>(root)); 111 } 112 113 @Override 114 protected T computeNext() { 115 while (!stack.isEmpty()) { 116 InOrderNode<T> inOrderNode = stack.getLast(); 117 if (inOrderNode.hasExpandedLeft) { 118 stack.removeLast(); 119 pushIfPresent(rightChild(inOrderNode.node)); 120 return inOrderNode.node; 121 } else { 122 inOrderNode.hasExpandedLeft = true; 123 pushIfPresent(leftChild(inOrderNode.node)); 124 } 125 } 126 return endOfData(); 127 } 128 129 private void pushIfPresent(Optional<T> node) { 130 if (node.isPresent()) { 131 stack.addLast(new InOrderNode<T>(node.get())); 132 } 133 } 134 } 135} 136