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