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