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