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 // don't short-circuit if the range is empty - it may be between two ranges we can coalesce. 123 if (!range.isEmpty()) { 124 checkNotNull(value); 125 remove(range); 126 entriesByLowerBound.put(range.lowerBound, new RangeMapEntry<K, V>(range, value)); 127 } 128 } 129 130 @Override 131 public void putCoalescing(Range<K> range, V value) { 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() || range.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}