1 /* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations 12 * under the License. 13 */ 14 15 package com.google.common.collect; 16 17 import static org.truth0.Truth.ASSERT; 18 19 import com.google.common.annotations.GwtCompatible; 20 import com.google.common.annotations.GwtIncompatible; 21 import com.google.common.base.Optional; 22 import com.google.common.testing.NullPointerTester; 23 24 import junit.framework.TestCase; 25 26 import java.util.Arrays; 27 import java.util.List; 28 29 import javax.annotation.Nullable; 30 31 /** 32 * Tests for {@code TreeTraverser}. 33 * 34 * @author Louis Wasserman 35 */ 36 @GwtCompatible(emulated = true) 37 public class TreeTraverserTest extends TestCase { 38 private static final class Tree { 39 final char value; 40 final List<Tree> children; 41 Tree(char value, Tree... children)42 public Tree(char value, Tree... children) { 43 this.value = value; 44 this.children = Arrays.asList(children); 45 } 46 } 47 48 private static final class BinaryTree { 49 final char value; 50 @Nullable 51 final BinaryTree left; 52 @Nullable 53 final BinaryTree right; 54 BinaryTree(char value, BinaryTree left, BinaryTree right)55 private BinaryTree(char value, BinaryTree left, BinaryTree right) { 56 this.value = value; 57 this.left = left; 58 this.right = right; 59 } 60 } 61 62 private static final TreeTraverser<Tree> ADAPTER = new TreeTraverser<Tree>() { 63 @Override 64 public Iterable<Tree> children(Tree node) { 65 return node.children; 66 } 67 }; 68 69 private static final BinaryTreeTraverser<BinaryTree> BIN_ADAPTER = 70 new BinaryTreeTraverser<BinaryTree>() { 71 72 @Override 73 public Optional<BinaryTree> leftChild(BinaryTree node) { 74 return Optional.fromNullable(node.left); 75 } 76 77 @Override 78 public Optional<BinaryTree> rightChild(BinaryTree node) { 79 return Optional.fromNullable(node.right); 80 } 81 }; 82 83 // h 84 // / | \ 85 // / e \ 86 // d g 87 // /|\ | 88 // / | \ f 89 // a b c 90 static final Tree a = new Tree('a'); 91 static final Tree b = new Tree('b'); 92 static final Tree c = new Tree('c'); 93 static final Tree d = new Tree('d', a, b, c); 94 static final Tree e = new Tree('e'); 95 static final Tree f = new Tree('f'); 96 static final Tree g = new Tree('g', f); 97 static final Tree h = new Tree('h', d, e, g); 98 99 // d 100 // / \ 101 // b e 102 // / \ \ 103 // a c f 104 // / 105 // g 106 static final BinaryTree ba = new BinaryTree('a', null, null); 107 static final BinaryTree bc = new BinaryTree('c', null, null); 108 static final BinaryTree bb = new BinaryTree('b', ba, bc); 109 static final BinaryTree bg = new BinaryTree('g', null, null); 110 static final BinaryTree bf = new BinaryTree('f', bg, null); 111 static final BinaryTree be = new BinaryTree('e', null, bf); 112 static final BinaryTree bd = new BinaryTree('d', bb, be); 113 iterationOrder(Iterable<Tree> iterable)114 static String iterationOrder(Iterable<Tree> iterable) { 115 StringBuilder builder = new StringBuilder(); 116 for (Tree t : iterable) { 117 builder.append(t.value); 118 } 119 return builder.toString(); 120 } 121 binaryIterationOrder(Iterable<BinaryTree> iterable)122 static String binaryIterationOrder(Iterable<BinaryTree> iterable) { 123 StringBuilder builder = new StringBuilder(); 124 for (BinaryTree t : iterable) { 125 builder.append(t.value); 126 } 127 return builder.toString(); 128 } 129 testPreOrder()130 public void testPreOrder() { 131 ASSERT.that(iterationOrder(ADAPTER.preOrderTraversal(h))).is("hdabcegf"); 132 ASSERT.that(binaryIterationOrder(BIN_ADAPTER.preOrderTraversal(bd))).is("dbacefg"); 133 } 134 testPostOrder()135 public void testPostOrder() { 136 ASSERT.that(iterationOrder(ADAPTER.postOrderTraversal(h))).is("abcdefgh"); 137 ASSERT.that(binaryIterationOrder(BIN_ADAPTER.postOrderTraversal(bd))).is("acbgfed"); 138 } 139 testBreadthOrder()140 public void testBreadthOrder() { 141 ASSERT.that(iterationOrder(ADAPTER.breadthFirstTraversal(h))).is("hdegabcf"); 142 ASSERT.that(binaryIterationOrder(BIN_ADAPTER.breadthFirstTraversal(bd))).is("dbeacfg"); 143 } 144 testInOrder()145 public void testInOrder() { 146 ASSERT.that(binaryIterationOrder(BIN_ADAPTER.inOrderTraversal(bd))).is("abcdegf"); 147 } 148 149 @GwtIncompatible("NullPointerTester") testNulls()150 public void testNulls() { 151 NullPointerTester tester = new NullPointerTester(); 152 tester.testAllPublicInstanceMethods(ADAPTER); 153 tester.testAllPublicInstanceMethods(BIN_ADAPTER); 154 } 155 } 156