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