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.BoundType.CLOSED; 18 import static com.google.common.collect.BoundType.OPEN; 19 import static com.google.common.collect.BstSide.LEFT; 20 import static com.google.common.collect.BstSide.RIGHT; 21 import static com.google.common.collect.BstTesting.assertInOrderTraversalIs; 22 import static com.google.common.collect.BstTesting.balancePolicy; 23 import static com.google.common.collect.BstTesting.countAggregate; 24 import static com.google.common.collect.BstTesting.defaultNullPointerTester; 25 import static com.google.common.collect.BstTesting.nodeFactory; 26 import static com.google.common.collect.BstTesting.pathFactory; 27 import static com.google.common.collect.BstTesting.pathToList; 28 import static org.junit.contrib.truth.Truth.ASSERT; 29 30 import com.google.common.annotations.GwtCompatible; 31 import com.google.common.annotations.GwtIncompatible; 32 import com.google.common.collect.BstTesting.SimpleNode; 33 34 import junit.framework.TestCase; 35 36 import java.util.SortedSet; 37 38 /** 39 * Tests for {@code BSTRangeOps}. 40 * 41 * @author Louis Wasserman 42 */ 43 @GwtCompatible(emulated = true) 44 public class BstRangeOpsTest extends TestCase { 45 private static final SortedSet<Character> MODEL = 46 ImmutableSortedSet.of('a', 'b', 'c', 'd', 'e', 'f', 'g'); 47 private static final SimpleNode ROOT; 48 49 static { 50 SimpleNode a = new SimpleNode('a', null, null); 51 SimpleNode c = new SimpleNode('c', null, null); 52 SimpleNode b = new SimpleNode('b', a, c); 53 SimpleNode e = new SimpleNode('e', null, null); 54 SimpleNode g = new SimpleNode('g', null, null); 55 SimpleNode f = new SimpleNode('f', e, g); 56 SimpleNode d = new SimpleNode('d', b, f); 57 ROOT = d; 58 } 59 60 public void testCountInRangeLowerBound() { 61 for (char c : "abcdefg".toCharArray()) { 62 for (BoundType type : BoundType.values()) { 63 long count = BstRangeOps.totalInRange( 64 countAggregate, GeneralRange.downTo(Ordering.natural(), c, type), ROOT); 65 char d = c; 66 if (type == BoundType.OPEN) { 67 d++; 68 } 69 assertEquals(MODEL.tailSet(d).size(), count); 70 } 71 } 72 } 73 74 public void testCountInRangeUpperBound() { 75 for (char c : "abcdefg".toCharArray()) { 76 for (BoundType type : BoundType.values()) { 77 long count = BstRangeOps.totalInRange( 78 countAggregate, GeneralRange.upTo(Ordering.natural(), c, type), ROOT); 79 char d = c; 80 if (type == BoundType.CLOSED) { 81 d++; 82 } 83 assertEquals(MODEL.headSet(d).size(), count); 84 } 85 } 86 } 87 88 public void testCountInRangeBothBounds() { 89 String chars = "abcdefg"; 90 for (int i = 0; i < chars.length(); i++) { 91 for (BoundType lb : BoundType.values()) { 92 for (int j = i; j < chars.length(); j++) { 93 for (BoundType ub : BoundType.values()) { 94 if (i == j && lb == BoundType.OPEN && ub == BoundType.OPEN) { 95 continue; 96 } 97 long count = BstRangeOps.totalInRange(countAggregate, GeneralRange.range( 98 Ordering.natural(), chars.charAt(i), lb, chars.charAt(j), ub), ROOT); 99 char lo = chars.charAt(i); 100 if (lb == BoundType.OPEN) { 101 lo++; 102 } 103 char hi = chars.charAt(j); 104 if (ub == BoundType.CLOSED) { 105 hi++; 106 } 107 if (lo > hi) { 108 lo = hi; 109 } 110 assertEquals(MODEL.subSet(lo, hi).size(), count); 111 } 112 } 113 } 114 } 115 } 116 117 public void testCountInRangeAll() { 118 assertEquals(MODEL.size(), BstRangeOps.totalInRange( 119 countAggregate, GeneralRange.<Character>all(Ordering.natural()), ROOT)); 120 } 121 122 public void testCountInRangeEmpty() { 123 SimpleNode empty = null; 124 GeneralRange<Character> range = GeneralRange.all(Ordering.natural()); 125 assertEquals(0, BstRangeOps.totalInRange(countAggregate, range, empty)); 126 } 127 128 public void testClearRangeLowerBound() { 129 // d 130 // / \ 131 // b f 132 // / / \ 133 // a e g 134 SimpleNode a = new SimpleNode('a', null, null); 135 SimpleNode b = new SimpleNode('b', a, null); 136 SimpleNode e = new SimpleNode('e', null, null); 137 SimpleNode g = new SimpleNode('g', null, null); 138 SimpleNode f = new SimpleNode('f', e, g); 139 SimpleNode d = new SimpleNode('d', b, f); 140 141 assertInOrderTraversalIs(d, "abdefg"); 142 GeneralRange<Character> range1 = GeneralRange.downTo(Ordering.natural(), 'f', CLOSED); 143 testTraversalAfterClearingRangeIs(d, range1, "abde"); 144 145 GeneralRange<Character> range2 = GeneralRange.downTo(Ordering.natural(), 'f', OPEN); 146 testTraversalAfterClearingRangeIs(d, range2, "abdef"); 147 148 GeneralRange<Character> range3 = GeneralRange.downTo(Ordering.natural(), 'a', CLOSED); 149 testTraversalAfterClearingRangeIs(d, range3, ""); 150 151 GeneralRange<Character> range4 = GeneralRange.downTo(Ordering.natural(), 'a', OPEN); 152 testTraversalAfterClearingRangeIs(d, range4, "a"); 153 154 GeneralRange<Character> range5 = GeneralRange.downTo(Ordering.natural(), 'c', OPEN); 155 testTraversalAfterClearingRangeIs(d, range5, "ab"); 156 157 GeneralRange<Character> range6 = GeneralRange.downTo(Ordering.natural(), 'c', CLOSED); 158 testTraversalAfterClearingRangeIs(d, range6, "ab"); 159 } 160 161 public void testClearRangeUpperBound() { 162 // d 163 // / \ 164 // b f 165 // / / \ 166 // a e g 167 SimpleNode a = new SimpleNode('a', null, null); 168 SimpleNode b = new SimpleNode('b', a, null); 169 SimpleNode e = new SimpleNode('e', null, null); 170 SimpleNode g = new SimpleNode('g', null, null); 171 SimpleNode f = new SimpleNode('f', e, g); 172 SimpleNode d = new SimpleNode('d', b, f); 173 174 assertInOrderTraversalIs(d, "abdefg"); 175 GeneralRange<Character> range1 = GeneralRange.upTo(Ordering.natural(), 'f', CLOSED); 176 testTraversalAfterClearingRangeIs(d, range1, "g"); 177 178 GeneralRange<Character> range2 = GeneralRange.upTo(Ordering.natural(), 'f', OPEN); 179 testTraversalAfterClearingRangeIs(d, range2, "fg"); 180 181 GeneralRange<Character> range3 = GeneralRange.upTo(Ordering.natural(), 'a', CLOSED); 182 testTraversalAfterClearingRangeIs(d, range3, "bdefg"); 183 184 GeneralRange<Character> range4 = GeneralRange.upTo(Ordering.natural(), 'a', OPEN); 185 testTraversalAfterClearingRangeIs(d, range4, "abdefg"); 186 187 GeneralRange<Character> range5 = GeneralRange.upTo(Ordering.natural(), 'c', OPEN); 188 testTraversalAfterClearingRangeIs(d, range5, "defg"); 189 190 GeneralRange<Character> range6 = GeneralRange.upTo(Ordering.natural(), 'c', CLOSED); 191 testTraversalAfterClearingRangeIs(d, range6, "defg"); 192 } 193 194 public void testClearRangeDoublyBounded() { 195 // d 196 // / \ 197 // b f 198 // / \ / \ 199 // a c e g 200 SimpleNode a = new SimpleNode('a', null, null); 201 SimpleNode c = new SimpleNode('c', null, null); 202 SimpleNode b = new SimpleNode('b', a, c); 203 SimpleNode e = new SimpleNode('e', null, null); 204 SimpleNode g = new SimpleNode('g', null, null); 205 SimpleNode f = new SimpleNode('f', e, g); 206 SimpleNode d = new SimpleNode('d', b, f); 207 208 GeneralRange<Character> range1 = 209 GeneralRange.range(Ordering.natural(), 'c', OPEN, 'f', CLOSED); 210 testTraversalAfterClearingRangeIs(d, range1, "abcg"); 211 212 GeneralRange<Character> range2 = 213 GeneralRange.range(Ordering.natural(), 'a', CLOSED, 'h', OPEN); 214 testTraversalAfterClearingRangeIs(d, range2, ""); 215 216 } 217 218 public void testClearRangeAll() { 219 // d 220 // / \ 221 // b f 222 // / \ / \ 223 // a c e g 224 SimpleNode a = new SimpleNode('a', null, null); 225 SimpleNode c = new SimpleNode('c', null, null); 226 SimpleNode b = new SimpleNode('b', a, c); 227 SimpleNode e = new SimpleNode('e', null, null); 228 SimpleNode g = new SimpleNode('g', null, null); 229 SimpleNode f = new SimpleNode('f', e, g); 230 SimpleNode d = new SimpleNode('d', b, f); 231 232 testTraversalAfterClearingRangeIs(d, GeneralRange.<Character>all(Ordering.natural()), ""); 233 } 234 235 private void testTraversalAfterClearingRangeIs( 236 SimpleNode d, GeneralRange<Character> range, String expected) { 237 assertInOrderTraversalIs( 238 BstRangeOps.minusRange(range, balancePolicy, nodeFactory, d), expected); 239 } 240 241 public void testLeftmostPathAll() { 242 // d 243 // / \ 244 // b f 245 // \ / \ 246 // c e g 247 SimpleNode c = new SimpleNode('c', null, null); 248 SimpleNode b = new SimpleNode('b', null, c); 249 SimpleNode e = new SimpleNode('e', null, null); 250 SimpleNode g = new SimpleNode('g', null, null); 251 SimpleNode f = new SimpleNode('f', e, g); 252 SimpleNode d = new SimpleNode('d', b, f); 253 254 GeneralRange<Character> range1 = GeneralRange.all(Ordering.natural()); 255 ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, LEFT, pathFactory, d))) 256 .hasContentsInOrder(b, d); 257 258 assertNull(BstRangeOps.furthestPath(range1, LEFT, pathFactory, null)); 259 } 260 261 public void testLeftmostPathDownTo() { 262 // d 263 // / \ 264 // b f 265 // \ / \ 266 // c e g 267 SimpleNode c = new SimpleNode('c', null, null); 268 SimpleNode b = new SimpleNode('b', null, c); 269 SimpleNode e = new SimpleNode('e', null, null); 270 SimpleNode g = new SimpleNode('g', null, null); 271 SimpleNode f = new SimpleNode('f', e, g); 272 SimpleNode d = new SimpleNode('d', b, f); 273 274 GeneralRange<Character> range1 = GeneralRange.downTo(Ordering.natural(), 'd', OPEN); 275 ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, LEFT, pathFactory, d))) 276 .hasContentsInOrder(e, f, d); 277 278 GeneralRange<Character> range2 = GeneralRange.downTo(Ordering.natural(), 'd', CLOSED); 279 ASSERT.that(pathToList(BstRangeOps.furthestPath(range2, LEFT, pathFactory, d))) 280 .hasContentsInOrder(d); 281 282 GeneralRange<Character> range3 = GeneralRange.downTo(Ordering.natural(), 'a', CLOSED); 283 ASSERT.that(pathToList(BstRangeOps.furthestPath(range3, LEFT, pathFactory, d))) 284 .hasContentsInOrder(b, d); 285 286 GeneralRange<Character> range4 = GeneralRange.downTo(Ordering.natural(), 'h', CLOSED); 287 assertNull(BstRangeOps.furthestPath(range4, LEFT, pathFactory, d)); 288 } 289 290 public void testLeftmostPathUpTo() { 291 // d 292 // / \ 293 // b f 294 // \ / \ 295 // c e g 296 SimpleNode c = new SimpleNode('c', null, null); 297 SimpleNode b = new SimpleNode('b', null, c); 298 SimpleNode e = new SimpleNode('e', null, null); 299 SimpleNode g = new SimpleNode('g', null, null); 300 SimpleNode f = new SimpleNode('f', e, g); 301 SimpleNode d = new SimpleNode('d', b, f); 302 303 GeneralRange<Character> range1 = GeneralRange.upTo(Ordering.natural(), 'd', OPEN); 304 ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, LEFT, pathFactory, d))) 305 .hasContentsInOrder(b, d); 306 307 GeneralRange<Character> range2 = GeneralRange.upTo(Ordering.natural(), 'd', CLOSED); 308 ASSERT.that(pathToList(BstRangeOps.furthestPath(range2, LEFT, pathFactory, d))) 309 .hasContentsInOrder(b, d); 310 311 GeneralRange<Character> range3 = GeneralRange.upTo(Ordering.natural(), 'a', CLOSED); 312 assertNull(BstRangeOps.furthestPath(range3, LEFT, pathFactory, d)); 313 } 314 315 public void testRightmostPathAll() { 316 // d 317 // / \ 318 // b f 319 // \ / \ 320 // c e g 321 SimpleNode c = new SimpleNode('c', null, null); 322 SimpleNode b = new SimpleNode('b', null, c); 323 SimpleNode e = new SimpleNode('e', null, null); 324 SimpleNode g = new SimpleNode('g', null, null); 325 SimpleNode f = new SimpleNode('f', e, g); 326 SimpleNode d = new SimpleNode('d', b, f); 327 328 GeneralRange<Character> range1 = GeneralRange.all(Ordering.natural()); 329 ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, RIGHT, pathFactory, d))) 330 .hasContentsInOrder(g, f, d); 331 332 assertNull(BstRangeOps.furthestPath(range1, RIGHT, pathFactory, null)); 333 } 334 335 public void testRightmostPathDownTo() { 336 // d 337 // / \ 338 // b f 339 // \ / \ 340 // c e g 341 SimpleNode c = new SimpleNode('c', null, null); 342 SimpleNode b = new SimpleNode('b', null, c); 343 SimpleNode e = new SimpleNode('e', null, null); 344 SimpleNode g = new SimpleNode('g', null, null); 345 SimpleNode f = new SimpleNode('f', e, g); 346 SimpleNode d = new SimpleNode('d', b, f); 347 348 GeneralRange<Character> range1 = GeneralRange.downTo(Ordering.natural(), 'd', OPEN); 349 ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, RIGHT, pathFactory, d))) 350 .hasContentsInOrder(g, f, d); 351 352 GeneralRange<Character> range2 = GeneralRange.downTo(Ordering.natural(), 'd', CLOSED); 353 ASSERT.that(pathToList(BstRangeOps.furthestPath(range2, RIGHT, pathFactory, d))) 354 .hasContentsInOrder(g, f, d); 355 356 GeneralRange<Character> range3 = GeneralRange.downTo(Ordering.natural(), 'a', CLOSED); 357 ASSERT.that(pathToList(BstRangeOps.furthestPath(range3, RIGHT, pathFactory, d))) 358 .hasContentsInOrder(g, f, d); 359 360 GeneralRange<Character> range4 = GeneralRange.downTo(Ordering.natural(), 'h', CLOSED); 361 assertNull(BstRangeOps.furthestPath(range4, RIGHT, pathFactory, d)); 362 } 363 364 public void testRightmostPathUpTo() { 365 // d 366 // / \ 367 // b f 368 // \ / \ 369 // c e g 370 SimpleNode c = new SimpleNode('c', null, null); 371 SimpleNode b = new SimpleNode('b', null, c); 372 SimpleNode e = new SimpleNode('e', null, null); 373 SimpleNode g = new SimpleNode('g', null, null); 374 SimpleNode f = new SimpleNode('f', e, g); 375 SimpleNode d = new SimpleNode('d', b, f); 376 377 GeneralRange<Character> range1 = GeneralRange.upTo(Ordering.natural(), 'd', OPEN); 378 ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, RIGHT, pathFactory, d))) 379 .hasContentsInOrder(c, b, d); 380 381 GeneralRange<Character> range2 = GeneralRange.upTo(Ordering.natural(), 'd', CLOSED); 382 ASSERT.that(pathToList(BstRangeOps.furthestPath(range2, RIGHT, pathFactory, d))) 383 .hasContentsInOrder(d); 384 385 GeneralRange<Character> range3 = GeneralRange.upTo(Ordering.natural(), 'a', CLOSED); 386 assertNull(BstRangeOps.furthestPath(range3, RIGHT, pathFactory, d)); 387 388 GeneralRange<Character> range4 = GeneralRange.upTo(Ordering.natural(), 'h', CLOSED); 389 ASSERT.that(pathToList(BstRangeOps.furthestPath(range4, RIGHT, pathFactory, d))) 390 .hasContentsInOrder(g, f, d); 391 } 392 393 @GwtIncompatible("NullPointerTester") 394 public void testNullPointers() throws Exception { 395 defaultNullPointerTester().testAllPublicStaticMethods(BstRangeOps.class); 396 } 397 } 398