Source code

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