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