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