Source code

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