001/* 002 * Copyright (C) 2012 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.collect; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkElementIndex; 019import static com.google.common.base.Preconditions.checkNotNull; 020import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER; 021import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER; 022import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT; 023import static java.util.Objects.requireNonNull; 024 025import com.google.common.annotations.GwtIncompatible; 026import com.google.common.annotations.J2ktIncompatible; 027import com.google.common.collect.SortedLists.KeyAbsentBehavior; 028import com.google.common.collect.SortedLists.KeyPresentBehavior; 029import com.google.common.primitives.Ints; 030import com.google.errorprone.annotations.CanIgnoreReturnValue; 031import com.google.errorprone.annotations.DoNotCall; 032import com.google.errorprone.annotations.concurrent.LazyInit; 033import java.io.InvalidObjectException; 034import java.io.ObjectInputStream; 035import java.io.Serializable; 036import java.util.Collections; 037import java.util.Iterator; 038import java.util.List; 039import java.util.NoSuchElementException; 040import java.util.Set; 041import java.util.stream.Collector; 042import javax.annotation.CheckForNull; 043 044/** 045 * A {@link RangeSet} whose contents will never change, with many other important properties 046 * detailed at {@link ImmutableCollection}. 047 * 048 * @author Louis Wasserman 049 * @since 14.0 050 */ 051@SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989 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::lowerBound, 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::lowerBound, 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::lowerBound, 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 // redeclare to help optimizers with b/310253115 374 @SuppressWarnings("RedundantOverride") 375 @Override 376 @J2ktIncompatible // serialization 377 Object writeReplace() { 378 return super.writeReplace(); 379 } 380 } 381 382 @Override 383 public ImmutableRangeSet<C> complement() { 384 ImmutableRangeSet<C> result = complement; 385 if (result != null) { 386 return result; 387 } else if (ranges.isEmpty()) { 388 return complement = all(); 389 } else if (ranges.size() == 1 && ranges.get(0).equals(Range.all())) { 390 return complement = of(); 391 } else { 392 ImmutableList<Range<C>> complementRanges = new ComplementRanges(); 393 result = complement = new ImmutableRangeSet<C>(complementRanges, this); 394 } 395 return result; 396 } 397 398 /** 399 * Returns a new range set consisting of the union of this range set and {@code other}. 400 * 401 * <p>This is essentially the same as {@code TreeRangeSet.create(this).addAll(other)} except it 402 * returns an {@code ImmutableRangeSet}. 403 * 404 * @since 21.0 405 */ 406 public ImmutableRangeSet<C> union(RangeSet<C> other) { 407 return unionOf(Iterables.concat(asRanges(), other.asRanges())); 408 } 409 410 /** 411 * Returns a new range set consisting of the intersection of this range set and {@code other}. 412 * 413 * <p>This is essentially the same as {@code 414 * TreeRangeSet.create(this).removeAll(other.complement())} except it returns an {@code 415 * ImmutableRangeSet}. 416 * 417 * @since 21.0 418 */ 419 public ImmutableRangeSet<C> intersection(RangeSet<C> other) { 420 RangeSet<C> copy = TreeRangeSet.create(this); 421 copy.removeAll(other.complement()); 422 return copyOf(copy); 423 } 424 425 /** 426 * Returns a new range set consisting of the difference of this range set and {@code other}. 427 * 428 * <p>This is essentially the same as {@code TreeRangeSet.create(this).removeAll(other)} except it 429 * returns an {@code ImmutableRangeSet}. 430 * 431 * @since 21.0 432 */ 433 public ImmutableRangeSet<C> difference(RangeSet<C> other) { 434 RangeSet<C> copy = TreeRangeSet.create(this); 435 copy.removeAll(other); 436 return copyOf(copy); 437 } 438 439 /** 440 * Returns a list containing the nonempty intersections of {@code range} with the ranges in this 441 * range set. 442 */ 443 private ImmutableList<Range<C>> intersectRanges(final Range<C> range) { 444 if (ranges.isEmpty() || range.isEmpty()) { 445 return ImmutableList.of(); 446 } else if (range.encloses(span())) { 447 return ranges; 448 } 449 450 final int fromIndex; 451 if (range.hasLowerBound()) { 452 fromIndex = 453 SortedLists.binarySearch( 454 ranges, 455 Range::upperBound, 456 range.lowerBound, 457 KeyPresentBehavior.FIRST_AFTER, 458 KeyAbsentBehavior.NEXT_HIGHER); 459 } else { 460 fromIndex = 0; 461 } 462 463 int toIndex; 464 if (range.hasUpperBound()) { 465 toIndex = 466 SortedLists.binarySearch( 467 ranges, 468 Range::lowerBound, 469 range.upperBound, 470 KeyPresentBehavior.FIRST_PRESENT, 471 KeyAbsentBehavior.NEXT_HIGHER); 472 } else { 473 toIndex = ranges.size(); 474 } 475 final int length = toIndex - fromIndex; 476 if (length == 0) { 477 return ImmutableList.of(); 478 } else { 479 return new ImmutableList<Range<C>>() { 480 @Override 481 public int size() { 482 return length; 483 } 484 485 @Override 486 public Range<C> get(int index) { 487 checkElementIndex(index, length); 488 if (index == 0 || index == length - 1) { 489 return ranges.get(index + fromIndex).intersection(range); 490 } else { 491 return ranges.get(index + fromIndex); 492 } 493 } 494 495 @Override 496 boolean isPartialView() { 497 return true; 498 } 499 500 // redeclare to help optimizers with b/310253115 501 @SuppressWarnings("RedundantOverride") 502 @Override 503 @J2ktIncompatible // serialization 504 @GwtIncompatible // serialization 505 Object writeReplace() { 506 return super.writeReplace(); 507 } 508 }; 509 } 510 } 511 512 /** Returns a view of the intersection of this range set with the given range. */ 513 @Override 514 public ImmutableRangeSet<C> subRangeSet(Range<C> range) { 515 if (!isEmpty()) { 516 Range<C> span = span(); 517 if (range.encloses(span)) { 518 return this; 519 } else if (range.isConnected(span)) { 520 return new ImmutableRangeSet<C>(intersectRanges(range)); 521 } 522 } 523 return of(); 524 } 525 526 /** 527 * Returns an {@link ImmutableSortedSet} containing the same values in the given domain 528 * {@linkplain RangeSet#contains contained} by this range set. 529 * 530 * <p><b>Note:</b> {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For 531 * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty 532 * ranges {@code [3..3)} and {@code [4..4)}. 533 * 534 * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet} view of a large 535 * range set (such as {@code ImmutableRangeSet.of(Range.greaterThan(0))}). Certain operations on 536 * such a set can be performed efficiently, but others (such as {@link Set#hashCode} or {@link 537 * Collections#frequency}) can cause major performance problems. 538 * 539 * <p>The returned set's {@link Object#toString} method returns a shorthand form of the set's 540 * contents, such as {@code "[1..100]}"}. 541 * 542 * @throws IllegalArgumentException if neither this range nor the domain has a lower bound, or if 543 * neither has an upper bound 544 */ 545 public ImmutableSortedSet<C> asSet(DiscreteDomain<C> domain) { 546 checkNotNull(domain); 547 if (isEmpty()) { 548 return ImmutableSortedSet.of(); 549 } 550 Range<C> span = span().canonical(domain); 551 if (!span.hasLowerBound()) { 552 // according to the spec of canonical, neither this ImmutableRangeSet nor 553 // the range have a lower bound 554 throw new IllegalArgumentException( 555 "Neither the DiscreteDomain nor this range set are bounded below"); 556 } else if (!span.hasUpperBound()) { 557 try { 558 domain.maxValue(); 559 } catch (NoSuchElementException e) { 560 throw new IllegalArgumentException( 561 "Neither the DiscreteDomain nor this range set are bounded above"); 562 } 563 } 564 565 return new AsSet(domain); 566 } 567 568 private final class AsSet extends ImmutableSortedSet<C> { 569 private final DiscreteDomain<C> domain; 570 571 AsSet(DiscreteDomain<C> domain) { 572 super(Ordering.natural()); 573 this.domain = domain; 574 } 575 576 @LazyInit @CheckForNull private transient Integer size; 577 578 @Override 579 public int size() { 580 // racy single-check idiom 581 Integer result = size; 582 if (result == null) { 583 long total = 0; 584 for (Range<C> range : ranges) { 585 total += ContiguousSet.create(range, domain).size(); 586 if (total >= Integer.MAX_VALUE) { 587 break; 588 } 589 } 590 result = size = Ints.saturatedCast(total); 591 } 592 return result.intValue(); 593 } 594 595 @Override 596 public UnmodifiableIterator<C> iterator() { 597 return new AbstractIterator<C>() { 598 final Iterator<Range<C>> rangeItr = ranges.iterator(); 599 Iterator<C> elemItr = Iterators.emptyIterator(); 600 601 @Override 602 @CheckForNull 603 protected C computeNext() { 604 while (!elemItr.hasNext()) { 605 if (rangeItr.hasNext()) { 606 elemItr = ContiguousSet.create(rangeItr.next(), domain).iterator(); 607 } else { 608 return endOfData(); 609 } 610 } 611 return elemItr.next(); 612 } 613 }; 614 } 615 616 @Override 617 @GwtIncompatible("NavigableSet") 618 public UnmodifiableIterator<C> descendingIterator() { 619 return new AbstractIterator<C>() { 620 final Iterator<Range<C>> rangeItr = ranges.reverse().iterator(); 621 Iterator<C> elemItr = Iterators.emptyIterator(); 622 623 @Override 624 @CheckForNull 625 protected C computeNext() { 626 while (!elemItr.hasNext()) { 627 if (rangeItr.hasNext()) { 628 elemItr = ContiguousSet.create(rangeItr.next(), domain).descendingIterator(); 629 } else { 630 return endOfData(); 631 } 632 } 633 return elemItr.next(); 634 } 635 }; 636 } 637 638 ImmutableSortedSet<C> subSet(Range<C> range) { 639 return subRangeSet(range).asSet(domain); 640 } 641 642 @Override 643 ImmutableSortedSet<C> headSetImpl(C toElement, boolean inclusive) { 644 return subSet(Range.upTo(toElement, BoundType.forBoolean(inclusive))); 645 } 646 647 @Override 648 ImmutableSortedSet<C> subSetImpl( 649 C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) { 650 if (!fromInclusive && !toInclusive && Range.compareOrThrow(fromElement, toElement) == 0) { 651 return ImmutableSortedSet.of(); 652 } 653 return subSet( 654 Range.range( 655 fromElement, BoundType.forBoolean(fromInclusive), 656 toElement, BoundType.forBoolean(toInclusive))); 657 } 658 659 @Override 660 ImmutableSortedSet<C> tailSetImpl(C fromElement, boolean inclusive) { 661 return subSet(Range.downTo(fromElement, BoundType.forBoolean(inclusive))); 662 } 663 664 @Override 665 public boolean contains(@CheckForNull Object o) { 666 if (o == null) { 667 return false; 668 } 669 try { 670 @SuppressWarnings("unchecked") // we catch CCE's 671 C c = (C) o; 672 return ImmutableRangeSet.this.contains(c); 673 } catch (ClassCastException e) { 674 return false; 675 } 676 } 677 678 @Override 679 int indexOf(@CheckForNull Object target) { 680 if (contains(target)) { 681 @SuppressWarnings("unchecked") // if it's contained, it's definitely a C 682 C c = (C) requireNonNull(target); 683 long total = 0; 684 for (Range<C> range : ranges) { 685 if (range.contains(c)) { 686 return Ints.saturatedCast(total + ContiguousSet.create(range, domain).indexOf(c)); 687 } else { 688 total += ContiguousSet.create(range, domain).size(); 689 } 690 } 691 throw new AssertionError("impossible"); 692 } 693 return -1; 694 } 695 696 @Override 697 ImmutableSortedSet<C> createDescendingSet() { 698 return new DescendingImmutableSortedSet<C>(this); 699 } 700 701 @Override 702 boolean isPartialView() { 703 return ranges.isPartialView(); 704 } 705 706 @Override 707 public String toString() { 708 return ranges.toString(); 709 } 710 711 @Override 712 @J2ktIncompatible // serialization 713 Object writeReplace() { 714 return new AsSetSerializedForm<C>(ranges, domain); 715 } 716 717 @J2ktIncompatible // java.io.ObjectInputStream 718 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 719 throw new InvalidObjectException("Use SerializedForm"); 720 } 721 } 722 723 private static class AsSetSerializedForm<C extends Comparable> implements Serializable { 724 private final ImmutableList<Range<C>> ranges; 725 private final DiscreteDomain<C> domain; 726 727 AsSetSerializedForm(ImmutableList<Range<C>> ranges, DiscreteDomain<C> domain) { 728 this.ranges = ranges; 729 this.domain = domain; 730 } 731 732 Object readResolve() { 733 return new ImmutableRangeSet<C>(ranges).asSet(domain); 734 } 735 } 736 737 /** 738 * Returns {@code true} if this immutable range set's implementation contains references to 739 * user-created objects that aren't accessible via this range set's methods. This is generally 740 * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid 741 * memory leaks. 742 */ 743 boolean isPartialView() { 744 return ranges.isPartialView(); 745 } 746 747 /** Returns a new builder for an immutable range set. */ 748 public static <C extends Comparable<?>> Builder<C> builder() { 749 return new Builder<C>(); 750 } 751 752 /** 753 * A builder for immutable range sets. 754 * 755 * @since 14.0 756 */ 757 public static class Builder<C extends Comparable<?>> { 758 private final List<Range<C>> ranges; 759 760 public Builder() { 761 this.ranges = Lists.newArrayList(); 762 } 763 764 // TODO(lowasser): consider adding union, in addition to add, that does allow overlap 765 766 /** 767 * Add the specified range to this builder. Adjacent ranges are permitted and will be merged, 768 * but overlapping ranges will cause an exception when {@link #build()} is called. 769 * 770 * @throws IllegalArgumentException if {@code range} is empty 771 */ 772 @CanIgnoreReturnValue 773 public Builder<C> add(Range<C> range) { 774 checkArgument(!range.isEmpty(), "range must not be empty, but was %s", range); 775 ranges.add(range); 776 return this; 777 } 778 779 /** 780 * Add all ranges from the specified range set to this builder. Adjacent ranges are permitted 781 * and will be merged, but overlapping ranges will cause an exception when {@link #build()} is 782 * called. 783 */ 784 @CanIgnoreReturnValue 785 public Builder<C> addAll(RangeSet<C> ranges) { 786 return addAll(ranges.asRanges()); 787 } 788 789 /** 790 * Add all of the specified ranges to this builder. Adjacent ranges are permitted and will be 791 * merged, but overlapping ranges will cause an exception when {@link #build()} is called. 792 * 793 * @throws IllegalArgumentException if any inserted ranges are empty 794 * @since 21.0 795 */ 796 @CanIgnoreReturnValue 797 public Builder<C> addAll(Iterable<Range<C>> ranges) { 798 for (Range<C> range : ranges) { 799 add(range); 800 } 801 return this; 802 } 803 804 @CanIgnoreReturnValue 805 Builder<C> combine(Builder<C> builder) { 806 addAll(builder.ranges); 807 return this; 808 } 809 810 /** 811 * Returns an {@code ImmutableRangeSet} containing the ranges added to this builder. 812 * 813 * @throws IllegalArgumentException if any input ranges have nonempty overlap 814 */ 815 public ImmutableRangeSet<C> build() { 816 ImmutableList.Builder<Range<C>> mergedRangesBuilder = 817 new ImmutableList.Builder<>(ranges.size()); 818 Collections.sort(ranges, Range.<C>rangeLexOrdering()); 819 PeekingIterator<Range<C>> peekingItr = Iterators.peekingIterator(ranges.iterator()); 820 while (peekingItr.hasNext()) { 821 Range<C> range = peekingItr.next(); 822 while (peekingItr.hasNext()) { 823 Range<C> nextRange = peekingItr.peek(); 824 if (range.isConnected(nextRange)) { 825 checkArgument( 826 range.intersection(nextRange).isEmpty(), 827 "Overlapping ranges not permitted but found %s overlapping %s", 828 range, 829 nextRange); 830 range = range.span(peekingItr.next()); 831 } else { 832 break; 833 } 834 } 835 mergedRangesBuilder.add(range); 836 } 837 ImmutableList<Range<C>> mergedRanges = mergedRangesBuilder.build(); 838 if (mergedRanges.isEmpty()) { 839 return of(); 840 } else if (mergedRanges.size() == 1 841 && Iterables.getOnlyElement(mergedRanges).equals(Range.all())) { 842 return all(); 843 } else { 844 return new ImmutableRangeSet<C>(mergedRanges); 845 } 846 } 847 } 848 849 private static final class SerializedForm<C extends Comparable> implements Serializable { 850 private final ImmutableList<Range<C>> ranges; 851 852 SerializedForm(ImmutableList<Range<C>> ranges) { 853 this.ranges = ranges; 854 } 855 856 Object readResolve() { 857 if (ranges.isEmpty()) { 858 return of(); 859 } else if (ranges.equals(ImmutableList.of(Range.all()))) { 860 return all(); 861 } else { 862 return new ImmutableRangeSet<C>(ranges); 863 } 864 } 865 } 866 867 @J2ktIncompatible // java.io.ObjectInputStream 868 Object writeReplace() { 869 return new SerializedForm<C>(ranges); 870 } 871 872 @J2ktIncompatible // java.io.ObjectInputStream 873 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 874 throw new InvalidObjectException("Use SerializedForm"); 875 } 876}