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