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
samples()57     public SampleElements<Integer> samples() {
58       return new SampleElements<Integer>(1, 4, 3, 2, 5);
59     }
60 
61     @Override
createArray(int length)62     public Integer[] createArray(int length) {
63       return new Integer[length];
64     }
65 
66     @Override
order(List<Integer> insertionOrder)67     public Iterable<Integer> order(List<Integer> insertionOrder) {
68       return Ordering.natural().sortedCopy(insertionOrder);
69     }
70 
71     @Override
create(Object... elements)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
samples()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
createArray(int length)95     public BigInteger[] createArray(int length) {
96       return new BigInteger[length];
97     }
98 
99     @Override
order(List<BigInteger> insertionOrder)100     public Iterable<BigInteger> order(List<BigInteger> insertionOrder) {
101       return Ordering.natural().sortedCopy(insertionOrder);
102     }
103 
104     @Override
create(Object... elements)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 
suite()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 
testEmpty()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 
testAll()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 
testSingleBoundedRange()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 
testSingleBoundedBelowRange()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 
testSingleBoundedAboveRange()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 
testMultipleBoundedRanges()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 
testMultipleBoundedBelowRanges()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 
testMultipleBoundedAboveRanges()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 
testAddUnsupported()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 
testAddAllUnsupported()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 
testRemoveUnsupported()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 
testRemoveAllUnsupported()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 
testExhaustive()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 
testAsSet()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 
testAsSetHeadSet()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 
testAsSetTailSet()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 
testAsSetSubSet()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 
testSubRangeSet()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