View Javadoc
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.base.Preconditions.checkArgument;
18  import static com.google.common.base.Preconditions.checkNotNull;
19  
20  import com.google.common.annotations.Beta;
21  import com.google.common.annotations.GwtIncompatible;
22  import com.google.common.annotations.VisibleForTesting;
23  import com.google.common.base.MoreObjects;
24  import java.io.Serializable;
25  import java.util.Collection;
26  import java.util.Comparator;
27  import java.util.Iterator;
28  import java.util.Map.Entry;
29  import java.util.NavigableMap;
30  import java.util.NoSuchElementException;
31  import java.util.Set;
32  import java.util.TreeMap;
33  import javax.annotation.Nullable;
34  
35  /**
36   * An implementation of {@link RangeSet} backed by a {@link TreeMap}.
37   *
38   * @author Louis Wasserman
39   * @since 14.0
40   */
41  @Beta
42  @GwtIncompatible // uses NavigableMap
43  public class TreeRangeSet<C extends Comparable<?>> extends AbstractRangeSet<C>
44      implements Serializable {
45  
46    @VisibleForTesting final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
47  
48    /**
49     * Creates an empty {@code TreeRangeSet} instance.
50     */
51    public static <C extends Comparable<?>> TreeRangeSet<C> create() {
52      return new TreeRangeSet<C>(new TreeMap<Cut<C>, Range<C>>());
53    }
54  
55    /**
56     * Returns a {@code TreeRangeSet} initialized with the ranges in the specified range set.
57     */
58    public static <C extends Comparable<?>> TreeRangeSet<C> create(RangeSet<C> rangeSet) {
59      TreeRangeSet<C> result = create();
60      result.addAll(rangeSet);
61      return result;
62    }
63  
64    /**
65     * Returns a {@code TreeRangeSet} representing the union of the specified ranges.
66     *
67     * <p>This is the smallest {@code RangeSet} which encloses each of the specified ranges. An
68     * element will be contained in this {@code RangeSet} if and only if it is contained in at least
69     * one {@code Range} in {@code ranges}.
70     *
71     * @since 21.0
72     */
73    public static <C extends Comparable<?>> TreeRangeSet<C> create(Iterable<Range<C>> ranges) {
74      TreeRangeSet<C> result = create();
75      result.addAll(ranges);
76      return result;
77    }
78  
79    private TreeRangeSet(NavigableMap<Cut<C>, Range<C>> rangesByLowerCut) {
80      this.rangesByLowerBound = rangesByLowerCut;
81    }
82  
83    private transient Set<Range<C>> asRanges;
84    private transient Set<Range<C>> asDescendingSetOfRanges;
85  
86    @Override
87    public Set<Range<C>> asRanges() {
88      Set<Range<C>> result = asRanges;
89      return (result == null) ? asRanges = new AsRanges(rangesByLowerBound.values()) : result;
90    }
91  
92    @Override
93    public Set<Range<C>> asDescendingSetOfRanges() {
94      Set<Range<C>> result = asDescendingSetOfRanges;
95      return (result == null)
96          ? asDescendingSetOfRanges = new AsRanges(rangesByLowerBound.descendingMap().values())
97          : result;
98    }
99  
100   final class AsRanges extends ForwardingCollection<Range<C>> implements Set<Range<C>> {
101 
102     final Collection<Range<C>> delegate;
103 
104     AsRanges(Collection<Range<C>> delegate) {
105       this.delegate = delegate;
106     }
107 
108     @Override
109     protected Collection<Range<C>> delegate() {
110       return delegate;
111     }
112 
113     @Override
114     public int hashCode() {
115       return Sets.hashCodeImpl(this);
116     }
117 
118     @Override
119     public boolean equals(@Nullable Object o) {
120       return Sets.equalsImpl(this, o);
121     }
122   }
123 
124   @Override
125   @Nullable
126   public Range<C> rangeContaining(C value) {
127     checkNotNull(value);
128     Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(Cut.belowValue(value));
129     if (floorEntry != null && floorEntry.getValue().contains(value)) {
130       return floorEntry.getValue();
131     } else {
132       // TODO(kevinb): revisit this design choice
133       return null;
134     }
135   }
136 
137   @Override
138   public boolean intersects(Range<C> range) {
139     checkNotNull(range);
140     Entry<Cut<C>, Range<C>> ceilingEntry = rangesByLowerBound.ceilingEntry(range.lowerBound);
141     if (ceilingEntry != null
142         && ceilingEntry.getValue().isConnected(range)
143         && !ceilingEntry.getValue().intersection(range).isEmpty()) {
144       return true;
145     }
146     Entry<Cut<C>, Range<C>> priorEntry = rangesByLowerBound.lowerEntry(range.lowerBound);
147     return priorEntry != null
148         && priorEntry.getValue().isConnected(range)
149         && !priorEntry.getValue().intersection(range).isEmpty();
150   }
151 
152   @Override
153   public boolean encloses(Range<C> range) {
154     checkNotNull(range);
155     Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
156     return floorEntry != null && floorEntry.getValue().encloses(range);
157   }
158 
159   @Nullable
160   private Range<C> rangeEnclosing(Range<C> range) {
161     checkNotNull(range);
162     Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
163     return (floorEntry != null && floorEntry.getValue().encloses(range))
164         ? floorEntry.getValue()
165         : null;
166   }
167 
168   @Override
169   public Range<C> span() {
170     Entry<Cut<C>, Range<C>> firstEntry = rangesByLowerBound.firstEntry();
171     Entry<Cut<C>, Range<C>> lastEntry = rangesByLowerBound.lastEntry();
172     if (firstEntry == null) {
173       throw new NoSuchElementException();
174     }
175     return Range.create(firstEntry.getValue().lowerBound, lastEntry.getValue().upperBound);
176   }
177 
178   @Override
179   public void add(Range<C> rangeToAdd) {
180     checkNotNull(rangeToAdd);
181 
182     if (rangeToAdd.isEmpty()) {
183       return;
184     }
185 
186     // We will use { } to illustrate ranges currently in the range set, and < >
187     // to illustrate rangeToAdd.
188     Cut<C> lbToAdd = rangeToAdd.lowerBound;
189     Cut<C> ubToAdd = rangeToAdd.upperBound;
190 
191     Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(lbToAdd);
192     if (entryBelowLB != null) {
193       // { <
194       Range<C> rangeBelowLB = entryBelowLB.getValue();
195       if (rangeBelowLB.upperBound.compareTo(lbToAdd) >= 0) {
196         // { < }, and we will need to coalesce
197         if (rangeBelowLB.upperBound.compareTo(ubToAdd) >= 0) {
198           // { < > }
199           ubToAdd = rangeBelowLB.upperBound;
200           /*
201            * TODO(cpovirk): can we just "return;" here? Or, can we remove this if() entirely? If
202            * not, add tests to demonstrate the problem with each approach
203            */
204         }
205         lbToAdd = rangeBelowLB.lowerBound;
206       }
207     }
208 
209     Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(ubToAdd);
210     if (entryBelowUB != null) {
211       // { >
212       Range<C> rangeBelowUB = entryBelowUB.getValue();
213       if (rangeBelowUB.upperBound.compareTo(ubToAdd) >= 0) {
214         // { > }, and we need to coalesce
215         ubToAdd = rangeBelowUB.upperBound;
216       }
217     }
218 
219     // Remove ranges which are strictly enclosed.
220     rangesByLowerBound.subMap(lbToAdd, ubToAdd).clear();
221 
222     replaceRangeWithSameLowerBound(Range.create(lbToAdd, ubToAdd));
223   }
224 
225   @Override
226   public void remove(Range<C> rangeToRemove) {
227     checkNotNull(rangeToRemove);
228 
229     if (rangeToRemove.isEmpty()) {
230       return;
231     }
232 
233     // We will use { } to illustrate ranges currently in the range set, and < >
234     // to illustrate rangeToRemove.
235 
236     Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
237     if (entryBelowLB != null) {
238       // { <
239       Range<C> rangeBelowLB = entryBelowLB.getValue();
240       if (rangeBelowLB.upperBound.compareTo(rangeToRemove.lowerBound) >= 0) {
241         // { < }, and we will need to subdivide
242         if (rangeToRemove.hasUpperBound()
243             && rangeBelowLB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) {
244           // { < > }
245           replaceRangeWithSameLowerBound(
246               Range.create(rangeToRemove.upperBound, rangeBelowLB.upperBound));
247         }
248         replaceRangeWithSameLowerBound(
249             Range.create(rangeBelowLB.lowerBound, rangeToRemove.lowerBound));
250       }
251     }
252 
253     Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(rangeToRemove.upperBound);
254     if (entryBelowUB != null) {
255       // { >
256       Range<C> rangeBelowUB = entryBelowUB.getValue();
257       if (rangeToRemove.hasUpperBound()
258           && rangeBelowUB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) {
259         // { > }
260         replaceRangeWithSameLowerBound(
261             Range.create(rangeToRemove.upperBound, rangeBelowUB.upperBound));
262       }
263     }
264 
265     rangesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
266   }
267 
268   private void replaceRangeWithSameLowerBound(Range<C> range) {
269     if (range.isEmpty()) {
270       rangesByLowerBound.remove(range.lowerBound);
271     } else {
272       rangesByLowerBound.put(range.lowerBound, range);
273     }
274   }
275 
276   private transient RangeSet<C> complement;
277 
278   @Override
279   public RangeSet<C> complement() {
280     RangeSet<C> result = complement;
281     return (result == null) ? complement = new Complement() : result;
282   }
283 
284   @VisibleForTesting
285   static final class RangesByUpperBound<C extends Comparable<?>>
286       extends AbstractNavigableMap<Cut<C>, Range<C>> {
287     private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
288 
289     /**
290      * upperBoundWindow represents the headMap/subMap/tailMap view of the entire "ranges by upper
291      * bound" map; it's a constraint on the *keys*, and does not affect the values.
292      */
293     private final Range<Cut<C>> upperBoundWindow;
294 
295     RangesByUpperBound(NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) {
296       this.rangesByLowerBound = rangesByLowerBound;
297       this.upperBoundWindow = Range.all();
298     }
299 
300     private RangesByUpperBound(
301         NavigableMap<Cut<C>, Range<C>> rangesByLowerBound, Range<Cut<C>> upperBoundWindow) {
302       this.rangesByLowerBound = rangesByLowerBound;
303       this.upperBoundWindow = upperBoundWindow;
304     }
305 
306     private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) {
307       if (window.isConnected(upperBoundWindow)) {
308         return new RangesByUpperBound<C>(rangesByLowerBound, window.intersection(upperBoundWindow));
309       } else {
310         return ImmutableSortedMap.of();
311       }
312     }
313 
314     @Override
315     public NavigableMap<Cut<C>, Range<C>> subMap(
316         Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
317       return subMap(
318           Range.range(
319               fromKey, BoundType.forBoolean(fromInclusive),
320               toKey, BoundType.forBoolean(toInclusive)));
321     }
322 
323     @Override
324     public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
325       return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
326     }
327 
328     @Override
329     public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
330       return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
331     }
332 
333     @Override
334     public Comparator<? super Cut<C>> comparator() {
335       return Ordering.<Cut<C>>natural();
336     }
337 
338     @Override
339     public boolean containsKey(@Nullable Object key) {
340       return get(key) != null;
341     }
342 
343     @Override
344     public Range<C> get(@Nullable Object key) {
345       if (key instanceof Cut) {
346         try {
347           @SuppressWarnings("unchecked") // we catch CCEs
348           Cut<C> cut = (Cut<C>) key;
349           if (!upperBoundWindow.contains(cut)) {
350             return null;
351           }
352           Entry<Cut<C>, Range<C>> candidate = rangesByLowerBound.lowerEntry(cut);
353           if (candidate != null && candidate.getValue().upperBound.equals(cut)) {
354             return candidate.getValue();
355           }
356         } catch (ClassCastException e) {
357           return null;
358         }
359       }
360       return null;
361     }
362 
363     @Override
364     Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
365       /*
366        * We want to start the iteration at the first range where the upper bound is in
367        * upperBoundWindow.
368        */
369       final Iterator<Range<C>> backingItr;
370       if (!upperBoundWindow.hasLowerBound()) {
371         backingItr = rangesByLowerBound.values().iterator();
372       } else {
373         Entry<Cut<C>, Range<C>> lowerEntry =
374             rangesByLowerBound.lowerEntry(upperBoundWindow.lowerEndpoint());
375         if (lowerEntry == null) {
376           backingItr = rangesByLowerBound.values().iterator();
377         } else if (upperBoundWindow.lowerBound.isLessThan(lowerEntry.getValue().upperBound)) {
378           backingItr = rangesByLowerBound.tailMap(lowerEntry.getKey(), true).values().iterator();
379         } else {
380           backingItr =
381               rangesByLowerBound
382                   .tailMap(upperBoundWindow.lowerEndpoint(), true)
383                   .values()
384                   .iterator();
385         }
386       }
387       return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
388         @Override
389         protected Entry<Cut<C>, Range<C>> computeNext() {
390           if (!backingItr.hasNext()) {
391             return endOfData();
392           }
393           Range<C> range = backingItr.next();
394           if (upperBoundWindow.upperBound.isLessThan(range.upperBound)) {
395             return endOfData();
396           } else {
397             return Maps.immutableEntry(range.upperBound, range);
398           }
399         }
400       };
401     }
402 
403     @Override
404     Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
405       Collection<Range<C>> candidates;
406       if (upperBoundWindow.hasUpperBound()) {
407         candidates =
408             rangesByLowerBound
409                 .headMap(upperBoundWindow.upperEndpoint(), false)
410                 .descendingMap()
411                 .values();
412       } else {
413         candidates = rangesByLowerBound.descendingMap().values();
414       }
415       final PeekingIterator<Range<C>> backingItr = Iterators.peekingIterator(candidates.iterator());
416       if (backingItr.hasNext()
417           && upperBoundWindow.upperBound.isLessThan(backingItr.peek().upperBound)) {
418         backingItr.next();
419       }
420       return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
421         @Override
422         protected Entry<Cut<C>, Range<C>> computeNext() {
423           if (!backingItr.hasNext()) {
424             return endOfData();
425           }
426           Range<C> range = backingItr.next();
427           return upperBoundWindow.lowerBound.isLessThan(range.upperBound)
428               ? Maps.immutableEntry(range.upperBound, range)
429               : endOfData();
430         }
431       };
432     }
433 
434     @Override
435     public int size() {
436       if (upperBoundWindow.equals(Range.all())) {
437         return rangesByLowerBound.size();
438       }
439       return Iterators.size(entryIterator());
440     }
441 
442     @Override
443     public boolean isEmpty() {
444       return upperBoundWindow.equals(Range.all())
445           ? rangesByLowerBound.isEmpty()
446           : !entryIterator().hasNext();
447     }
448   }
449 
450   private static final class ComplementRangesByLowerBound<C extends Comparable<?>>
451       extends AbstractNavigableMap<Cut<C>, Range<C>> {
452     private final NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound;
453     private final NavigableMap<Cut<C>, Range<C>> positiveRangesByUpperBound;
454 
455     /**
456      * complementLowerBoundWindow represents the headMap/subMap/tailMap view of the entire
457      * "complement ranges by lower bound" map; it's a constraint on the *keys*, and does not affect
458      * the values.
459      */
460     private final Range<Cut<C>> complementLowerBoundWindow;
461 
462     ComplementRangesByLowerBound(NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound) {
463       this(positiveRangesByLowerBound, Range.<Cut<C>>all());
464     }
465 
466     private ComplementRangesByLowerBound(
467         NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound, Range<Cut<C>> window) {
468       this.positiveRangesByLowerBound = positiveRangesByLowerBound;
469       this.positiveRangesByUpperBound = new RangesByUpperBound<C>(positiveRangesByLowerBound);
470       this.complementLowerBoundWindow = window;
471     }
472 
473     private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> subWindow) {
474       if (!complementLowerBoundWindow.isConnected(subWindow)) {
475         return ImmutableSortedMap.of();
476       } else {
477         subWindow = subWindow.intersection(complementLowerBoundWindow);
478         return new ComplementRangesByLowerBound<C>(positiveRangesByLowerBound, subWindow);
479       }
480     }
481 
482     @Override
483     public NavigableMap<Cut<C>, Range<C>> subMap(
484         Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
485       return subMap(
486           Range.range(
487               fromKey, BoundType.forBoolean(fromInclusive),
488               toKey, BoundType.forBoolean(toInclusive)));
489     }
490 
491     @Override
492     public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
493       return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
494     }
495 
496     @Override
497     public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
498       return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
499     }
500 
501     @Override
502     public Comparator<? super Cut<C>> comparator() {
503       return Ordering.<Cut<C>>natural();
504     }
505 
506     @Override
507     Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
508       /*
509        * firstComplementRangeLowerBound is the first complement range lower bound inside
510        * complementLowerBoundWindow. Complement range lower bounds are either positive range upper
511        * bounds, or Cut.belowAll().
512        *
513        * positiveItr starts at the first positive range with lower bound greater than
514        * firstComplementRangeLowerBound. (Positive range lower bounds correspond to complement range
515        * upper bounds.)
516        */
517       Collection<Range<C>> positiveRanges;
518       if (complementLowerBoundWindow.hasLowerBound()) {
519         positiveRanges =
520             positiveRangesByUpperBound
521                 .tailMap(
522                     complementLowerBoundWindow.lowerEndpoint(),
523                     complementLowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
524                 .values();
525       } else {
526         positiveRanges = positiveRangesByUpperBound.values();
527       }
528       final PeekingIterator<Range<C>> positiveItr =
529           Iterators.peekingIterator(positiveRanges.iterator());
530       final Cut<C> firstComplementRangeLowerBound;
531       if (complementLowerBoundWindow.contains(Cut.<C>belowAll())
532           && (!positiveItr.hasNext() || positiveItr.peek().lowerBound != Cut.<C>belowAll())) {
533         firstComplementRangeLowerBound = Cut.belowAll();
534       } else if (positiveItr.hasNext()) {
535         firstComplementRangeLowerBound = positiveItr.next().upperBound;
536       } else {
537         return Iterators.emptyIterator();
538       }
539       return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
540         Cut<C> nextComplementRangeLowerBound = firstComplementRangeLowerBound;
541 
542         @Override
543         protected Entry<Cut<C>, Range<C>> computeNext() {
544           if (complementLowerBoundWindow.upperBound.isLessThan(nextComplementRangeLowerBound)
545               || nextComplementRangeLowerBound == Cut.<C>aboveAll()) {
546             return endOfData();
547           }
548           Range<C> negativeRange;
549           if (positiveItr.hasNext()) {
550             Range<C> positiveRange = positiveItr.next();
551             negativeRange = Range.create(nextComplementRangeLowerBound, positiveRange.lowerBound);
552             nextComplementRangeLowerBound = positiveRange.upperBound;
553           } else {
554             negativeRange = Range.create(nextComplementRangeLowerBound, Cut.<C>aboveAll());
555             nextComplementRangeLowerBound = Cut.aboveAll();
556           }
557           return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
558         }
559       };
560     }
561 
562     @Override
563     Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
564       /*
565        * firstComplementRangeUpperBound is the upper bound of the last complement range with lower
566        * bound inside complementLowerBoundWindow.
567        *
568        * positiveItr starts at the first positive range with upper bound less than
569        * firstComplementRangeUpperBound. (Positive range upper bounds correspond to complement range
570        * lower bounds.)
571        */
572       Cut<C> startingPoint =
573           complementLowerBoundWindow.hasUpperBound()
574               ? complementLowerBoundWindow.upperEndpoint()
575               : Cut.<C>aboveAll();
576       boolean inclusive =
577           complementLowerBoundWindow.hasUpperBound()
578               && complementLowerBoundWindow.upperBoundType() == BoundType.CLOSED;
579       final PeekingIterator<Range<C>> positiveItr =
580           Iterators.peekingIterator(
581               positiveRangesByUpperBound
582                   .headMap(startingPoint, inclusive)
583                   .descendingMap()
584                   .values()
585                   .iterator());
586       Cut<C> cut;
587       if (positiveItr.hasNext()) {
588         cut =
589             (positiveItr.peek().upperBound == Cut.<C>aboveAll())
590                 ? positiveItr.next().lowerBound
591                 : positiveRangesByLowerBound.higherKey(positiveItr.peek().upperBound);
592       } else if (!complementLowerBoundWindow.contains(Cut.<C>belowAll())
593           || positiveRangesByLowerBound.containsKey(Cut.belowAll())) {
594         return Iterators.emptyIterator();
595       } else {
596         cut = positiveRangesByLowerBound.higherKey(Cut.<C>belowAll());
597       }
598       final Cut<C> firstComplementRangeUpperBound =
599           MoreObjects.firstNonNull(cut, Cut.<C>aboveAll());
600       return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
601         Cut<C> nextComplementRangeUpperBound = firstComplementRangeUpperBound;
602 
603         @Override
604         protected Entry<Cut<C>, Range<C>> computeNext() {
605           if (nextComplementRangeUpperBound == Cut.<C>belowAll()) {
606             return endOfData();
607           } else if (positiveItr.hasNext()) {
608             Range<C> positiveRange = positiveItr.next();
609             Range<C> negativeRange =
610                 Range.create(positiveRange.upperBound, nextComplementRangeUpperBound);
611             nextComplementRangeUpperBound = positiveRange.lowerBound;
612             if (complementLowerBoundWindow.lowerBound.isLessThan(negativeRange.lowerBound)) {
613               return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
614             }
615           } else if (complementLowerBoundWindow.lowerBound.isLessThan(Cut.<C>belowAll())) {
616             Range<C> negativeRange = Range.create(Cut.<C>belowAll(), nextComplementRangeUpperBound);
617             nextComplementRangeUpperBound = Cut.belowAll();
618             return Maps.immutableEntry(Cut.<C>belowAll(), negativeRange);
619           }
620           return endOfData();
621         }
622       };
623     }
624 
625     @Override
626     public int size() {
627       return Iterators.size(entryIterator());
628     }
629 
630     @Override
631     @Nullable
632     public Range<C> get(Object key) {
633       if (key instanceof Cut) {
634         try {
635           @SuppressWarnings("unchecked")
636           Cut<C> cut = (Cut<C>) key;
637           // tailMap respects the current window
638           Entry<Cut<C>, Range<C>> firstEntry = tailMap(cut, true).firstEntry();
639           if (firstEntry != null && firstEntry.getKey().equals(cut)) {
640             return firstEntry.getValue();
641           }
642         } catch (ClassCastException e) {
643           return null;
644         }
645       }
646       return null;
647     }
648 
649     @Override
650     public boolean containsKey(Object key) {
651       return get(key) != null;
652     }
653   }
654 
655   private final class Complement extends TreeRangeSet<C> {
656     Complement() {
657       super(new ComplementRangesByLowerBound<C>(TreeRangeSet.this.rangesByLowerBound));
658     }
659 
660     @Override
661     public void add(Range<C> rangeToAdd) {
662       TreeRangeSet.this.remove(rangeToAdd);
663     }
664 
665     @Override
666     public void remove(Range<C> rangeToRemove) {
667       TreeRangeSet.this.add(rangeToRemove);
668     }
669 
670     @Override
671     public boolean contains(C value) {
672       return !TreeRangeSet.this.contains(value);
673     }
674 
675     @Override
676     public RangeSet<C> complement() {
677       return TreeRangeSet.this;
678     }
679   }
680 
681   private static final class SubRangeSetRangesByLowerBound<C extends Comparable<?>>
682       extends AbstractNavigableMap<Cut<C>, Range<C>> {
683     /**
684      * lowerBoundWindow is the headMap/subMap/tailMap view; it only restricts the keys, and does not
685      * affect the values.
686      */
687     private final Range<Cut<C>> lowerBoundWindow;
688 
689     /**
690      * restriction is the subRangeSet view; ranges are truncated to their intersection with
691      * restriction.
692      */
693     private final Range<C> restriction;
694 
695     private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
696     private final NavigableMap<Cut<C>, Range<C>> rangesByUpperBound;
697 
698     private SubRangeSetRangesByLowerBound(
699         Range<Cut<C>> lowerBoundWindow,
700         Range<C> restriction,
701         NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) {
702       this.lowerBoundWindow = checkNotNull(lowerBoundWindow);
703       this.restriction = checkNotNull(restriction);
704       this.rangesByLowerBound = checkNotNull(rangesByLowerBound);
705       this.rangesByUpperBound = new RangesByUpperBound<C>(rangesByLowerBound);
706     }
707 
708     private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) {
709       if (!window.isConnected(lowerBoundWindow)) {
710         return ImmutableSortedMap.of();
711       } else {
712         return new SubRangeSetRangesByLowerBound<C>(
713             lowerBoundWindow.intersection(window), restriction, rangesByLowerBound);
714       }
715     }
716 
717     @Override
718     public NavigableMap<Cut<C>, Range<C>> subMap(
719         Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
720       return subMap(
721           Range.range(
722               fromKey,
723               BoundType.forBoolean(fromInclusive),
724               toKey,
725               BoundType.forBoolean(toInclusive)));
726     }
727 
728     @Override
729     public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
730       return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
731     }
732 
733     @Override
734     public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
735       return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
736     }
737 
738     @Override
739     public Comparator<? super Cut<C>> comparator() {
740       return Ordering.<Cut<C>>natural();
741     }
742 
743     @Override
744     public boolean containsKey(@Nullable Object key) {
745       return get(key) != null;
746     }
747 
748     @Override
749     @Nullable
750     public Range<C> get(@Nullable Object key) {
751       if (key instanceof Cut) {
752         try {
753           @SuppressWarnings("unchecked") // we catch CCE's
754           Cut<C> cut = (Cut<C>) key;
755           if (!lowerBoundWindow.contains(cut)
756               || cut.compareTo(restriction.lowerBound) < 0
757               || cut.compareTo(restriction.upperBound) >= 0) {
758             return null;
759           } else if (cut.equals(restriction.lowerBound)) {
760             // it might be present, truncated on the left
761             Range<C> candidate = Maps.valueOrNull(rangesByLowerBound.floorEntry(cut));
762             if (candidate != null && candidate.upperBound.compareTo(restriction.lowerBound) > 0) {
763               return candidate.intersection(restriction);
764             }
765           } else {
766             Range<C> result = rangesByLowerBound.get(cut);
767             if (result != null) {
768               return result.intersection(restriction);
769             }
770           }
771         } catch (ClassCastException e) {
772           return null;
773         }
774       }
775       return null;
776     }
777 
778     @Override
779     Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
780       if (restriction.isEmpty()) {
781         return Iterators.emptyIterator();
782       }
783       final Iterator<Range<C>> completeRangeItr;
784       if (lowerBoundWindow.upperBound.isLessThan(restriction.lowerBound)) {
785         return Iterators.emptyIterator();
786       } else if (lowerBoundWindow.lowerBound.isLessThan(restriction.lowerBound)) {
787         // starts at the first range with upper bound strictly greater than restriction.lowerBound
788         completeRangeItr =
789             rangesByUpperBound.tailMap(restriction.lowerBound, false).values().iterator();
790       } else {
791         // starts at the first range with lower bound above lowerBoundWindow.lowerBound
792         completeRangeItr =
793             rangesByLowerBound
794                 .tailMap(
795                     lowerBoundWindow.lowerBound.endpoint(),
796                     lowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
797                 .values()
798                 .iterator();
799       }
800       final Cut<Cut<C>> upperBoundOnLowerBounds =
801           Ordering.natural()
802               .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
803       return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
804         @Override
805         protected Entry<Cut<C>, Range<C>> computeNext() {
806           if (!completeRangeItr.hasNext()) {
807             return endOfData();
808           }
809           Range<C> nextRange = completeRangeItr.next();
810           if (upperBoundOnLowerBounds.isLessThan(nextRange.lowerBound)) {
811             return endOfData();
812           } else {
813             nextRange = nextRange.intersection(restriction);
814             return Maps.immutableEntry(nextRange.lowerBound, nextRange);
815           }
816         }
817       };
818     }
819 
820     @Override
821     Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
822       if (restriction.isEmpty()) {
823         return Iterators.emptyIterator();
824       }
825       Cut<Cut<C>> upperBoundOnLowerBounds =
826           Ordering.natural()
827               .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
828       final Iterator<Range<C>> completeRangeItr =
829           rangesByLowerBound
830               .headMap(
831                   upperBoundOnLowerBounds.endpoint(),
832                   upperBoundOnLowerBounds.typeAsUpperBound() == BoundType.CLOSED)
833               .descendingMap()
834               .values()
835               .iterator();
836       return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
837         @Override
838         protected Entry<Cut<C>, Range<C>> computeNext() {
839           if (!completeRangeItr.hasNext()) {
840             return endOfData();
841           }
842           Range<C> nextRange = completeRangeItr.next();
843           if (restriction.lowerBound.compareTo(nextRange.upperBound) >= 0) {
844             return endOfData();
845           }
846           nextRange = nextRange.intersection(restriction);
847           if (lowerBoundWindow.contains(nextRange.lowerBound)) {
848             return Maps.immutableEntry(nextRange.lowerBound, nextRange);
849           } else {
850             return endOfData();
851           }
852         }
853       };
854     }
855 
856     @Override
857     public int size() {
858       return Iterators.size(entryIterator());
859     }
860   }
861 
862   @Override
863   public RangeSet<C> subRangeSet(Range<C> view) {
864     return view.equals(Range.<C>all()) ? this : new SubRangeSet(view);
865   }
866 
867   private final class SubRangeSet extends TreeRangeSet<C> {
868     private final Range<C> restriction;
869 
870     SubRangeSet(Range<C> restriction) {
871       super(
872           new SubRangeSetRangesByLowerBound<C>(
873               Range.<Cut<C>>all(), restriction, TreeRangeSet.this.rangesByLowerBound));
874       this.restriction = restriction;
875     }
876 
877     @Override
878     public boolean encloses(Range<C> range) {
879       if (!restriction.isEmpty() && restriction.encloses(range)) {
880         Range<C> enclosing = TreeRangeSet.this.rangeEnclosing(range);
881         return enclosing != null && !enclosing.intersection(restriction).isEmpty();
882       }
883       return false;
884     }
885 
886     @Override
887     @Nullable
888     public Range<C> rangeContaining(C value) {
889       if (!restriction.contains(value)) {
890         return null;
891       }
892       Range<C> result = TreeRangeSet.this.rangeContaining(value);
893       return (result == null) ? null : result.intersection(restriction);
894     }
895 
896     @Override
897     public void add(Range<C> rangeToAdd) {
898       checkArgument(
899           restriction.encloses(rangeToAdd),
900           "Cannot add range %s to subRangeSet(%s)",
901           rangeToAdd,
902           restriction);
903       super.add(rangeToAdd);
904     }
905 
906     @Override
907     public void remove(Range<C> rangeToRemove) {
908       if (rangeToRemove.isConnected(restriction)) {
909         TreeRangeSet.this.remove(rangeToRemove.intersection(restriction));
910       }
911     }
912 
913     @Override
914     public boolean contains(C value) {
915       return restriction.contains(value) && TreeRangeSet.this.contains(value);
916     }
917 
918     @Override
919     public void clear() {
920       TreeRangeSet.this.remove(restriction);
921     }
922 
923     @Override
924     public RangeSet<C> subRangeSet(Range<C> view) {
925       if (view.encloses(restriction)) {
926         return this;
927       } else if (view.isConnected(restriction)) {
928         return new SubRangeSet(restriction.intersection(view));
929       } else {
930         return ImmutableRangeSet.of();
931       }
932     }
933   }
934 }