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.GwtIncompatible;
021import com.google.common.annotations.VisibleForTesting;
022import com.google.common.base.MoreObjects;
023import com.google.errorprone.annotations.concurrent.LazyInit;
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 javax.annotation.CheckForNull;
034
035/**
036 * An implementation of {@link RangeSet} backed by a {@link TreeMap}.
037 *
038 * @author Louis Wasserman
039 * @since 14.0
040 */
041@GwtIncompatible // uses NavigableMap
042@ElementTypesAreNonnullByDefault
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<>(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  @LazyInit @CheckForNull private transient Set<Range<C>> asRanges;
080  @LazyInit @CheckForNull 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(@CheckForNull Object o) {
116      return Sets.equalsImpl(this, o);
117    }
118  }
119
120  @Override
121  @CheckForNull
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  @CheckForNull
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 || lastEntry == null) {
169      /*
170       * Either both are null or neither is: Either the set is empty, or it's not. But we check both
171       * to make the nullness checker happy.
172       */
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  @LazyInit @CheckForNull 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<>(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(@CheckForNull Object key) {
340      return get(key) != null;
341    }
342
343    @Override
344    @CheckForNull
345    public Range<C> get(@CheckForNull Object key) {
346      if (key instanceof Cut) {
347        try {
348          @SuppressWarnings("unchecked") // we catch CCEs
349          Cut<C> cut = (Cut<C>) key;
350          if (!upperBoundWindow.contains(cut)) {
351            return null;
352          }
353          Entry<Cut<C>, Range<C>> candidate = rangesByLowerBound.lowerEntry(cut);
354          if (candidate != null && candidate.getValue().upperBound.equals(cut)) {
355            return candidate.getValue();
356          }
357        } catch (ClassCastException e) {
358          return null;
359        }
360      }
361      return null;
362    }
363
364    @Override
365    Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
366      /*
367       * We want to start the iteration at the first range where the upper bound is in
368       * upperBoundWindow.
369       */
370      Iterator<Range<C>> backingItr;
371      if (!upperBoundWindow.hasLowerBound()) {
372        backingItr = rangesByLowerBound.values().iterator();
373      } else {
374        Entry<Cut<C>, Range<C>> lowerEntry =
375            rangesByLowerBound.lowerEntry(upperBoundWindow.lowerEndpoint());
376        if (lowerEntry == null) {
377          backingItr = rangesByLowerBound.values().iterator();
378        } else if (upperBoundWindow.lowerBound.isLessThan(lowerEntry.getValue().upperBound)) {
379          backingItr = rangesByLowerBound.tailMap(lowerEntry.getKey(), true).values().iterator();
380        } else {
381          backingItr =
382              rangesByLowerBound
383                  .tailMap(upperBoundWindow.lowerEndpoint(), true)
384                  .values()
385                  .iterator();
386        }
387      }
388      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
389        @Override
390        @CheckForNull
391        protected Entry<Cut<C>, Range<C>> computeNext() {
392          if (!backingItr.hasNext()) {
393            return endOfData();
394          }
395          Range<C> range = backingItr.next();
396          if (upperBoundWindow.upperBound.isLessThan(range.upperBound)) {
397            return endOfData();
398          } else {
399            return Maps.immutableEntry(range.upperBound, range);
400          }
401        }
402      };
403    }
404
405    @Override
406    Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
407      Collection<Range<C>> candidates;
408      if (upperBoundWindow.hasUpperBound()) {
409        candidates =
410            rangesByLowerBound
411                .headMap(upperBoundWindow.upperEndpoint(), false)
412                .descendingMap()
413                .values();
414      } else {
415        candidates = rangesByLowerBound.descendingMap().values();
416      }
417      PeekingIterator<Range<C>> backingItr = Iterators.peekingIterator(candidates.iterator());
418      if (backingItr.hasNext()
419          && upperBoundWindow.upperBound.isLessThan(backingItr.peek().upperBound)) {
420        backingItr.next();
421      }
422      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
423        @Override
424        @CheckForNull
425        protected Entry<Cut<C>, Range<C>> computeNext() {
426          if (!backingItr.hasNext()) {
427            return endOfData();
428          }
429          Range<C> range = backingItr.next();
430          return upperBoundWindow.lowerBound.isLessThan(range.upperBound)
431              ? Maps.immutableEntry(range.upperBound, range)
432              : endOfData();
433        }
434      };
435    }
436
437    @Override
438    public int size() {
439      if (upperBoundWindow.equals(Range.all())) {
440        return rangesByLowerBound.size();
441      }
442      return Iterators.size(entryIterator());
443    }
444
445    @Override
446    public boolean isEmpty() {
447      return upperBoundWindow.equals(Range.all())
448          ? rangesByLowerBound.isEmpty()
449          : !entryIterator().hasNext();
450    }
451  }
452
453  private static final class ComplementRangesByLowerBound<C extends Comparable<?>>
454      extends AbstractNavigableMap<Cut<C>, Range<C>> {
455    private final NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound;
456    private final NavigableMap<Cut<C>, Range<C>> positiveRangesByUpperBound;
457
458    /**
459     * complementLowerBoundWindow represents the headMap/subMap/tailMap view of the entire
460     * "complement ranges by lower bound" map; it's a constraint on the *keys*, and does not affect
461     * the values.
462     */
463    private final Range<Cut<C>> complementLowerBoundWindow;
464
465    ComplementRangesByLowerBound(NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound) {
466      this(positiveRangesByLowerBound, Range.<Cut<C>>all());
467    }
468
469    private ComplementRangesByLowerBound(
470        NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound, Range<Cut<C>> window) {
471      this.positiveRangesByLowerBound = positiveRangesByLowerBound;
472      this.positiveRangesByUpperBound = new RangesByUpperBound<>(positiveRangesByLowerBound);
473      this.complementLowerBoundWindow = window;
474    }
475
476    private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> subWindow) {
477      if (!complementLowerBoundWindow.isConnected(subWindow)) {
478        return ImmutableSortedMap.of();
479      } else {
480        subWindow = subWindow.intersection(complementLowerBoundWindow);
481        return new ComplementRangesByLowerBound<>(positiveRangesByLowerBound, subWindow);
482      }
483    }
484
485    @Override
486    public NavigableMap<Cut<C>, Range<C>> subMap(
487        Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
488      return subMap(
489          Range.range(
490              fromKey, BoundType.forBoolean(fromInclusive),
491              toKey, BoundType.forBoolean(toInclusive)));
492    }
493
494    @Override
495    public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
496      return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
497    }
498
499    @Override
500    public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
501      return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
502    }
503
504    @Override
505    public Comparator<? super Cut<C>> comparator() {
506      return Ordering.<Cut<C>>natural();
507    }
508
509    @Override
510    Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
511      /*
512       * firstComplementRangeLowerBound is the first complement range lower bound inside
513       * complementLowerBoundWindow. Complement range lower bounds are either positive range upper
514       * bounds, or Cut.belowAll().
515       *
516       * positiveItr starts at the first positive range with lower bound greater than
517       * firstComplementRangeLowerBound. (Positive range lower bounds correspond to complement range
518       * upper bounds.)
519       */
520      Collection<Range<C>> positiveRanges;
521      if (complementLowerBoundWindow.hasLowerBound()) {
522        positiveRanges =
523            positiveRangesByUpperBound
524                .tailMap(
525                    complementLowerBoundWindow.lowerEndpoint(),
526                    complementLowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
527                .values();
528      } else {
529        positiveRanges = positiveRangesByUpperBound.values();
530      }
531      PeekingIterator<Range<C>> positiveItr = Iterators.peekingIterator(positiveRanges.iterator());
532      Cut<C> firstComplementRangeLowerBound;
533      if (complementLowerBoundWindow.contains(Cut.<C>belowAll())
534          && (!positiveItr.hasNext() || positiveItr.peek().lowerBound != Cut.<C>belowAll())) {
535        firstComplementRangeLowerBound = Cut.belowAll();
536      } else if (positiveItr.hasNext()) {
537        firstComplementRangeLowerBound = positiveItr.next().upperBound;
538      } else {
539        return Iterators.emptyIterator();
540      }
541      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
542        Cut<C> nextComplementRangeLowerBound = firstComplementRangeLowerBound;
543
544        @Override
545        @CheckForNull
546        protected Entry<Cut<C>, Range<C>> computeNext() {
547          if (complementLowerBoundWindow.upperBound.isLessThan(nextComplementRangeLowerBound)
548              || nextComplementRangeLowerBound == Cut.<C>aboveAll()) {
549            return endOfData();
550          }
551          Range<C> negativeRange;
552          if (positiveItr.hasNext()) {
553            Range<C> positiveRange = positiveItr.next();
554            negativeRange = Range.create(nextComplementRangeLowerBound, positiveRange.lowerBound);
555            nextComplementRangeLowerBound = positiveRange.upperBound;
556          } else {
557            negativeRange = Range.create(nextComplementRangeLowerBound, Cut.<C>aboveAll());
558            nextComplementRangeLowerBound = Cut.aboveAll();
559          }
560          return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
561        }
562      };
563    }
564
565    @Override
566    Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
567      /*
568       * firstComplementRangeUpperBound is the upper bound of the last complement range with lower
569       * bound inside complementLowerBoundWindow.
570       *
571       * positiveItr starts at the first positive range with upper bound less than
572       * firstComplementRangeUpperBound. (Positive range upper bounds correspond to complement range
573       * lower bounds.)
574       */
575      Cut<C> startingPoint =
576          complementLowerBoundWindow.hasUpperBound()
577              ? complementLowerBoundWindow.upperEndpoint()
578              : Cut.<C>aboveAll();
579      boolean inclusive =
580          complementLowerBoundWindow.hasUpperBound()
581              && complementLowerBoundWindow.upperBoundType() == BoundType.CLOSED;
582      PeekingIterator<Range<C>> positiveItr =
583          Iterators.peekingIterator(
584              positiveRangesByUpperBound
585                  .headMap(startingPoint, inclusive)
586                  .descendingMap()
587                  .values()
588                  .iterator());
589      Cut<C> cut;
590      if (positiveItr.hasNext()) {
591        cut =
592            (positiveItr.peek().upperBound == Cut.<C>aboveAll())
593                ? positiveItr.next().lowerBound
594                : positiveRangesByLowerBound.higherKey(positiveItr.peek().upperBound);
595      } else if (!complementLowerBoundWindow.contains(Cut.<C>belowAll())
596          || positiveRangesByLowerBound.containsKey(Cut.belowAll())) {
597        return Iterators.emptyIterator();
598      } else {
599        cut = positiveRangesByLowerBound.higherKey(Cut.<C>belowAll());
600      }
601      Cut<C> firstComplementRangeUpperBound = MoreObjects.firstNonNull(cut, Cut.<C>aboveAll());
602      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
603        Cut<C> nextComplementRangeUpperBound = firstComplementRangeUpperBound;
604
605        @Override
606        @CheckForNull
607        protected Entry<Cut<C>, Range<C>> computeNext() {
608          if (nextComplementRangeUpperBound == Cut.<C>belowAll()) {
609            return endOfData();
610          } else if (positiveItr.hasNext()) {
611            Range<C> positiveRange = positiveItr.next();
612            Range<C> negativeRange =
613                Range.create(positiveRange.upperBound, nextComplementRangeUpperBound);
614            nextComplementRangeUpperBound = positiveRange.lowerBound;
615            if (complementLowerBoundWindow.lowerBound.isLessThan(negativeRange.lowerBound)) {
616              return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
617            }
618          } else if (complementLowerBoundWindow.lowerBound.isLessThan(Cut.<C>belowAll())) {
619            Range<C> negativeRange = Range.create(Cut.<C>belowAll(), nextComplementRangeUpperBound);
620            nextComplementRangeUpperBound = Cut.belowAll();
621            return Maps.immutableEntry(Cut.<C>belowAll(), negativeRange);
622          }
623          return endOfData();
624        }
625      };
626    }
627
628    @Override
629    public int size() {
630      return Iterators.size(entryIterator());
631    }
632
633    @Override
634    @CheckForNull
635    public Range<C> get(@CheckForNull Object key) {
636      if (key instanceof Cut) {
637        try {
638          @SuppressWarnings("unchecked")
639          Cut<C> cut = (Cut<C>) key;
640          // tailMap respects the current window
641          Entry<Cut<C>, Range<C>> firstEntry = tailMap(cut, true).firstEntry();
642          if (firstEntry != null && firstEntry.getKey().equals(cut)) {
643            return firstEntry.getValue();
644          }
645        } catch (ClassCastException e) {
646          return null;
647        }
648      }
649      return null;
650    }
651
652    @Override
653    public boolean containsKey(@CheckForNull Object key) {
654      return get(key) != null;
655    }
656  }
657
658  private final class Complement extends TreeRangeSet<C> {
659    Complement() {
660      super(new ComplementRangesByLowerBound<C>(TreeRangeSet.this.rangesByLowerBound));
661    }
662
663    @Override
664    public void add(Range<C> rangeToAdd) {
665      TreeRangeSet.this.remove(rangeToAdd);
666    }
667
668    @Override
669    public void remove(Range<C> rangeToRemove) {
670      TreeRangeSet.this.add(rangeToRemove);
671    }
672
673    @Override
674    public boolean contains(C value) {
675      return !TreeRangeSet.this.contains(value);
676    }
677
678    @Override
679    public RangeSet<C> complement() {
680      return TreeRangeSet.this;
681    }
682  }
683
684  private static final class SubRangeSetRangesByLowerBound<C extends Comparable<?>>
685      extends AbstractNavigableMap<Cut<C>, Range<C>> {
686    /**
687     * lowerBoundWindow is the headMap/subMap/tailMap view; it only restricts the keys, and does not
688     * affect the values.
689     */
690    private final Range<Cut<C>> lowerBoundWindow;
691
692    /**
693     * restriction is the subRangeSet view; ranges are truncated to their intersection with
694     * restriction.
695     */
696    private final Range<C> restriction;
697
698    private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
699    private final NavigableMap<Cut<C>, Range<C>> rangesByUpperBound;
700
701    private SubRangeSetRangesByLowerBound(
702        Range<Cut<C>> lowerBoundWindow,
703        Range<C> restriction,
704        NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) {
705      this.lowerBoundWindow = checkNotNull(lowerBoundWindow);
706      this.restriction = checkNotNull(restriction);
707      this.rangesByLowerBound = checkNotNull(rangesByLowerBound);
708      this.rangesByUpperBound = new RangesByUpperBound<>(rangesByLowerBound);
709    }
710
711    private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) {
712      if (!window.isConnected(lowerBoundWindow)) {
713        return ImmutableSortedMap.of();
714      } else {
715        return new SubRangeSetRangesByLowerBound<>(
716            lowerBoundWindow.intersection(window), restriction, rangesByLowerBound);
717      }
718    }
719
720    @Override
721    public NavigableMap<Cut<C>, Range<C>> subMap(
722        Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
723      return subMap(
724          Range.range(
725              fromKey,
726              BoundType.forBoolean(fromInclusive),
727              toKey,
728              BoundType.forBoolean(toInclusive)));
729    }
730
731    @Override
732    public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
733      return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
734    }
735
736    @Override
737    public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
738      return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
739    }
740
741    @Override
742    public Comparator<? super Cut<C>> comparator() {
743      return Ordering.<Cut<C>>natural();
744    }
745
746    @Override
747    public boolean containsKey(@CheckForNull Object key) {
748      return get(key) != null;
749    }
750
751    @Override
752    @CheckForNull
753    public Range<C> get(@CheckForNull Object key) {
754      if (key instanceof Cut) {
755        try {
756          @SuppressWarnings("unchecked") // we catch CCE's
757          Cut<C> cut = (Cut<C>) key;
758          if (!lowerBoundWindow.contains(cut)
759              || cut.compareTo(restriction.lowerBound) < 0
760              || cut.compareTo(restriction.upperBound) >= 0) {
761            return null;
762          } else if (cut.equals(restriction.lowerBound)) {
763            // it might be present, truncated on the left
764            Range<C> candidate = Maps.valueOrNull(rangesByLowerBound.floorEntry(cut));
765            if (candidate != null && candidate.upperBound.compareTo(restriction.lowerBound) > 0) {
766              return candidate.intersection(restriction);
767            }
768          } else {
769            Range<C> result = rangesByLowerBound.get(cut);
770            if (result != null) {
771              return result.intersection(restriction);
772            }
773          }
774        } catch (ClassCastException e) {
775          return null;
776        }
777      }
778      return null;
779    }
780
781    @Override
782    Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
783      if (restriction.isEmpty()) {
784        return Iterators.emptyIterator();
785      }
786      Iterator<Range<C>> completeRangeItr;
787      if (lowerBoundWindow.upperBound.isLessThan(restriction.lowerBound)) {
788        return Iterators.emptyIterator();
789      } else if (lowerBoundWindow.lowerBound.isLessThan(restriction.lowerBound)) {
790        // starts at the first range with upper bound strictly greater than restriction.lowerBound
791        completeRangeItr =
792            rangesByUpperBound.tailMap(restriction.lowerBound, false).values().iterator();
793      } else {
794        // starts at the first range with lower bound above lowerBoundWindow.lowerBound
795        completeRangeItr =
796            rangesByLowerBound
797                .tailMap(
798                    lowerBoundWindow.lowerBound.endpoint(),
799                    lowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
800                .values()
801                .iterator();
802      }
803      Cut<Cut<C>> upperBoundOnLowerBounds =
804          Ordering.<Cut<Cut<C>>>natural()
805              .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
806      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
807        @Override
808        @CheckForNull
809        protected Entry<Cut<C>, Range<C>> computeNext() {
810          if (!completeRangeItr.hasNext()) {
811            return endOfData();
812          }
813          Range<C> nextRange = completeRangeItr.next();
814          if (upperBoundOnLowerBounds.isLessThan(nextRange.lowerBound)) {
815            return endOfData();
816          } else {
817            nextRange = nextRange.intersection(restriction);
818            return Maps.immutableEntry(nextRange.lowerBound, nextRange);
819          }
820        }
821      };
822    }
823
824    @Override
825    Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
826      if (restriction.isEmpty()) {
827        return Iterators.emptyIterator();
828      }
829      Cut<Cut<C>> upperBoundOnLowerBounds =
830          Ordering.<Cut<Cut<C>>>natural()
831              .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
832      Iterator<Range<C>> completeRangeItr =
833          rangesByLowerBound
834              .headMap(
835                  upperBoundOnLowerBounds.endpoint(),
836                  upperBoundOnLowerBounds.typeAsUpperBound() == BoundType.CLOSED)
837              .descendingMap()
838              .values()
839              .iterator();
840      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
841        @Override
842        @CheckForNull
843        protected Entry<Cut<C>, Range<C>> computeNext() {
844          if (!completeRangeItr.hasNext()) {
845            return endOfData();
846          }
847          Range<C> nextRange = completeRangeItr.next();
848          if (restriction.lowerBound.compareTo(nextRange.upperBound) >= 0) {
849            return endOfData();
850          }
851          nextRange = nextRange.intersection(restriction);
852          if (lowerBoundWindow.contains(nextRange.lowerBound)) {
853            return Maps.immutableEntry(nextRange.lowerBound, nextRange);
854          } else {
855            return endOfData();
856          }
857        }
858      };
859    }
860
861    @Override
862    public int size() {
863      return Iterators.size(entryIterator());
864    }
865  }
866
867  @Override
868  public RangeSet<C> subRangeSet(Range<C> view) {
869    return view.equals(Range.<C>all()) ? this : new SubRangeSet(view);
870  }
871
872  private final class SubRangeSet extends TreeRangeSet<C> {
873    private final Range<C> restriction;
874
875    SubRangeSet(Range<C> restriction) {
876      super(
877          new SubRangeSetRangesByLowerBound<C>(
878              Range.<Cut<C>>all(), restriction, TreeRangeSet.this.rangesByLowerBound));
879      this.restriction = restriction;
880    }
881
882    @Override
883    public boolean encloses(Range<C> range) {
884      if (!restriction.isEmpty() && restriction.encloses(range)) {
885        Range<C> enclosing = TreeRangeSet.this.rangeEnclosing(range);
886        return enclosing != null && !enclosing.intersection(restriction).isEmpty();
887      }
888      return false;
889    }
890
891    @Override
892    @CheckForNull
893    public Range<C> rangeContaining(C value) {
894      if (!restriction.contains(value)) {
895        return null;
896      }
897      Range<C> result = TreeRangeSet.this.rangeContaining(value);
898      return (result == null) ? null : result.intersection(restriction);
899    }
900
901    @Override
902    public void add(Range<C> rangeToAdd) {
903      checkArgument(
904          restriction.encloses(rangeToAdd),
905          "Cannot add range %s to subRangeSet(%s)",
906          rangeToAdd,
907          restriction);
908      TreeRangeSet.this.add(rangeToAdd);
909    }
910
911    @Override
912    public void remove(Range<C> rangeToRemove) {
913      if (rangeToRemove.isConnected(restriction)) {
914        TreeRangeSet.this.remove(rangeToRemove.intersection(restriction));
915      }
916    }
917
918    @Override
919    public boolean contains(C value) {
920      return restriction.contains(value) && TreeRangeSet.this.contains(value);
921    }
922
923    @Override
924    public void clear() {
925      TreeRangeSet.this.remove(restriction);
926    }
927
928    @Override
929    public RangeSet<C> subRangeSet(Range<C> view) {
930      if (view.encloses(restriction)) {
931        return this;
932      } else if (view.isConnected(restriction)) {
933        return new SubRangeSet(restriction.intersection(view));
934      } else {
935        return ImmutableRangeSet.of();
936      }
937    }
938  }
939}