001/* 002 * Copyright (C) 2011 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.collect; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkNotNull; 019 020import com.google.common.annotations.Beta; 021import com.google.common.annotations.GwtIncompatible; 022import com.google.common.annotations.VisibleForTesting; 023import com.google.common.base.MoreObjects; 024import java.io.Serializable; 025import java.util.Collection; 026import java.util.Comparator; 027import java.util.Iterator; 028import java.util.Map.Entry; 029import java.util.NavigableMap; 030import java.util.NoSuchElementException; 031import java.util.Set; 032import java.util.TreeMap; 033import org.checkerframework.checker.nullness.qual.MonotonicNonNull; 034import org.checkerframework.checker.nullness.qual.Nullable; 035 036/** 037 * An implementation of {@link RangeSet} backed by a {@link TreeMap}. 038 * 039 * @author Louis Wasserman 040 * @since 14.0 041 */ 042@Beta 043@GwtIncompatible // uses NavigableMap 044public class TreeRangeSet<C extends Comparable<?>> extends AbstractRangeSet<C> 045 implements Serializable { 046 047 @VisibleForTesting final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound; 048 049 /** Creates an empty {@code TreeRangeSet} instance. */ 050 public static <C extends Comparable<?>> TreeRangeSet<C> create() { 051 return new TreeRangeSet<C>(new TreeMap<Cut<C>, Range<C>>()); 052 } 053 054 /** Returns a {@code TreeRangeSet} initialized with the ranges in the specified range set. */ 055 public static <C extends Comparable<?>> TreeRangeSet<C> create(RangeSet<C> rangeSet) { 056 TreeRangeSet<C> result = create(); 057 result.addAll(rangeSet); 058 return result; 059 } 060 061 /** 062 * Returns a {@code TreeRangeSet} representing the union of the specified ranges. 063 * 064 * <p>This is the smallest {@code RangeSet} which encloses each of the specified ranges. An 065 * element will be contained in this {@code RangeSet} if and only if it is contained in at least 066 * one {@code Range} in {@code ranges}. 067 * 068 * @since 21.0 069 */ 070 public static <C extends Comparable<?>> TreeRangeSet<C> create(Iterable<Range<C>> ranges) { 071 TreeRangeSet<C> result = create(); 072 result.addAll(ranges); 073 return result; 074 } 075 076 private TreeRangeSet(NavigableMap<Cut<C>, Range<C>> rangesByLowerCut) { 077 this.rangesByLowerBound = rangesByLowerCut; 078 } 079 080 private transient @MonotonicNonNull Set<Range<C>> asRanges; 081 private transient @MonotonicNonNull Set<Range<C>> asDescendingSetOfRanges; 082 083 @Override 084 public Set<Range<C>> asRanges() { 085 Set<Range<C>> result = asRanges; 086 return (result == null) ? asRanges = new AsRanges(rangesByLowerBound.values()) : result; 087 } 088 089 @Override 090 public Set<Range<C>> asDescendingSetOfRanges() { 091 Set<Range<C>> result = asDescendingSetOfRanges; 092 return (result == null) 093 ? asDescendingSetOfRanges = new AsRanges(rangesByLowerBound.descendingMap().values()) 094 : result; 095 } 096 097 final class AsRanges extends ForwardingCollection<Range<C>> implements Set<Range<C>> { 098 099 final Collection<Range<C>> delegate; 100 101 AsRanges(Collection<Range<C>> delegate) { 102 this.delegate = delegate; 103 } 104 105 @Override 106 protected Collection<Range<C>> delegate() { 107 return delegate; 108 } 109 110 @Override 111 public int hashCode() { 112 return Sets.hashCodeImpl(this); 113 } 114 115 @Override 116 public boolean equals(@Nullable Object o) { 117 return Sets.equalsImpl(this, o); 118 } 119 } 120 121 @Override 122 public @Nullable Range<C> rangeContaining(C value) { 123 checkNotNull(value); 124 Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(Cut.belowValue(value)); 125 if (floorEntry != null && floorEntry.getValue().contains(value)) { 126 return floorEntry.getValue(); 127 } else { 128 // TODO(kevinb): revisit this design choice 129 return null; 130 } 131 } 132 133 @Override 134 public boolean intersects(Range<C> range) { 135 checkNotNull(range); 136 Entry<Cut<C>, Range<C>> ceilingEntry = rangesByLowerBound.ceilingEntry(range.lowerBound); 137 if (ceilingEntry != null 138 && ceilingEntry.getValue().isConnected(range) 139 && !ceilingEntry.getValue().intersection(range).isEmpty()) { 140 return true; 141 } 142 Entry<Cut<C>, Range<C>> priorEntry = rangesByLowerBound.lowerEntry(range.lowerBound); 143 return priorEntry != null 144 && priorEntry.getValue().isConnected(range) 145 && !priorEntry.getValue().intersection(range).isEmpty(); 146 } 147 148 @Override 149 public boolean encloses(Range<C> range) { 150 checkNotNull(range); 151 Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound); 152 return floorEntry != null && floorEntry.getValue().encloses(range); 153 } 154 155 private @Nullable Range<C> rangeEnclosing(Range<C> range) { 156 checkNotNull(range); 157 Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound); 158 return (floorEntry != null && floorEntry.getValue().encloses(range)) 159 ? floorEntry.getValue() 160 : null; 161 } 162 163 @Override 164 public Range<C> span() { 165 Entry<Cut<C>, Range<C>> firstEntry = rangesByLowerBound.firstEntry(); 166 Entry<Cut<C>, Range<C>> lastEntry = rangesByLowerBound.lastEntry(); 167 if (firstEntry == null) { 168 throw new NoSuchElementException(); 169 } 170 return Range.create(firstEntry.getValue().lowerBound, lastEntry.getValue().upperBound); 171 } 172 173 @Override 174 public void add(Range<C> rangeToAdd) { 175 checkNotNull(rangeToAdd); 176 177 if (rangeToAdd.isEmpty()) { 178 return; 179 } 180 181 // We will use { } to illustrate ranges currently in the range set, and < > 182 // to illustrate rangeToAdd. 183 Cut<C> lbToAdd = rangeToAdd.lowerBound; 184 Cut<C> ubToAdd = rangeToAdd.upperBound; 185 186 Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(lbToAdd); 187 if (entryBelowLB != null) { 188 // { < 189 Range<C> rangeBelowLB = entryBelowLB.getValue(); 190 if (rangeBelowLB.upperBound.compareTo(lbToAdd) >= 0) { 191 // { < }, and we will need to coalesce 192 if (rangeBelowLB.upperBound.compareTo(ubToAdd) >= 0) { 193 // { < > } 194 ubToAdd = rangeBelowLB.upperBound; 195 /* 196 * TODO(cpovirk): can we just "return;" here? Or, can we remove this if() entirely? If 197 * not, add tests to demonstrate the problem with each approach 198 */ 199 } 200 lbToAdd = rangeBelowLB.lowerBound; 201 } 202 } 203 204 Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(ubToAdd); 205 if (entryBelowUB != null) { 206 // { > 207 Range<C> rangeBelowUB = entryBelowUB.getValue(); 208 if (rangeBelowUB.upperBound.compareTo(ubToAdd) >= 0) { 209 // { > }, and we need to coalesce 210 ubToAdd = rangeBelowUB.upperBound; 211 } 212 } 213 214 // Remove ranges which are strictly enclosed. 215 rangesByLowerBound.subMap(lbToAdd, ubToAdd).clear(); 216 217 replaceRangeWithSameLowerBound(Range.create(lbToAdd, ubToAdd)); 218 } 219 220 @Override 221 public void remove(Range<C> rangeToRemove) { 222 checkNotNull(rangeToRemove); 223 224 if (rangeToRemove.isEmpty()) { 225 return; 226 } 227 228 // We will use { } to illustrate ranges currently in the range set, and < > 229 // to illustrate rangeToRemove. 230 231 Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(rangeToRemove.lowerBound); 232 if (entryBelowLB != null) { 233 // { < 234 Range<C> rangeBelowLB = entryBelowLB.getValue(); 235 if (rangeBelowLB.upperBound.compareTo(rangeToRemove.lowerBound) >= 0) { 236 // { < }, and we will need to subdivide 237 if (rangeToRemove.hasUpperBound() 238 && rangeBelowLB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) { 239 // { < > } 240 replaceRangeWithSameLowerBound( 241 Range.create(rangeToRemove.upperBound, rangeBelowLB.upperBound)); 242 } 243 replaceRangeWithSameLowerBound( 244 Range.create(rangeBelowLB.lowerBound, rangeToRemove.lowerBound)); 245 } 246 } 247 248 Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(rangeToRemove.upperBound); 249 if (entryBelowUB != null) { 250 // { > 251 Range<C> rangeBelowUB = entryBelowUB.getValue(); 252 if (rangeToRemove.hasUpperBound() 253 && rangeBelowUB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) { 254 // { > } 255 replaceRangeWithSameLowerBound( 256 Range.create(rangeToRemove.upperBound, rangeBelowUB.upperBound)); 257 } 258 } 259 260 rangesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear(); 261 } 262 263 private void replaceRangeWithSameLowerBound(Range<C> range) { 264 if (range.isEmpty()) { 265 rangesByLowerBound.remove(range.lowerBound); 266 } else { 267 rangesByLowerBound.put(range.lowerBound, range); 268 } 269 } 270 271 private transient @MonotonicNonNull RangeSet<C> complement; 272 273 @Override 274 public RangeSet<C> complement() { 275 RangeSet<C> result = complement; 276 return (result == null) ? complement = new Complement() : result; 277 } 278 279 @VisibleForTesting 280 static final class RangesByUpperBound<C extends Comparable<?>> 281 extends AbstractNavigableMap<Cut<C>, Range<C>> { 282 private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound; 283 284 /** 285 * upperBoundWindow represents the headMap/subMap/tailMap view of the entire "ranges by upper 286 * bound" map; it's a constraint on the *keys*, and does not affect the values. 287 */ 288 private final Range<Cut<C>> upperBoundWindow; 289 290 RangesByUpperBound(NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) { 291 this.rangesByLowerBound = rangesByLowerBound; 292 this.upperBoundWindow = Range.all(); 293 } 294 295 private RangesByUpperBound( 296 NavigableMap<Cut<C>, Range<C>> rangesByLowerBound, Range<Cut<C>> upperBoundWindow) { 297 this.rangesByLowerBound = rangesByLowerBound; 298 this.upperBoundWindow = upperBoundWindow; 299 } 300 301 private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) { 302 if (window.isConnected(upperBoundWindow)) { 303 return new RangesByUpperBound<C>(rangesByLowerBound, window.intersection(upperBoundWindow)); 304 } else { 305 return ImmutableSortedMap.of(); 306 } 307 } 308 309 @Override 310 public NavigableMap<Cut<C>, Range<C>> subMap( 311 Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) { 312 return subMap( 313 Range.range( 314 fromKey, BoundType.forBoolean(fromInclusive), 315 toKey, BoundType.forBoolean(toInclusive))); 316 } 317 318 @Override 319 public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) { 320 return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive))); 321 } 322 323 @Override 324 public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) { 325 return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive))); 326 } 327 328 @Override 329 public Comparator<? super Cut<C>> comparator() { 330 return Ordering.<Cut<C>>natural(); 331 } 332 333 @Override 334 public boolean containsKey(@Nullable Object key) { 335 return get(key) != null; 336 } 337 338 @Override 339 public Range<C> get(@Nullable Object key) { 340 if (key instanceof Cut) { 341 try { 342 @SuppressWarnings("unchecked") // we catch CCEs 343 Cut<C> cut = (Cut<C>) key; 344 if (!upperBoundWindow.contains(cut)) { 345 return null; 346 } 347 Entry<Cut<C>, Range<C>> candidate = rangesByLowerBound.lowerEntry(cut); 348 if (candidate != null && candidate.getValue().upperBound.equals(cut)) { 349 return candidate.getValue(); 350 } 351 } catch (ClassCastException e) { 352 return null; 353 } 354 } 355 return null; 356 } 357 358 @Override 359 Iterator<Entry<Cut<C>, Range<C>>> entryIterator() { 360 /* 361 * We want to start the iteration at the first range where the upper bound is in 362 * upperBoundWindow. 363 */ 364 final Iterator<Range<C>> backingItr; 365 if (!upperBoundWindow.hasLowerBound()) { 366 backingItr = rangesByLowerBound.values().iterator(); 367 } else { 368 Entry<Cut<C>, Range<C>> lowerEntry = 369 rangesByLowerBound.lowerEntry(upperBoundWindow.lowerEndpoint()); 370 if (lowerEntry == null) { 371 backingItr = rangesByLowerBound.values().iterator(); 372 } else if (upperBoundWindow.lowerBound.isLessThan(lowerEntry.getValue().upperBound)) { 373 backingItr = rangesByLowerBound.tailMap(lowerEntry.getKey(), true).values().iterator(); 374 } else { 375 backingItr = 376 rangesByLowerBound 377 .tailMap(upperBoundWindow.lowerEndpoint(), true) 378 .values() 379 .iterator(); 380 } 381 } 382 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() { 383 @Override 384 protected Entry<Cut<C>, Range<C>> computeNext() { 385 if (!backingItr.hasNext()) { 386 return endOfData(); 387 } 388 Range<C> range = backingItr.next(); 389 if (upperBoundWindow.upperBound.isLessThan(range.upperBound)) { 390 return endOfData(); 391 } else { 392 return Maps.immutableEntry(range.upperBound, range); 393 } 394 } 395 }; 396 } 397 398 @Override 399 Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() { 400 Collection<Range<C>> candidates; 401 if (upperBoundWindow.hasUpperBound()) { 402 candidates = 403 rangesByLowerBound 404 .headMap(upperBoundWindow.upperEndpoint(), false) 405 .descendingMap() 406 .values(); 407 } else { 408 candidates = rangesByLowerBound.descendingMap().values(); 409 } 410 final PeekingIterator<Range<C>> backingItr = Iterators.peekingIterator(candidates.iterator()); 411 if (backingItr.hasNext() 412 && upperBoundWindow.upperBound.isLessThan(backingItr.peek().upperBound)) { 413 backingItr.next(); 414 } 415 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() { 416 @Override 417 protected Entry<Cut<C>, Range<C>> computeNext() { 418 if (!backingItr.hasNext()) { 419 return endOfData(); 420 } 421 Range<C> range = backingItr.next(); 422 return upperBoundWindow.lowerBound.isLessThan(range.upperBound) 423 ? Maps.immutableEntry(range.upperBound, range) 424 : endOfData(); 425 } 426 }; 427 } 428 429 @Override 430 public int size() { 431 if (upperBoundWindow.equals(Range.all())) { 432 return rangesByLowerBound.size(); 433 } 434 return Iterators.size(entryIterator()); 435 } 436 437 @Override 438 public boolean isEmpty() { 439 return upperBoundWindow.equals(Range.all()) 440 ? rangesByLowerBound.isEmpty() 441 : !entryIterator().hasNext(); 442 } 443 } 444 445 private static final class ComplementRangesByLowerBound<C extends Comparable<?>> 446 extends AbstractNavigableMap<Cut<C>, Range<C>> { 447 private final NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound; 448 private final NavigableMap<Cut<C>, Range<C>> positiveRangesByUpperBound; 449 450 /** 451 * complementLowerBoundWindow represents the headMap/subMap/tailMap view of the entire 452 * "complement ranges by lower bound" map; it's a constraint on the *keys*, and does not affect 453 * the values. 454 */ 455 private final Range<Cut<C>> complementLowerBoundWindow; 456 457 ComplementRangesByLowerBound(NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound) { 458 this(positiveRangesByLowerBound, Range.<Cut<C>>all()); 459 } 460 461 private ComplementRangesByLowerBound( 462 NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound, Range<Cut<C>> window) { 463 this.positiveRangesByLowerBound = positiveRangesByLowerBound; 464 this.positiveRangesByUpperBound = new RangesByUpperBound<C>(positiveRangesByLowerBound); 465 this.complementLowerBoundWindow = window; 466 } 467 468 private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> subWindow) { 469 if (!complementLowerBoundWindow.isConnected(subWindow)) { 470 return ImmutableSortedMap.of(); 471 } else { 472 subWindow = subWindow.intersection(complementLowerBoundWindow); 473 return new ComplementRangesByLowerBound<C>(positiveRangesByLowerBound, subWindow); 474 } 475 } 476 477 @Override 478 public NavigableMap<Cut<C>, Range<C>> subMap( 479 Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) { 480 return subMap( 481 Range.range( 482 fromKey, BoundType.forBoolean(fromInclusive), 483 toKey, BoundType.forBoolean(toInclusive))); 484 } 485 486 @Override 487 public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) { 488 return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive))); 489 } 490 491 @Override 492 public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) { 493 return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive))); 494 } 495 496 @Override 497 public Comparator<? super Cut<C>> comparator() { 498 return Ordering.<Cut<C>>natural(); 499 } 500 501 @Override 502 Iterator<Entry<Cut<C>, Range<C>>> entryIterator() { 503 /* 504 * firstComplementRangeLowerBound is the first complement range lower bound inside 505 * complementLowerBoundWindow. Complement range lower bounds are either positive range upper 506 * bounds, or Cut.belowAll(). 507 * 508 * positiveItr starts at the first positive range with lower bound greater than 509 * firstComplementRangeLowerBound. (Positive range lower bounds correspond to complement range 510 * upper bounds.) 511 */ 512 Collection<Range<C>> positiveRanges; 513 if (complementLowerBoundWindow.hasLowerBound()) { 514 positiveRanges = 515 positiveRangesByUpperBound 516 .tailMap( 517 complementLowerBoundWindow.lowerEndpoint(), 518 complementLowerBoundWindow.lowerBoundType() == BoundType.CLOSED) 519 .values(); 520 } else { 521 positiveRanges = positiveRangesByUpperBound.values(); 522 } 523 final PeekingIterator<Range<C>> positiveItr = 524 Iterators.peekingIterator(positiveRanges.iterator()); 525 final Cut<C> firstComplementRangeLowerBound; 526 if (complementLowerBoundWindow.contains(Cut.<C>belowAll()) 527 && (!positiveItr.hasNext() || positiveItr.peek().lowerBound != Cut.<C>belowAll())) { 528 firstComplementRangeLowerBound = Cut.belowAll(); 529 } else if (positiveItr.hasNext()) { 530 firstComplementRangeLowerBound = positiveItr.next().upperBound; 531 } else { 532 return Iterators.emptyIterator(); 533 } 534 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() { 535 Cut<C> nextComplementRangeLowerBound = firstComplementRangeLowerBound; 536 537 @Override 538 protected Entry<Cut<C>, Range<C>> computeNext() { 539 if (complementLowerBoundWindow.upperBound.isLessThan(nextComplementRangeLowerBound) 540 || nextComplementRangeLowerBound == Cut.<C>aboveAll()) { 541 return endOfData(); 542 } 543 Range<C> negativeRange; 544 if (positiveItr.hasNext()) { 545 Range<C> positiveRange = positiveItr.next(); 546 negativeRange = Range.create(nextComplementRangeLowerBound, positiveRange.lowerBound); 547 nextComplementRangeLowerBound = positiveRange.upperBound; 548 } else { 549 negativeRange = Range.create(nextComplementRangeLowerBound, Cut.<C>aboveAll()); 550 nextComplementRangeLowerBound = Cut.aboveAll(); 551 } 552 return Maps.immutableEntry(negativeRange.lowerBound, negativeRange); 553 } 554 }; 555 } 556 557 @Override 558 Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() { 559 /* 560 * firstComplementRangeUpperBound is the upper bound of the last complement range with lower 561 * bound inside complementLowerBoundWindow. 562 * 563 * positiveItr starts at the first positive range with upper bound less than 564 * firstComplementRangeUpperBound. (Positive range upper bounds correspond to complement range 565 * lower bounds.) 566 */ 567 Cut<C> startingPoint = 568 complementLowerBoundWindow.hasUpperBound() 569 ? complementLowerBoundWindow.upperEndpoint() 570 : Cut.<C>aboveAll(); 571 boolean inclusive = 572 complementLowerBoundWindow.hasUpperBound() 573 && complementLowerBoundWindow.upperBoundType() == BoundType.CLOSED; 574 final PeekingIterator<Range<C>> positiveItr = 575 Iterators.peekingIterator( 576 positiveRangesByUpperBound 577 .headMap(startingPoint, inclusive) 578 .descendingMap() 579 .values() 580 .iterator()); 581 Cut<C> cut; 582 if (positiveItr.hasNext()) { 583 cut = 584 (positiveItr.peek().upperBound == Cut.<C>aboveAll()) 585 ? positiveItr.next().lowerBound 586 : positiveRangesByLowerBound.higherKey(positiveItr.peek().upperBound); 587 } else if (!complementLowerBoundWindow.contains(Cut.<C>belowAll()) 588 || positiveRangesByLowerBound.containsKey(Cut.belowAll())) { 589 return Iterators.emptyIterator(); 590 } else { 591 cut = positiveRangesByLowerBound.higherKey(Cut.<C>belowAll()); 592 } 593 final Cut<C> firstComplementRangeUpperBound = 594 MoreObjects.firstNonNull(cut, Cut.<C>aboveAll()); 595 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() { 596 Cut<C> nextComplementRangeUpperBound = firstComplementRangeUpperBound; 597 598 @Override 599 protected Entry<Cut<C>, Range<C>> computeNext() { 600 if (nextComplementRangeUpperBound == Cut.<C>belowAll()) { 601 return endOfData(); 602 } else if (positiveItr.hasNext()) { 603 Range<C> positiveRange = positiveItr.next(); 604 Range<C> negativeRange = 605 Range.create(positiveRange.upperBound, nextComplementRangeUpperBound); 606 nextComplementRangeUpperBound = positiveRange.lowerBound; 607 if (complementLowerBoundWindow.lowerBound.isLessThan(negativeRange.lowerBound)) { 608 return Maps.immutableEntry(negativeRange.lowerBound, negativeRange); 609 } 610 } else if (complementLowerBoundWindow.lowerBound.isLessThan(Cut.<C>belowAll())) { 611 Range<C> negativeRange = Range.create(Cut.<C>belowAll(), nextComplementRangeUpperBound); 612 nextComplementRangeUpperBound = Cut.belowAll(); 613 return Maps.immutableEntry(Cut.<C>belowAll(), negativeRange); 614 } 615 return endOfData(); 616 } 617 }; 618 } 619 620 @Override 621 public int size() { 622 return Iterators.size(entryIterator()); 623 } 624 625 @Override 626 public @Nullable Range<C> get(Object key) { 627 if (key instanceof Cut) { 628 try { 629 @SuppressWarnings("unchecked") 630 Cut<C> cut = (Cut<C>) key; 631 // tailMap respects the current window 632 Entry<Cut<C>, Range<C>> firstEntry = tailMap(cut, true).firstEntry(); 633 if (firstEntry != null && firstEntry.getKey().equals(cut)) { 634 return firstEntry.getValue(); 635 } 636 } catch (ClassCastException e) { 637 return null; 638 } 639 } 640 return null; 641 } 642 643 @Override 644 public boolean containsKey(Object key) { 645 return get(key) != null; 646 } 647 } 648 649 private final class Complement extends TreeRangeSet<C> { 650 Complement() { 651 super(new ComplementRangesByLowerBound<C>(TreeRangeSet.this.rangesByLowerBound)); 652 } 653 654 @Override 655 public void add(Range<C> rangeToAdd) { 656 TreeRangeSet.this.remove(rangeToAdd); 657 } 658 659 @Override 660 public void remove(Range<C> rangeToRemove) { 661 TreeRangeSet.this.add(rangeToRemove); 662 } 663 664 @Override 665 public boolean contains(C value) { 666 return !TreeRangeSet.this.contains(value); 667 } 668 669 @Override 670 public RangeSet<C> complement() { 671 return TreeRangeSet.this; 672 } 673 } 674 675 private static final class SubRangeSetRangesByLowerBound<C extends Comparable<?>> 676 extends AbstractNavigableMap<Cut<C>, Range<C>> { 677 /** 678 * lowerBoundWindow is the headMap/subMap/tailMap view; it only restricts the keys, and does not 679 * affect the values. 680 */ 681 private final Range<Cut<C>> lowerBoundWindow; 682 683 /** 684 * restriction is the subRangeSet view; ranges are truncated to their intersection with 685 * restriction. 686 */ 687 private final Range<C> restriction; 688 689 private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound; 690 private final NavigableMap<Cut<C>, Range<C>> rangesByUpperBound; 691 692 private SubRangeSetRangesByLowerBound( 693 Range<Cut<C>> lowerBoundWindow, 694 Range<C> restriction, 695 NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) { 696 this.lowerBoundWindow = checkNotNull(lowerBoundWindow); 697 this.restriction = checkNotNull(restriction); 698 this.rangesByLowerBound = checkNotNull(rangesByLowerBound); 699 this.rangesByUpperBound = new RangesByUpperBound<C>(rangesByLowerBound); 700 } 701 702 private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) { 703 if (!window.isConnected(lowerBoundWindow)) { 704 return ImmutableSortedMap.of(); 705 } else { 706 return new SubRangeSetRangesByLowerBound<C>( 707 lowerBoundWindow.intersection(window), restriction, rangesByLowerBound); 708 } 709 } 710 711 @Override 712 public NavigableMap<Cut<C>, Range<C>> subMap( 713 Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) { 714 return subMap( 715 Range.range( 716 fromKey, 717 BoundType.forBoolean(fromInclusive), 718 toKey, 719 BoundType.forBoolean(toInclusive))); 720 } 721 722 @Override 723 public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) { 724 return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive))); 725 } 726 727 @Override 728 public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) { 729 return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive))); 730 } 731 732 @Override 733 public Comparator<? super Cut<C>> comparator() { 734 return Ordering.<Cut<C>>natural(); 735 } 736 737 @Override 738 public boolean containsKey(@Nullable Object key) { 739 return get(key) != null; 740 } 741 742 @Override 743 public @Nullable Range<C> get(@Nullable Object key) { 744 if (key instanceof Cut) { 745 try { 746 @SuppressWarnings("unchecked") // we catch CCE's 747 Cut<C> cut = (Cut<C>) key; 748 if (!lowerBoundWindow.contains(cut) 749 || cut.compareTo(restriction.lowerBound) < 0 750 || cut.compareTo(restriction.upperBound) >= 0) { 751 return null; 752 } else if (cut.equals(restriction.lowerBound)) { 753 // it might be present, truncated on the left 754 Range<C> candidate = Maps.valueOrNull(rangesByLowerBound.floorEntry(cut)); 755 if (candidate != null && candidate.upperBound.compareTo(restriction.lowerBound) > 0) { 756 return candidate.intersection(restriction); 757 } 758 } else { 759 Range<C> result = rangesByLowerBound.get(cut); 760 if (result != null) { 761 return result.intersection(restriction); 762 } 763 } 764 } catch (ClassCastException e) { 765 return null; 766 } 767 } 768 return null; 769 } 770 771 @Override 772 Iterator<Entry<Cut<C>, Range<C>>> entryIterator() { 773 if (restriction.isEmpty()) { 774 return Iterators.emptyIterator(); 775 } 776 final Iterator<Range<C>> completeRangeItr; 777 if (lowerBoundWindow.upperBound.isLessThan(restriction.lowerBound)) { 778 return Iterators.emptyIterator(); 779 } else if (lowerBoundWindow.lowerBound.isLessThan(restriction.lowerBound)) { 780 // starts at the first range with upper bound strictly greater than restriction.lowerBound 781 completeRangeItr = 782 rangesByUpperBound.tailMap(restriction.lowerBound, false).values().iterator(); 783 } else { 784 // starts at the first range with lower bound above lowerBoundWindow.lowerBound 785 completeRangeItr = 786 rangesByLowerBound 787 .tailMap( 788 lowerBoundWindow.lowerBound.endpoint(), 789 lowerBoundWindow.lowerBoundType() == BoundType.CLOSED) 790 .values() 791 .iterator(); 792 } 793 final Cut<Cut<C>> upperBoundOnLowerBounds = 794 Ordering.natural() 795 .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound)); 796 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() { 797 @Override 798 protected Entry<Cut<C>, Range<C>> computeNext() { 799 if (!completeRangeItr.hasNext()) { 800 return endOfData(); 801 } 802 Range<C> nextRange = completeRangeItr.next(); 803 if (upperBoundOnLowerBounds.isLessThan(nextRange.lowerBound)) { 804 return endOfData(); 805 } else { 806 nextRange = nextRange.intersection(restriction); 807 return Maps.immutableEntry(nextRange.lowerBound, nextRange); 808 } 809 } 810 }; 811 } 812 813 @Override 814 Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() { 815 if (restriction.isEmpty()) { 816 return Iterators.emptyIterator(); 817 } 818 Cut<Cut<C>> upperBoundOnLowerBounds = 819 Ordering.natural() 820 .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound)); 821 final Iterator<Range<C>> completeRangeItr = 822 rangesByLowerBound 823 .headMap( 824 upperBoundOnLowerBounds.endpoint(), 825 upperBoundOnLowerBounds.typeAsUpperBound() == BoundType.CLOSED) 826 .descendingMap() 827 .values() 828 .iterator(); 829 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() { 830 @Override 831 protected Entry<Cut<C>, Range<C>> computeNext() { 832 if (!completeRangeItr.hasNext()) { 833 return endOfData(); 834 } 835 Range<C> nextRange = completeRangeItr.next(); 836 if (restriction.lowerBound.compareTo(nextRange.upperBound) >= 0) { 837 return endOfData(); 838 } 839 nextRange = nextRange.intersection(restriction); 840 if (lowerBoundWindow.contains(nextRange.lowerBound)) { 841 return Maps.immutableEntry(nextRange.lowerBound, nextRange); 842 } else { 843 return endOfData(); 844 } 845 } 846 }; 847 } 848 849 @Override 850 public int size() { 851 return Iterators.size(entryIterator()); 852 } 853 } 854 855 @Override 856 public RangeSet<C> subRangeSet(Range<C> view) { 857 return view.equals(Range.<C>all()) ? this : new SubRangeSet(view); 858 } 859 860 private final class SubRangeSet extends TreeRangeSet<C> { 861 private final Range<C> restriction; 862 863 SubRangeSet(Range<C> restriction) { 864 super( 865 new SubRangeSetRangesByLowerBound<C>( 866 Range.<Cut<C>>all(), restriction, TreeRangeSet.this.rangesByLowerBound)); 867 this.restriction = restriction; 868 } 869 870 @Override 871 public boolean encloses(Range<C> range) { 872 if (!restriction.isEmpty() && restriction.encloses(range)) { 873 Range<C> enclosing = TreeRangeSet.this.rangeEnclosing(range); 874 return enclosing != null && !enclosing.intersection(restriction).isEmpty(); 875 } 876 return false; 877 } 878 879 @Override 880 public @Nullable Range<C> rangeContaining(C value) { 881 if (!restriction.contains(value)) { 882 return null; 883 } 884 Range<C> result = TreeRangeSet.this.rangeContaining(value); 885 return (result == null) ? null : result.intersection(restriction); 886 } 887 888 @Override 889 public void add(Range<C> rangeToAdd) { 890 checkArgument( 891 restriction.encloses(rangeToAdd), 892 "Cannot add range %s to subRangeSet(%s)", 893 rangeToAdd, 894 restriction); 895 super.add(rangeToAdd); 896 } 897 898 @Override 899 public void remove(Range<C> rangeToRemove) { 900 if (rangeToRemove.isConnected(restriction)) { 901 TreeRangeSet.this.remove(rangeToRemove.intersection(restriction)); 902 } 903 } 904 905 @Override 906 public boolean contains(C value) { 907 return restriction.contains(value) && TreeRangeSet.this.contains(value); 908 } 909 910 @Override 911 public void clear() { 912 TreeRangeSet.this.remove(restriction); 913 } 914 915 @Override 916 public RangeSet<C> subRangeSet(Range<C> view) { 917 if (view.encloses(restriction)) { 918 return this; 919 } else if (view.isConnected(restriction)) { 920 return new SubRangeSet(restriction.intersection(view)); 921 } else { 922 return ImmutableRangeSet.of(); 923 } 924 } 925 } 926}