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