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
15package com.google.common.collect;
16
17import static com.google.common.truth.Truth.assertThat;
18
19import com.google.common.annotations.GwtIncompatible;
20import com.google.common.collect.testing.NavigableSetTestSuiteBuilder;
21import com.google.common.collect.testing.SampleElements;
22import com.google.common.collect.testing.TestSetGenerator;
23import com.google.common.collect.testing.features.CollectionFeature;
24import com.google.common.collect.testing.features.CollectionSize;
25import com.google.common.testing.SerializableTester;
26
27import junit.framework.Test;
28import junit.framework.TestSuite;
29
30import java.math.BigInteger;
31import java.util.List;
32import java.util.Set;
33
34/**
35 * Tests for {@link ImmutableRangeSet}.
36 *
37 * @author Louis Wasserman
38 */
39@GwtIncompatible("ImmutableRangeSet")
40public 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