001/* 002 * Copyright (C) 2012 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.checkElementIndex; 019import static com.google.common.base.Preconditions.checkNotNull; 020import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER; 021import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER; 022import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT; 023import static java.util.Objects.requireNonNull; 024 025import com.google.common.annotations.GwtIncompatible; 026import com.google.common.annotations.J2ktIncompatible; 027import com.google.common.collect.SortedLists.KeyAbsentBehavior; 028import com.google.common.collect.SortedLists.KeyPresentBehavior; 029import com.google.common.primitives.Ints; 030import com.google.errorprone.annotations.CanIgnoreReturnValue; 031import com.google.errorprone.annotations.DoNotCall; 032import com.google.errorprone.annotations.concurrent.LazyInit; 033import java.io.InvalidObjectException; 034import java.io.ObjectInputStream; 035import java.io.Serializable; 036import java.util.Collections; 037import java.util.Iterator; 038import java.util.List; 039import java.util.NoSuchElementException; 040import java.util.Set; 041import java.util.stream.Collector; 042import javax.annotation.CheckForNull; 043 044/** 045 * A {@link RangeSet} whose contents will never change, with many other important properties 046 * detailed at {@link ImmutableCollection}. 047 * 048 * @author Louis Wasserman 049 * @since 14.0 050 */ 051@GwtIncompatible 052@ElementTypesAreNonnullByDefault 053public final class ImmutableRangeSet<C extends Comparable> extends AbstractRangeSet<C> 054 implements Serializable { 055 056 private static final ImmutableRangeSet<Comparable<?>> EMPTY = 057 new ImmutableRangeSet<>(ImmutableList.<Range<Comparable<?>>>of()); 058 059 private static final ImmutableRangeSet<Comparable<?>> ALL = 060 new ImmutableRangeSet<>(ImmutableList.of(Range.<Comparable<?>>all())); 061 062 /** 063 * Returns a {@code Collector} that accumulates the input elements into a new {@code 064 * ImmutableRangeSet}. As in {@link Builder}, overlapping ranges are not permitted and adjacent 065 * ranges will be merged. 066 * 067 * @since 23.1 068 */ 069 public static <E extends Comparable<? super E>> 070 Collector<Range<E>, ?, ImmutableRangeSet<E>> toImmutableRangeSet() { 071 return CollectCollectors.toImmutableRangeSet(); 072 } 073 074 /** 075 * Returns an empty immutable range set. 076 * 077 * <p><b>Performance note:</b> the instance returned is a singleton. 078 */ 079 @SuppressWarnings("unchecked") 080 public static <C extends Comparable> ImmutableRangeSet<C> of() { 081 return (ImmutableRangeSet<C>) EMPTY; 082 } 083 084 /** 085 * Returns an immutable range set containing the specified single range. If {@link Range#isEmpty() 086 * range.isEmpty()}, this is equivalent to {@link ImmutableRangeSet#of()}. 087 */ 088 public static <C extends Comparable> ImmutableRangeSet<C> of(Range<C> range) { 089 checkNotNull(range); 090 if (range.isEmpty()) { 091 return of(); 092 } else if (range.equals(Range.all())) { 093 return all(); 094 } else { 095 return new ImmutableRangeSet<C>(ImmutableList.of(range)); 096 } 097 } 098 099 /** Returns an immutable range set containing the single range {@link Range#all()}. */ 100 @SuppressWarnings("unchecked") 101 static <C extends Comparable> ImmutableRangeSet<C> all() { 102 return (ImmutableRangeSet<C>) ALL; 103 } 104 105 /** Returns an immutable copy of the specified {@code RangeSet}. */ 106 public static <C extends Comparable> ImmutableRangeSet<C> copyOf(RangeSet<C> rangeSet) { 107 checkNotNull(rangeSet); 108 if (rangeSet.isEmpty()) { 109 return of(); 110 } else if (rangeSet.encloses(Range.<C>all())) { 111 return all(); 112 } 113 114 if (rangeSet instanceof ImmutableRangeSet) { 115 ImmutableRangeSet<C> immutableRangeSet = (ImmutableRangeSet<C>) rangeSet; 116 if (!immutableRangeSet.isPartialView()) { 117 return immutableRangeSet; 118 } 119 } 120 return new ImmutableRangeSet<C>(ImmutableList.copyOf(rangeSet.asRanges())); 121 } 122 123 /** 124 * Returns an {@code ImmutableRangeSet} containing each of the specified disjoint ranges. 125 * Overlapping ranges and empty ranges are forbidden, though adjacent ranges are permitted and 126 * will be merged. 127 * 128 * @throws IllegalArgumentException if any ranges overlap or are empty 129 * @since 21.0 130 */ 131 public static <C extends Comparable<?>> ImmutableRangeSet<C> copyOf(Iterable<Range<C>> ranges) { 132 return new ImmutableRangeSet.Builder<C>().addAll(ranges).build(); 133 } 134 135 /** 136 * Returns an {@code ImmutableRangeSet} representing the union of the specified ranges. 137 * 138 * <p>This is the smallest {@code RangeSet} which encloses each of the specified ranges. Duplicate 139 * or connected ranges are permitted, and will be coalesced in the result. 140 * 141 * @since 21.0 142 */ 143 public static <C extends Comparable<?>> ImmutableRangeSet<C> unionOf(Iterable<Range<C>> ranges) { 144 return copyOf(TreeRangeSet.create(ranges)); 145 } 146 147 ImmutableRangeSet(ImmutableList<Range<C>> ranges) { 148 this.ranges = ranges; 149 } 150 151 private ImmutableRangeSet(ImmutableList<Range<C>> ranges, ImmutableRangeSet<C> complement) { 152 this.ranges = ranges; 153 this.complement = complement; 154 } 155 156 private final transient ImmutableList<Range<C>> ranges; 157 158 @Override 159 public boolean intersects(Range<C> otherRange) { 160 int ceilingIndex = 161 SortedLists.binarySearch( 162 ranges, 163 Range.<C>lowerBoundFn(), 164 otherRange.lowerBound, 165 Ordering.natural(), 166 ANY_PRESENT, 167 NEXT_HIGHER); 168 if (ceilingIndex < ranges.size() 169 && ranges.get(ceilingIndex).isConnected(otherRange) 170 && !ranges.get(ceilingIndex).intersection(otherRange).isEmpty()) { 171 return true; 172 } 173 return ceilingIndex > 0 174 && ranges.get(ceilingIndex - 1).isConnected(otherRange) 175 && !ranges.get(ceilingIndex - 1).intersection(otherRange).isEmpty(); 176 } 177 178 @Override 179 public boolean encloses(Range<C> otherRange) { 180 int index = 181 SortedLists.binarySearch( 182 ranges, 183 Range.<C>lowerBoundFn(), 184 otherRange.lowerBound, 185 Ordering.natural(), 186 ANY_PRESENT, 187 NEXT_LOWER); 188 return index != -1 && ranges.get(index).encloses(otherRange); 189 } 190 191 @Override 192 @CheckForNull 193 public Range<C> rangeContaining(C value) { 194 int index = 195 SortedLists.binarySearch( 196 ranges, 197 Range.<C>lowerBoundFn(), 198 Cut.belowValue(value), 199 Ordering.natural(), 200 ANY_PRESENT, 201 NEXT_LOWER); 202 if (index != -1) { 203 Range<C> range = ranges.get(index); 204 return range.contains(value) ? range : null; 205 } 206 return null; 207 } 208 209 @Override 210 public Range<C> span() { 211 if (ranges.isEmpty()) { 212 throw new NoSuchElementException(); 213 } 214 return Range.create(ranges.get(0).lowerBound, ranges.get(ranges.size() - 1).upperBound); 215 } 216 217 @Override 218 public boolean isEmpty() { 219 return ranges.isEmpty(); 220 } 221 222 /** 223 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 224 * 225 * @throws UnsupportedOperationException always 226 * @deprecated Unsupported operation. 227 */ 228 @Deprecated 229 @Override 230 @DoNotCall("Always throws UnsupportedOperationException") 231 public void add(Range<C> range) { 232 throw new UnsupportedOperationException(); 233 } 234 235 /** 236 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 237 * 238 * @throws UnsupportedOperationException always 239 * @deprecated Unsupported operation. 240 */ 241 @Deprecated 242 @Override 243 @DoNotCall("Always throws UnsupportedOperationException") 244 public void addAll(RangeSet<C> other) { 245 throw new UnsupportedOperationException(); 246 } 247 248 /** 249 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 250 * 251 * @throws UnsupportedOperationException always 252 * @deprecated Unsupported operation. 253 */ 254 @Deprecated 255 @Override 256 @DoNotCall("Always throws UnsupportedOperationException") 257 public void addAll(Iterable<Range<C>> other) { 258 throw new UnsupportedOperationException(); 259 } 260 261 /** 262 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 263 * 264 * @throws UnsupportedOperationException always 265 * @deprecated Unsupported operation. 266 */ 267 @Deprecated 268 @Override 269 @DoNotCall("Always throws UnsupportedOperationException") 270 public void remove(Range<C> range) { 271 throw new UnsupportedOperationException(); 272 } 273 274 /** 275 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 276 * 277 * @throws UnsupportedOperationException always 278 * @deprecated Unsupported operation. 279 */ 280 @Deprecated 281 @Override 282 @DoNotCall("Always throws UnsupportedOperationException") 283 public void removeAll(RangeSet<C> other) { 284 throw new UnsupportedOperationException(); 285 } 286 287 /** 288 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 289 * 290 * @throws UnsupportedOperationException always 291 * @deprecated Unsupported operation. 292 */ 293 @Deprecated 294 @Override 295 @DoNotCall("Always throws UnsupportedOperationException") 296 public void removeAll(Iterable<Range<C>> other) { 297 throw new UnsupportedOperationException(); 298 } 299 300 @Override 301 public ImmutableSet<Range<C>> asRanges() { 302 if (ranges.isEmpty()) { 303 return ImmutableSet.of(); 304 } 305 return new RegularImmutableSortedSet<>(ranges, Range.<C>rangeLexOrdering()); 306 } 307 308 @Override 309 public ImmutableSet<Range<C>> asDescendingSetOfRanges() { 310 if (ranges.isEmpty()) { 311 return ImmutableSet.of(); 312 } 313 return new RegularImmutableSortedSet<>(ranges.reverse(), Range.<C>rangeLexOrdering().reverse()); 314 } 315 316 @LazyInit @CheckForNull private transient ImmutableRangeSet<C> complement; 317 318 private final class ComplementRanges extends ImmutableList<Range<C>> { 319 // True if the "positive" range set is empty or bounded below. 320 private final boolean positiveBoundedBelow; 321 322 // True if the "positive" range set is empty or bounded above. 323 private final boolean positiveBoundedAbove; 324 325 private final int size; 326 327 ComplementRanges() { 328 this.positiveBoundedBelow = ranges.get(0).hasLowerBound(); 329 this.positiveBoundedAbove = Iterables.getLast(ranges).hasUpperBound(); 330 331 int size = ranges.size() - 1; 332 if (positiveBoundedBelow) { 333 size++; 334 } 335 if (positiveBoundedAbove) { 336 size++; 337 } 338 this.size = size; 339 } 340 341 @Override 342 public int size() { 343 return size; 344 } 345 346 @Override 347 public Range<C> get(int index) { 348 checkElementIndex(index, size); 349 350 Cut<C> lowerBound; 351 if (positiveBoundedBelow) { 352 lowerBound = (index == 0) ? Cut.<C>belowAll() : ranges.get(index - 1).upperBound; 353 } else { 354 lowerBound = ranges.get(index).upperBound; 355 } 356 357 Cut<C> upperBound; 358 if (positiveBoundedAbove && index == size - 1) { 359 upperBound = Cut.<C>aboveAll(); 360 } else { 361 upperBound = ranges.get(index + (positiveBoundedBelow ? 0 : 1)).lowerBound; 362 } 363 364 return Range.create(lowerBound, upperBound); 365 } 366 367 @Override 368 boolean isPartialView() { 369 return true; 370 } 371 } 372 373 @Override 374 public ImmutableRangeSet<C> complement() { 375 ImmutableRangeSet<C> result = complement; 376 if (result != null) { 377 return result; 378 } else if (ranges.isEmpty()) { 379 return complement = all(); 380 } else if (ranges.size() == 1 && ranges.get(0).equals(Range.all())) { 381 return complement = of(); 382 } else { 383 ImmutableList<Range<C>> complementRanges = new ComplementRanges(); 384 result = complement = new ImmutableRangeSet<C>(complementRanges, this); 385 } 386 return result; 387 } 388 389 /** 390 * Returns a new range set consisting of the union of this range set and {@code other}. 391 * 392 * <p>This is essentially the same as {@code TreeRangeSet.create(this).addAll(other)} except it 393 * returns an {@code ImmutableRangeSet}. 394 * 395 * @since 21.0 396 */ 397 public ImmutableRangeSet<C> union(RangeSet<C> other) { 398 return unionOf(Iterables.concat(asRanges(), other.asRanges())); 399 } 400 401 /** 402 * Returns a new range set consisting of the intersection of this range set and {@code other}. 403 * 404 * <p>This is essentially the same as {@code 405 * TreeRangeSet.create(this).removeAll(other.complement())} except it returns an {@code 406 * ImmutableRangeSet}. 407 * 408 * @since 21.0 409 */ 410 public ImmutableRangeSet<C> intersection(RangeSet<C> other) { 411 RangeSet<C> copy = TreeRangeSet.create(this); 412 copy.removeAll(other.complement()); 413 return copyOf(copy); 414 } 415 416 /** 417 * Returns a new range set consisting of the difference of this range set and {@code other}. 418 * 419 * <p>This is essentially the same as {@code TreeRangeSet.create(this).removeAll(other)} except it 420 * returns an {@code ImmutableRangeSet}. 421 * 422 * @since 21.0 423 */ 424 public ImmutableRangeSet<C> difference(RangeSet<C> other) { 425 RangeSet<C> copy = TreeRangeSet.create(this); 426 copy.removeAll(other); 427 return copyOf(copy); 428 } 429 430 /** 431 * Returns a list containing the nonempty intersections of {@code range} with the ranges in this 432 * range set. 433 */ 434 private ImmutableList<Range<C>> intersectRanges(final Range<C> range) { 435 if (ranges.isEmpty() || range.isEmpty()) { 436 return ImmutableList.of(); 437 } else if (range.encloses(span())) { 438 return ranges; 439 } 440 441 final int fromIndex; 442 if (range.hasLowerBound()) { 443 fromIndex = 444 SortedLists.binarySearch( 445 ranges, 446 Range.<C>upperBoundFn(), 447 range.lowerBound, 448 KeyPresentBehavior.FIRST_AFTER, 449 KeyAbsentBehavior.NEXT_HIGHER); 450 } else { 451 fromIndex = 0; 452 } 453 454 int toIndex; 455 if (range.hasUpperBound()) { 456 toIndex = 457 SortedLists.binarySearch( 458 ranges, 459 Range.<C>lowerBoundFn(), 460 range.upperBound, 461 KeyPresentBehavior.FIRST_PRESENT, 462 KeyAbsentBehavior.NEXT_HIGHER); 463 } else { 464 toIndex = ranges.size(); 465 } 466 final int length = toIndex - fromIndex; 467 if (length == 0) { 468 return ImmutableList.of(); 469 } else { 470 return new ImmutableList<Range<C>>() { 471 @Override 472 public int size() { 473 return length; 474 } 475 476 @Override 477 public Range<C> get(int index) { 478 checkElementIndex(index, length); 479 if (index == 0 || index == length - 1) { 480 return ranges.get(index + fromIndex).intersection(range); 481 } else { 482 return ranges.get(index + fromIndex); 483 } 484 } 485 486 @Override 487 boolean isPartialView() { 488 return true; 489 } 490 }; 491 } 492 } 493 494 /** Returns a view of the intersection of this range set with the given range. */ 495 @Override 496 public ImmutableRangeSet<C> subRangeSet(Range<C> range) { 497 if (!isEmpty()) { 498 Range<C> span = span(); 499 if (range.encloses(span)) { 500 return this; 501 } else if (range.isConnected(span)) { 502 return new ImmutableRangeSet<C>(intersectRanges(range)); 503 } 504 } 505 return of(); 506 } 507 508 /** 509 * Returns an {@link ImmutableSortedSet} containing the same values in the given domain 510 * {@linkplain RangeSet#contains contained} by this range set. 511 * 512 * <p><b>Note:</b> {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For 513 * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty 514 * ranges {@code [3..3)} and {@code [4..4)}. 515 * 516 * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet} view of a large 517 * range set (such as {@code ImmutableRangeSet.of(Range.greaterThan(0))}). Certain operations on 518 * such a set can be performed efficiently, but others (such as {@link Set#hashCode} or {@link 519 * Collections#frequency}) can cause major performance problems. 520 * 521 * <p>The returned set's {@link Object#toString} method returns a shorthand form of the set's 522 * contents, such as {@code "[1..100]}"}. 523 * 524 * @throws IllegalArgumentException if neither this range nor the domain has a lower bound, or if 525 * neither has an upper bound 526 */ 527 public ImmutableSortedSet<C> asSet(DiscreteDomain<C> domain) { 528 checkNotNull(domain); 529 if (isEmpty()) { 530 return ImmutableSortedSet.of(); 531 } 532 Range<C> span = span().canonical(domain); 533 if (!span.hasLowerBound()) { 534 // according to the spec of canonical, neither this ImmutableRangeSet nor 535 // the range have a lower bound 536 throw new IllegalArgumentException( 537 "Neither the DiscreteDomain nor this range set are bounded below"); 538 } else if (!span.hasUpperBound()) { 539 try { 540 domain.maxValue(); 541 } catch (NoSuchElementException e) { 542 throw new IllegalArgumentException( 543 "Neither the DiscreteDomain nor this range set are bounded above"); 544 } 545 } 546 547 return new AsSet(domain); 548 } 549 550 private final class AsSet extends ImmutableSortedSet<C> { 551 private final DiscreteDomain<C> domain; 552 553 AsSet(DiscreteDomain<C> domain) { 554 super(Ordering.natural()); 555 this.domain = domain; 556 } 557 558 @LazyInit @CheckForNull private transient Integer size; 559 560 @Override 561 public int size() { 562 // racy single-check idiom 563 Integer result = size; 564 if (result == null) { 565 long total = 0; 566 for (Range<C> range : ranges) { 567 total += ContiguousSet.create(range, domain).size(); 568 if (total >= Integer.MAX_VALUE) { 569 break; 570 } 571 } 572 result = size = Ints.saturatedCast(total); 573 } 574 return result.intValue(); 575 } 576 577 @Override 578 public UnmodifiableIterator<C> iterator() { 579 return new AbstractIterator<C>() { 580 final Iterator<Range<C>> rangeItr = ranges.iterator(); 581 Iterator<C> elemItr = Iterators.emptyIterator(); 582 583 @Override 584 @CheckForNull 585 protected C computeNext() { 586 while (!elemItr.hasNext()) { 587 if (rangeItr.hasNext()) { 588 elemItr = ContiguousSet.create(rangeItr.next(), domain).iterator(); 589 } else { 590 return endOfData(); 591 } 592 } 593 return elemItr.next(); 594 } 595 }; 596 } 597 598 @Override 599 @GwtIncompatible("NavigableSet") 600 public UnmodifiableIterator<C> descendingIterator() { 601 return new AbstractIterator<C>() { 602 final Iterator<Range<C>> rangeItr = ranges.reverse().iterator(); 603 Iterator<C> elemItr = Iterators.emptyIterator(); 604 605 @Override 606 @CheckForNull 607 protected C computeNext() { 608 while (!elemItr.hasNext()) { 609 if (rangeItr.hasNext()) { 610 elemItr = ContiguousSet.create(rangeItr.next(), domain).descendingIterator(); 611 } else { 612 return endOfData(); 613 } 614 } 615 return elemItr.next(); 616 } 617 }; 618 } 619 620 ImmutableSortedSet<C> subSet(Range<C> range) { 621 return subRangeSet(range).asSet(domain); 622 } 623 624 @Override 625 ImmutableSortedSet<C> headSetImpl(C toElement, boolean inclusive) { 626 return subSet(Range.upTo(toElement, BoundType.forBoolean(inclusive))); 627 } 628 629 @Override 630 ImmutableSortedSet<C> subSetImpl( 631 C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) { 632 if (!fromInclusive && !toInclusive && Range.compareOrThrow(fromElement, toElement) == 0) { 633 return ImmutableSortedSet.of(); 634 } 635 return subSet( 636 Range.range( 637 fromElement, BoundType.forBoolean(fromInclusive), 638 toElement, BoundType.forBoolean(toInclusive))); 639 } 640 641 @Override 642 ImmutableSortedSet<C> tailSetImpl(C fromElement, boolean inclusive) { 643 return subSet(Range.downTo(fromElement, BoundType.forBoolean(inclusive))); 644 } 645 646 @Override 647 public boolean contains(@CheckForNull Object o) { 648 if (o == null) { 649 return false; 650 } 651 try { 652 @SuppressWarnings("unchecked") // we catch CCE's 653 C c = (C) o; 654 return ImmutableRangeSet.this.contains(c); 655 } catch (ClassCastException e) { 656 return false; 657 } 658 } 659 660 @Override 661 int indexOf(@CheckForNull Object target) { 662 if (contains(target)) { 663 @SuppressWarnings("unchecked") // if it's contained, it's definitely a C 664 C c = (C) requireNonNull(target); 665 long total = 0; 666 for (Range<C> range : ranges) { 667 if (range.contains(c)) { 668 return Ints.saturatedCast(total + ContiguousSet.create(range, domain).indexOf(c)); 669 } else { 670 total += ContiguousSet.create(range, domain).size(); 671 } 672 } 673 throw new AssertionError("impossible"); 674 } 675 return -1; 676 } 677 678 @Override 679 ImmutableSortedSet<C> createDescendingSet() { 680 return new DescendingImmutableSortedSet<C>(this); 681 } 682 683 @Override 684 boolean isPartialView() { 685 return ranges.isPartialView(); 686 } 687 688 @Override 689 public String toString() { 690 return ranges.toString(); 691 } 692 693 @Override 694 @J2ktIncompatible // serialization 695 Object writeReplace() { 696 return new AsSetSerializedForm<C>(ranges, domain); 697 } 698 699 @J2ktIncompatible // java.io.ObjectInputStream 700 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 701 throw new InvalidObjectException("Use SerializedForm"); 702 } 703 } 704 705 private static class AsSetSerializedForm<C extends Comparable> implements Serializable { 706 private final ImmutableList<Range<C>> ranges; 707 private final DiscreteDomain<C> domain; 708 709 AsSetSerializedForm(ImmutableList<Range<C>> ranges, DiscreteDomain<C> domain) { 710 this.ranges = ranges; 711 this.domain = domain; 712 } 713 714 Object readResolve() { 715 return new ImmutableRangeSet<C>(ranges).asSet(domain); 716 } 717 } 718 719 /** 720 * Returns {@code true} if this immutable range set's implementation contains references to 721 * user-created objects that aren't accessible via this range set's methods. This is generally 722 * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid 723 * memory leaks. 724 */ 725 boolean isPartialView() { 726 return ranges.isPartialView(); 727 } 728 729 /** Returns a new builder for an immutable range set. */ 730 public static <C extends Comparable<?>> Builder<C> builder() { 731 return new Builder<C>(); 732 } 733 734 /** 735 * A builder for immutable range sets. 736 * 737 * @since 14.0 738 */ 739 public static class Builder<C extends Comparable<?>> { 740 private final List<Range<C>> ranges; 741 742 public Builder() { 743 this.ranges = Lists.newArrayList(); 744 } 745 746 // TODO(lowasser): consider adding union, in addition to add, that does allow overlap 747 748 /** 749 * Add the specified range to this builder. Adjacent ranges are permitted and will be merged, 750 * but overlapping ranges will cause an exception when {@link #build()} is called. 751 * 752 * @throws IllegalArgumentException if {@code range} is empty 753 */ 754 @CanIgnoreReturnValue 755 public Builder<C> add(Range<C> range) { 756 checkArgument(!range.isEmpty(), "range must not be empty, but was %s", range); 757 ranges.add(range); 758 return this; 759 } 760 761 /** 762 * Add all ranges from the specified range set to this builder. Adjacent ranges are permitted 763 * and will be merged, but overlapping ranges will cause an exception when {@link #build()} is 764 * called. 765 */ 766 @CanIgnoreReturnValue 767 public Builder<C> addAll(RangeSet<C> ranges) { 768 return addAll(ranges.asRanges()); 769 } 770 771 /** 772 * Add all of the specified ranges to this builder. Adjacent ranges are permitted and will be 773 * merged, but overlapping ranges will cause an exception when {@link #build()} is called. 774 * 775 * @throws IllegalArgumentException if any inserted ranges are empty 776 * @since 21.0 777 */ 778 @CanIgnoreReturnValue 779 public Builder<C> addAll(Iterable<Range<C>> ranges) { 780 for (Range<C> range : ranges) { 781 add(range); 782 } 783 return this; 784 } 785 786 @CanIgnoreReturnValue 787 Builder<C> combine(Builder<C> builder) { 788 addAll(builder.ranges); 789 return this; 790 } 791 792 /** 793 * Returns an {@code ImmutableRangeSet} containing the ranges added to this builder. 794 * 795 * @throws IllegalArgumentException if any input ranges have nonempty overlap 796 */ 797 public ImmutableRangeSet<C> build() { 798 ImmutableList.Builder<Range<C>> mergedRangesBuilder = 799 new ImmutableList.Builder<>(ranges.size()); 800 Collections.sort(ranges, Range.<C>rangeLexOrdering()); 801 PeekingIterator<Range<C>> peekingItr = Iterators.peekingIterator(ranges.iterator()); 802 while (peekingItr.hasNext()) { 803 Range<C> range = peekingItr.next(); 804 while (peekingItr.hasNext()) { 805 Range<C> nextRange = peekingItr.peek(); 806 if (range.isConnected(nextRange)) { 807 checkArgument( 808 range.intersection(nextRange).isEmpty(), 809 "Overlapping ranges not permitted but found %s overlapping %s", 810 range, 811 nextRange); 812 range = range.span(peekingItr.next()); 813 } else { 814 break; 815 } 816 } 817 mergedRangesBuilder.add(range); 818 } 819 ImmutableList<Range<C>> mergedRanges = mergedRangesBuilder.build(); 820 if (mergedRanges.isEmpty()) { 821 return of(); 822 } else if (mergedRanges.size() == 1 823 && Iterables.getOnlyElement(mergedRanges).equals(Range.all())) { 824 return all(); 825 } else { 826 return new ImmutableRangeSet<C>(mergedRanges); 827 } 828 } 829 } 830 831 private static final class SerializedForm<C extends Comparable> implements Serializable { 832 private final ImmutableList<Range<C>> ranges; 833 834 SerializedForm(ImmutableList<Range<C>> ranges) { 835 this.ranges = ranges; 836 } 837 838 Object readResolve() { 839 if (ranges.isEmpty()) { 840 return of(); 841 } else if (ranges.equals(ImmutableList.of(Range.all()))) { 842 return all(); 843 } else { 844 return new ImmutableRangeSet<C>(ranges); 845 } 846 } 847 } 848 849 @J2ktIncompatible // java.io.ObjectInputStream 850 Object writeReplace() { 851 return new SerializedForm<C>(ranges); 852 } 853 854 @J2ktIncompatible // java.io.ObjectInputStream 855 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 856 throw new InvalidObjectException("Use SerializedForm"); 857 } 858}