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