11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2011 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in compliance with the License. You may obtain a copy of the License at 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software distributed under the License 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or implied. See the License for the specific language governing permissions and limitations under 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the License. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.BstSide.LEFT; 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.BstSide.RIGHT; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static junit.framework.Assert.assertEquals; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Objects; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.testing.NullPointerTester; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Testing classes and utilities to be used in tests of the binary search tree framework. 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(emulated = true) 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class BstTesting { 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final class SimpleNode extends BstNode<Character, SimpleNode> { 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SimpleNode(Character key, @Nullable SimpleNode left, @Nullable SimpleNode right) { 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(key, left, right); 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public String toString() { 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return getKey().toString(); 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean equals(@Nullable Object obj) { 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (obj instanceof SimpleNode) { 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SimpleNode node = (SimpleNode) obj; 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return getKey().equals(node.getKey()) 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert && Objects.equal(childOrNull(LEFT), node.childOrNull(LEFT)) 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert && Objects.equal(childOrNull(RIGHT), node.childOrNull(RIGHT)); 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int hashCode() { 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Objects.hashCode(getKey(), childOrNull(LEFT), childOrNull(RIGHT)); 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final BstNodeFactory<SimpleNode> nodeFactory = new BstNodeFactory<SimpleNode>() { 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SimpleNode createNode( 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SimpleNode source, @Nullable SimpleNode left, @Nullable SimpleNode right) { 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new SimpleNode(source.getKey(), left, right); 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final BstBalancePolicy<SimpleNode> balancePolicy = new BstBalancePolicy<SimpleNode>() { 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SimpleNode balance(BstNodeFactory<SimpleNode> nodeFactory, SimpleNode source, 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable SimpleNode left, @Nullable SimpleNode right) { 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return checkNotNull(nodeFactory).createNode(source, left, right); 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SimpleNode combine(BstNodeFactory<SimpleNode> nodeFactory, @Nullable SimpleNode left, 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable SimpleNode right) { 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Shove right into the rightmost position in the left tree. 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (left == null) { 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return right; 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (right == null) { 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return left; 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (left.hasChild(RIGHT)) { 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nodeFactory.createNode( 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert left, left.childOrNull(LEFT), combine(nodeFactory, left.childOrNull(RIGHT), right)); 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nodeFactory.createNode(left, left.childOrNull(LEFT), right); 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> pathFactory = 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstInOrderPath.inOrderFactory(); 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // A direct, if dumb, way to count total nodes in a tree. 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final BstAggregate<SimpleNode> countAggregate = new BstAggregate<SimpleNode>() { 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int entryValue(SimpleNode entry) { 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 1; 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public long treeValue(@Nullable SimpleNode tree) { 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (tree == null) { 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 1 + treeValue(tree.childOrNull(LEFT)) + treeValue(tree.childOrNull(RIGHT)); 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <P extends BstPath<SimpleNode, P>> List<SimpleNode> pathToList(P path) { 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<SimpleNode> list = Lists.newArrayList(); 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (; path != null; path = path.prefixOrNull()) { 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert list.add(path.getTip()); 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return list; 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <N extends BstNode<?, N>, P extends BstPath<N, P>> P extension( 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstPathFactory<N, P> factory, N root, BstSide... sides) { 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert P path = factory.initialPath(root); 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (BstSide side : sides) { 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert path = factory.extension(path, side); 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return path; 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static void assertInOrderTraversalIs(@Nullable SimpleNode root, String order) { 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (root == null) { 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("", order); 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstInOrderPath<SimpleNode> path = pathFactory.initialPath(root); 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (path.getTip().hasChild(LEFT)) { 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert path = pathFactory.extension(path, LEFT); 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(order.charAt(0), path 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .getTip() 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .getKey() 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .charValue()); 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int i; 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (i = 1; path.hasNext(RIGHT); i++) { 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert path = path.next(RIGHT); 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(order.charAt(i), path 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .getTip() 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .getKey() 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .charValue()); 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(i, order.length()); 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("NullPointerTester") 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static NullPointerTester defaultNullPointerTester() { 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert NullPointerTester tester = new NullPointerTester(); 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SimpleNode node = new SimpleNode('a', null, null); 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(BstNode.class, node); 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(BstSide.class, LEFT); 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(BstNodeFactory.class, nodeFactory); 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(BstBalancePolicy.class, balancePolicy); 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(BstPathFactory.class, pathFactory); 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(BstPath.class, pathFactory.initialPath(node)); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(BstInOrderPath.class, pathFactory.initialPath(node)); 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(Object.class, 'a'); 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(GeneralRange.class, GeneralRange.all(Ordering.natural())); 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(BstAggregate.class, countAggregate); 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstModifier<Character, SimpleNode> modifier = new BstModifier<Character, SimpleNode>() { 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public BstModificationResult<SimpleNode> modify( 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Character key, @Nullable SimpleNode originalEntry) { 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return BstModificationResult.identity(originalEntry); 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault( 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstModificationResult.class, BstModificationResult.<SimpleNode>identity(null)); 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(BstModifier.class, modifier); 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault( 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstMutationRule.class, BstMutationRule.createRule(modifier, balancePolicy, nodeFactory)); 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return tester; 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 189