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 10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 11 * express or implied. See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 15 package com.google.common.collect; 16 17 import static com.google.common.collect.BstTesting.assertInOrderTraversalIs; 18 import static com.google.common.collect.BstTesting.nodeFactory; 19 20 import com.google.common.annotations.GwtCompatible; 21 import com.google.common.collect.BstTesting.SimpleNode; 22 23 import junit.framework.TestCase; 24 25 import javax.annotation.Nullable; 26 27 /** 28 * Tests for an arbitrary {@code BSTRebalancePolicy}. 29 * 30 * @author Louis Wasserman 31 */ 32 @GwtCompatible 33 public abstract class AbstractBstBalancePolicyTest extends TestCase { 34 protected abstract BstBalancePolicy<SimpleNode> getBalancePolicy(); 35 36 public void testBalanceLeaf() { 37 SimpleNode a = new SimpleNode('a', null, null); 38 assertInOrderTraversalIs(getBalancePolicy().balance(nodeFactory, a, null, null), "a"); 39 } 40 41 private SimpleNode balanceNew(char c, @Nullable SimpleNode left, @Nullable SimpleNode right) { 42 return getBalancePolicy().balance(nodeFactory, new SimpleNode(c, null, null), left, right); 43 } 44 45 public void testBalanceTree1() { 46 // b 47 // \ 48 // c 49 SimpleNode c = balanceNew('c', null, null); 50 SimpleNode b = balanceNew('b', null, c); 51 assertInOrderTraversalIs(b, "bc"); 52 } 53 54 public void testBalanceTree2() { 55 // b 56 // / 57 // a 58 SimpleNode a = balanceNew('a', null, null); 59 SimpleNode b = balanceNew('b', a, null); 60 assertInOrderTraversalIs(b, "ab"); 61 } 62 63 public void testBalanceTree3() { 64 // b 65 // / \ 66 // a c 67 SimpleNode a = balanceNew('a', null, null); 68 SimpleNode c = balanceNew('c', null, null); 69 SimpleNode b = balanceNew('b', a, c); 70 assertInOrderTraversalIs(b, "abc"); 71 } 72 73 public void testBalanceTree4() { 74 // a 75 // \ 76 // b 77 // \ 78 // c 79 // \ 80 // d 81 // \ 82 // e 83 // \ 84 // f 85 86 SimpleNode f = balanceNew('f', null, null); 87 SimpleNode e = balanceNew('e', null, f); 88 SimpleNode d = balanceNew('d', null, e); 89 SimpleNode c = balanceNew('c', null, d); 90 SimpleNode b = balanceNew('b', null, c); 91 SimpleNode a = balanceNew('a', null, b); 92 assertInOrderTraversalIs(a, "abcdef"); 93 } 94 95 public void testBalanceTree5() { 96 // f 97 // / 98 // e 99 // / 100 // d 101 // / 102 // c 103 // / 104 // b 105 // / 106 // a 107 SimpleNode a = balanceNew('a', null, null); 108 SimpleNode b = balanceNew('b', a, null); 109 SimpleNode c = balanceNew('c', b, null); 110 SimpleNode d = balanceNew('d', c, null); 111 SimpleNode e = balanceNew('e', d, null); 112 SimpleNode f = balanceNew('f', e, null); 113 assertInOrderTraversalIs(f, "abcdef"); 114 } 115 } 116
