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