Home | History | Annotate | Download | only in collect 
      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> {
     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