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