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
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;
20import static com.google.common.collect.BstTesting.extension;
21import static com.google.common.collect.BstTesting.pathToList;
22import static org.junit.contrib.truth.Truth.ASSERT;
23
24import com.google.common.annotations.GwtCompatible;
25import com.google.common.annotations.GwtIncompatible;
26import com.google.common.collect.BstTesting.SimpleNode;
27
28import junit.framework.TestCase;
29
30/**
31 * Tests for {@code BstInOrderPath}.
32 *
33 * @author Louis Wasserman
34 */
35@GwtCompatible(emulated = true)
36public class BstInOrderPathTest extends TestCase {
37  public void testFullTreeRight() {
38    //    d
39    //   / \
40    //  b   f
41    // / \ / \
42    // a c e g
43    SimpleNode a = new SimpleNode('a', null, null);
44    SimpleNode c = new SimpleNode('c', null, null);
45    SimpleNode b = new SimpleNode('b', a, c);
46    SimpleNode e = new SimpleNode('e', null, null);
47    SimpleNode g = new SimpleNode('g', null, null);
48    SimpleNode f = new SimpleNode('f', e, g);
49    SimpleNode d = new SimpleNode('d', b, f);
50    BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory =
51        BstInOrderPath.inOrderFactory();
52    BstInOrderPath<SimpleNode> path = extension(factory, d, LEFT, LEFT);
53    ASSERT.that(pathToList(path)).hasContentsInOrder(a, b, d);
54    path = testNextPathIs(path, b, d);
55    path = testNextPathIs(path, c, b, d);
56    path = testNextPathIs(path, d);
57    path = testNextPathIs(path, e, f, d);
58    path = testNextPathIs(path, f, d);
59    path = testNextPathIs(path, g, f, d);
60    assertFalse(path.hasNext(RIGHT));
61  }
62
63  public void testFullTreeLeft() {
64    //    d
65    //   / \
66    //  b   f
67    // / \ / \
68    // a c e g
69    SimpleNode a = new SimpleNode('a', null, null);
70    SimpleNode c = new SimpleNode('c', null, null);
71    SimpleNode b = new SimpleNode('b', a, c);
72    SimpleNode e = new SimpleNode('e', null, null);
73    SimpleNode g = new SimpleNode('g', null, null);
74    SimpleNode f = new SimpleNode('f', e, g);
75    SimpleNode d = new SimpleNode('d', b, f);
76    BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory =
77        BstInOrderPath.inOrderFactory();
78    BstInOrderPath<SimpleNode> path = extension(factory, d, RIGHT, RIGHT);
79    ASSERT.that(pathToList(path)).hasContentsInOrder(g, f, d);
80    path = testPrevPathIs(path, f, d);
81    path = testPrevPathIs(path, e, f, d);
82    path = testPrevPathIs(path, d);
83    path = testPrevPathIs(path, c, b, d);
84    path = testPrevPathIs(path, b, d);
85    path = testPrevPathIs(path, a, b, d);
86    assertFalse(path.hasNext(LEFT));
87  }
88
89  public void testPartialTree1Right() {
90
91    //    d
92    //   / \
93    //  b   f
94    // /     \
95    // a     g
96    SimpleNode a = new SimpleNode('a', null, null);
97    SimpleNode b = new SimpleNode('b', a, null);
98    SimpleNode g = new SimpleNode('g', null, null);
99    SimpleNode f = new SimpleNode('f', null, g);
100    SimpleNode d = new SimpleNode('d', b, f);
101    BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory =
102        BstInOrderPath.inOrderFactory();
103    BstInOrderPath<SimpleNode> path = extension(factory, d, LEFT, LEFT);
104    ASSERT.that(pathToList(path)).hasContentsInOrder(a, b, d);
105    path = testNextPathIs(path, b, d);
106    path = testNextPathIs(path, d);
107    path = testNextPathIs(path, f, d);
108    path = testNextPathIs(path, g, f, d);
109    assertFalse(path.hasNext(RIGHT));
110  }
111
112  public void testPartialTree1Left() {
113
114    //    d
115    //   / \
116    //  b   f
117    // /     \
118    // a     g
119    SimpleNode a = new SimpleNode('a', null, null);
120    SimpleNode b = new SimpleNode('b', a, null);
121    SimpleNode g = new SimpleNode('g', null, null);
122    SimpleNode f = new SimpleNode('f', null, g);
123    SimpleNode d = new SimpleNode('d', b, f);
124    BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory =
125        BstInOrderPath.inOrderFactory();
126    BstInOrderPath<SimpleNode> path = extension(factory, d, RIGHT, RIGHT);
127    ASSERT.that(pathToList(path)).hasContentsInOrder(g, f, d);
128    path = testPrevPathIs(path, f, d);
129    path = testPrevPathIs(path, d);
130    path = testPrevPathIs(path, b, d);
131    path = testPrevPathIs(path, a, b, d);
132    assertFalse(path.hasNext(LEFT));
133  }
134
135  public void testPartialTree2Right() {
136    //    d
137    //   / \
138    //  b   f
139    //   \ /
140    //   c e
141    SimpleNode c = new SimpleNode('c', null, null);
142    SimpleNode b = new SimpleNode('b', null, c);
143    SimpleNode e = new SimpleNode('e', null, null);
144    SimpleNode f = new SimpleNode('f', e, null);
145    SimpleNode d = new SimpleNode('d', b, f);
146    BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory =
147        BstInOrderPath.inOrderFactory();
148    BstInOrderPath<SimpleNode> path = extension(factory, d, LEFT);
149    ASSERT.that(pathToList(path)).hasContentsInOrder(b, d);
150    path = testNextPathIs(path, c, b, d);
151    path = testNextPathIs(path, d);
152    path = testNextPathIs(path, e, f, d);
153    path = testNextPathIs(path, f, d);
154    assertFalse(path.hasNext(RIGHT));
155  }
156
157  public void testPartialTree2Left() {
158    //    d
159    //   / \
160    //  b   f
161    //   \ /
162    //   c e
163    SimpleNode c = new SimpleNode('c', null, null);
164    SimpleNode b = new SimpleNode('b', null, c);
165    SimpleNode e = new SimpleNode('e', null, null);
166    SimpleNode f = new SimpleNode('f', e, null);
167    SimpleNode d = new SimpleNode('d', b, f);
168    BstPathFactory<SimpleNode, BstInOrderPath<SimpleNode>> factory =
169        BstInOrderPath.inOrderFactory();
170    BstInOrderPath<SimpleNode> path = extension(factory, d, RIGHT);
171    ASSERT.that(pathToList(path)).hasContentsInOrder(f, d);
172    path = testPrevPathIs(path, e,f,d);
173    path = testPrevPathIs(path, d);
174    path = testPrevPathIs(path, c,b, d);
175    path = testPrevPathIs(path, b, d);
176    assertFalse(path.hasNext(LEFT));
177  }
178
179  private static BstInOrderPath<SimpleNode> testNextPathIs(
180      BstInOrderPath<SimpleNode> path, SimpleNode... nodes) {
181    assertTrue(path.hasNext(RIGHT));
182    path = path.next(RIGHT);
183    ASSERT.that(pathToList(path)).hasContentsInOrder(nodes);
184    return path;
185  }
186
187  private static BstInOrderPath<SimpleNode> testPrevPathIs(
188      BstInOrderPath<SimpleNode> path, SimpleNode... nodes) {
189    assertTrue(path.hasNext(LEFT));
190    path = path.next(LEFT);
191    ASSERT.that(pathToList(path)).hasContentsInOrder(nodes);
192    return path;
193  }
194
195  @GwtIncompatible("NullPointerTester")
196  public void testNullPointers() throws Exception {
197    defaultNullPointerTester().testAllPublicStaticMethods(BstInOrderPath.class);
198  }
199}
200