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