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 42 import junit.framework.Test; 43 import junit.framework.TestCase; 44 import junit.framework.TestSuite; 45 46 import java.util.Set; 47 48 /** 49 * @author Gregory Kick 50 */ 51 @GwtCompatible(emulated = true) 52 public class ContiguousSetTest extends TestCase { 53 private static DiscreteDomain<Integer> NOT_EQUAL_TO_INTEGERS = new DiscreteDomain<Integer>() { 54 @Override public Integer next(Integer value) { 55 return integers().next(value); 56 } 57 58 @Override public Integer previous(Integer value) { 59 return integers().previous(value); 60 } 61 62 @Override public long distance(Integer start, Integer end) { 63 return integers().distance(start, end); 64 } 65 66 @Override public Integer minValue() { 67 return integers().minValue(); 68 } 69 70 @Override public Integer maxValue() { 71 return integers().maxValue(); 72 } 73 }; 74 75 public void testEquals() { 76 new EqualsTester() 77 .addEqualityGroup( 78 ContiguousSet.create(Range.closed(1, 3), integers()), 79 ContiguousSet.create(Range.closedOpen(1, 4), integers()), 80 ContiguousSet.create(Range.openClosed(0, 3), integers()), 81 ContiguousSet.create(Range.open(0, 4), integers()), 82 ContiguousSet.create(Range.closed(1, 3), NOT_EQUAL_TO_INTEGERS), 83 ContiguousSet.create(Range.closedOpen(1, 4), NOT_EQUAL_TO_INTEGERS), 84 ContiguousSet.create(Range.openClosed(0, 3), NOT_EQUAL_TO_INTEGERS), 85 ContiguousSet.create(Range.open(0, 4), NOT_EQUAL_TO_INTEGERS), 86 ImmutableSortedSet.of(1, 2, 3)) 87 .testEquals(); 88 // not testing hashCode for these because it takes forever to compute 89 assertEquals( 90 ContiguousSet.create(Range.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), integers()), 91 ContiguousSet.create(Range.<Integer>all(), integers())); 92 assertEquals( 93 ContiguousSet.create(Range.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), integers()), 94 ContiguousSet.create(Range.atLeast(Integer.MIN_VALUE), integers())); 95 assertEquals( 96 ContiguousSet.create(Range.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), integers()), 97 ContiguousSet.create(Range.atMost(Integer.MAX_VALUE), integers())); 98 } 99 100 @GwtIncompatible("SerializableTester") 101 public void testSerialization() { 102 ContiguousSet<Integer> empty = ContiguousSet.create(Range.closedOpen(1, 1), integers()); 103 assertTrue(empty instanceof EmptyContiguousSet); 104 reserializeAndAssert(empty); 105 106 ContiguousSet<Integer> regular = ContiguousSet.create(Range.closed(1, 3), integers()); 107 assertTrue(regular instanceof RegularContiguousSet); 108 reserializeAndAssert(regular); 109 110 /* 111 * Make sure that we're using RegularContiguousSet.SerializedForm and not 112 * ImmutableSet.SerializedForm, which would be enormous. 113 */ 114 ContiguousSet<Integer> enormous = ContiguousSet.create(Range.<Integer>all(), integers()); 115 assertTrue(enormous instanceof RegularContiguousSet); 116 // We can't use reserializeAndAssert because it calls hashCode, which is enormously slow. 117 ContiguousSet<Integer> enormousReserialized = reserialize(enormous); 118 assertEquals(enormous, enormousReserialized); 119 } 120 121 public void testCreate_noMin() { 122 Range<Integer> range = Range.lessThan(0); 123 try { 124 ContiguousSet.create(range, RangeTest.UNBOUNDED_DOMAIN); 125 fail(); 126 } catch (IllegalArgumentException expected) {} 127 } 128 129 public void testCreate_noMax() { 130 Range<Integer> range = Range.greaterThan(0); 131 try { 132 ContiguousSet.create(range, RangeTest.UNBOUNDED_DOMAIN); 133 fail(); 134 } catch (IllegalArgumentException expected) {} 135 } 136 137 public void testCreate_empty() { 138 assertEquals(ImmutableSet.of(), ContiguousSet.create(Range.closedOpen(1, 1), integers())); 139 assertEquals(ImmutableSet.of(), ContiguousSet.create(Range.openClosed(5, 5), integers())); 140 assertEquals(ImmutableSet.of(), 141 ContiguousSet.create(Range.lessThan(Integer.MIN_VALUE), integers())); 142 assertEquals(ImmutableSet.of(), 143 ContiguousSet.create(Range.greaterThan(Integer.MAX_VALUE), integers())); 144 } 145 146 public void testHeadSet() { 147 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 148 assertThat(set.headSet(1)).isEmpty(); 149 assertThat(set.headSet(2)).has().item(1); 150 assertThat(set.headSet(3)).has().exactly(1, 2).inOrder(); 151 assertThat(set.headSet(4)).has().exactly(1, 2, 3).inOrder(); 152 assertThat(set.headSet(Integer.MAX_VALUE)).has().exactly(1, 2, 3).inOrder(); 153 assertThat(set.headSet(1, true)).has().item(1); 154 assertThat(set.headSet(2, true)).has().exactly(1, 2).inOrder(); 155 assertThat(set.headSet(3, true)).has().exactly(1, 2, 3).inOrder(); 156 assertThat(set.headSet(4, true)).has().exactly(1, 2, 3).inOrder(); 157 assertThat(set.headSet(Integer.MAX_VALUE, true)).has().exactly(1, 2, 3).inOrder(); 158 } 159 160 public void testHeadSet_tooSmall() { 161 assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).headSet(0)).isEmpty(); 162 } 163 164 public void testTailSet() { 165 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 166 assertThat(set.tailSet(Integer.MIN_VALUE)).has().exactly(1, 2, 3).inOrder(); 167 assertThat(set.tailSet(1)).has().exactly(1, 2, 3).inOrder(); 168 assertThat(set.tailSet(2)).has().exactly(2, 3).inOrder(); 169 assertThat(set.tailSet(3)).has().item(3); 170 assertThat(set.tailSet(Integer.MIN_VALUE, false)).has().exactly(1, 2, 3).inOrder(); 171 assertThat(set.tailSet(1, false)).has().exactly(2, 3).inOrder(); 172 assertThat(set.tailSet(2, false)).has().item(3); 173 assertThat(set.tailSet(3, false)).isEmpty(); 174 } 175 176 public void testTailSet_tooLarge() { 177 assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).tailSet(4)).isEmpty(); 178 } 179 180 public void testSubSet() { 181 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 182 assertThat(set.subSet(1, 4)).has().exactly(1, 2, 3).inOrder(); 183 assertThat(set.subSet(2, 4)).has().exactly(2, 3).inOrder(); 184 assertThat(set.subSet(3, 4)).has().item(3); 185 assertThat(set.subSet(3, 3)).isEmpty(); 186 assertThat(set.subSet(2, 3)).has().item(2); 187 assertThat(set.subSet(1, 3)).has().exactly(1, 2).inOrder(); 188 assertThat(set.subSet(1, 2)).has().item(1); 189 assertThat(set.subSet(2, 2)).isEmpty(); 190 assertThat(set.subSet(Integer.MIN_VALUE, Integer.MAX_VALUE)).has().exactly(1, 2, 3).inOrder(); 191 assertThat(set.subSet(1, true, 3, true)).has().exactly(1, 2, 3).inOrder(); 192 assertThat(set.subSet(1, false, 3, true)).has().exactly(2, 3).inOrder(); 193 assertThat(set.subSet(1, true, 3, false)).has().exactly(1, 2).inOrder(); 194 assertThat(set.subSet(1, false, 3, false)).has().item(2); 195 } 196 197 public void testSubSet_outOfOrder() { 198 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 199 try { 200 set.subSet(3, 2); 201 fail(); 202 } catch (IllegalArgumentException expected) {} 203 } 204 205 public void testSubSet_tooLarge() { 206 assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).subSet(4, 6)).isEmpty(); 207 } 208 209 public void testSubSet_tooSmall() { 210 assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).subSet(-1, 0)).isEmpty(); 211 } 212 213 public void testFirst() { 214 assertEquals(1, ContiguousSet.create(Range.closed(1, 3), integers()).first().intValue()); 215 assertEquals(1, ContiguousSet.create(Range.open(0, 4), integers()).first().intValue()); 216 assertEquals(Integer.MIN_VALUE, 217 ContiguousSet.create(Range.<Integer>all(), integers()).first().intValue()); 218 } 219 220 public void testLast() { 221 assertEquals(3, ContiguousSet.create(Range.closed(1, 3), integers()).last().intValue()); 222 assertEquals(3, ContiguousSet.create(Range.open(0, 4), integers()).last().intValue()); 223 assertEquals(Integer.MAX_VALUE, 224 ContiguousSet.create(Range.<Integer>all(), integers()).last().intValue()); 225 } 226 227 public void testContains() { 228 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 229 assertFalse(set.contains(0)); 230 assertTrue(set.contains(1)); 231 assertTrue(set.contains(2)); 232 assertTrue(set.contains(3)); 233 assertFalse(set.contains(4)); 234 set = ContiguousSet.create(Range.open(0, 4), integers()); 235 assertFalse(set.contains(0)); 236 assertTrue(set.contains(1)); 237 assertTrue(set.contains(2)); 238 assertTrue(set.contains(3)); 239 assertFalse(set.contains(4)); 240 assertFalse(set.contains("blah")); 241 } 242 243 public void testContainsAll() { 244 ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 245 for (Set<Integer> subset : Sets.powerSet(ImmutableSet.of(1, 2, 3))) { 246 assertTrue(set.containsAll(subset)); 247 } 248 for (Set<Integer> subset : Sets.powerSet(ImmutableSet.of(1, 2, 3))) { 249 assertFalse(set.containsAll(Sets.union(subset, ImmutableSet.of(9)))); 250 } 251 assertFalse(set.containsAll(ImmutableSet.of("blah"))); 252 } 253 254 public void testRange() { 255 assertEquals(Range.closed(1, 3), 256 ContiguousSet.create(Range.closed(1, 3), integers()).range()); 257 assertEquals(Range.closed(1, 3), 258 ContiguousSet.create(Range.closedOpen(1, 4), integers()).range()); 259 assertEquals(Range.closed(1, 3), ContiguousSet.create(Range.open(0, 4), integers()).range()); 260 assertEquals(Range.closed(1, 3), 261 ContiguousSet.create(Range.openClosed(0, 3), integers()).range()); 262 263 assertEquals(Range.openClosed(0, 3), 264 ContiguousSet.create(Range.closed(1, 3), integers()).range(OPEN, CLOSED)); 265 assertEquals(Range.openClosed(0, 3), 266 ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(OPEN, CLOSED)); 267 assertEquals(Range.openClosed(0, 3), 268 ContiguousSet.create(Range.open(0, 4), integers()).range(OPEN, CLOSED)); 269 assertEquals(Range.openClosed(0, 3), 270 ContiguousSet.create(Range.openClosed(0, 3), integers()).range(OPEN, CLOSED)); 271 272 assertEquals(Range.open(0, 4), 273 ContiguousSet.create(Range.closed(1, 3), integers()).range(OPEN, OPEN)); 274 assertEquals(Range.open(0, 4), 275 ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(OPEN, OPEN)); 276 assertEquals(Range.open(0, 4), 277 ContiguousSet.create(Range.open(0, 4), integers()).range(OPEN, OPEN)); 278 assertEquals(Range.open(0, 4), 279 ContiguousSet.create(Range.openClosed(0, 3), integers()).range(OPEN, OPEN)); 280 281 assertEquals(Range.closedOpen(1, 4), 282 ContiguousSet.create(Range.closed(1, 3), integers()).range(CLOSED, OPEN)); 283 assertEquals(Range.closedOpen(1, 4), 284 ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(CLOSED, OPEN)); 285 assertEquals(Range.closedOpen(1, 4), 286 ContiguousSet.create(Range.open(0, 4), integers()).range(CLOSED, OPEN)); 287 assertEquals(Range.closedOpen(1, 4), 288 ContiguousSet.create(Range.openClosed(0, 3), integers()).range(CLOSED, OPEN)); 289 } 290 291 public void testRange_unboundedRange() { 292 assertEquals(Range.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), 293 ContiguousSet.create(Range.<Integer>all(), integers()).range()); 294 assertEquals(Range.atLeast(Integer.MIN_VALUE), 295 ContiguousSet.create(Range.<Integer>all(), integers()).range(CLOSED, OPEN)); 296 assertEquals(Range.all(), 297 ContiguousSet.create(Range.<Integer>all(), integers()).range(OPEN, OPEN)); 298 assertEquals(Range.atMost(Integer.MAX_VALUE), 299 ContiguousSet.create(Range.<Integer>all(), integers()).range(OPEN, CLOSED)); 300 } 301 302 public void testIntersection_empty() { 303 ContiguousSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 304 ContiguousSet<Integer> emptySet = ContiguousSet.create(Range.closedOpen(2, 2), integers()); 305 assertEquals(ImmutableSet.of(), set.intersection(emptySet)); 306 assertEquals(ImmutableSet.of(), emptySet.intersection(set)); 307 assertEquals(ImmutableSet.of(), 308 ContiguousSet.create(Range.closed(-5, -1), integers()).intersection( 309 ContiguousSet.create(Range.open(3, 64), integers()))); 310 } 311 312 public void testIntersection() { 313 ContiguousSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers()); 314 assertEquals(ImmutableSet.of(1, 2, 3), 315 ContiguousSet.create(Range.open(-1, 4), integers()).intersection(set)); 316 assertEquals(ImmutableSet.of(1, 2, 3), 317 set.intersection(ContiguousSet.create(Range.open(-1, 4), integers()))); 318 } 319 320 @GwtIncompatible("suite") 321 public static class BuiltTests extends TestCase { 322 public static Test suite() { 323 TestSuite suite = new TestSuite(); 324 325 suite.addTest(NavigableSetTestSuiteBuilder.using( 326 new ContiguousSetGenerator()) 327 .named("Range.asSet") 328 .withFeatures(CollectionSize.ANY, KNOWN_ORDER, ALLOWS_NULL_QUERIES, 329 NON_STANDARD_TOSTRING, RESTRICTS_ELEMENTS) 330 .suppressing(getHoleMethods()) 331 .createTestSuite()); 332 333 suite.addTest(NavigableSetTestSuiteBuilder.using( 334 new ContiguousSetHeadsetGenerator()) 335 .named("Range.asSet, headset") 336 .withFeatures(CollectionSize.ANY, KNOWN_ORDER, ALLOWS_NULL_QUERIES, 337 NON_STANDARD_TOSTRING, RESTRICTS_ELEMENTS) 338 .suppressing(getHoleMethods()) 339 .createTestSuite()); 340 341 suite.addTest(NavigableSetTestSuiteBuilder.using( 342 new ContiguousSetTailsetGenerator()) 343 .named("Range.asSet, tailset") 344 .withFeatures(CollectionSize.ANY, KNOWN_ORDER, ALLOWS_NULL_QUERIES, 345 NON_STANDARD_TOSTRING, RESTRICTS_ELEMENTS) 346 .suppressing(getHoleMethods()) 347 .createTestSuite()); 348 349 suite.addTest(NavigableSetTestSuiteBuilder.using( 350 new ContiguousSetSubsetGenerator()) 351 .named("Range.asSet, subset") 352 .withFeatures(CollectionSize.ANY, KNOWN_ORDER, ALLOWS_NULL_QUERIES, 353 NON_STANDARD_TOSTRING, RESTRICTS_ELEMENTS) 354 .suppressing(getHoleMethods()) 355 .createTestSuite()); 356 357 suite.addTest(NavigableSetTestSuiteBuilder.using( 358 new ContiguousSetDescendingGenerator()) 359 .named("Range.asSet.descendingSet") 360 .withFeatures(CollectionSize.ANY, KNOWN_ORDER, ALLOWS_NULL_QUERIES, 361 NON_STANDARD_TOSTRING, RESTRICTS_ELEMENTS) 362 .suppressing(getHoleMethods()) 363 .createTestSuite()); 364 365 return suite; 366 } 367 } 368 } 369