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