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<Comparable<?>>(ImmutableList.<Range<Comparable<?>>>of());
052
053  private static final ImmutableRangeSet<Comparable<?>> ALL =
054      new ImmutableRangeSet<Comparable<?>>(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<Range<C>>(ranges, Range.RANGE_LEX_ORDERING);
283  }
284
285  @Override
286  public ImmutableSet<Range<C>> asDescendingSetOfRanges() {
287    if (ranges.isEmpty()) {
288      return ImmutableSet.of();
289    }
290    return new RegularImmutableSortedSet<Range<C>>(
291        ranges.reverse(), Range.RANGE_LEX_ORDERING.reverse());
292  }
293
294  @LazyInit
295  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}
411   * with the ranges in this 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  /**
474   * Returns a view of the intersection of this range set with the given range.
475   */
476  @Override
477  public ImmutableRangeSet<C> subRangeSet(Range<C> range) {
478    if (!isEmpty()) {
479      Range<C> span = span();
480      if (range.encloses(span)) {
481        return this;
482      } else if (range.isConnected(span)) {
483        return new ImmutableRangeSet<C>(intersectRanges(range));
484      }
485    }
486    return of();
487  }
488
489  /**
490   * Returns an {@link ImmutableSortedSet} containing the same values in the given domain
491   * {@linkplain RangeSet#contains contained} by this range set.
492   *
493   * <p><b>Note:</b> {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For
494   * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty
495   * ranges {@code [3..3)} and {@code [4..4)}.
496   *
497   * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet} view of a large
498   * range set (such as {@code ImmutableRangeSet.of(Range.greaterThan(0))}). Certain operations on
499   * such a set can be performed efficiently, but others (such as {@link Set#hashCode} or
500   * {@link Collections#frequency}) can cause major performance problems.
501   *
502   * <p>The returned set's {@link Object#toString} method returns a short-hand form of the set's
503   * contents, such as {@code "[1..100]}"}.
504   *
505   * @throws IllegalArgumentException if neither this range nor the domain has a lower bound, or if
506   *         neither has an upper bound
507   */
508  public ImmutableSortedSet<C> asSet(DiscreteDomain<C> domain) {
509    checkNotNull(domain);
510    if (isEmpty()) {
511      return ImmutableSortedSet.of();
512    }
513    Range<C> span = span().canonical(domain);
514    if (!span.hasLowerBound()) {
515      // according to the spec of canonical, neither this ImmutableRangeSet nor
516      // the range have a lower bound
517      throw new IllegalArgumentException(
518          "Neither the DiscreteDomain nor this range set are bounded below");
519    } else if (!span.hasUpperBound()) {
520      try {
521        domain.maxValue();
522      } catch (NoSuchElementException e) {
523        throw new IllegalArgumentException(
524            "Neither the DiscreteDomain nor this range set are bounded above");
525      }
526    }
527
528    return new AsSet(domain);
529  }
530
531  private final class AsSet extends ImmutableSortedSet<C> {
532    private final DiscreteDomain<C> domain;
533
534    AsSet(DiscreteDomain<C> domain) {
535      super(Ordering.natural());
536      this.domain = domain;
537    }
538
539    private transient Integer size;
540
541    @Override
542    public int size() {
543      // racy single-check idiom
544      Integer result = size;
545      if (result == null) {
546        long total = 0;
547        for (Range<C> range : ranges) {
548          total += ContiguousSet.create(range, domain).size();
549          if (total >= Integer.MAX_VALUE) {
550            break;
551          }
552        }
553        result = size = Ints.saturatedCast(total);
554      }
555      return result.intValue();
556    }
557
558    @Override
559    public UnmodifiableIterator<C> iterator() {
560      return new AbstractIterator<C>() {
561        final Iterator<Range<C>> rangeItr = ranges.iterator();
562        Iterator<C> elemItr = Iterators.emptyIterator();
563
564        @Override
565        protected C computeNext() {
566          while (!elemItr.hasNext()) {
567            if (rangeItr.hasNext()) {
568              elemItr = ContiguousSet.create(rangeItr.next(), domain).iterator();
569            } else {
570              return endOfData();
571            }
572          }
573          return elemItr.next();
574        }
575      };
576    }
577
578    @Override
579    @GwtIncompatible("NavigableSet")
580    public UnmodifiableIterator<C> descendingIterator() {
581      return new AbstractIterator<C>() {
582        final Iterator<Range<C>> rangeItr = ranges.reverse().iterator();
583        Iterator<C> elemItr = Iterators.emptyIterator();
584
585        @Override
586        protected C computeNext() {
587          while (!elemItr.hasNext()) {
588            if (rangeItr.hasNext()) {
589              elemItr = ContiguousSet.create(rangeItr.next(), domain).descendingIterator();
590            } else {
591              return endOfData();
592            }
593          }
594          return elemItr.next();
595        }
596      };
597    }
598
599    ImmutableSortedSet<C> subSet(Range<C> range) {
600      return subRangeSet(range).asSet(domain);
601    }
602
603    @Override
604    ImmutableSortedSet<C> headSetImpl(C toElement, boolean inclusive) {
605      return subSet(Range.upTo(toElement, BoundType.forBoolean(inclusive)));
606    }
607
608    @Override
609    ImmutableSortedSet<C> subSetImpl(
610        C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) {
611      if (!fromInclusive && !toInclusive && Range.compareOrThrow(fromElement, toElement) == 0) {
612        return ImmutableSortedSet.of();
613      }
614      return subSet(
615          Range.range(
616              fromElement, BoundType.forBoolean(fromInclusive),
617              toElement, BoundType.forBoolean(toInclusive)));
618    }
619
620    @Override
621    ImmutableSortedSet<C> tailSetImpl(C fromElement, boolean inclusive) {
622      return subSet(Range.downTo(fromElement, BoundType.forBoolean(inclusive)));
623    }
624
625    @Override
626    public boolean contains(@Nullable Object o) {
627      if (o == null) {
628        return false;
629      }
630      try {
631        @SuppressWarnings("unchecked") // we catch CCE's
632        C c = (C) o;
633        return ImmutableRangeSet.this.contains(c);
634      } catch (ClassCastException e) {
635        return false;
636      }
637    }
638
639    @Override
640    int indexOf(Object target) {
641      if (contains(target)) {
642        @SuppressWarnings("unchecked") // if it's contained, it's definitely a C
643        C c = (C) target;
644        long total = 0;
645        for (Range<C> range : ranges) {
646          if (range.contains(c)) {
647            return Ints.saturatedCast(total + ContiguousSet.create(range, domain).indexOf(c));
648          } else {
649            total += ContiguousSet.create(range, domain).size();
650          }
651        }
652        throw new AssertionError("impossible");
653      }
654      return -1;
655    }
656
657    @Override
658    boolean isPartialView() {
659      return ranges.isPartialView();
660    }
661
662    @Override
663    public String toString() {
664      return ranges.toString();
665    }
666
667    @Override
668    Object writeReplace() {
669      return new AsSetSerializedForm<C>(ranges, domain);
670    }
671  }
672
673  private static class AsSetSerializedForm<C extends Comparable> implements Serializable {
674    private final ImmutableList<Range<C>> ranges;
675    private final DiscreteDomain<C> domain;
676
677    AsSetSerializedForm(ImmutableList<Range<C>> ranges, DiscreteDomain<C> domain) {
678      this.ranges = ranges;
679      this.domain = domain;
680    }
681
682    Object readResolve() {
683      return new ImmutableRangeSet<C>(ranges).asSet(domain);
684    }
685  }
686
687  /**
688   * Returns {@code true} if this immutable range set's implementation contains references to
689   * user-created objects that aren't accessible via this range set's methods. This is generally
690   * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid
691   * memory leaks.
692   */
693  boolean isPartialView() {
694    return ranges.isPartialView();
695  }
696
697  /**
698   * Returns a new builder for an immutable range set.
699   */
700  public static <C extends Comparable<?>> Builder<C> builder() {
701    return new Builder<C>();
702  }
703
704  /**
705   * A builder for immutable range sets.
706   */
707  public static class Builder<C extends Comparable<?>> {
708    private final List<Range<C>> ranges;
709
710    public Builder() {
711      this.ranges = Lists.newArrayList();
712    }
713
714    // TODO(lowasser): consider adding union, in addition to add, that does allow overlap
715
716    /**
717     * Add the specified range to this builder. Adjacent ranges are permitted and will be merged,
718     * but overlapping ranges will cause an exception when {@link #build()} is called.
719     *
720     * @throws IllegalArgumentException if {@code range} is empty
721     */
722    @CanIgnoreReturnValue
723    public Builder<C> add(Range<C> range) {
724      checkArgument(!range.isEmpty(), "range must not be empty, but was %s", range);
725      ranges.add(range);
726      return this;
727    }
728
729    /**
730     * Add all ranges from the specified range set to this builder. Adjacent ranges are permitted
731     * and will be merged, but overlapping ranges will cause an exception when {@link #build()} is
732     * called.
733     */
734    @CanIgnoreReturnValue
735    public Builder<C> addAll(RangeSet<C> ranges) {
736      return addAll(ranges.asRanges());
737    }
738
739    /**
740     * Add all of the specified ranges to this builder. Adjacent ranges are permitted and will be
741     * merged, but overlapping ranges will cause an exception when {@link #build()} is called.
742     *
743     * @throws IllegalArgumentException if any inserted ranges are empty
744     * @since 21.0
745     */
746    @CanIgnoreReturnValue
747    public Builder<C> addAll(Iterable<Range<C>> ranges) {
748      for (Range<C> range : ranges) {
749        add(range);
750      }
751      return this;
752    }
753
754    /**
755     * Returns an {@code ImmutableRangeSet} containing the ranges added to this builder.
756     *
757     * @throws IllegalArgumentException if any input ranges have nonempty overlap
758     */
759    public ImmutableRangeSet<C> build() {
760      ImmutableList.Builder<Range<C>> mergedRangesBuilder =
761          new ImmutableList.Builder<Range<C>>(ranges.size());
762      Collections.sort(ranges, Range.RANGE_LEX_ORDERING);
763      PeekingIterator<Range<C>> peekingItr = Iterators.peekingIterator(ranges.iterator());
764      while (peekingItr.hasNext()) {
765        Range<C> range = peekingItr.next();
766        while (peekingItr.hasNext()) {
767          Range<C> nextRange = peekingItr.peek();
768          if (range.isConnected(nextRange)) {
769            checkArgument(
770                range.intersection(nextRange).isEmpty(),
771                "Overlapping ranges not permitted but found %s overlapping %s",
772                range,
773                nextRange);
774            range = range.span(peekingItr.next());
775          } else {
776            break;
777          }
778        }
779        mergedRangesBuilder.add(range);
780      }
781      ImmutableList<Range<C>> mergedRanges = mergedRangesBuilder.build();
782      if (mergedRanges.isEmpty()) {
783        return of();
784      } else if (mergedRanges.size() == 1
785          && Iterables.getOnlyElement(mergedRanges).equals(Range.all())) {
786        return all();
787      } else {
788        return new ImmutableRangeSet<C>(mergedRanges);
789      }
790    }
791  }
792
793  private static final class SerializedForm<C extends Comparable> implements Serializable {
794    private final ImmutableList<Range<C>> ranges;
795
796    SerializedForm(ImmutableList<Range<C>> ranges) {
797      this.ranges = ranges;
798    }
799
800    Object readResolve() {
801      if (ranges.isEmpty()) {
802        return of();
803      } else if (ranges.equals(ImmutableList.of(Range.all()))) {
804        return all();
805      } else {
806        return new ImmutableRangeSet<C>(ranges);
807      }
808    }
809  }
810
811  Object writeReplace() {
812    return new SerializedForm<C>(ranges);
813  }
814}