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