1/*
2 * Copyright (C) 2011 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.collect.BoundType.OPEN;
18import static com.google.common.collect.Range.range;
19import static com.google.common.truth.Truth.assertThat;
20
21import com.google.common.annotations.GwtIncompatible;
22
23import java.util.List;
24import java.util.NavigableMap;
25
26/**
27 * Tests for {@link TreeRangeSet}.
28 *
29 * @author Louis Wasserman
30 * @author Chris Povirk
31 */
32@GwtIncompatible("TreeRangeSet")
33public class TreeRangeSetTest extends AbstractRangeSetTest {
34  // TODO(cpovirk): test all of these with the ranges added in the reverse order
35
36  private static final ImmutableList<Range<Integer>> QUERY_RANGES;
37
38  private static final int MIN_BOUND = -1;
39  private static final int MAX_BOUND = 1;
40
41  static {
42    ImmutableList.Builder<Range<Integer>> queryBuilder = ImmutableList.builder();
43
44    queryBuilder.add(Range.<Integer>all());
45
46    for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
47      for (BoundType boundType : BoundType.values()) {
48        queryBuilder.add(Range.upTo(i, boundType));
49        queryBuilder.add(Range.downTo(i, boundType));
50      }
51      queryBuilder.add(Range.singleton(i));
52      queryBuilder.add(Range.openClosed(i, i));
53      queryBuilder.add(Range.closedOpen(i, i));
54
55      for (BoundType lowerBoundType : BoundType.values()) {
56        for (int j = i + 1; j <= MAX_BOUND; j++) {
57          for (BoundType upperBoundType : BoundType.values()) {
58            queryBuilder.add(Range.range(i, lowerBoundType, j, upperBoundType));
59          }
60        }
61      }
62    }
63    QUERY_RANGES = queryBuilder.build();
64  }
65
66  void testViewAgainstExpected(RangeSet<Integer> expected, RangeSet<Integer> view) {
67    assertEquals(expected, view);
68    assertEquals(expected.asRanges(), view.asRanges());
69    assertEquals(expected.isEmpty(), view.isEmpty());
70
71    if (!expected.isEmpty()) {
72      assertEquals(expected.span(), view.span());
73    }
74
75    for (int i = MIN_BOUND - 1; i <= MAX_BOUND + 1; i++) {
76      assertEquals(expected.contains(i), view.contains(i));
77      assertEquals(expected.rangeContaining(i), view.rangeContaining(i));
78    }
79    testEnclosing(view);
80    if (view instanceof TreeRangeSet) {
81      testRangesByLowerBounds((TreeRangeSet<Integer>) view, expected.asRanges());
82    }
83  }
84
85  private static final ImmutableList<Cut<Integer>> CUTS_TO_TEST;
86
87  static {
88    List<Cut<Integer>> cutsToTest = Lists.newArrayList();
89    for (int i = MIN_BOUND - 1; i <= MAX_BOUND + 1; i++) {
90      cutsToTest.add(Cut.belowValue(i));
91      cutsToTest.add(Cut.aboveValue(i));
92    }
93    cutsToTest.add(Cut.<Integer>aboveAll());
94    cutsToTest.add(Cut.<Integer>belowAll());
95    CUTS_TO_TEST = ImmutableList.copyOf(cutsToTest);
96  }
97
98  private void testRangesByLowerBounds(
99      TreeRangeSet<Integer> rangeSet, Iterable<Range<Integer>> expectedRanges) {
100    NavigableMap<Cut<Integer>, Range<Integer>> expectedRangesByLowerBound = Maps.newTreeMap();
101    for (Range<Integer> range : expectedRanges) {
102      expectedRangesByLowerBound.put(range.lowerBound, range);
103    }
104
105    NavigableMap<Cut<Integer>, Range<Integer>> rangesByLowerBound = rangeSet.rangesByLowerBound;
106    testNavigationAgainstExpected(expectedRangesByLowerBound, rangesByLowerBound, CUTS_TO_TEST);
107  }
108
109  <K, V> void testNavigationAgainstExpected(
110      NavigableMap<K, V> expected, NavigableMap<K, V> navigableMap, Iterable<K> keysToTest) {
111    for (K key : keysToTest) {
112      assertEquals(expected.lowerEntry(key), navigableMap.lowerEntry(key));
113      assertEquals(expected.floorEntry(key), navigableMap.floorEntry(key));
114      assertEquals(expected.ceilingEntry(key), navigableMap.ceilingEntry(key));
115      assertEquals(expected.higherEntry(key), navigableMap.higherEntry(key));
116      for (boolean inclusive : new boolean[] {false, true}) {
117        assertThat(navigableMap.headMap(key, inclusive).entrySet())
118            .has().exactlyAs(expected.headMap(key, inclusive).entrySet()).inOrder();
119        assertThat(navigableMap.tailMap(key, inclusive).entrySet())
120            .has().exactlyAs(expected.tailMap(key, inclusive).entrySet()).inOrder();
121        assertThat(navigableMap.headMap(key, inclusive).descendingMap().entrySet())
122            .has().exactlyAs(expected.headMap(key, inclusive).descendingMap().entrySet()).inOrder();
123        assertThat(navigableMap.tailMap(key, inclusive).descendingMap().entrySet())
124            .has().exactlyAs(expected.tailMap(key, inclusive).descendingMap().entrySet()).inOrder();
125      }
126    }
127  }
128
129  public void testEnclosing(RangeSet<Integer> rangeSet) {
130    for (Range<Integer> query : QUERY_RANGES) {
131      boolean expectEnclose = false;
132      for (Range<Integer> expectedRange : rangeSet.asRanges()) {
133        if (expectedRange.encloses(query)) {
134          expectEnclose = true;
135          break;
136        }
137      }
138
139      assertEquals(rangeSet + " was incorrect on encloses(" + query + ")", expectEnclose,
140          rangeSet.encloses(query));
141    }
142  }
143
144  public void testAllSingleRangesComplementAgainstRemove() {
145    for (Range<Integer> range : QUERY_RANGES) {
146      TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
147      rangeSet.add(range);
148
149      TreeRangeSet<Integer> complement = TreeRangeSet.create();
150      complement.add(Range.<Integer>all());
151      complement.remove(range);
152
153      assertEquals(complement, rangeSet.complement());
154      assertThat(rangeSet.complement().asRanges())
155          .has().exactlyAs(complement.asRanges()).inOrder();
156    }
157  }
158
159  public void testInvariantsEmpty() {
160    testInvariants(TreeRangeSet.create());
161  }
162
163  public void testAllSingleRangesEnclosing() {
164    for (Range<Integer> range : QUERY_RANGES) {
165      TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
166      rangeSet.add(range);
167      testEnclosing(rangeSet);
168      testEnclosing(rangeSet.complement());
169    }
170  }
171
172  public void testAllTwoRangesEnclosing() {
173    for (Range<Integer> range1 : QUERY_RANGES) {
174      for (Range<Integer> range2 : QUERY_RANGES) {
175        TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
176        rangeSet.add(range1);
177        rangeSet.add(range2);
178        testEnclosing(rangeSet);
179        testEnclosing(rangeSet.complement());
180      }
181    }
182  }
183
184  public void testCreateCopy() {
185    for (Range<Integer> range1 : QUERY_RANGES) {
186      for (Range<Integer> range2 : QUERY_RANGES) {
187        TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
188        rangeSet.add(range1);
189        rangeSet.add(range2);
190
191        assertEquals(rangeSet, TreeRangeSet.create(rangeSet));
192      }
193    }
194  }
195
196  private RangeSet<Integer> expectedSubRangeSet(
197      RangeSet<Integer> rangeSet, Range<Integer> subRange) {
198    RangeSet<Integer> expected = TreeRangeSet.create();
199    for (Range<Integer> range : rangeSet.asRanges()) {
200      if (range.isConnected(subRange)) {
201        expected.add(range.intersection(subRange));
202      }
203    }
204    return expected;
205  }
206
207  private RangeSet<Integer> expectedComplement(RangeSet<Integer> rangeSet) {
208    RangeSet<Integer> expected = TreeRangeSet.create();
209    expected.add(Range.<Integer>all());
210    expected.removeAll(rangeSet);
211    return expected;
212  }
213
214  public void testSubRangeSet() {
215    for (Range<Integer> range1 : QUERY_RANGES) {
216      for (Range<Integer> range2 : QUERY_RANGES) {
217        TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
218        rangeSet.add(range1);
219        rangeSet.add(range2);
220        for (Range<Integer> subRange : QUERY_RANGES) {
221          testViewAgainstExpected(
222              expectedSubRangeSet(rangeSet, subRange), rangeSet.subRangeSet(subRange));
223        }
224      }
225    }
226  }
227
228  public void testComplement() {
229    for (Range<Integer> range1 : QUERY_RANGES) {
230      for (Range<Integer> range2 : QUERY_RANGES) {
231        TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
232        rangeSet.add(range1);
233        rangeSet.add(range2);
234        testViewAgainstExpected(expectedComplement(rangeSet), rangeSet.complement());
235      }
236    }
237  }
238
239  public void testSubRangeSetOfComplement() {
240    for (Range<Integer> range1 : QUERY_RANGES) {
241      for (Range<Integer> range2 : QUERY_RANGES) {
242        TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
243        rangeSet.add(range1);
244        rangeSet.add(range2);
245        for (Range<Integer> subRange : QUERY_RANGES) {
246          testViewAgainstExpected(
247              expectedSubRangeSet(expectedComplement(rangeSet), subRange),
248              rangeSet.complement().subRangeSet(subRange));
249        }
250      }
251    }
252  }
253
254  public void testComplementOfSubRangeSet() {
255    for (Range<Integer> range1 : QUERY_RANGES) {
256      for (Range<Integer> range2 : QUERY_RANGES) {
257        TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
258        rangeSet.add(range1);
259        rangeSet.add(range2);
260        for (Range<Integer> subRange : QUERY_RANGES) {
261          testViewAgainstExpected(
262              expectedComplement(expectedSubRangeSet(rangeSet, subRange)),
263              rangeSet.subRangeSet(subRange).complement());
264        }
265      }
266    }
267  }
268
269  public void testRangesByUpperBound() {
270    for (Range<Integer> range1 : QUERY_RANGES) {
271      for (Range<Integer> range2 : QUERY_RANGES) {
272        TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
273        rangeSet.add(range1);
274        rangeSet.add(range2);
275
276        NavigableMap<Cut<Integer>, Range<Integer>> expectedRangesByUpperBound = Maps.newTreeMap();
277        for (Range<Integer> range : rangeSet.asRanges()) {
278          expectedRangesByUpperBound.put(range.upperBound, range);
279        }
280        testNavigationAgainstExpected(expectedRangesByUpperBound,
281            new TreeRangeSet.RangesByUpperBound<Integer>(rangeSet.rangesByLowerBound),
282            CUTS_TO_TEST);
283      }
284    }
285  }
286
287  public void testMergesConnectedWithOverlap() {
288    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
289    rangeSet.add(Range.closed(1, 4));
290    rangeSet.add(Range.open(2, 6));
291    testInvariants(rangeSet);
292    assertThat(rangeSet.asRanges()).has().item(Range.closedOpen(1, 6));
293    assertThat(rangeSet.complement().asRanges())
294        .has().exactly(Range.lessThan(1), Range.atLeast(6)).inOrder();
295  }
296
297  public void testMergesConnectedDisjoint() {
298    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
299    rangeSet.add(Range.closed(1, 4));
300    rangeSet.add(Range.open(4, 6));
301    testInvariants(rangeSet);
302    assertThat(rangeSet.asRanges()).has().item(Range.closedOpen(1, 6));
303    assertThat(rangeSet.complement().asRanges())
304        .has().exactly(Range.lessThan(1), Range.atLeast(6)).inOrder();
305  }
306
307  public void testIgnoresSmallerSharingNoBound() {
308    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
309    rangeSet.add(Range.closed(1, 6));
310    rangeSet.add(Range.open(2, 4));
311    testInvariants(rangeSet);
312    assertThat(rangeSet.asRanges()).has().item(Range.closed(1, 6));
313    assertThat(rangeSet.complement().asRanges())
314        .has().exactly(Range.lessThan(1), Range.greaterThan(6)).inOrder();
315  }
316
317  public void testIgnoresSmallerSharingLowerBound() {
318    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
319    rangeSet.add(Range.closed(1, 6));
320    rangeSet.add(Range.closed(1, 4));
321    testInvariants(rangeSet);
322    assertThat(rangeSet.asRanges()).has().item(Range.closed(1, 6));
323    assertThat(rangeSet.complement().asRanges())
324        .has().exactly(Range.lessThan(1), Range.greaterThan(6)).inOrder();
325  }
326
327  public void testIgnoresSmallerSharingUpperBound() {
328    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
329    rangeSet.add(Range.closed(1, 6));
330    rangeSet.add(Range.closed(3, 6));
331    testInvariants(rangeSet);
332    assertThat(rangeSet.asRanges()).has().item(Range.closed(1, 6));
333    assertThat(rangeSet.complement().asRanges())
334        .has().exactly(Range.lessThan(1), Range.greaterThan(6)).inOrder();
335  }
336
337  public void testIgnoresEqual() {
338    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
339    rangeSet.add(Range.closed(1, 6));
340    rangeSet.add(Range.closed(1, 6));
341    testInvariants(rangeSet);
342    assertThat(rangeSet.asRanges()).has().item(Range.closed(1, 6));
343    assertThat(rangeSet.complement().asRanges())
344        .has().exactly(Range.lessThan(1), Range.greaterThan(6)).inOrder();
345  }
346
347  public void testExtendSameLowerBound() {
348    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
349    rangeSet.add(Range.closed(1, 4));
350    rangeSet.add(Range.closed(1, 6));
351    testInvariants(rangeSet);
352    assertThat(rangeSet.asRanges()).has().item(Range.closed(1, 6));
353    assertThat(rangeSet.complement().asRanges())
354        .has().exactly(Range.lessThan(1), Range.greaterThan(6)).inOrder();
355  }
356
357  public void testExtendSameUpperBound() {
358    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
359    rangeSet.add(Range.closed(3, 6));
360    rangeSet.add(Range.closed(1, 6));
361    testInvariants(rangeSet);
362    assertThat(rangeSet.asRanges()).has().item(Range.closed(1, 6));
363    assertThat(rangeSet.complement().asRanges())
364        .has().exactly(Range.lessThan(1), Range.greaterThan(6)).inOrder();
365  }
366
367  public void testExtendBothDirections() {
368    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
369    rangeSet.add(Range.closed(3, 4));
370    rangeSet.add(Range.closed(1, 6));
371    testInvariants(rangeSet);
372    assertThat(rangeSet.asRanges()).has().item(Range.closed(1, 6));
373    assertThat(rangeSet.complement().asRanges())
374        .has().exactly(Range.lessThan(1), Range.greaterThan(6)).inOrder();
375  }
376
377  public void testAddEmpty() {
378    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
379    rangeSet.add(Range.closedOpen(3, 3));
380    testInvariants(rangeSet);
381    assertThat(rangeSet.asRanges()).isEmpty();
382    assertThat(rangeSet.complement().asRanges()).has().exactly(Range.<Integer>all()).inOrder();
383  }
384
385  public void testFillHoleExactly() {
386    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
387    rangeSet.add(Range.closedOpen(1, 3));
388    rangeSet.add(Range.closedOpen(4, 6));
389    rangeSet.add(Range.closedOpen(3, 4));
390    testInvariants(rangeSet);
391    assertThat(rangeSet.asRanges()).has().item(Range.closedOpen(1, 6));
392    assertThat(rangeSet.complement().asRanges())
393        .has().exactly(Range.lessThan(1), Range.atLeast(6)).inOrder();
394  }
395
396  public void testFillHoleWithOverlap() {
397    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
398    rangeSet.add(Range.closedOpen(1, 3));
399    rangeSet.add(Range.closedOpen(4, 6));
400    rangeSet.add(Range.closedOpen(2, 5));
401    testInvariants(rangeSet);
402    assertThat(rangeSet.asRanges()).has().item(Range.closedOpen(1, 6));
403    assertThat(rangeSet.complement().asRanges())
404        .has().exactly(Range.lessThan(1), Range.atLeast(6)).inOrder();
405  }
406
407  public void testAddManyPairs() {
408    for (int aLow = 0; aLow < 6; aLow++) {
409      for (int aHigh = 0; aHigh < 6; aHigh++) {
410        for (BoundType aLowType : BoundType.values()) {
411          for (BoundType aHighType : BoundType.values()) {
412            if ((aLow == aHigh && aLowType == OPEN && aHighType == OPEN) || aLow > aHigh) {
413              continue;
414            }
415            for (int bLow = 0; bLow < 6; bLow++) {
416              for (int bHigh = 0; bHigh < 6; bHigh++) {
417                for (BoundType bLowType : BoundType.values()) {
418                  for (BoundType bHighType : BoundType.values()) {
419                    if ((bLow == bHigh && bLowType == OPEN && bHighType == OPEN) || bLow > bHigh) {
420                      continue;
421                    }
422                    doPairTest(range(aLow, aLowType, aHigh, aHighType),
423                        range(bLow, bLowType, bHigh, bHighType));
424                  }
425                }
426              }
427            }
428          }
429        }
430      }
431    }
432  }
433
434  private static void doPairTest(Range<Integer> a, Range<Integer> b) {
435    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
436    rangeSet.add(a);
437    rangeSet.add(b);
438    if (a.isEmpty() && b.isEmpty()) {
439      assertThat(rangeSet.asRanges()).isEmpty();
440    } else if (a.isEmpty()) {
441      assertThat(rangeSet.asRanges()).has().item(b);
442    } else if (b.isEmpty()) {
443      assertThat(rangeSet.asRanges()).has().item(a);
444    } else if (a.isConnected(b)) {
445      assertThat(rangeSet.asRanges()).has().exactly(a.span(b)).inOrder();
446    } else {
447      if (a.lowerEndpoint() < b.lowerEndpoint()) {
448        assertThat(rangeSet.asRanges()).has().exactly(a, b).inOrder();
449      } else {
450        assertThat(rangeSet.asRanges()).has().exactly(b, a).inOrder();
451      }
452    }
453  }
454
455  public void testRemoveEmpty() {
456    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
457    rangeSet.add(Range.closed(1, 6));
458    rangeSet.remove(Range.closedOpen(3, 3));
459    testInvariants(rangeSet);
460    assertThat(rangeSet.asRanges()).has().item(Range.closed(1, 6));
461    assertThat(rangeSet.complement().asRanges())
462        .has().exactly(Range.lessThan(1), Range.greaterThan(6)).inOrder();
463  }
464
465  public void testRemovePartSharingLowerBound() {
466    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
467    rangeSet.add(Range.closed(3, 5));
468    rangeSet.remove(Range.closedOpen(3, 5));
469    testInvariants(rangeSet);
470    assertThat(rangeSet.asRanges()).has().item(Range.singleton(5));
471    assertThat(rangeSet.complement().asRanges())
472        .has().exactly(Range.lessThan(5), Range.greaterThan(5)).inOrder();
473  }
474
475  public void testRemovePartSharingUpperBound() {
476    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
477    rangeSet.add(Range.closed(3, 5));
478    rangeSet.remove(Range.openClosed(3, 5));
479    testInvariants(rangeSet);
480    assertThat(rangeSet.asRanges()).has().item(Range.singleton(3));
481    assertThat(rangeSet.complement().asRanges())
482        .has().exactly(Range.lessThan(3), Range.greaterThan(3)).inOrder();
483  }
484
485  public void testRemoveMiddle() {
486    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
487    rangeSet.add(Range.atMost(6));
488    rangeSet.remove(Range.closedOpen(3, 4));
489    testInvariants(rangeSet);
490    assertThat(rangeSet.asRanges()).has().exactly(Range.lessThan(3), Range.closed(4, 6)).inOrder();
491    assertThat(rangeSet.complement().asRanges())
492        .has().exactly(Range.closedOpen(3, 4), Range.greaterThan(6)).inOrder();
493  }
494
495  public void testRemoveNoOverlap() {
496    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
497    rangeSet.add(Range.closed(3, 6));
498    rangeSet.remove(Range.closedOpen(1, 3));
499    testInvariants(rangeSet);
500    assertThat(rangeSet.asRanges()).has().exactly(Range.closed(3, 6)).inOrder();
501  }
502
503  public void testRemovePartFromBelowLowerBound() {
504    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
505    rangeSet.add(Range.closed(3, 6));
506    rangeSet.remove(Range.closed(1, 3));
507    testInvariants(rangeSet);
508    assertThat(rangeSet.asRanges()).has().exactly(Range.openClosed(3, 6)).inOrder();
509  }
510
511  public void testRemovePartFromAboveUpperBound() {
512    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
513    rangeSet.add(Range.closed(3, 6));
514    rangeSet.remove(Range.closed(6, 9));
515    testInvariants(rangeSet);
516    assertThat(rangeSet.asRanges()).has().exactly(Range.closedOpen(3, 6)).inOrder();
517  }
518
519  public void testRemoveExact() {
520    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
521    rangeSet.add(Range.closed(3, 6));
522    rangeSet.remove(Range.closed(3, 6));
523    testInvariants(rangeSet);
524    assertThat(rangeSet.asRanges()).isEmpty();
525  }
526
527  public void testRemoveAllFromBelowLowerBound() {
528    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
529    rangeSet.add(Range.closed(3, 6));
530    rangeSet.remove(Range.closed(2, 6));
531    testInvariants(rangeSet);
532    assertThat(rangeSet.asRanges()).isEmpty();
533  }
534
535  public void testRemoveAllFromAboveUpperBound() {
536    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
537    rangeSet.add(Range.closed(3, 6));
538    rangeSet.remove(Range.closed(3, 7));
539    testInvariants(rangeSet);
540    assertThat(rangeSet.asRanges()).isEmpty();
541  }
542
543  public void testRemoveAllExtendingBothDirections() {
544    TreeRangeSet<Integer> rangeSet = TreeRangeSet.create();
545    rangeSet.add(Range.closed(3, 6));
546    rangeSet.remove(Range.closed(2, 7));
547    testInvariants(rangeSet);
548    assertThat(rangeSet.asRanges()).isEmpty();
549  }
550
551  public void testRangeContaining1() {
552    RangeSet<Integer> rangeSet = TreeRangeSet.create();
553    rangeSet.add(Range.closed(3, 10));
554    assertEquals(Range.closed(3, 10), rangeSet.rangeContaining(5));
555    assertTrue(rangeSet.contains(5));
556    assertNull(rangeSet.rangeContaining(1));
557    assertFalse(rangeSet.contains(1));
558  }
559
560  public void testRangeContaining2() {
561    RangeSet<Integer> rangeSet = TreeRangeSet.create();
562    rangeSet.add(Range.closed(3, 10));
563    rangeSet.remove(Range.open(5, 7));
564    assertEquals(Range.closed(3, 5), rangeSet.rangeContaining(5));
565    assertTrue(rangeSet.contains(5));
566    assertEquals(Range.closed(7, 10), rangeSet.rangeContaining(8));
567    assertTrue(rangeSet.contains(8));
568    assertNull(rangeSet.rangeContaining(6));
569    assertFalse(rangeSet.contains(6));
570  }
571}
572