1 /* 2 * Copyright (C) 2012 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.truth.Truth.assertThat; 18 19 import com.google.common.annotations.GwtIncompatible; 20 import com.google.common.collect.testing.NavigableSetTestSuiteBuilder; 21 import com.google.common.collect.testing.SampleElements; 22 import com.google.common.collect.testing.TestSetGenerator; 23 import com.google.common.collect.testing.features.CollectionFeature; 24 import com.google.common.collect.testing.features.CollectionSize; 25 import com.google.common.testing.SerializableTester; 26 27 import junit.framework.Test; 28 import junit.framework.TestSuite; 29 30 import java.math.BigInteger; 31 import java.util.List; 32 import java.util.Set; 33 34 /** 35 * Tests for {@link ImmutableRangeSet}. 36 * 37 * @author Louis Wasserman 38 */ 39 @GwtIncompatible("ImmutableRangeSet") 40 public class ImmutableRangeSetTest extends AbstractRangeSetTest { 41 @SuppressWarnings("unchecked") // varargs 42 private static final ImmutableSet<Range<Integer>> RANGES = ImmutableSet.of( 43 Range.<Integer>all(), 44 Range.closedOpen(3, 5), 45 Range.singleton(1), 46 Range.lessThan(2), 47 Range.greaterThan(10), 48 Range.atMost(4), 49 Range.atLeast(3), 50 Range.closed(4, 6), 51 Range.closedOpen(1, 3), 52 Range.openClosed(5, 7), 53 Range.open(3, 4)); 54 55 static final class ImmutableRangeSetIntegerAsSetGenerator implements TestSetGenerator<Integer> { 56 @Override 57 public SampleElements<Integer> samples() { 58 return new SampleElements<Integer>(1, 4, 3, 2, 5); 59 } 60 61 @Override 62 public Integer[] createArray(int length) { 63 return new Integer[length]; 64 } 65 66 @Override 67 public Iterable<Integer> order(List<Integer> insertionOrder) { 68 return Ordering.natural().sortedCopy(insertionOrder); 69 } 70 71 @Override 72 public Set<Integer> create(Object... elements) { 73 ImmutableRangeSet.Builder<Integer> builder = ImmutableRangeSet.builder(); 74 for (Object o : elements) { 75 Integer i = (Integer) o; 76 builder.add(Range.singleton(i)); 77 } 78 return builder.build().asSet(DiscreteDomain.integers()); 79 } 80 } 81 82 static final class ImmutableRangeSetBigIntegerAsSetGenerator 83 implements TestSetGenerator<BigInteger> { 84 @Override 85 public SampleElements<BigInteger> samples() { 86 return new SampleElements<BigInteger>( 87 BigInteger.valueOf(1), 88 BigInteger.valueOf(4), 89 BigInteger.valueOf(3), 90 BigInteger.valueOf(2), 91 BigInteger.valueOf(5)); 92 } 93 94 @Override 95 public BigInteger[] createArray(int length) { 96 return new BigInteger[length]; 97 } 98 99 @Override 100 public Iterable<BigInteger> order(List<BigInteger> insertionOrder) { 101 return Ordering.natural().sortedCopy(insertionOrder); 102 } 103 104 @Override 105 public Set<BigInteger> create(Object... elements) { 106 ImmutableRangeSet.Builder<BigInteger> builder = ImmutableRangeSet.builder(); 107 for (Object o : elements) { 108 BigInteger i = (BigInteger) o; 109 builder.add(Range.closedOpen(i, i.add(BigInteger.ONE))); 110 } 111 return builder.build().asSet(DiscreteDomain.bigIntegers()); 112 } 113 } 114 115 public static Test suite() { 116 TestSuite suite = new TestSuite(); 117 suite.addTestSuite(ImmutableRangeSetTest.class); 118 suite.addTest(NavigableSetTestSuiteBuilder.using(new ImmutableRangeSetIntegerAsSetGenerator()) 119 .named("ImmutableRangeSet.asSet[DiscreteDomain.integers[]]") 120 .withFeatures( 121 CollectionSize.ANY, 122 CollectionFeature.REJECTS_DUPLICATES_AT_CREATION, 123 CollectionFeature.ALLOWS_NULL_QUERIES, 124 CollectionFeature.KNOWN_ORDER, 125 CollectionFeature.NON_STANDARD_TOSTRING, 126 CollectionFeature.SERIALIZABLE) 127 .createTestSuite()); 128 129 suite.addTest(NavigableSetTestSuiteBuilder.using( 130 new ImmutableRangeSetBigIntegerAsSetGenerator()) 131 .named("ImmutableRangeSet.asSet[DiscreteDomain.bigIntegers[]]") 132 .withFeatures( 133 CollectionSize.ANY, 134 CollectionFeature.REJECTS_DUPLICATES_AT_CREATION, 135 CollectionFeature.ALLOWS_NULL_QUERIES, 136 CollectionFeature.KNOWN_ORDER, 137 CollectionFeature.NON_STANDARD_TOSTRING, 138 CollectionFeature.SERIALIZABLE) 139 .createTestSuite()); 140 return suite; 141 } 142 143 public void testEmpty() { 144 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.of(); 145 146 assertThat(rangeSet.asRanges()).isEmpty(); 147 assertEquals(ImmutableRangeSet.<Integer>all(), rangeSet.complement()); 148 assertFalse(rangeSet.contains(0)); 149 assertFalse(rangeSet.encloses(Range.singleton(0))); 150 assertTrue(rangeSet.enclosesAll(rangeSet)); 151 assertTrue(rangeSet.isEmpty()); 152 } 153 154 public void testAll() { 155 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.all(); 156 157 assertThat(rangeSet.asRanges()).has().item(Range.<Integer>all()); 158 assertTrue(rangeSet.contains(0)); 159 assertTrue(rangeSet.encloses(Range.<Integer>all())); 160 assertTrue(rangeSet.enclosesAll(rangeSet)); 161 assertEquals(ImmutableRangeSet.<Integer>of(), rangeSet.complement()); 162 } 163 164 public void testSingleBoundedRange() { 165 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.of(Range.closedOpen(1, 5)); 166 167 assertThat(rangeSet.asRanges()).has().item(Range.closedOpen(1, 5)); 168 169 assertTrue(rangeSet.encloses(Range.closed(3, 4))); 170 assertTrue(rangeSet.encloses(Range.closedOpen(1, 4))); 171 assertTrue(rangeSet.encloses(Range.closedOpen(1, 5))); 172 assertFalse(rangeSet.encloses(Range.greaterThan(2))); 173 174 assertTrue(rangeSet.contains(3)); 175 assertFalse(rangeSet.contains(5)); 176 assertFalse(rangeSet.contains(0)); 177 178 RangeSet<Integer> expectedComplement = TreeRangeSet.create(); 179 expectedComplement.add(Range.lessThan(1)); 180 expectedComplement.add(Range.atLeast(5)); 181 182 assertEquals(expectedComplement, rangeSet.complement()); 183 } 184 185 public void testSingleBoundedBelowRange() { 186 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.of(Range.greaterThan(2)); 187 188 assertThat(rangeSet.asRanges()).has().item(Range.greaterThan(2)); 189 190 assertTrue(rangeSet.encloses(Range.closed(3, 4))); 191 assertTrue(rangeSet.encloses(Range.greaterThan(3))); 192 assertFalse(rangeSet.encloses(Range.closedOpen(1, 5))); 193 194 assertTrue(rangeSet.contains(3)); 195 assertTrue(rangeSet.contains(5)); 196 assertFalse(rangeSet.contains(0)); 197 assertFalse(rangeSet.contains(2)); 198 199 assertEquals(ImmutableRangeSet.of(Range.atMost(2)), rangeSet.complement()); 200 } 201 202 public void testSingleBoundedAboveRange() { 203 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.of(Range.atMost(3)); 204 205 assertThat(rangeSet.asRanges()).has().item(Range.atMost(3)); 206 207 assertTrue(rangeSet.encloses(Range.closed(2, 3))); 208 assertTrue(rangeSet.encloses(Range.lessThan(1))); 209 assertFalse(rangeSet.encloses(Range.closedOpen(1, 5))); 210 211 assertTrue(rangeSet.contains(3)); 212 assertTrue(rangeSet.contains(0)); 213 assertFalse(rangeSet.contains(4)); 214 assertFalse(rangeSet.contains(5)); 215 216 assertEquals(ImmutableRangeSet.of(Range.greaterThan(3)), rangeSet.complement()); 217 } 218 219 public void testMultipleBoundedRanges() { 220 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 221 .add(Range.closed(5, 8)).add(Range.closedOpen(1, 3)).build(); 222 223 assertThat(rangeSet.asRanges()) 224 .has().exactly(Range.closedOpen(1, 3), Range.closed(5, 8)).inOrder(); 225 226 assertTrue(rangeSet.encloses(Range.closed(1, 2))); 227 assertTrue(rangeSet.encloses(Range.open(5, 8))); 228 assertFalse(rangeSet.encloses(Range.closed(1, 8))); 229 assertFalse(rangeSet.encloses(Range.greaterThan(5))); 230 231 RangeSet<Integer> expectedComplement = ImmutableRangeSet.<Integer>builder() 232 .add(Range.lessThan(1)) 233 .add(Range.closedOpen(3, 5)) 234 .add(Range.greaterThan(8)) 235 .build(); 236 237 assertEquals(expectedComplement, rangeSet.complement()); 238 } 239 240 public void testMultipleBoundedBelowRanges() { 241 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 242 .add(Range.greaterThan(6)).add(Range.closedOpen(1, 3)).build(); 243 244 assertThat(rangeSet.asRanges()) 245 .has().exactly(Range.closedOpen(1, 3), Range.greaterThan(6)).inOrder(); 246 247 assertTrue(rangeSet.encloses(Range.closed(1, 2))); 248 assertTrue(rangeSet.encloses(Range.open(6, 8))); 249 assertFalse(rangeSet.encloses(Range.closed(1, 8))); 250 assertFalse(rangeSet.encloses(Range.greaterThan(5))); 251 252 RangeSet<Integer> expectedComplement = ImmutableRangeSet.<Integer>builder() 253 .add(Range.lessThan(1)) 254 .add(Range.closed(3, 6)) 255 .build(); 256 257 assertEquals(expectedComplement, rangeSet.complement()); 258 } 259 260 public void testMultipleBoundedAboveRanges() { 261 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 262 .add(Range.atMost(0)).add(Range.closedOpen(2, 5)).build(); 263 264 assertThat(rangeSet.asRanges()) 265 .has().exactly(Range.atMost(0), Range.closedOpen(2, 5)).inOrder(); 266 267 assertTrue(rangeSet.encloses(Range.closed(2, 4))); 268 assertTrue(rangeSet.encloses(Range.open(-5, -2))); 269 assertFalse(rangeSet.encloses(Range.closed(1, 8))); 270 assertFalse(rangeSet.encloses(Range.greaterThan(5))); 271 272 RangeSet<Integer> expectedComplement = ImmutableRangeSet.<Integer>builder() 273 .add(Range.open(0, 2)) 274 .add(Range.atLeast(5)) 275 .build(); 276 277 assertEquals(expectedComplement, rangeSet.complement()); 278 } 279 280 public void testAddUnsupported() { 281 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 282 .add(Range.closed(5, 8)).add(Range.closedOpen(1, 3)).build(); 283 284 try { 285 rangeSet.add(Range.open(3, 4)); 286 fail(); 287 } catch (UnsupportedOperationException expected) { 288 // success 289 } 290 } 291 292 public void testAddAllUnsupported() { 293 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 294 .add(Range.closed(5, 8)).add(Range.closedOpen(1, 3)).build(); 295 296 try { 297 rangeSet.addAll(ImmutableRangeSet.<Integer>of()); 298 fail(); 299 } catch (UnsupportedOperationException expected) { 300 // success 301 } 302 } 303 304 public void testRemoveUnsupported() { 305 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 306 .add(Range.closed(5, 8)).add(Range.closedOpen(1, 3)).build(); 307 308 try { 309 rangeSet.remove(Range.closed(6, 7)); 310 fail(); 311 } catch (UnsupportedOperationException expected) { 312 // success 313 } 314 } 315 316 public void testRemoveAllUnsupported() { 317 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 318 .add(Range.closed(5, 8)).add(Range.closedOpen(1, 3)).build(); 319 320 try { 321 rangeSet.removeAll(ImmutableRangeSet.<Integer>of()); 322 fail(); 323 } catch (UnsupportedOperationException expected) { 324 // success 325 } 326 327 try { 328 rangeSet.removeAll(ImmutableRangeSet.of(Range.closed(6, 8))); 329 fail(); 330 } catch (UnsupportedOperationException expected) { 331 // success 332 } 333 } 334 335 public void testExhaustive() { 336 @SuppressWarnings("unchecked") 337 ImmutableSet<Range<Integer>> ranges = ImmutableSet.of( 338 Range.<Integer>all(), 339 Range.<Integer>closedOpen(3, 5), 340 Range.singleton(1), 341 Range.lessThan(2), 342 Range.greaterThan(10), 343 Range.atMost(4), 344 Range.atLeast(3), 345 Range.closed(4, 6), 346 Range.closedOpen(1, 3), 347 Range.openClosed(5, 7), 348 Range.open(3, 4)); 349 for (Set<Range<Integer>> subset : Sets.powerSet(ranges)) { 350 RangeSet<Integer> mutable = TreeRangeSet.create(); 351 ImmutableRangeSet.Builder<Integer> builder = ImmutableRangeSet.builder(); 352 353 int expectedRanges = 0; 354 for (Range<Integer> range : subset) { 355 boolean overlaps = false; 356 for (Range<Integer> other : mutable.asRanges()) { 357 if (other.isConnected(range) && !other.intersection(range).isEmpty()) { 358 overlaps = true; 359 } 360 } 361 362 try { 363 builder.add(range); 364 assertFalse(overlaps); 365 mutable.add(range); 366 } catch (IllegalArgumentException e) { 367 assertTrue(overlaps); 368 } 369 } 370 371 ImmutableRangeSet<Integer> built = builder.build(); 372 assertEquals(mutable, built); 373 assertEquals(ImmutableRangeSet.copyOf(mutable), built); 374 assertEquals(mutable.complement(), built.complement()); 375 376 for (int i = 0; i <= 11; i++) { 377 assertEquals(mutable.contains(i), built.contains(i)); 378 } 379 380 SerializableTester.reserializeAndAssert(built); 381 } 382 } 383 384 public void testAsSet() { 385 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 386 .add(Range.closed(2, 4)) 387 .add(Range.open(6, 7)) 388 .add(Range.closedOpen(8, 10)) 389 .add(Range.openClosed(15, 17)) 390 .build(); 391 ImmutableSortedSet<Integer> expectedSet = ImmutableSortedSet.of(2, 3, 4, 8, 9, 16, 17); 392 ImmutableSortedSet<Integer> asSet = rangeSet.asSet(DiscreteDomain.integers()); 393 assertEquals(expectedSet, asSet); 394 assertThat(asSet).has().exactlyAs(expectedSet).inOrder(); 395 assertTrue(asSet.containsAll(expectedSet)); 396 SerializableTester.reserializeAndAssert(asSet); 397 } 398 399 public void testAsSetHeadSet() { 400 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 401 .add(Range.closed(2, 4)) 402 .add(Range.open(6, 7)) 403 .add(Range.closedOpen(8, 10)) 404 .add(Range.openClosed(15, 17)) 405 .build(); 406 407 ImmutableSortedSet<Integer> expectedSet = ImmutableSortedSet.of(2, 3, 4, 8, 9, 16, 17); 408 ImmutableSortedSet<Integer> asSet = rangeSet.asSet(DiscreteDomain.integers()); 409 410 for (int i = 0; i <= 20; i++) { 411 assertEquals(asSet.headSet(i, false), expectedSet.headSet(i, false)); 412 assertEquals(asSet.headSet(i, true), expectedSet.headSet(i, true)); 413 } 414 } 415 416 public void testAsSetTailSet() { 417 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 418 .add(Range.closed(2, 4)) 419 .add(Range.open(6, 7)) 420 .add(Range.closedOpen(8, 10)) 421 .add(Range.openClosed(15, 17)) 422 .build(); 423 424 ImmutableSortedSet<Integer> expectedSet = ImmutableSortedSet.of(2, 3, 4, 8, 9, 16, 17); 425 ImmutableSortedSet<Integer> asSet = rangeSet.asSet(DiscreteDomain.integers()); 426 427 for (int i = 0; i <= 20; i++) { 428 assertEquals(asSet.tailSet(i, false), expectedSet.tailSet(i, false)); 429 assertEquals(asSet.tailSet(i, true), expectedSet.tailSet(i, true)); 430 } 431 } 432 433 public void testAsSetSubSet() { 434 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 435 .add(Range.closed(2, 4)) 436 .add(Range.open(6, 7)) 437 .add(Range.closedOpen(8, 10)) 438 .add(Range.openClosed(15, 17)) 439 .build(); 440 441 ImmutableSortedSet<Integer> expectedSet = ImmutableSortedSet.of(2, 3, 4, 8, 9, 16, 17); 442 ImmutableSortedSet<Integer> asSet = rangeSet.asSet(DiscreteDomain.integers()); 443 444 for (int i = 0; i <= 20; i++) { 445 for (int j = i + 1; j <= 20; j++) { 446 assertEquals(expectedSet.subSet(i, false, j, false), 447 asSet.subSet(i, false, j, false)); 448 assertEquals(expectedSet.subSet(i, true, j, false), 449 asSet.subSet(i, true, j, false)); 450 assertEquals(expectedSet.subSet(i, false, j, true), 451 asSet.subSet(i, false, j, true)); 452 assertEquals(expectedSet.subSet(i, true, j, true), 453 asSet.subSet(i, true, j, true)); 454 } 455 } 456 } 457 458 public void testSubRangeSet() { 459 ImmutableList.Builder<Range<Integer>> rangesBuilder = ImmutableList.builder(); 460 rangesBuilder.add(Range.<Integer>all()); 461 for (int i = -2; i <= 2; i++) { 462 for (BoundType boundType : BoundType.values()) { 463 rangesBuilder.add(Range.upTo(i, boundType)); 464 rangesBuilder.add(Range.downTo(i, boundType)); 465 } 466 for (int j = i + 1; j <= 2; j++) { 467 for (BoundType lbType : BoundType.values()) { 468 for (BoundType ubType : BoundType.values()) { 469 rangesBuilder.add(Range.range(i, lbType, j, ubType)); 470 } 471 } 472 } 473 } 474 ImmutableList<Range<Integer>> ranges = rangesBuilder.build(); 475 for (int i = -2; i <= 2; i++) { 476 rangesBuilder.add(Range.closedOpen(i, i)); 477 rangesBuilder.add(Range.openClosed(i, i)); 478 } 479 ImmutableList<Range<Integer>> subRanges = rangesBuilder.build(); 480 for (Range<Integer> range1 : ranges) { 481 for (Range<Integer> range2 : ranges) { 482 if (!range1.isConnected(range2) || range1.intersection(range2).isEmpty()) { 483 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder() 484 .add(range1) 485 .add(range2) 486 .build(); 487 for (Range<Integer> subRange : subRanges) { 488 RangeSet<Integer> expected = TreeRangeSet.create(); 489 for (Range<Integer> range : rangeSet.asRanges()) { 490 if (range.isConnected(subRange)) { 491 expected.add(range.intersection(subRange)); 492 } 493 } 494 ImmutableRangeSet<Integer> subRangeSet = rangeSet.subRangeSet(subRange); 495 assertEquals(expected, subRangeSet); 496 assertEquals(expected.asRanges(), subRangeSet.asRanges()); 497 if (!expected.isEmpty()) { 498 assertEquals(expected.span(), subRangeSet.span()); 499 } 500 for (int i = -3; i <= 3; i++) { 501 assertEquals(expected.contains(i), subRangeSet.contains(i)); 502 } 503 } 504 } 505 } 506 } 507 } 508 } 509
