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