Home | History | Annotate | Download | only in collect 
      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 
     15 package com.google.common.collect;
     16 
     17 import static com.google.common.collect.BoundType.OPEN;
     18 import static com.google.common.collect.Range.range;
     19 import static com.google.common.truth.Truth.assertThat;
     20 
     21 import com.google.common.annotations.GwtIncompatible;
     22 
     23 import java.util.List;
     24 import java.util.NavigableMap;
     25 
     26 /**
     27  * Tests for {@link TreeRangeSet}.
     28  *
     29  * @author Louis Wasserman
     30  * @author Chris Povirk
     31  */
     32 @GwtIncompatible("TreeRangeSet")
     33 public 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