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