1 files changed, 188 insertions, 0 deletions
diff --git a/guava-tests/test/com/google/common/collect/BstTesting.java b/guava-tests/test/com/google/common/collect/BstTesting.java
new file mode 100644
index 0000000..af929b2
--- /dev/null
+++ b/guava-tests/test/com/google/common/collect/BstTesting.java
@@ -0,0 +1,188 @@
+/*
+ * Copyright (C) 2011 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.collect;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.collect.BstSide.LEFT;
+import static com.google.common.collect.BstSide.RIGHT;
+import static junit.framework.Assert.assertEquals;
+
+import com.google.common.annotations.GwtCompatible;
+import com.google.common.annotations.GwtIncompatible;
+import com.google.common.base.Objects;
+import com.google.common.testing.NullPointerTester;
+
+import java.util.List;
+
+import javax.annotation.Nullable;
+
+/**
+ * Testing classes and utilities to be used in tests of the binary search tree framework.
+ *
+ * @author Louis Wasserman
+ */
+@GwtCompatible(emulated = true)
+public class BstTesting {
+  static final class SimpleNode extends BstNode<Character, SimpleNode> {
+    SimpleNode(Character key, @Nullable SimpleNode left, @Nullable SimpleNode right) {
+      super(key, left, right);
+    }
+
+    @Override
+    public String toString() {
+      return getKey().toString();
+    }
+
+    @Override
+    public boolean equals(@Nullable Object obj) {
+      if (obj instanceof SimpleNode) {
+        SimpleNode node = (SimpleNode) obj;
+        return getKey().equals(node.getKey())
+            && Objects.equal(childOrNull(LEFT), node.childOrNull(LEFT))
+            && Objects.equal(childOrNull(RIGHT), node.childOrNull(RIGHT));
+      }
+      return false;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hashCode(getKey(), childOrNull(LEFT), childOrNull(RIGHT));
+    }
+  }
+
+  static final BstNodeFactory<SimpleNode> nodeFactory = new BstNodeFactory<SimpleNode>() {
+    @Override
+    public SimpleNode createNode(
+        SimpleNode source, @Nullable SimpleNode left, @Nullable SimpleNode right) {
+      return new SimpleNode(source.getKey(), left, right);
+    }
+  };
+
+  static final BstBalancePolicy<SimpleNode> balancePolicy = new BstBalancePolicy<SimpleNode>() {
+    @Override
+    public SimpleNode balance(BstNodeFactory<SimpleNode> nodeFactory, SimpleNode source,
+        @Nullable SimpleNode left, @Nullable SimpleNode right) {
+      return checkNotNull(nodeFactory).createNode(source, left, right);
+    }
+
+    @Nullable
+    @Override
+    public SimpleNode combine(BstNodeFactory<SimpleNode> nodeFactory, @Nullable SimpleNode left,
+        @Nullable SimpleNode right) {
+      // Shove right into the rightmost position in the left tree.
+      if (left == null) {
+        return right;
+      } else if (right == null) {
+        return left;
+      } else if (left.hasChild(RIGHT)) {
+        return nodeFactory.createNode(
+            left, left.childOrNull(LEFT), combine(nodeFactory, left.childOrNull(RIGHT), right));
+      } else {
+        return nodeFactory.createNode(left, left.childOrNull(LEFT), right);
+      }
+    }
+  };
+
+  static final BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> pathFactory =
+      BstInOrderPath.inOrderFactory();
+
+  // A direct, if dumb, way to count total nodes in a tree.
+  static final BstAggregate<SimpleNode> countAggregate = new BstAggregate<SimpleNode>() {
+    @Override
+    public int entryValue(SimpleNode entry) {
+      return 1;
+    }
+
+    @Override
+    public long treeValue(@Nullable SimpleNode tree) {
+      if (tree == null) {
+        return 0;
+      } else {
+        return 1 + treeValue(tree.childOrNull(LEFT)) + treeValue(tree.childOrNull(RIGHT));
+      }
+    }
+  };
+
+  static <P extends BstPath<SimpleNode, P>> List<SimpleNode> pathToList(P path) {
+    List<SimpleNode> list = Lists.newArrayList();
+    for (; path != null; path = path.prefixOrNull()) {
+      list.add(path.getTip());
+    }
+    return list;
+  }
+
+  static <N extends BstNode<?, N>, P extends BstPath<N, P>> P extension(
+      BstPathFactory<N, P> factory, N root, BstSide... sides) {
+    P path = factory.initialPath(root);
+    for (BstSide side : sides) {
+      path = factory.extension(path, side);
+    }
+    return path;
+  }
+
+  static void assertInOrderTraversalIs(@Nullable SimpleNode root, String order) {
+    if (root == null) {
+      assertEquals("", order);
+    } else {
+      BstInOrderPath<SimpleNode> path = pathFactory.initialPath(root);
+      while (path.getTip().hasChild(LEFT)) {
+        path = pathFactory.extension(path, LEFT);
+      }
+      assertEquals(order.charAt(0), path
+          .getTip()
+          .getKey()
+          .charValue());
+      int i;
+      for (i = 1; path.hasNext(RIGHT); i++) {
+        path = path.next(RIGHT);
+        assertEquals(order.charAt(i), path
+            .getTip()
+            .getKey()
+            .charValue());
+      }
+      assertEquals(i, order.length());
+    }
+  }
+
+  @GwtIncompatible("NullPointerTester")
+  static NullPointerTester defaultNullPointerTester() {
+    NullPointerTester tester = new NullPointerTester();
+    SimpleNode node = new SimpleNode('a', null, null);
+    tester.setDefault(BstNode.class, node);
+    tester.setDefault(BstSide.class, LEFT);
+    tester.setDefault(BstNodeFactory.class, nodeFactory);
+    tester.setDefault(BstBalancePolicy.class, balancePolicy);
+    tester.setDefault(BstPathFactory.class, pathFactory);
+    tester.setDefault(BstPath.class, pathFactory.initialPath(node));
+    tester.setDefault(BstInOrderPath.class, pathFactory.initialPath(node));
+    tester.setDefault(Object.class, 'a');
+    tester.setDefault(GeneralRange.class, GeneralRange.all(Ordering.natural()));
+    tester.setDefault(BstAggregate.class, countAggregate);
+    BstModifier<Character, SimpleNode> modifier = new BstModifier<Character, SimpleNode>() {
+      @Nullable
+      @Override
+      public BstModificationResult<SimpleNode> modify(
+          Character key, @Nullable SimpleNode originalEntry) {
+        return BstModificationResult.identity(originalEntry);
+      }
+    };
+    tester.setDefault(
+        BstModificationResult.class, BstModificationResult.<SimpleNode>identity(null));
+    tester.setDefault(BstModifier.class, modifier);
+    tester.setDefault(
+        BstMutationRule.class, BstMutationRule.createRule(modifier, balancePolicy, nodeFactory));
+    return tester;
+  }
+}