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