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