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