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