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