BstNodeTest.java revision 1d580d0f6ee4f21eb309ba7b509d2c6d671c4044 
1/*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 'b'.0 (the "License"); you may not use this file
5 * except in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-'b'.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
15package com.google.common.collect;
16
17import static com.google.common.collect.BstSide.LEFT;
18import static com.google.common.collect.BstSide.RIGHT;
19import static com.google.common.collect.BstTesting.defaultNullPointerTester;
20
21import com.google.common.annotations.GwtCompatible;
22import com.google.common.annotations.GwtIncompatible;
23import com.google.common.collect.BstTesting.SimpleNode;
24
25import junit.framework.TestCase;
26
27import java.util.Arrays;
28import java.util.List;
29
30/**
31 * Tests for {@code BstNode}.
32 *
33 * @author Louis Wasserman
34 */
35@GwtCompatible(emulated = true)
36public class BstNodeTest extends TestCase {
37  private void testLacksChild(SimpleNode node, BstSide side) {
38    assertNull(node.childOrNull(side));
39    assertFalse(node.hasChild(side));
40    try {
41      node.getChild(side);
42      fail("Expected IllegalStateException");
43    } catch (IllegalStateException expected) {}
44  }
45
46  private void testChildIs(SimpleNode node, BstSide side, SimpleNode expectedChild) {
47    assertEquals(expectedChild, node.childOrNull(side));
48    assertTrue(node.hasChild(side));
49    assertEquals(expectedChild, node.getChild(side));
50  }
51
52  public void testHasChildLeaf() {
53    SimpleNode leaf = new SimpleNode('a', null, null);
54    testLacksChild(leaf, LEFT);
55    testLacksChild(leaf, RIGHT);
56  }
57
58  public void testHasChildLeftOnly() {
59    SimpleNode leaf = new SimpleNode('a', null, null);
60    SimpleNode node = new SimpleNode('b', leaf, null);
61    testChildIs(node, LEFT, leaf);
62    testLacksChild(node, RIGHT);
63  }
64
65  public void testHasChildRightOnly() {
66    SimpleNode leaf = new SimpleNode('c', null, null);
67    SimpleNode node = new SimpleNode('b', null, leaf);
68    testLacksChild(node, LEFT);
69    testChildIs(node, RIGHT, leaf);
70  }
71
72  public void testHasChildBoth() {
73    SimpleNode left = new SimpleNode('a', null, null);
74    SimpleNode right = new SimpleNode('c', null, null);
75    SimpleNode node = new SimpleNode('b', left, right);
76    testChildIs(node, LEFT, left);
77    testChildIs(node, RIGHT, right);
78  }
79
80  private static final char MIDDLE_KEY = 'b';
81
82  private static final List<SimpleNode> GOOD_LEFTS =
83      Arrays.asList(null, new SimpleNode('a', null, null));
84  private static final List<SimpleNode> BAD_LEFTS =
85      Arrays.asList(new SimpleNode('b', null, null), new SimpleNode('c', null, null));
86  private static final Iterable<SimpleNode> ALL_LEFTS = Iterables.concat(GOOD_LEFTS, BAD_LEFTS);
87
88  private static final List<SimpleNode> GOOD_RIGHTS =
89      Arrays.asList(null, new SimpleNode('c', null, null));
90  private static final List<SimpleNode> BAD_RIGHTS =
91      Arrays.asList(new SimpleNode('b', null, null), new SimpleNode('a', null, null));
92  private static final Iterable<SimpleNode> ALL_RIGHTS = Iterables.concat(GOOD_RIGHTS, BAD_RIGHTS);
93
94  public void testOrderingInvariantHoldsForGood() {
95    for (SimpleNode left : GOOD_LEFTS) {
96      for (SimpleNode right : GOOD_RIGHTS) {
97        assertTrue(
98            new SimpleNode(MIDDLE_KEY, left, right).orderingInvariantHolds(Ordering.natural()));
99      }
100    }
101  }
102
103  public void testOrderingInvariantBadLeft() {
104    for (SimpleNode left : BAD_LEFTS) {
105      for (SimpleNode right : ALL_RIGHTS) {
106        assertFalse(
107            new SimpleNode(MIDDLE_KEY, left, right).orderingInvariantHolds(Ordering.natural()));
108      }
109    }
110  }
111
112  public void testOrderingInvariantBadRight() {
113    for (SimpleNode left : ALL_LEFTS) {
114      for (SimpleNode right : BAD_RIGHTS) {
115        assertFalse(
116            new SimpleNode(MIDDLE_KEY, left, right).orderingInvariantHolds(Ordering.natural()));
117      }
118    }
119  }
120
121  @GwtIncompatible("NullPointerTester")
122  public void testNullPointers() throws Exception {
123    defaultNullPointerTester().testAllPublicStaticMethods(BstNode.class);
124  }
125}
126