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