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