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