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