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 under 12 * the License. 13 */ 14 15 package com.google.common.collect; 16 17 import static com.google.common.base.Preconditions.checkNotNull; 18 import static com.google.common.collect.BstSide.LEFT; 19 import static com.google.common.collect.BstSide.RIGHT; 20 import static junit.framework.Assert.assertEquals; 21 22 import com.google.common.annotations.GwtCompatible; 23 import com.google.common.annotations.GwtIncompatible; 24 import com.google.common.base.Objects; 25 import com.google.common.testing.NullPointerTester; 26 27 import java.util.List; 28 29 import javax.annotation.Nullable; 30 31 /** 32 * Testing classes and utilities to be used in tests of the binary search tree framework. 33 * 34 * @author Louis Wasserman 35 */ 36 @GwtCompatible(emulated = true) 37 public class BstTesting { 38 static final class SimpleNode extends BstNode<Character, SimpleNode> { SimpleNode(Character key, @Nullable SimpleNode left, @Nullable SimpleNode right)39 SimpleNode(Character key, @Nullable SimpleNode left, @Nullable SimpleNode right) { 40 super(key, left, right); 41 } 42 43 @Override toString()44 public String toString() { 45 return getKey().toString(); 46 } 47 48 @Override equals(@ullable Object obj)49 public boolean equals(@Nullable Object obj) { 50 if (obj instanceof SimpleNode) { 51 SimpleNode node = (SimpleNode) obj; 52 return getKey().equals(node.getKey()) 53 && Objects.equal(childOrNull(LEFT), node.childOrNull(LEFT)) 54 && Objects.equal(childOrNull(RIGHT), node.childOrNull(RIGHT)); 55 } 56 return false; 57 } 58 59 @Override hashCode()60 public int hashCode() { 61 return Objects.hashCode(getKey(), childOrNull(LEFT), childOrNull(RIGHT)); 62 } 63 } 64 65 static final BstNodeFactory<SimpleNode> nodeFactory = new BstNodeFactory<SimpleNode>() { 66 @Override 67 public SimpleNode createNode( 68 SimpleNode source, @Nullable SimpleNode left, @Nullable SimpleNode right) { 69 return new SimpleNode(source.getKey(), left, right); 70 } 71 }; 72 73 static final BstBalancePolicy<SimpleNode> balancePolicy = new BstBalancePolicy<SimpleNode>() { 74 @Override 75 public SimpleNode balance(BstNodeFactory<SimpleNode> nodeFactory, SimpleNode source, 76 @Nullable SimpleNode left, @Nullable SimpleNode right) { 77 return checkNotNull(nodeFactory).createNode(source, left, right); 78 } 79 80 @Nullable 81 @Override 82 public SimpleNode combine(BstNodeFactory<SimpleNode> nodeFactory, @Nullable SimpleNode left, 83 @Nullable SimpleNode right) { 84 // Shove right into the rightmost position in the left tree. 85 if (left == null) { 86 return right; 87 } else if (right == null) { 88 return left; 89 } else if (left.hasChild(RIGHT)) { 90 return nodeFactory.createNode( 91 left, left.childOrNull(LEFT), combine(nodeFactory, left.childOrNull(RIGHT), right)); 92 } else { 93 return nodeFactory.createNode(left, left.childOrNull(LEFT), right); 94 } 95 } 96 }; 97 98 static final BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> pathFactory = 99 BstInOrderPath.inOrderFactory(); 100 101 // A direct, if dumb, way to count total nodes in a tree. 102 static final BstAggregate<SimpleNode> countAggregate = new BstAggregate<SimpleNode>() { 103 @Override 104 public int entryValue(SimpleNode entry) { 105 return 1; 106 } 107 108 @Override 109 public long treeValue(@Nullable SimpleNode tree) { 110 if (tree == null) { 111 return 0; 112 } else { 113 return 1 + treeValue(tree.childOrNull(LEFT)) + treeValue(tree.childOrNull(RIGHT)); 114 } 115 } 116 }; 117 pathToList(P path)118 static <P extends BstPath<SimpleNode, P>> List<SimpleNode> pathToList(P path) { 119 List<SimpleNode> list = Lists.newArrayList(); 120 for (; path != null; path = path.prefixOrNull()) { 121 list.add(path.getTip()); 122 } 123 return list; 124 } 125 extension( BstPathFactory<N, P> factory, N root, BstSide... sides)126 static <N extends BstNode<?, N>, P extends BstPath<N, P>> P extension( 127 BstPathFactory<N, P> factory, N root, BstSide... sides) { 128 P path = factory.initialPath(root); 129 for (BstSide side : sides) { 130 path = factory.extension(path, side); 131 } 132 return path; 133 } 134 assertInOrderTraversalIs(@ullable SimpleNode root, String order)135 static void assertInOrderTraversalIs(@Nullable SimpleNode root, String order) { 136 if (root == null) { 137 assertEquals("", order); 138 } else { 139 BstInOrderPath<SimpleNode> path = pathFactory.initialPath(root); 140 while (path.getTip().hasChild(LEFT)) { 141 path = pathFactory.extension(path, LEFT); 142 } 143 assertEquals(order.charAt(0), path 144 .getTip() 145 .getKey() 146 .charValue()); 147 int i; 148 for (i = 1; path.hasNext(RIGHT); i++) { 149 path = path.next(RIGHT); 150 assertEquals(order.charAt(i), path 151 .getTip() 152 .getKey() 153 .charValue()); 154 } 155 assertEquals(i, order.length()); 156 } 157 } 158 159 @GwtIncompatible("NullPointerTester") defaultNullPointerTester()160 static NullPointerTester defaultNullPointerTester() { 161 NullPointerTester tester = new NullPointerTester(); 162 SimpleNode node = new SimpleNode('a', null, null); 163 tester.setDefault(BstNode.class, node); 164 tester.setDefault(BstSide.class, LEFT); 165 tester.setDefault(BstNodeFactory.class, nodeFactory); 166 tester.setDefault(BstBalancePolicy.class, balancePolicy); 167 tester.setDefault(BstPathFactory.class, pathFactory); 168 tester.setDefault(BstPath.class, pathFactory.initialPath(node)); 169 tester.setDefault(BstInOrderPath.class, pathFactory.initialPath(node)); 170 tester.setDefault(Object.class, 'a'); 171 tester.setDefault(GeneralRange.class, GeneralRange.all(Ordering.natural())); 172 tester.setDefault(BstAggregate.class, countAggregate); 173 BstModifier<Character, SimpleNode> modifier = new BstModifier<Character, SimpleNode>() { 174 @Nullable 175 @Override 176 public BstModificationResult<SimpleNode> modify( 177 Character key, @Nullable SimpleNode originalEntry) { 178 return BstModificationResult.identity(originalEntry); 179 } 180 }; 181 tester.setDefault( 182 BstModificationResult.class, BstModificationResult.<SimpleNode>identity(null)); 183 tester.setDefault(BstModifier.class, modifier); 184 tester.setDefault( 185 BstMutationRule.class, BstMutationRule.createRule(modifier, balancePolicy, nodeFactory)); 186 return tester; 187 } 188 } 189