Source code

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