Source code

001/*
002 * Copyright (C) 2012 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021import static com.google.common.base.Predicates.compose;
022import static com.google.common.base.Predicates.in;
023import static com.google.common.base.Predicates.not;
024import static com.google.common.collect.Iterators.emptyIterator;
025import static com.google.common.collect.Maps.immutableEntry;
026import static java.util.Collections.emptyMap;
027import static java.util.Objects.requireNonNull;
028
029import com.google.common.annotations.GwtIncompatible;
030import com.google.common.base.MoreObjects;
031import com.google.common.base.Predicate;
032import com.google.common.collect.Maps.IteratorBasedAbstractMap;
033import java.util.AbstractMap;
034import java.util.Collection;
035import java.util.Iterator;
036import java.util.List;
037import java.util.Map;
038import java.util.Map.Entry;
039import java.util.NavigableMap;
040import java.util.NoSuchElementException;
041import java.util.Set;
042import java.util.function.BiFunction;
043import javax.annotation.CheckForNull;
044import org.checkerframework.checker.nullness.qual.Nullable;
045
046/**
047 * An implementation of {@code RangeMap} based on a {@code TreeMap}, supporting all optional
048 * operations.
049 *
050 * <p>Like all {@code RangeMap} implementations, this supports neither null keys nor null values.
051 *
052 * @author Louis Wasserman
053 * @since 14.0
054 */
055@SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989
056@GwtIncompatible // NavigableMap
057@ElementTypesAreNonnullByDefault
058public final class TreeRangeMap<K extends Comparable, V> implements RangeMap<K, V> {
059
060  private final NavigableMap<Cut<K>, RangeMapEntry<K, V>> entriesByLowerBound;
061
062  /** Returns a new, empty {@link TreeRangeMap}. */
063  public static <K extends Comparable, V> TreeRangeMap<K, V> create() {
064    return new TreeRangeMap<>();
065  }
066
067  /**
068   * Returns a new {@link TreeRangeMap} containing the same ranges as the given {@code RangeMap}.
069   *
070   * @since NEXT
071   */
072  @SuppressWarnings("unchecked")
073  public static <K extends Comparable<?>, V> TreeRangeMap<K, V> copyOf(
074      RangeMap<K, ? extends V> rangeMap) {
075    if (rangeMap instanceof TreeRangeMap) {
076      NavigableMap<Cut<K>, RangeMapEntry<K, V>> entriesByLowerBound = Maps.newTreeMap();
077      entriesByLowerBound.putAll(((TreeRangeMap<K, V>) rangeMap).entriesByLowerBound);
078      return new TreeRangeMap<>(entriesByLowerBound);
079    } else {
080      NavigableMap<Cut<K>, RangeMapEntry<K, V>> entriesByLowerBound = Maps.newTreeMap();
081      for (Entry<Range<K>, ? extends V> entry : rangeMap.asMapOfRanges().entrySet()) {
082        entriesByLowerBound.put(
083            entry.getKey().lowerBound(), new RangeMapEntry<K, V>(entry.getKey(), entry.getValue()));
084      }
085      return new TreeRangeMap<>(entriesByLowerBound);
086    }
087  }
088
089  private TreeRangeMap() {
090    this.entriesByLowerBound = Maps.newTreeMap();
091  }
092
093  private TreeRangeMap(NavigableMap<Cut<K>, RangeMapEntry<K, V>> entriesByLowerBound) {
094    this.entriesByLowerBound = entriesByLowerBound;
095  }
096
097  private static final class RangeMapEntry<K extends Comparable, V>
098      extends AbstractMapEntry<Range<K>, V> {
099    private final Range<K> range;
100    private final V value;
101
102    RangeMapEntry(Cut<K> lowerBound, Cut<K> upperBound, V value) {
103      this(Range.create(lowerBound, upperBound), value);
104    }
105
106    RangeMapEntry(Range<K> range, V value) {
107      this.range = range;
108      this.value = value;
109    }
110
111    @Override
112    public Range<K> getKey() {
113      return range;
114    }
115
116    @Override
117    public V getValue() {
118      return value;
119    }
120
121    public boolean contains(K value) {
122      return range.contains(value);
123    }
124
125    Cut<K> getLowerBound() {
126      return range.lowerBound;
127    }
128
129    Cut<K> getUpperBound() {
130      return range.upperBound;
131    }
132  }
133
134  @Override
135  @CheckForNull
136  public V get(K key) {
137    Entry<Range<K>, V> entry = getEntry(key);
138    return (entry == null) ? null : entry.getValue();
139  }
140
141  @Override
142  @CheckForNull
143  public Entry<Range<K>, V> getEntry(K key) {
144    Entry<Cut<K>, RangeMapEntry<K, V>> mapEntry =
145        entriesByLowerBound.floorEntry(Cut.belowValue(key));
146    if (mapEntry != null && mapEntry.getValue().contains(key)) {
147      return mapEntry.getValue();
148    } else {
149      return null;
150    }
151  }
152
153  @Override
154  public void put(Range<K> range, V value) {
155    if (!range.isEmpty()) {
156      checkNotNull(value);
157      remove(range);
158      entriesByLowerBound.put(range.lowerBound, new RangeMapEntry<K, V>(range, value));
159    }
160  }
161
162  @Override
163  public void putCoalescing(Range<K> range, V value) {
164    // don't short-circuit if the range is empty - it may be between two ranges we can coalesce.
165    if (entriesByLowerBound.isEmpty()) {
166      put(range, value);
167      return;
168    }
169
170    Range<K> coalescedRange = coalescedRange(range, checkNotNull(value));
171    put(coalescedRange, value);
172  }
173
174  /** Computes the coalesced range for the given range+value - does not mutate the map. */
175  private Range<K> coalescedRange(Range<K> range, V value) {
176    Range<K> coalescedRange = range;
177    Entry<Cut<K>, RangeMapEntry<K, V>> lowerEntry =
178        entriesByLowerBound.lowerEntry(range.lowerBound);
179    coalescedRange = coalesce(coalescedRange, value, lowerEntry);
180
181    Entry<Cut<K>, RangeMapEntry<K, V>> higherEntry =
182        entriesByLowerBound.floorEntry(range.upperBound);
183    coalescedRange = coalesce(coalescedRange, value, higherEntry);
184
185    return coalescedRange;
186  }
187
188  /** Returns the range that spans the given range and entry, if the entry can be coalesced. */
189  private static <K extends Comparable, V> Range<K> coalesce(
190      Range<K> range, V value, @CheckForNull Entry<Cut<K>, RangeMapEntry<K, V>> entry) {
191    if (entry != null
192        && entry.getValue().getKey().isConnected(range)
193        && entry.getValue().getValue().equals(value)) {
194      return range.span(entry.getValue().getKey());
195    }
196    return range;
197  }
198
199  @Override
200  public void putAll(RangeMap<K, ? extends V> rangeMap) {
201    for (Entry<Range<K>, ? extends V> entry : rangeMap.asMapOfRanges().entrySet()) {
202      put(entry.getKey(), entry.getValue());
203    }
204  }
205
206  @Override
207  public void clear() {
208    entriesByLowerBound.clear();
209  }
210
211  @Override
212  public Range<K> span() {
213    Entry<Cut<K>, RangeMapEntry<K, V>> firstEntry = entriesByLowerBound.firstEntry();
214    Entry<Cut<K>, RangeMapEntry<K, V>> lastEntry = entriesByLowerBound.lastEntry();
215    // Either both are null or neither is, but we check both to satisfy the nullness checker.
216    if (firstEntry == null || lastEntry == null) {
217      throw new NoSuchElementException();
218    }
219    return Range.create(
220        firstEntry.getValue().getKey().lowerBound, lastEntry.getValue().getKey().upperBound);
221  }
222
223  private void putRangeMapEntry(Cut<K> lowerBound, Cut<K> upperBound, V value) {
224    entriesByLowerBound.put(lowerBound, new RangeMapEntry<K, V>(lowerBound, upperBound, value));
225  }
226
227  @Override
228  public void remove(Range<K> rangeToRemove) {
229    if (rangeToRemove.isEmpty()) {
230      return;
231    }
232
233    /*
234     * The comments for this method will use [ ] to indicate the bounds of rangeToRemove and ( ) to
235     * indicate the bounds of ranges in the range map.
236     */
237    Entry<Cut<K>, RangeMapEntry<K, V>> mapEntryBelowToTruncate =
238        entriesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
239    if (mapEntryBelowToTruncate != null) {
240      // we know ( [
241      RangeMapEntry<K, V> rangeMapEntry = mapEntryBelowToTruncate.getValue();
242      if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.lowerBound) > 0) {
243        // we know ( [ )
244        if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.upperBound) > 0) {
245          // we know ( [ ] ), so insert the range ] ) back into the map --
246          // it's being split apart
247          putRangeMapEntry(
248              rangeToRemove.upperBound,
249              rangeMapEntry.getUpperBound(),
250              mapEntryBelowToTruncate.getValue().getValue());
251        }
252        // overwrite mapEntryToTruncateBelow with a truncated range
253        putRangeMapEntry(
254            rangeMapEntry.getLowerBound(),
255            rangeToRemove.lowerBound,
256            mapEntryBelowToTruncate.getValue().getValue());
257      }
258    }
259
260    Entry<Cut<K>, RangeMapEntry<K, V>> mapEntryAboveToTruncate =
261        entriesByLowerBound.lowerEntry(rangeToRemove.upperBound);
262    if (mapEntryAboveToTruncate != null) {
263      // we know ( ]
264      RangeMapEntry<K, V> rangeMapEntry = mapEntryAboveToTruncate.getValue();
265      if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.upperBound) > 0) {
266        // we know ( ] ), and since we dealt with truncating below already,
267        // we know [ ( ] )
268        putRangeMapEntry(
269            rangeToRemove.upperBound,
270            rangeMapEntry.getUpperBound(),
271            mapEntryAboveToTruncate.getValue().getValue());
272      }
273    }
274    entriesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
275  }
276
277  private void split(Cut<K> cut) {
278    /*
279     * The comments for this method will use | to indicate the cut point and ( ) to indicate the
280     * bounds of ranges in the range map.
281     */
282    Entry<Cut<K>, RangeMapEntry<K, V>> mapEntryToSplit = entriesByLowerBound.lowerEntry(cut);
283    if (mapEntryToSplit == null) {
284      return;
285    }
286    // we know ( |
287    RangeMapEntry<K, V> rangeMapEntry = mapEntryToSplit.getValue();
288    if (rangeMapEntry.getUpperBound().compareTo(cut) <= 0) {
289      return;
290    }
291    // we know ( | )
292    putRangeMapEntry(rangeMapEntry.getLowerBound(), cut, rangeMapEntry.getValue());
293    putRangeMapEntry(cut, rangeMapEntry.getUpperBound(), rangeMapEntry.getValue());
294  }
295
296  /**
297   * @since 28.1
298   */
299  @Override
300  public void merge(
301      Range<K> range,
302      @CheckForNull V value,
303      BiFunction<? super V, ? super @Nullable V, ? extends @Nullable V> remappingFunction) {
304    checkNotNull(range);
305    checkNotNull(remappingFunction);
306
307    if (range.isEmpty()) {
308      return;
309    }
310    split(range.lowerBound);
311    split(range.upperBound);
312
313    // Due to the splitting of any entries spanning the range bounds, we know that any entry with a
314    // lower bound in the merge range is entirely contained by the merge range.
315    Set<Entry<Cut<K>, RangeMapEntry<K, V>>> entriesInMergeRange =
316        entriesByLowerBound.subMap(range.lowerBound, range.upperBound).entrySet();
317
318    // Create entries mapping any unmapped ranges in the merge range to the specified value.
319    ImmutableMap.Builder<Cut<K>, RangeMapEntry<K, V>> gaps = ImmutableMap.builder();
320    if (value != null) {
321      final Iterator<Entry<Cut<K>, RangeMapEntry<K, V>>> backingItr =
322          entriesInMergeRange.iterator();
323      Cut<K> lowerBound = range.lowerBound;
324      while (backingItr.hasNext()) {
325        RangeMapEntry<K, V> entry = backingItr.next().getValue();
326        Cut<K> upperBound = entry.getLowerBound();
327        if (!lowerBound.equals(upperBound)) {
328          gaps.put(lowerBound, new RangeMapEntry<K, V>(lowerBound, upperBound, value));
329        }
330        lowerBound = entry.getUpperBound();
331      }
332      if (!lowerBound.equals(range.upperBound)) {
333        gaps.put(lowerBound, new RangeMapEntry<K, V>(lowerBound, range.upperBound, value));
334      }
335    }
336
337    // Remap all existing entries in the merge range.
338    final Iterator<Entry<Cut<K>, RangeMapEntry<K, V>>> backingItr = entriesInMergeRange.iterator();
339    while (backingItr.hasNext()) {
340      Entry<Cut<K>, RangeMapEntry<K, V>> entry = backingItr.next();
341      V newValue = remappingFunction.apply(entry.getValue().getValue(), value);
342      if (newValue == null) {
343        backingItr.remove();
344      } else {
345        entry.setValue(
346            new RangeMapEntry<K, V>(
347                entry.getValue().getLowerBound(), entry.getValue().getUpperBound(), newValue));
348      }
349    }
350
351    entriesByLowerBound.putAll(gaps.build());
352  }
353
354  @Override
355  public Map<Range<K>, V> asMapOfRanges() {
356    return new AsMapOfRanges(entriesByLowerBound.values());
357  }
358
359  @Override
360  public Map<Range<K>, V> asDescendingMapOfRanges() {
361    return new AsMapOfRanges(entriesByLowerBound.descendingMap().values());
362  }
363
364  private final class AsMapOfRanges extends IteratorBasedAbstractMap<Range<K>, V> {
365
366    final Iterable<Entry<Range<K>, V>> entryIterable;
367
368    @SuppressWarnings("unchecked") // it's safe to upcast iterables
369    AsMapOfRanges(Iterable<RangeMapEntry<K, V>> entryIterable) {
370      this.entryIterable = (Iterable) entryIterable;
371    }
372
373    @Override
374    public boolean containsKey(@CheckForNull Object key) {
375      return get(key) != null;
376    }
377
378    @Override
379    @CheckForNull
380    public V get(@CheckForNull Object key) {
381      if (key instanceof Range) {
382        Range<?> range = (Range<?>) key;
383        RangeMapEntry<K, V> rangeMapEntry = entriesByLowerBound.get(range.lowerBound);
384        if (rangeMapEntry != null && rangeMapEntry.getKey().equals(range)) {
385          return rangeMapEntry.getValue();
386        }
387      }
388      return null;
389    }
390
391    @Override
392    public int size() {
393      return entriesByLowerBound.size();
394    }
395
396    @Override
397    Iterator<Entry<Range<K>, V>> entryIterator() {
398      return entryIterable.iterator();
399    }
400  }
401
402  @Override
403  public RangeMap<K, V> subRangeMap(Range<K> subRange) {
404    if (subRange.equals(Range.all())) {
405      return this;
406    } else {
407      return new SubRangeMap(subRange);
408    }
409  }
410
411  @SuppressWarnings("unchecked")
412  private RangeMap<K, V> emptySubRangeMap() {
413    return (RangeMap<K, V>) (RangeMap<?, ?>) EMPTY_SUB_RANGE_MAP;
414  }
415
416  @SuppressWarnings("ConstantCaseForConstants") // This RangeMap is immutable.
417  private static final RangeMap<Comparable<?>, Object> EMPTY_SUB_RANGE_MAP =
418      new RangeMap<Comparable<?>, Object>() {
419        @Override
420        @CheckForNull
421        public Object get(Comparable<?> key) {
422          return null;
423        }
424
425        @Override
426        @CheckForNull
427        public Entry<Range<Comparable<?>>, Object> getEntry(Comparable<?> key) {
428          return null;
429        }
430
431        @Override
432        public Range<Comparable<?>> span() {
433          throw new NoSuchElementException();
434        }
435
436        @Override
437        public void put(Range<Comparable<?>> range, Object value) {
438          checkNotNull(range);
439          throw new IllegalArgumentException(
440              "Cannot insert range " + range + " into an empty subRangeMap");
441        }
442
443        @Override
444        public void putCoalescing(Range<Comparable<?>> range, Object value) {
445          checkNotNull(range);
446          throw new IllegalArgumentException(
447              "Cannot insert range " + range + " into an empty subRangeMap");
448        }
449
450        @Override
451        public void putAll(RangeMap<Comparable<?>, ? extends Object> rangeMap) {
452          if (!rangeMap.asMapOfRanges().isEmpty()) {
453            throw new IllegalArgumentException(
454                "Cannot putAll(nonEmptyRangeMap) into an empty subRangeMap");
455          }
456        }
457
458        @Override
459        public void clear() {}
460
461        @Override
462        public void remove(Range<Comparable<?>> range) {
463          checkNotNull(range);
464        }
465
466        @Override
467        // https://github.com/jspecify/jspecify-reference-checker/issues/162
468        @SuppressWarnings("nullness")
469        public void merge(
470            Range<Comparable<?>> range,
471            @CheckForNull Object value,
472            BiFunction<? super Object, ? super @Nullable Object, ? extends @Nullable Object>
473                remappingFunction) {
474          checkNotNull(range);
475          throw new IllegalArgumentException(
476              "Cannot merge range " + range + " into an empty subRangeMap");
477        }
478
479        @Override
480        public Map<Range<Comparable<?>>, Object> asMapOfRanges() {
481          return emptyMap();
482        }
483
484        @Override
485        public Map<Range<Comparable<?>>, Object> asDescendingMapOfRanges() {
486          return emptyMap();
487        }
488
489        @Override
490        public RangeMap<Comparable<?>, Object> subRangeMap(Range<Comparable<?>> range) {
491          checkNotNull(range);
492          return this;
493        }
494      };
495
496  private class SubRangeMap implements RangeMap<K, V> {
497
498    private final Range<K> subRange;
499
500    SubRangeMap(Range<K> subRange) {
501      this.subRange = subRange;
502    }
503
504    @Override
505    @CheckForNull
506    public V get(K key) {
507      return subRange.contains(key) ? TreeRangeMap.this.get(key) : null;
508    }
509
510    @Override
511    @CheckForNull
512    public Entry<Range<K>, V> getEntry(K key) {
513      if (subRange.contains(key)) {
514        Entry<Range<K>, V> entry = TreeRangeMap.this.getEntry(key);
515        if (entry != null) {
516          return immutableEntry(entry.getKey().intersection(subRange), entry.getValue());
517        }
518      }
519      return null;
520    }
521
522    @Override
523    public Range<K> span() {
524      Cut<K> lowerBound;
525      Entry<Cut<K>, RangeMapEntry<K, V>> lowerEntry =
526          entriesByLowerBound.floorEntry(subRange.lowerBound);
527      if (lowerEntry != null
528          && lowerEntry.getValue().getUpperBound().compareTo(subRange.lowerBound) > 0) {
529        lowerBound = subRange.lowerBound;
530      } else {
531        lowerBound = entriesByLowerBound.ceilingKey(subRange.lowerBound);
532        if (lowerBound == null || lowerBound.compareTo(subRange.upperBound) >= 0) {
533          throw new NoSuchElementException();
534        }
535      }
536
537      Cut<K> upperBound;
538      Entry<Cut<K>, RangeMapEntry<K, V>> upperEntry =
539          entriesByLowerBound.lowerEntry(subRange.upperBound);
540      if (upperEntry == null) {
541        throw new NoSuchElementException();
542      } else if (upperEntry.getValue().getUpperBound().compareTo(subRange.upperBound) >= 0) {
543        upperBound = subRange.upperBound;
544      } else {
545        upperBound = upperEntry.getValue().getUpperBound();
546      }
547      return Range.create(lowerBound, upperBound);
548    }
549
550    @Override
551    public void put(Range<K> range, V value) {
552      checkArgument(
553          subRange.encloses(range), "Cannot put range %s into a subRangeMap(%s)", range, subRange);
554      TreeRangeMap.this.put(range, value);
555    }
556
557    @Override
558    public void putCoalescing(Range<K> range, V value) {
559      if (entriesByLowerBound.isEmpty() || !subRange.encloses(range)) {
560        put(range, value);
561        return;
562      }
563
564      Range<K> coalescedRange = coalescedRange(range, checkNotNull(value));
565      // only coalesce ranges within the subRange
566      put(coalescedRange.intersection(subRange), value);
567    }
568
569    @Override
570    public void putAll(RangeMap<K, ? extends V> rangeMap) {
571      if (rangeMap.asMapOfRanges().isEmpty()) {
572        return;
573      }
574      Range<K> span = rangeMap.span();
575      checkArgument(
576          subRange.encloses(span),
577          "Cannot putAll rangeMap with span %s into a subRangeMap(%s)",
578          span,
579          subRange);
580      TreeRangeMap.this.putAll(rangeMap);
581    }
582
583    @Override
584    public void clear() {
585      TreeRangeMap.this.remove(subRange);
586    }
587
588    @Override
589    public void remove(Range<K> range) {
590      if (range.isConnected(subRange)) {
591        TreeRangeMap.this.remove(range.intersection(subRange));
592      }
593    }
594
595    @Override
596    public void merge(
597        Range<K> range,
598        @CheckForNull V value,
599        BiFunction<? super V, ? super @Nullable V, ? extends @Nullable V> remappingFunction) {
600      checkArgument(
601          subRange.encloses(range),
602          "Cannot merge range %s into a subRangeMap(%s)",
603          range,
604          subRange);
605      TreeRangeMap.this.merge(range, value, remappingFunction);
606    }
607
608    @Override
609    public RangeMap<K, V> subRangeMap(Range<K> range) {
610      if (!range.isConnected(subRange)) {
611        return emptySubRangeMap();
612      } else {
613        return TreeRangeMap.this.subRangeMap(range.intersection(subRange));
614      }
615    }
616
617    @Override
618    public Map<Range<K>, V> asMapOfRanges() {
619      return new SubRangeMapAsMap();
620    }
621
622    @Override
623    public Map<Range<K>, V> asDescendingMapOfRanges() {
624      return new SubRangeMapAsMap() {
625
626        @Override
627        Iterator<Entry<Range<K>, V>> entryIterator() {
628          if (subRange.isEmpty()) {
629            return emptyIterator();
630          }
631          final Iterator<RangeMapEntry<K, V>> backingItr =
632              entriesByLowerBound
633                  .headMap(subRange.upperBound, false)
634                  .descendingMap()
635                  .values()
636                  .iterator();
637          return new AbstractIterator<Entry<Range<K>, V>>() {
638
639            @Override
640            @CheckForNull
641            protected Entry<Range<K>, V> computeNext() {
642              if (backingItr.hasNext()) {
643                RangeMapEntry<K, V> entry = backingItr.next();
644                if (entry.getUpperBound().compareTo(subRange.lowerBound) <= 0) {
645                  return endOfData();
646                }
647                return immutableEntry(entry.getKey().intersection(subRange), entry.getValue());
648              }
649              return endOfData();
650            }
651          };
652        }
653      };
654    }
655
656    @Override
657    public boolean equals(@CheckForNull Object o) {
658      if (o instanceof RangeMap) {
659        RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
660        return asMapOfRanges().equals(rangeMap.asMapOfRanges());
661      }
662      return false;
663    }
664
665    @Override
666    public int hashCode() {
667      return asMapOfRanges().hashCode();
668    }
669
670    @Override
671    public String toString() {
672      return asMapOfRanges().toString();
673    }
674
675    class SubRangeMapAsMap extends AbstractMap<Range<K>, V> {
676
677      @Override
678      public boolean containsKey(@CheckForNull Object key) {
679        return get(key) != null;
680      }
681
682      @Override
683      @CheckForNull
684      public V get(@CheckForNull Object key) {
685        try {
686          if (key instanceof Range) {
687            @SuppressWarnings("unchecked") // we catch ClassCastExceptions
688            Range<K> r = (Range<K>) key;
689            if (!subRange.encloses(r) || r.isEmpty()) {
690              return null;
691            }
692            RangeMapEntry<K, V> candidate = null;
693            if (r.lowerBound.compareTo(subRange.lowerBound) == 0) {
694              // r could be truncated on the left
695              Entry<Cut<K>, RangeMapEntry<K, V>> entry =
696                  entriesByLowerBound.floorEntry(r.lowerBound);
697              if (entry != null) {
698                candidate = entry.getValue();
699              }
700            } else {
701              candidate = entriesByLowerBound.get(r.lowerBound);
702            }
703
704            if (candidate != null
705                && candidate.getKey().isConnected(subRange)
706                && candidate.getKey().intersection(subRange).equals(r)) {
707              return candidate.getValue();
708            }
709          }
710        } catch (ClassCastException e) {
711          return null;
712        }
713        return null;
714      }
715
716      @Override
717      @CheckForNull
718      public V remove(@CheckForNull Object key) {
719        V value = get(key);
720        if (value != null) {
721          // it's definitely in the map, so the cast and requireNonNull are safe
722          @SuppressWarnings("unchecked")
723          Range<K> range = (Range<K>) requireNonNull(key);
724          TreeRangeMap.this.remove(range);
725          return value;
726        }
727        return null;
728      }
729
730      @Override
731      public void clear() {
732        SubRangeMap.this.clear();
733      }
734
735      private boolean removeEntryIf(Predicate<? super Entry<Range<K>, V>> predicate) {
736        List<Range<K>> toRemove = Lists.newArrayList();
737        for (Entry<Range<K>, V> entry : entrySet()) {
738          if (predicate.apply(entry)) {
739            toRemove.add(entry.getKey());
740          }
741        }
742        for (Range<K> range : toRemove) {
743          TreeRangeMap.this.remove(range);
744        }
745        return !toRemove.isEmpty();
746      }
747
748      @Override
749      public Set<Range<K>> keySet() {
750        return new Maps.KeySet<Range<K>, V>(SubRangeMapAsMap.this) {
751          @Override
752          public boolean remove(@CheckForNull Object o) {
753            return SubRangeMapAsMap.this.remove(o) != null;
754          }
755
756          @Override
757          public boolean retainAll(Collection<?> c) {
758            return removeEntryIf(compose(not(in(c)), Maps.<Range<K>>keyFunction()));
759          }
760        };
761      }
762
763      @Override
764      public Set<Entry<Range<K>, V>> entrySet() {
765        return new Maps.EntrySet<Range<K>, V>() {
766          @Override
767          Map<Range<K>, V> map() {
768            return SubRangeMapAsMap.this;
769          }
770
771          @Override
772          public Iterator<Entry<Range<K>, V>> iterator() {
773            return entryIterator();
774          }
775
776          @Override
777          public boolean retainAll(Collection<?> c) {
778            return removeEntryIf(not(in(c)));
779          }
780
781          @Override
782          public int size() {
783            return Iterators.size(iterator());
784          }
785
786          @Override
787          public boolean isEmpty() {
788            return !iterator().hasNext();
789          }
790        };
791      }
792
793      Iterator<Entry<Range<K>, V>> entryIterator() {
794        if (subRange.isEmpty()) {
795          return emptyIterator();
796        }
797        Cut<K> cutToStart =
798            MoreObjects.firstNonNull(
799                entriesByLowerBound.floorKey(subRange.lowerBound), subRange.lowerBound);
800        final Iterator<RangeMapEntry<K, V>> backingItr =
801            entriesByLowerBound.tailMap(cutToStart, true).values().iterator();
802        return new AbstractIterator<Entry<Range<K>, V>>() {
803
804          @Override
805          @CheckForNull
806          protected Entry<Range<K>, V> computeNext() {
807            while (backingItr.hasNext()) {
808              RangeMapEntry<K, V> entry = backingItr.next();
809              if (entry.getLowerBound().compareTo(subRange.upperBound) >= 0) {
810                return endOfData();
811              } else if (entry.getUpperBound().compareTo(subRange.lowerBound) > 0) {
812                // this might not be true e.g. at the start of the iteration
813                return immutableEntry(entry.getKey().intersection(subRange), entry.getValue());
814              }
815            }
816            return endOfData();
817          }
818        };
819      }
820
821      @Override
822      public Collection<V> values() {
823        return new Maps.Values<Range<K>, V>(this) {
824          @Override
825          public boolean removeAll(Collection<?> c) {
826            return removeEntryIf(compose(in(c), Maps.<V>valueFunction()));
827          }
828
829          @Override
830          public boolean retainAll(Collection<?> c) {
831            return removeEntryIf(compose(not(in(c)), Maps.<V>valueFunction()));
832          }
833        };
834      }
835    }
836  }
837
838  @Override
839  public boolean equals(@CheckForNull Object o) {
840    if (o instanceof RangeMap) {
841      RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
842      return asMapOfRanges().equals(rangeMap.asMapOfRanges());
843    }
844    return false;
845  }
846
847  @Override
848  public int hashCode() {
849    return asMapOfRanges().hashCode();
850  }
851
852  @Override
853  public String toString() {
854    return entriesByLowerBound.values().toString();
855  }
856}