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