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
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkNotNull;
18import static com.google.common.collect.BstSide.LEFT;
19import static com.google.common.collect.BstSide.RIGHT;
20import static junit.framework.Assert.assertEquals;
21
22import com.google.common.annotations.GwtCompatible;
23import com.google.common.annotations.GwtIncompatible;
24import com.google.common.base.Objects;
25import com.google.common.testing.NullPointerTester;
26
27import java.util.List;
28
29import 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)
37public class BstTesting {
38  static final class SimpleNode extends BstNode<Character, SimpleNode> {
39    SimpleNode(Character key, @Nullable SimpleNode left, @Nullable SimpleNode right) {
40      super(key, left, right);
41    }
42
43    @Override
44    public String toString() {
45      return getKey().toString();
46    }
47
48    @Override
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
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
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
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
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")
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