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