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}