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