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