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