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 10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 11 * express or implied. See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 15 package com.google.common.collect; 16 17 import static com.google.common.collect.BstSide.LEFT; 18 import static com.google.common.collect.BstSide.RIGHT; 19 import static com.google.common.collect.BstTesting.defaultNullPointerTester; 20 import static com.google.common.collect.BstTesting.extension; 21 import static com.google.common.collect.BstTesting.pathToList; 22 import static org.junit.contrib.truth.Truth.ASSERT; 23 24 import com.google.common.annotations.GwtCompatible; 25 import com.google.common.annotations.GwtIncompatible; 26 import com.google.common.collect.BstTesting.SimpleNode; 27 28 import junit.framework.TestCase; 29 30 /** 31 * Tests for {@code BstInOrderPath}. 32 * 33 * @author Louis Wasserman 34 */ 35 @GwtCompatible(emulated = true) 36 public class BstInOrderPathTest extends TestCase { 37 public void testFullTreeRight() { 38 // d 39 // / \ 40 // b f 41 // / \ / \ 42 // a c e g 43 SimpleNode a = new SimpleNode('a', null, null); 44 SimpleNode c = new SimpleNode('c', null, null); 45 SimpleNode b = new SimpleNode('b', a, c); 46 SimpleNode e = new SimpleNode('e', null, null); 47 SimpleNode g = new SimpleNode('g', null, null); 48 SimpleNode f = new SimpleNode('f', e, g); 49 SimpleNode d = new SimpleNode('d', b, f); 50 BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory = 51 BstInOrderPath.inOrderFactory(); 52 BstInOrderPath<SimpleNode> path = extension(factory, d, LEFT, LEFT); 53 ASSERT.that(pathToList(path)).hasContentsInOrder(a, b, d); 54 path = testNextPathIs(path, b, d); 55 path = testNextPathIs(path, c, b, d); 56 path = testNextPathIs(path, d); 57 path = testNextPathIs(path, e, f, d); 58 path = testNextPathIs(path, f, d); 59 path = testNextPathIs(path, g, f, d); 60 assertFalse(path.hasNext(RIGHT)); 61 } 62 63 public void testFullTreeLeft() { 64 // d 65 // / \ 66 // b f 67 // / \ / \ 68 // a c e g 69 SimpleNode a = new SimpleNode('a', null, null); 70 SimpleNode c = new SimpleNode('c', null, null); 71 SimpleNode b = new SimpleNode('b', a, c); 72 SimpleNode e = new SimpleNode('e', null, null); 73 SimpleNode g = new SimpleNode('g', null, null); 74 SimpleNode f = new SimpleNode('f', e, g); 75 SimpleNode d = new SimpleNode('d', b, f); 76 BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory = 77 BstInOrderPath.inOrderFactory(); 78 BstInOrderPath<SimpleNode> path = extension(factory, d, RIGHT, RIGHT); 79 ASSERT.that(pathToList(path)).hasContentsInOrder(g, f, d); 80 path = testPrevPathIs(path, f, d); 81 path = testPrevPathIs(path, e, f, d); 82 path = testPrevPathIs(path, d); 83 path = testPrevPathIs(path, c, b, d); 84 path = testPrevPathIs(path, b, d); 85 path = testPrevPathIs(path, a, b, d); 86 assertFalse(path.hasNext(LEFT)); 87 } 88 89 public void testPartialTree1Right() { 90 91 // d 92 // / \ 93 // b f 94 // / \ 95 // a g 96 SimpleNode a = new SimpleNode('a', null, null); 97 SimpleNode b = new SimpleNode('b', a, null); 98 SimpleNode g = new SimpleNode('g', null, null); 99 SimpleNode f = new SimpleNode('f', null, g); 100 SimpleNode d = new SimpleNode('d', b, f); 101 BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory = 102 BstInOrderPath.inOrderFactory(); 103 BstInOrderPath<SimpleNode> path = extension(factory, d, LEFT, LEFT); 104 ASSERT.that(pathToList(path)).hasContentsInOrder(a, b, d); 105 path = testNextPathIs(path, b, d); 106 path = testNextPathIs(path, d); 107 path = testNextPathIs(path, f, d); 108 path = testNextPathIs(path, g, f, d); 109 assertFalse(path.hasNext(RIGHT)); 110 } 111 112 public void testPartialTree1Left() { 113 114 // d 115 // / \ 116 // b f 117 // / \ 118 // a g 119 SimpleNode a = new SimpleNode('a', null, null); 120 SimpleNode b = new SimpleNode('b', a, null); 121 SimpleNode g = new SimpleNode('g', null, null); 122 SimpleNode f = new SimpleNode('f', null, g); 123 SimpleNode d = new SimpleNode('d', b, f); 124 BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory = 125 BstInOrderPath.inOrderFactory(); 126 BstInOrderPath<SimpleNode> path = extension(factory, d, RIGHT, RIGHT); 127 ASSERT.that(pathToList(path)).hasContentsInOrder(g, f, d); 128 path = testPrevPathIs(path, f, d); 129 path = testPrevPathIs(path, d); 130 path = testPrevPathIs(path, b, d); 131 path = testPrevPathIs(path, a, b, d); 132 assertFalse(path.hasNext(LEFT)); 133 } 134 135 public void testPartialTree2Right() { 136 // d 137 // / \ 138 // b f 139 // \ / 140 // c e 141 SimpleNode c = new SimpleNode('c', null, null); 142 SimpleNode b = new SimpleNode('b', null, c); 143 SimpleNode e = new SimpleNode('e', null, null); 144 SimpleNode f = new SimpleNode('f', e, null); 145 SimpleNode d = new SimpleNode('d', b, f); 146 BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory = 147 BstInOrderPath.inOrderFactory(); 148 BstInOrderPath<SimpleNode> path = extension(factory, d, LEFT); 149 ASSERT.that(pathToList(path)).hasContentsInOrder(b, d); 150 path = testNextPathIs(path, c, b, d); 151 path = testNextPathIs(path, d); 152 path = testNextPathIs(path, e, f, d); 153 path = testNextPathIs(path, f, d); 154 assertFalse(path.hasNext(RIGHT)); 155 } 156 157 public void testPartialTree2Left() { 158 // d 159 // / \ 160 // b f 161 // \ / 162 // c e 163 SimpleNode c = new SimpleNode('c', null, null); 164 SimpleNode b = new SimpleNode('b', null, c); 165 SimpleNode e = new SimpleNode('e', null, null); 166 SimpleNode f = new SimpleNode('f', e, null); 167 SimpleNode d = new SimpleNode('d', b, f); 168 BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory = 169 BstInOrderPath.inOrderFactory(); 170 BstInOrderPath<SimpleNode> path = extension(factory, d, RIGHT); 171 ASSERT.that(pathToList(path)).hasContentsInOrder(f, d); 172 path = testPrevPathIs(path, e,f,d); 173 path = testPrevPathIs(path, d); 174 path = testPrevPathIs(path, c,b, d); 175 path = testPrevPathIs(path, b, d); 176 assertFalse(path.hasNext(LEFT)); 177 } 178 179 private static BstInOrderPath<SimpleNode> testNextPathIs( 180 BstInOrderPath<SimpleNode> path, SimpleNode... nodes) { 181 assertTrue(path.hasNext(RIGHT)); 182 path = path.next(RIGHT); 183 ASSERT.that(pathToList(path)).hasContentsInOrder(nodes); 184 return path; 185 } 186 187 private static BstInOrderPath<SimpleNode> testPrevPathIs( 188 BstInOrderPath<SimpleNode> path, SimpleNode... nodes) { 189 assertTrue(path.hasNext(LEFT)); 190 path = path.next(LEFT); 191 ASSERT.that(pathToList(path)).hasContentsInOrder(nodes); 192 return path; 193 } 194 195 @GwtIncompatible("NullPointerTester") 196 public void testNullPointers() throws Exception { 197 defaultNullPointerTester().testAllPublicStaticMethods(BstInOrderPath.class); 198 } 199 } 200
