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