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