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