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.Beta; 026import com.google.common.annotations.GwtIncompatible; 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.Serializable; 034import java.util.Collections; 035import java.util.Iterator; 036import java.util.List; 037import java.util.NoSuchElementException; 038import java.util.Set; 039import javax.annotation.CheckForNull; 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 050@ElementTypesAreNonnullByDefault 051public final class ImmutableRangeSet<C extends Comparable> extends AbstractRangeSet<C> 052 implements Serializable { 053 054 private static final ImmutableRangeSet<Comparable<?>> EMPTY = 055 new ImmutableRangeSet<>(ImmutableList.<Range<Comparable<?>>>of()); 056 057 private static final ImmutableRangeSet<Comparable<?>> ALL = 058 new ImmutableRangeSet<>(ImmutableList.of(Range.<Comparable<?>>all())); 059 060 /** 061 * Returns an empty immutable range set. 062 * 063 * <p><b>Performance note:</b> the instance returned is a singleton. 064 */ 065 @SuppressWarnings("unchecked") 066 public static <C extends Comparable> ImmutableRangeSet<C> of() { 067 return (ImmutableRangeSet<C>) EMPTY; 068 } 069 070 /** 071 * Returns an immutable range set containing the specified single range. If {@link Range#isEmpty() 072 * range.isEmpty()}, this is equivalent to {@link ImmutableRangeSet#of()}. 073 */ 074 public static <C extends Comparable> ImmutableRangeSet<C> of(Range<C> range) { 075 checkNotNull(range); 076 if (range.isEmpty()) { 077 return of(); 078 } else if (range.equals(Range.all())) { 079 return all(); 080 } else { 081 return new ImmutableRangeSet<C>(ImmutableList.of(range)); 082 } 083 } 084 085 /** Returns an immutable range set containing the single range {@link Range#all()}. */ 086 @SuppressWarnings("unchecked") 087 static <C extends Comparable> ImmutableRangeSet<C> all() { 088 return (ImmutableRangeSet<C>) ALL; 089 } 090 091 /** Returns an immutable copy of the specified {@code RangeSet}. */ 092 public static <C extends Comparable> ImmutableRangeSet<C> copyOf(RangeSet<C> rangeSet) { 093 checkNotNull(rangeSet); 094 if (rangeSet.isEmpty()) { 095 return of(); 096 } else if (rangeSet.encloses(Range.<C>all())) { 097 return all(); 098 } 099 100 if (rangeSet instanceof ImmutableRangeSet) { 101 ImmutableRangeSet<C> immutableRangeSet = (ImmutableRangeSet<C>) rangeSet; 102 if (!immutableRangeSet.isPartialView()) { 103 return immutableRangeSet; 104 } 105 } 106 return new ImmutableRangeSet<C>(ImmutableList.copyOf(rangeSet.asRanges())); 107 } 108 109 /** 110 * Returns an {@code ImmutableRangeSet} containing each of the specified disjoint ranges. 111 * Overlapping ranges and empty ranges are forbidden, though adjacent ranges are permitted and 112 * will be merged. 113 * 114 * @throws IllegalArgumentException if any ranges overlap or are empty 115 * @since 21.0 116 */ 117 public static <C extends Comparable<?>> ImmutableRangeSet<C> copyOf(Iterable<Range<C>> ranges) { 118 return new ImmutableRangeSet.Builder<C>().addAll(ranges).build(); 119 } 120 121 /** 122 * Returns an {@code ImmutableRangeSet} representing the union of the specified ranges. 123 * 124 * <p>This is the smallest {@code RangeSet} which encloses each of the specified ranges. Duplicate 125 * or connected ranges are permitted, and will be coalesced in the result. 126 * 127 * @since 21.0 128 */ 129 public static <C extends Comparable<?>> ImmutableRangeSet<C> unionOf(Iterable<Range<C>> ranges) { 130 return copyOf(TreeRangeSet.create(ranges)); 131 } 132 133 ImmutableRangeSet(ImmutableList<Range<C>> ranges) { 134 this.ranges = ranges; 135 } 136 137 private ImmutableRangeSet(ImmutableList<Range<C>> ranges, ImmutableRangeSet<C> complement) { 138 this.ranges = ranges; 139 this.complement = complement; 140 } 141 142 private final transient ImmutableList<Range<C>> ranges; 143 144 @Override 145 public boolean intersects(Range<C> otherRange) { 146 int ceilingIndex = 147 SortedLists.binarySearch( 148 ranges, 149 Range.<C>lowerBoundFn(), 150 otherRange.lowerBound, 151 Ordering.natural(), 152 ANY_PRESENT, 153 NEXT_HIGHER); 154 if (ceilingIndex < ranges.size() 155 && ranges.get(ceilingIndex).isConnected(otherRange) 156 && !ranges.get(ceilingIndex).intersection(otherRange).isEmpty()) { 157 return true; 158 } 159 return ceilingIndex > 0 160 && ranges.get(ceilingIndex - 1).isConnected(otherRange) 161 && !ranges.get(ceilingIndex - 1).intersection(otherRange).isEmpty(); 162 } 163 164 @Override 165 public boolean encloses(Range<C> otherRange) { 166 int index = 167 SortedLists.binarySearch( 168 ranges, 169 Range.<C>lowerBoundFn(), 170 otherRange.lowerBound, 171 Ordering.natural(), 172 ANY_PRESENT, 173 NEXT_LOWER); 174 return index != -1 && ranges.get(index).encloses(otherRange); 175 } 176 177 @Override 178 @CheckForNull 179 public Range<C> rangeContaining(C value) { 180 int index = 181 SortedLists.binarySearch( 182 ranges, 183 Range.<C>lowerBoundFn(), 184 Cut.belowValue(value), 185 Ordering.natural(), 186 ANY_PRESENT, 187 NEXT_LOWER); 188 if (index != -1) { 189 Range<C> range = ranges.get(index); 190 return range.contains(value) ? range : null; 191 } 192 return null; 193 } 194 195 @Override 196 public Range<C> span() { 197 if (ranges.isEmpty()) { 198 throw new NoSuchElementException(); 199 } 200 return Range.create(ranges.get(0).lowerBound, ranges.get(ranges.size() - 1).upperBound); 201 } 202 203 @Override 204 public boolean isEmpty() { 205 return ranges.isEmpty(); 206 } 207 208 /** 209 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 210 * 211 * @throws UnsupportedOperationException always 212 * @deprecated Unsupported operation. 213 */ 214 @Deprecated 215 @Override 216 @DoNotCall("Always throws UnsupportedOperationException") 217 public void add(Range<C> range) { 218 throw new UnsupportedOperationException(); 219 } 220 221 /** 222 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 223 * 224 * @throws UnsupportedOperationException always 225 * @deprecated Unsupported operation. 226 */ 227 @Deprecated 228 @Override 229 @DoNotCall("Always throws UnsupportedOperationException") 230 public void addAll(RangeSet<C> other) { 231 throw new UnsupportedOperationException(); 232 } 233 234 /** 235 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 236 * 237 * @throws UnsupportedOperationException always 238 * @deprecated Unsupported operation. 239 */ 240 @Deprecated 241 @Override 242 @DoNotCall("Always throws UnsupportedOperationException") 243 public void addAll(Iterable<Range<C>> other) { 244 throw new UnsupportedOperationException(); 245 } 246 247 /** 248 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 249 * 250 * @throws UnsupportedOperationException always 251 * @deprecated Unsupported operation. 252 */ 253 @Deprecated 254 @Override 255 @DoNotCall("Always throws UnsupportedOperationException") 256 public void remove(Range<C> range) { 257 throw new UnsupportedOperationException(); 258 } 259 260 /** 261 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 262 * 263 * @throws UnsupportedOperationException always 264 * @deprecated Unsupported operation. 265 */ 266 @Deprecated 267 @Override 268 @DoNotCall("Always throws UnsupportedOperationException") 269 public void removeAll(RangeSet<C> other) { 270 throw new UnsupportedOperationException(); 271 } 272 273 /** 274 * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified. 275 * 276 * @throws UnsupportedOperationException always 277 * @deprecated Unsupported operation. 278 */ 279 @Deprecated 280 @Override 281 @DoNotCall("Always throws UnsupportedOperationException") 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 @CheckForNull 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 @CheckForNull private transient 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 @CheckForNull 571 protected C computeNext() { 572 while (!elemItr.hasNext()) { 573 if (rangeItr.hasNext()) { 574 elemItr = ContiguousSet.create(rangeItr.next(), domain).iterator(); 575 } else { 576 return endOfData(); 577 } 578 } 579 return elemItr.next(); 580 } 581 }; 582 } 583 584 @Override 585 @GwtIncompatible("NavigableSet") 586 public UnmodifiableIterator<C> descendingIterator() { 587 return new AbstractIterator<C>() { 588 final Iterator<Range<C>> rangeItr = ranges.reverse().iterator(); 589 Iterator<C> elemItr = Iterators.emptyIterator(); 590 591 @Override 592 @CheckForNull 593 protected C computeNext() { 594 while (!elemItr.hasNext()) { 595 if (rangeItr.hasNext()) { 596 elemItr = ContiguousSet.create(rangeItr.next(), domain).descendingIterator(); 597 } else { 598 return endOfData(); 599 } 600 } 601 return elemItr.next(); 602 } 603 }; 604 } 605 606 ImmutableSortedSet<C> subSet(Range<C> range) { 607 return subRangeSet(range).asSet(domain); 608 } 609 610 @Override 611 ImmutableSortedSet<C> headSetImpl(C toElement, boolean inclusive) { 612 return subSet(Range.upTo(toElement, BoundType.forBoolean(inclusive))); 613 } 614 615 @Override 616 ImmutableSortedSet<C> subSetImpl( 617 C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) { 618 if (!fromInclusive && !toInclusive && Range.compareOrThrow(fromElement, toElement) == 0) { 619 return ImmutableSortedSet.of(); 620 } 621 return subSet( 622 Range.range( 623 fromElement, BoundType.forBoolean(fromInclusive), 624 toElement, BoundType.forBoolean(toInclusive))); 625 } 626 627 @Override 628 ImmutableSortedSet<C> tailSetImpl(C fromElement, boolean inclusive) { 629 return subSet(Range.downTo(fromElement, BoundType.forBoolean(inclusive))); 630 } 631 632 @Override 633 public boolean contains(@CheckForNull Object o) { 634 if (o == null) { 635 return false; 636 } 637 try { 638 @SuppressWarnings("unchecked") // we catch CCE's 639 C c = (C) o; 640 return ImmutableRangeSet.this.contains(c); 641 } catch (ClassCastException e) { 642 return false; 643 } 644 } 645 646 @Override 647 int indexOf(@CheckForNull Object target) { 648 if (contains(target)) { 649 @SuppressWarnings("unchecked") // if it's contained, it's definitely a C 650 C c = (C) requireNonNull(target); 651 long total = 0; 652 for (Range<C> range : ranges) { 653 if (range.contains(c)) { 654 return Ints.saturatedCast(total + ContiguousSet.create(range, domain).indexOf(c)); 655 } else { 656 total += ContiguousSet.create(range, domain).size(); 657 } 658 } 659 throw new AssertionError("impossible"); 660 } 661 return -1; 662 } 663 664 @Override 665 ImmutableSortedSet<C> createDescendingSet() { 666 return new DescendingImmutableSortedSet<C>(this); 667 } 668 669 @Override 670 boolean isPartialView() { 671 return ranges.isPartialView(); 672 } 673 674 @Override 675 public String toString() { 676 return ranges.toString(); 677 } 678 679 @Override 680 Object writeReplace() { 681 return new AsSetSerializedForm<C>(ranges, domain); 682 } 683 } 684 685 private static class AsSetSerializedForm<C extends Comparable> implements Serializable { 686 private final ImmutableList<Range<C>> ranges; 687 private final DiscreteDomain<C> domain; 688 689 AsSetSerializedForm(ImmutableList<Range<C>> ranges, DiscreteDomain<C> domain) { 690 this.ranges = ranges; 691 this.domain = domain; 692 } 693 694 Object readResolve() { 695 return new ImmutableRangeSet<C>(ranges).asSet(domain); 696 } 697 } 698 699 /** 700 * Returns {@code true} if this immutable range set's implementation contains references to 701 * user-created objects that aren't accessible via this range set's methods. This is generally 702 * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid 703 * memory leaks. 704 */ 705 boolean isPartialView() { 706 return ranges.isPartialView(); 707 } 708 709 /** Returns a new builder for an immutable range set. */ 710 public static <C extends Comparable<?>> Builder<C> builder() { 711 return new Builder<C>(); 712 } 713 714 /** 715 * A builder for immutable range sets. 716 * 717 * @since 14.0 718 */ 719 public static class Builder<C extends Comparable<?>> { 720 private final List<Range<C>> ranges; 721 722 public Builder() { 723 this.ranges = Lists.newArrayList(); 724 } 725 726 // TODO(lowasser): consider adding union, in addition to add, that does allow overlap 727 728 /** 729 * Add the specified range to this builder. Adjacent ranges are permitted and will be merged, 730 * but overlapping ranges will cause an exception when {@link #build()} is called. 731 * 732 * @throws IllegalArgumentException if {@code range} is empty 733 */ 734 @CanIgnoreReturnValue 735 public Builder<C> add(Range<C> range) { 736 checkArgument(!range.isEmpty(), "range must not be empty, but was %s", range); 737 ranges.add(range); 738 return this; 739 } 740 741 /** 742 * Add all ranges from the specified range set to this builder. Adjacent ranges are permitted 743 * and will be merged, but overlapping ranges will cause an exception when {@link #build()} is 744 * called. 745 */ 746 @CanIgnoreReturnValue 747 public Builder<C> addAll(RangeSet<C> ranges) { 748 return addAll(ranges.asRanges()); 749 } 750 751 /** 752 * Add all of the specified ranges to this builder. Adjacent ranges are permitted and will be 753 * merged, but overlapping ranges will cause an exception when {@link #build()} is called. 754 * 755 * @throws IllegalArgumentException if any inserted ranges are empty 756 * @since 21.0 757 */ 758 @CanIgnoreReturnValue 759 public Builder<C> addAll(Iterable<Range<C>> ranges) { 760 for (Range<C> range : ranges) { 761 add(range); 762 } 763 return this; 764 } 765 766 @CanIgnoreReturnValue 767 Builder<C> combine(Builder<C> builder) { 768 addAll(builder.ranges); 769 return this; 770 } 771 772 /** 773 * Returns an {@code ImmutableRangeSet} containing the ranges added to this builder. 774 * 775 * @throws IllegalArgumentException if any input ranges have nonempty overlap 776 */ 777 public ImmutableRangeSet<C> build() { 778 ImmutableList.Builder<Range<C>> mergedRangesBuilder = 779 new ImmutableList.Builder<>(ranges.size()); 780 Collections.sort(ranges, Range.<C>rangeLexOrdering()); 781 PeekingIterator<Range<C>> peekingItr = Iterators.peekingIterator(ranges.iterator()); 782 while (peekingItr.hasNext()) { 783 Range<C> range = peekingItr.next(); 784 while (peekingItr.hasNext()) { 785 Range<C> nextRange = peekingItr.peek(); 786 if (range.isConnected(nextRange)) { 787 checkArgument( 788 range.intersection(nextRange).isEmpty(), 789 "Overlapping ranges not permitted but found %s overlapping %s", 790 range, 791 nextRange); 792 range = range.span(peekingItr.next()); 793 } else { 794 break; 795 } 796 } 797 mergedRangesBuilder.add(range); 798 } 799 ImmutableList<Range<C>> mergedRanges = mergedRangesBuilder.build(); 800 if (mergedRanges.isEmpty()) { 801 return of(); 802 } else if (mergedRanges.size() == 1 803 && Iterables.getOnlyElement(mergedRanges).equals(Range.all())) { 804 return all(); 805 } else { 806 return new ImmutableRangeSet<C>(mergedRanges); 807 } 808 } 809 } 810 811 private static final class SerializedForm<C extends Comparable> implements Serializable { 812 private final ImmutableList<Range<C>> ranges; 813 814 SerializedForm(ImmutableList<Range<C>> ranges) { 815 this.ranges = ranges; 816 } 817 818 Object readResolve() { 819 if (ranges.isEmpty()) { 820 return of(); 821 } else if (ranges.equals(ImmutableList.of(Range.all()))) { 822 return all(); 823 } else { 824 return new ImmutableRangeSet<C>(ranges); 825 } 826 } 827 } 828 829 Object writeReplace() { 830 return new SerializedForm<C>(ranges); 831 } 832}