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