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