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