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