1 /* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import static com.google.common.collect.BoundType.CLOSED; 20 import static com.google.common.collect.BoundType.OPEN; 21 import static com.google.common.collect.DiscreteDomain.integers; 22 import static com.google.common.collect.testing.features.CollectionFeature.ALLOWS_NULL_QUERIES; 23 import static com.google.common.collect.testing.features.CollectionFeature.KNOWN_ORDER; 24 import static com.google.common.collect.testing.features.CollectionFeature.NON_STANDARD_TOSTRING; 25 import static com.google.common.collect.testing.features.CollectionFeature.RESTRICTS_ELEMENTS; 26 import static com.google.common.collect.testing.testers.NavigableSetNavigationTester.getHoleMethods; 27 import static com.google.common.testing.SerializableTester.reserialize; 28 import static com.google.common.testing.SerializableTester.reserializeAndAssert; 29 import static com.google.common.truth.Truth.assertThat; 30 31 import com.google.common.annotations.GwtCompatible; 32 import com.google.common.annotations.GwtIncompatible; 33 import com.google.common.collect.testing.NavigableSetTestSuiteBuilder; 34 import com.google.common.collect.testing.features.CollectionSize; 35 import com.google.common.collect.testing.google.SetGenerators.ContiguousSetDescendingGenerator; 36 import com.google.common.collect.testing.google.SetGenerators.ContiguousSetGenerator; 37 import com.google.common.collect.testing.google.SetGenerators.ContiguousSetHeadsetGenerator; 38 import com.google.common.collect.testing.google.SetGenerators.ContiguousSetSubsetGenerator; 39 import com.google.common.collect.testing.google.SetGenerators.ContiguousSetTailsetGenerator; 40 import com.google.common.testing.EqualsTester; 41 import java.util.Collection; 42 import java.util.Set; 43 import junit.framework.Test; 44 import junit.framework.TestCase; 45 import junit.framework.TestSuite; 46 47 /** @author Gregory Kick */ 48 @GwtCompatible(emulated = true) 49 public class ContiguousSetTest extends TestCase { 50 private static final DiscreteDomain<Integer> NOT_EQUAL_TO_INTEGERS = 51 new DiscreteDomain<Integer>() { 52 @Override 53 public Integer next(Integer value) { 54 return integers().next(value); 55 } 56 57 @Override 58 public Integer previous(Integer value) { 59 return integers().previous(value); 60 } 61 62 @Override 63 public long distance(Integer start, Integer end) { 64 return integers().distance(start, end); 65 } 66 67 @Override 68 public Integer minValue() { 69 return integers().minValue(); 70 } 71 72 @Override 73 public Integer maxValue() { 74 return integers().maxValue(); 75 } 76 }; 77 testInvalidIntRange()78 public void testInvalidIntRange() { 79 try { 80 ContiguousSet.closed(2, 1); 81 fail(); 82 } catch (IllegalArgumentException expected) { 83 } 84 try { 85 ContiguousSet.closedOpen(2, 1); 86 fail(); 87 } catch (IllegalArgumentException expected) { 88 } 89 } 90 testInvalidLongRange()91 public void testInvalidLongRange() { 92 try { 93 ContiguousSet.closed(2L, 1L); 94 fail(); 95 } catch (IllegalArgumentException expected) { 96 } 97 try { 98 ContiguousSet.closedOpen(2L, 1L); 99 fail(); 100 } catch (IllegalArgumentException expected) { 101 } 102 } 103 testEquals()104 public void testEquals() { 105 new EqualsTester() 106 .addEqualityGroup( 107 ContiguousSet.create(Range.closed(1, 3), integers()), 108 ContiguousSet.closed(1, 3), 109 ContiguousSet.create(Range.closedOpen(1, 4), integers()), 110 ContiguousSet.closedOpen(1, 4), 111 ContiguousSet.create(Range.openClosed(0, 3), integers()), 112 ContiguousSet.create(Range.open(0, 4), integers()), 113 ContiguousSet.create(Range.closed(1, 3), NOT_EQUAL_TO_INTEGERS), 114 ContiguousSet.create(Range.closedOpen(1, 4), NOT_EQUAL_TO_INTEGERS), 115 ContiguousSet.create(Range.openClosed(0, 3), NOT_EQUAL_TO_INTEGERS), 116 ContiguousSet.create(Range.open(0, 4), NOT_EQUAL_TO_INTEGERS), 117 ImmutableSortedSet.of(1, 2, 3)) 118 .addEqualityGroup( 119 ContiguousSet.create(Range.closedOpen(1, 1), integers()), 120 ContiguousSet.closedOpen(1, 1), 121 ContiguousSet.closedOpen(Integer.MIN_VALUE, Integer.MIN_VALUE), 122 ImmutableSortedSet.of(), 123 ImmutableSet.of()) 124 .testEquals(); 125 // not testing hashCode for these because it takes forever to compute 126 assertEquals( 127 ContiguousSet.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), 128 ContiguousSet.create(Range.<Integer>all(), integers())); 129 assertEquals( 130 ContiguousSet.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), 131 ContiguousSet.create(Range.atLeast(Integer.MIN_VALUE), integers())); 132 assertEquals( 133 ContiguousSet.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), 134 ContiguousSet.create(Range.atMost(Integer.MAX_VALUE), integers())); 135 } 136 137 @GwtIncompatible // SerializableTester testSerialization()138 public void testSerialization() { 139 ContiguousSet<Integer> empty = ContiguousSet.create(Range.closedOpen(1, 1), integers()); 140 assertTrue(empty instanceof EmptyContiguousSet); 141 reserializeAndAssert(empty); 142 143 ContiguousSet<Integer> regular = ContiguousSet.create(Range.closed(1, 3), integers()); 144 assertTrue(regular instanceof RegularContiguousSet); 145 reserializeAndAssert(regular); 146 147 /* 148 * Make sure that we're using RegularContiguousSet.SerializedForm and not 149 * ImmutableSet.SerializedForm, which would be enormous. 150 */ 151 ContiguousSet<Integer> enormous = ContiguousSet.create(Range.<Integer>all(), integers()); 152 assertTrue(enormous instanceof RegularContiguousSet); 153 // We can't use reserializeAndAssert because it calls hashCode, which is enormously slow. 154 ContiguousSet<Integer> enormousReserialized = reserialize(enormous); 155 assertEquals(enormous, enormousReserialized); 156 } 157 testCreate_noMin()158 public void testCreate_noMin() { 159 Range<Integer> range = Range.lessThan(0); 160 try { 161 ContiguousSet.create(range, RangeTest.UNBOUNDED_DOMAIN); 162 fail(); 163 } catch (IllegalArgumentException expected) { 164 } 165 } 166 testCreate_noMax()167 public void testCreate_noMax() { 168 Range<Integer> range = Range.greaterThan(0); 169 try { 170 ContiguousSet.create(range, RangeTest.UNBOUNDED_DOMAIN); 171 fail(); 172 } catch (IllegalArgumentException expected) { 173 } 174 } 175 testCreate_empty()176 public void testCreate_empty() { 177 assertEquals(ImmutableSet.of(), ContiguousSet.create(Range.closedOpen(1, 1), integers())); 178 assertEquals(ImmutableSet.of(), ContiguousSet.closedOpen(1, 1)); 179 assertEquals(ImmutableSet.of(), ContiguousSet.create(Range.openClosed(5, 5), integers())); 180 assertEquals( 181 ImmutableSet.of(), ContiguousSet.create(Range.lessThan(Integer.MIN_VALUE), integers())); 182 assertEquals( 183 ImmutableSet.of(), ContiguousSet.create(Range.greaterThan(Integer.MAX_VALUE), integers())); 184 } 185 testHeadSet()186 public void testHeadSet() { 187 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 188 assertThat(set.headSet(1)).isEmpty(); 189 assertThat(set.headSet(2)).containsExactly(1).inOrder(); 190 assertThat(set.headSet(3)).containsExactly(1, 2).inOrder(); 191 assertThat(set.headSet(4)).containsExactly(1, 2, 3).inOrder(); 192 assertThat(set.headSet(Integer.MAX_VALUE)).containsExactly(1, 2, 3).inOrder(); 193 assertThat(set.headSet(1, true)).containsExactly(1).inOrder(); 194 assertThat(set.headSet(2, true)).containsExactly(1, 2).inOrder(); 195 assertThat(set.headSet(3, true)).containsExactly(1, 2, 3).inOrder(); 196 assertThat(set.headSet(4, true)).containsExactly(1, 2, 3).inOrder(); 197 assertThat(set.headSet(Integer.MAX_VALUE, true)).containsExactly(1, 2, 3).inOrder(); 198 } 199 testHeadSet_tooSmall()200 public void testHeadSet_tooSmall() { 201 assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).headSet(0)).isEmpty(); 202 } 203 testTailSet()204 public void testTailSet() { 205 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 206 assertThat(set.tailSet(Integer.MIN_VALUE)).containsExactly(1, 2, 3).inOrder(); 207 assertThat(set.tailSet(1)).containsExactly(1, 2, 3).inOrder(); 208 assertThat(set.tailSet(2)).containsExactly(2, 3).inOrder(); 209 assertThat(set.tailSet(3)).containsExactly(3).inOrder(); 210 assertThat(set.tailSet(Integer.MIN_VALUE, false)).containsExactly(1, 2, 3).inOrder(); 211 assertThat(set.tailSet(1, false)).containsExactly(2, 3).inOrder(); 212 assertThat(set.tailSet(2, false)).containsExactly(3).inOrder(); 213 assertThat(set.tailSet(3, false)).isEmpty(); 214 } 215 testTailSet_tooLarge()216 public void testTailSet_tooLarge() { 217 assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).tailSet(4)).isEmpty(); 218 } 219 testSubSet()220 public void testSubSet() { 221 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 222 assertThat(set.subSet(1, 4)).containsExactly(1, 2, 3).inOrder(); 223 assertThat(set.subSet(2, 4)).containsExactly(2, 3).inOrder(); 224 assertThat(set.subSet(3, 4)).containsExactly(3).inOrder(); 225 assertThat(set.subSet(3, 3)).isEmpty(); 226 assertThat(set.subSet(2, 3)).containsExactly(2).inOrder(); 227 assertThat(set.subSet(1, 3)).containsExactly(1, 2).inOrder(); 228 assertThat(set.subSet(1, 2)).containsExactly(1).inOrder(); 229 assertThat(set.subSet(2, 2)).isEmpty(); 230 assertThat(set.subSet(Integer.MIN_VALUE, Integer.MAX_VALUE)).containsExactly(1, 2, 3).inOrder(); 231 assertThat(set.subSet(1, true, 3, true)).containsExactly(1, 2, 3).inOrder(); 232 assertThat(set.subSet(1, false, 3, true)).containsExactly(2, 3).inOrder(); 233 assertThat(set.subSet(1, true, 3, false)).containsExactly(1, 2).inOrder(); 234 assertThat(set.subSet(1, false, 3, false)).containsExactly(2).inOrder(); 235 } 236 testSubSet_outOfOrder()237 public void testSubSet_outOfOrder() { 238 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 239 try { 240 set.subSet(3, 2); 241 fail(); 242 } catch (IllegalArgumentException expected) { 243 } 244 } 245 testSubSet_tooLarge()246 public void testSubSet_tooLarge() { 247 assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).subSet(4, 6)).isEmpty(); 248 } 249 testSubSet_tooSmall()250 public void testSubSet_tooSmall() { 251 assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).subSet(-1, 0)).isEmpty(); 252 } 253 testFirst()254 public void testFirst() { 255 assertEquals(1, ContiguousSet.create(Range.closed(1, 3), integers()).first().intValue()); 256 assertEquals(1, ContiguousSet.create(Range.open(0, 4), integers()).first().intValue()); 257 assertEquals( 258 Integer.MIN_VALUE, 259 ContiguousSet.create(Range.<Integer>all(), integers()).first().intValue()); 260 } 261 testLast()262 public void testLast() { 263 assertEquals(3, ContiguousSet.create(Range.closed(1, 3), integers()).last().intValue()); 264 assertEquals(3, ContiguousSet.create(Range.open(0, 4), integers()).last().intValue()); 265 assertEquals( 266 Integer.MAX_VALUE, 267 ContiguousSet.create(Range.<Integer>all(), integers()).last().intValue()); 268 } 269 testContains()270 public void testContains() { 271 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 272 assertFalse(set.contains(0)); 273 assertTrue(set.contains(1)); 274 assertTrue(set.contains(2)); 275 assertTrue(set.contains(3)); 276 assertFalse(set.contains(4)); 277 set = ContiguousSet.create(Range.open(0, 4), integers()); 278 assertFalse(set.contains(0)); 279 assertTrue(set.contains(1)); 280 assertTrue(set.contains(2)); 281 assertTrue(set.contains(3)); 282 assertFalse(set.contains(4)); 283 assertFalse(set.contains((Object) "blah")); 284 } 285 testContainsAll()286 public void testContainsAll() { 287 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 288 for (Set<Integer> subset : Sets.powerSet(ImmutableSet.of(1, 2, 3))) { 289 assertTrue(set.containsAll(subset)); 290 } 291 for (Set<Integer> subset : Sets.powerSet(ImmutableSet.of(1, 2, 3))) { 292 assertFalse(set.containsAll(Sets.union(subset, ImmutableSet.of(9)))); 293 } 294 assertFalse(set.containsAll((Collection<?>) ImmutableSet.of("blah"))); 295 } 296 testRange()297 public void testRange() { 298 assertEquals(Range.closed(1, 3), ContiguousSet.create(Range.closed(1, 3), integers()).range()); 299 assertEquals(Range.closed(1, 3), ContiguousSet.closed(1, 3).range()); 300 assertEquals( 301 Range.closed(1, 3), ContiguousSet.create(Range.closedOpen(1, 4), integers()).range()); 302 assertEquals(Range.closed(1, 3), ContiguousSet.closedOpen(1, 4).range()); 303 assertEquals(Range.closed(1, 3), ContiguousSet.create(Range.open(0, 4), integers()).range()); 304 assertEquals( 305 Range.closed(1, 3), ContiguousSet.create(Range.openClosed(0, 3), integers()).range()); 306 307 assertEquals( 308 Range.openClosed(0, 3), 309 ContiguousSet.create(Range.closed(1, 3), integers()).range(OPEN, CLOSED)); 310 assertEquals( 311 Range.openClosed(0, 3), 312 ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(OPEN, CLOSED)); 313 assertEquals( 314 Range.openClosed(0, 3), 315 ContiguousSet.create(Range.open(0, 4), integers()).range(OPEN, CLOSED)); 316 assertEquals( 317 Range.openClosed(0, 3), 318 ContiguousSet.create(Range.openClosed(0, 3), integers()).range(OPEN, CLOSED)); 319 320 assertEquals( 321 Range.open(0, 4), ContiguousSet.create(Range.closed(1, 3), integers()).range(OPEN, OPEN)); 322 assertEquals( 323 Range.open(0, 4), 324 ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(OPEN, OPEN)); 325 assertEquals( 326 Range.open(0, 4), ContiguousSet.create(Range.open(0, 4), integers()).range(OPEN, OPEN)); 327 assertEquals( 328 Range.open(0, 4), 329 ContiguousSet.create(Range.openClosed(0, 3), integers()).range(OPEN, OPEN)); 330 331 assertEquals( 332 Range.closedOpen(1, 4), 333 ContiguousSet.create(Range.closed(1, 3), integers()).range(CLOSED, OPEN)); 334 assertEquals( 335 Range.closedOpen(1, 4), 336 ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(CLOSED, OPEN)); 337 assertEquals( 338 Range.closedOpen(1, 4), 339 ContiguousSet.create(Range.open(0, 4), integers()).range(CLOSED, OPEN)); 340 assertEquals( 341 Range.closedOpen(1, 4), 342 ContiguousSet.create(Range.openClosed(0, 3), integers()).range(CLOSED, OPEN)); 343 } 344 testRange_unboundedRange()345 public void testRange_unboundedRange() { 346 assertEquals( 347 Range.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), 348 ContiguousSet.create(Range.<Integer>all(), integers()).range()); 349 assertEquals( 350 Range.atLeast(Integer.MIN_VALUE), 351 ContiguousSet.create(Range.<Integer>all(), integers()).range(CLOSED, OPEN)); 352 assertEquals( 353 Range.all(), ContiguousSet.create(Range.<Integer>all(), integers()).range(OPEN, OPEN)); 354 assertEquals( 355 Range.atMost(Integer.MAX_VALUE), 356 ContiguousSet.create(Range.<Integer>all(), integers()).range(OPEN, CLOSED)); 357 } 358 testIntersection_empty()359 public void testIntersection_empty() { 360 ContiguousSet<Integer> set = ContiguousSet.closed(1, 3); 361 ContiguousSet<Integer> emptySet = ContiguousSet.closedOpen(2, 2); 362 assertEquals(ImmutableSet.of(), set.intersection(emptySet)); 363 assertEquals(ImmutableSet.of(), emptySet.intersection(set)); 364 assertEquals( 365 ImmutableSet.of(), 366 ContiguousSet.create(Range.closed(-5, -1), integers()) 367 .intersection(ContiguousSet.create(Range.open(3, 64), integers()))); 368 } 369 testIntersection()370 public void testIntersection() { 371 ContiguousSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 372 assertEquals( 373 ImmutableSet.of(1, 2, 3), 374 ContiguousSet.create(Range.open(-1, 4), integers()).intersection(set)); 375 assertEquals( 376 ImmutableSet.of(1, 2, 3), 377 set.intersection(ContiguousSet.create(Range.open(-1, 4), integers()))); 378 assertEquals( 379 ImmutableSet.of(3), set.intersection(ContiguousSet.create(Range.closed(3, 5), integers()))); 380 } 381 testAsList()382 public void testAsList() { 383 ImmutableList<Integer> list = ContiguousSet.create(Range.closed(1, 3), integers()).asList(); 384 for (int i = 0; i < 3; i++) { 385 assertEquals(i + 1, list.get(i).intValue()); 386 } 387 assertEquals(ImmutableList.of(1, 2, 3), ImmutableList.copyOf(list.iterator())); 388 assertEquals(ImmutableList.of(1, 2, 3), ImmutableList.copyOf(list.toArray(new Integer[0]))); 389 } 390 391 @GwtIncompatible // suite 392 public static class BuiltTests extends TestCase { suite()393 public static Test suite() { 394 TestSuite suite = new TestSuite(); 395 396 suite.addTest( 397 NavigableSetTestSuiteBuilder.using(new ContiguousSetGenerator()) 398 .named("Range.asSet") 399 .withFeatures( 400 CollectionSize.ANY, 401 KNOWN_ORDER, 402 ALLOWS_NULL_QUERIES, 403 NON_STANDARD_TOSTRING, 404 RESTRICTS_ELEMENTS) 405 .suppressing(getHoleMethods()) 406 .createTestSuite()); 407 408 suite.addTest( 409 NavigableSetTestSuiteBuilder.using(new ContiguousSetHeadsetGenerator()) 410 .named("Range.asSet, headset") 411 .withFeatures( 412 CollectionSize.ANY, 413 KNOWN_ORDER, 414 ALLOWS_NULL_QUERIES, 415 NON_STANDARD_TOSTRING, 416 RESTRICTS_ELEMENTS) 417 .suppressing(getHoleMethods()) 418 .createTestSuite()); 419 420 suite.addTest( 421 NavigableSetTestSuiteBuilder.using(new ContiguousSetTailsetGenerator()) 422 .named("Range.asSet, tailset") 423 .withFeatures( 424 CollectionSize.ANY, 425 KNOWN_ORDER, 426 ALLOWS_NULL_QUERIES, 427 NON_STANDARD_TOSTRING, 428 RESTRICTS_ELEMENTS) 429 .suppressing(getHoleMethods()) 430 .createTestSuite()); 431 432 suite.addTest( 433 NavigableSetTestSuiteBuilder.using(new ContiguousSetSubsetGenerator()) 434 .named("Range.asSet, subset") 435 .withFeatures( 436 CollectionSize.ANY, 437 KNOWN_ORDER, 438 ALLOWS_NULL_QUERIES, 439 NON_STANDARD_TOSTRING, 440 RESTRICTS_ELEMENTS) 441 .suppressing(getHoleMethods()) 442 .createTestSuite()); 443 444 suite.addTest( 445 NavigableSetTestSuiteBuilder.using(new ContiguousSetDescendingGenerator()) 446 .named("Range.asSet.descendingSet") 447 .withFeatures( 448 CollectionSize.ANY, 449 KNOWN_ORDER, 450 ALLOWS_NULL_QUERIES, 451 NON_STANDARD_TOSTRING, 452 RESTRICTS_ELEMENTS) 453 .suppressing(getHoleMethods()) 454 .createTestSuite()); 455 456 return suite; 457 } 458 } 459 } 460