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