1 /*
2 * Copyright (C) 2012 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.base.Predicates.compose;
22 import static com.google.common.base.Predicates.in;
23 import static com.google.common.base.Predicates.not;
24
25 import com.google.common.annotations.Beta;
26 import com.google.common.annotations.GwtIncompatible;
27 import com.google.common.base.MoreObjects;
28 import com.google.common.base.Predicate;
29 import com.google.common.collect.Maps.IteratorBasedAbstractMap;
30 import java.util.AbstractMap;
31 import java.util.Collection;
32 import java.util.Collections;
33 import java.util.Iterator;
34 import java.util.List;
35 import java.util.Map;
36 import java.util.Map.Entry;
37 import java.util.NavigableMap;
38 import java.util.NoSuchElementException;
39 import java.util.Set;
40 import java.util.function.BiFunction;
41 import org.checkerframework.checker.nullness.qual.Nullable;
42
43 /**
44 * An implementation of {@code RangeMap} based on a {@code TreeMap}, supporting all optional
45 * operations.
46 *
47 * <p>Like all {@code RangeMap} implementations, this supports neither null keys nor null values.
48 *
49 * @author Louis Wasserman
50 * @since 14.0
51 */
52 @Beta
53 @GwtIncompatible // NavigableMap
54 public final class TreeRangeMap<K extends Comparable, V> implements RangeMap<K, V> {
55
56 private final NavigableMap<Cut<K>, RangeMapEntry<K, V>> entriesByLowerBound;
57
58 public static <K extends Comparable, V> TreeRangeMap<K, V> create() {
59 return new TreeRangeMap<>();
60 }
61
62 private TreeRangeMap() {
63 this.entriesByLowerBound = Maps.newTreeMap();
64 }
65
66 private static final class RangeMapEntry<K extends Comparable, V>
67 extends AbstractMapEntry<Range<K>, V> {
68 private final Range<K> range;
69 private final V value;
70
71 RangeMapEntry(Cut<K> lowerBound, Cut<K> upperBound, V value) {
72 this(Range.create(lowerBound, upperBound), value);
73 }
74
75 RangeMapEntry(Range<K> range, V value) {
76 this.range = range;
77 this.value = value;
78 }
79
80 @Override
81 public Range<K> getKey() {
82 return range;
83 }
84
85 @Override
86 public V getValue() {
87 return value;
88 }
89
90 public boolean contains(K value) {
91 return range.contains(value);
92 }
93
94 Cut<K> getLowerBound() {
95 return range.lowerBound;
96 }
97
98 Cut<K> getUpperBound() {
99 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 }