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