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