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