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