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@GwtIncompatible
052@ElementTypesAreNonnullByDefault
053public final class ImmutableRangeSet<C extends Comparable> extends AbstractRangeSet<C>
054    implements Serializable {
055
056  private static final ImmutableRangeSet<Comparable<?>> EMPTY =
057      new ImmutableRangeSet<>(ImmutableList.<Range<Comparable<?>>>of());
058
059  private static final ImmutableRangeSet<Comparable<?>> ALL =
060      new ImmutableRangeSet<>(ImmutableList.of(Range.<Comparable<?>>all()));
061
062  /**
063   * Returns a {@code Collector} that accumulates the input elements into a new {@code
064   * ImmutableRangeSet}. As in {@link Builder}, overlapping ranges are not permitted and adjacent
065   * ranges will be merged.
066   */
067  @SuppressWarnings({"AndroidJdkLibsChecker", "Java7ApiChecker"})
068  @IgnoreJRERequirement // Users will use this only if they're already using streams.
069  static <E extends Comparable<? super E>>
070      Collector<Range<E>, ?, ImmutableRangeSet<E>> toImmutableRangeSet() {
071    return CollectCollectors.toImmutableRangeSet();
072  }
073
074  /**
075   * Returns an empty immutable range set.
076   *
077   * <p><b>Performance note:</b> the instance returned is a singleton.
078   */
079  @SuppressWarnings("unchecked")
080  public static <C extends Comparable> ImmutableRangeSet<C> of() {
081    return (ImmutableRangeSet<C>) EMPTY;
082  }
083
084  /**
085   * Returns an immutable range set containing the specified single range. If {@link Range#isEmpty()
086   * range.isEmpty()}, this is equivalent to {@link ImmutableRangeSet#of()}.
087   */
088  public static <C extends Comparable> ImmutableRangeSet<C> of(Range<C> range) {
089    checkNotNull(range);
090    if (range.isEmpty()) {
091      return of();
092    } else if (range.equals(Range.all())) {
093      return all();
094    } else {
095      return new ImmutableRangeSet<C>(ImmutableList.of(range));
096    }
097  }
098
099  /** Returns an immutable range set containing the single range {@link Range#all()}. */
100  @SuppressWarnings("unchecked")
101  static <C extends Comparable> ImmutableRangeSet<C> all() {
102    return (ImmutableRangeSet<C>) ALL;
103  }
104
105  /** Returns an immutable copy of the specified {@code RangeSet}. */
106  public static <C extends Comparable> ImmutableRangeSet<C> copyOf(RangeSet<C> rangeSet) {
107    checkNotNull(rangeSet);
108    if (rangeSet.isEmpty()) {
109      return of();
110    } else if (rangeSet.encloses(Range.<C>all())) {
111      return all();
112    }
113
114    if (rangeSet instanceof ImmutableRangeSet) {
115      ImmutableRangeSet<C> immutableRangeSet = (ImmutableRangeSet<C>) rangeSet;
116      if (!immutableRangeSet.isPartialView()) {
117        return immutableRangeSet;
118      }
119    }
120    return new ImmutableRangeSet<C>(ImmutableList.copyOf(rangeSet.asRanges()));
121  }
122
123  /**
124   * Returns an {@code ImmutableRangeSet} containing each of the specified disjoint ranges.
125   * Overlapping ranges and empty ranges are forbidden, though adjacent ranges are permitted and
126   * will be merged.
127   *
128   * @throws IllegalArgumentException if any ranges overlap or are empty
129   * @since 21.0
130   */
131  public static <C extends Comparable<?>> ImmutableRangeSet<C> copyOf(Iterable<Range<C>> ranges) {
132    return new ImmutableRangeSet.Builder<C>().addAll(ranges).build();
133  }
134
135  /**
136   * Returns an {@code ImmutableRangeSet} representing the union of the specified ranges.
137   *
138   * <p>This is the smallest {@code RangeSet} which encloses each of the specified ranges. Duplicate
139   * or connected ranges are permitted, and will be coalesced in the result.
140   *
141   * @since 21.0
142   */
143  public static <C extends Comparable<?>> ImmutableRangeSet<C> unionOf(Iterable<Range<C>> ranges) {
144    return copyOf(TreeRangeSet.create(ranges));
145  }
146
147  ImmutableRangeSet(ImmutableList<Range<C>> ranges) {
148    this.ranges = ranges;
149  }
150
151  private ImmutableRangeSet(ImmutableList<Range<C>> ranges, ImmutableRangeSet<C> complement) {
152    this.ranges = ranges;
153    this.complement = complement;
154  }
155
156  private final transient ImmutableList<Range<C>> ranges;
157
158  @Override
159  public boolean intersects(Range<C> otherRange) {
160    int ceilingIndex =
161        SortedLists.binarySearch(
162            ranges,
163            Range.<C>lowerBoundFn(),
164            otherRange.lowerBound,
165            Ordering.natural(),
166            ANY_PRESENT,
167            NEXT_HIGHER);
168    if (ceilingIndex < ranges.size()
169        && ranges.get(ceilingIndex).isConnected(otherRange)
170        && !ranges.get(ceilingIndex).intersection(otherRange).isEmpty()) {
171      return true;
172    }
173    return ceilingIndex > 0
174        && ranges.get(ceilingIndex - 1).isConnected(otherRange)
175        && !ranges.get(ceilingIndex - 1).intersection(otherRange).isEmpty();
176  }
177
178  @Override
179  public boolean encloses(Range<C> otherRange) {
180    int index =
181        SortedLists.binarySearch(
182            ranges,
183            Range.<C>lowerBoundFn(),
184            otherRange.lowerBound,
185            Ordering.natural(),
186            ANY_PRESENT,
187            NEXT_LOWER);
188    return index != -1 && ranges.get(index).encloses(otherRange);
189  }
190
191  @Override
192  @CheckForNull
193  public Range<C> rangeContaining(C value) {
194    int index =
195        SortedLists.binarySearch(
196            ranges,
197            Range.<C>lowerBoundFn(),
198            Cut.belowValue(value),
199            Ordering.natural(),
200            ANY_PRESENT,
201            NEXT_LOWER);
202    if (index != -1) {
203      Range<C> range = ranges.get(index);
204      return range.contains(value) ? range : null;
205    }
206    return null;
207  }
208
209  @Override
210  public Range<C> span() {
211    if (ranges.isEmpty()) {
212      throw new NoSuchElementException();
213    }
214    return Range.create(ranges.get(0).lowerBound, ranges.get(ranges.size() - 1).upperBound);
215  }
216
217  @Override
218  public boolean isEmpty() {
219    return ranges.isEmpty();
220  }
221
222  /**
223   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
224   *
225   * @throws UnsupportedOperationException always
226   * @deprecated Unsupported operation.
227   */
228  @Deprecated
229  @Override
230  @DoNotCall("Always throws UnsupportedOperationException")
231  public void add(Range<C> range) {
232    throw new UnsupportedOperationException();
233  }
234
235  /**
236   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
237   *
238   * @throws UnsupportedOperationException always
239   * @deprecated Unsupported operation.
240   */
241  @Deprecated
242  @Override
243  @DoNotCall("Always throws UnsupportedOperationException")
244  public void addAll(RangeSet<C> other) {
245    throw new UnsupportedOperationException();
246  }
247
248  /**
249   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
250   *
251   * @throws UnsupportedOperationException always
252   * @deprecated Unsupported operation.
253   */
254  @Deprecated
255  @Override
256  @DoNotCall("Always throws UnsupportedOperationException")
257  public void addAll(Iterable<Range<C>> other) {
258    throw new UnsupportedOperationException();
259  }
260
261  /**
262   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
263   *
264   * @throws UnsupportedOperationException always
265   * @deprecated Unsupported operation.
266   */
267  @Deprecated
268  @Override
269  @DoNotCall("Always throws UnsupportedOperationException")
270  public void remove(Range<C> range) {
271    throw new UnsupportedOperationException();
272  }
273
274  /**
275   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
276   *
277   * @throws UnsupportedOperationException always
278   * @deprecated Unsupported operation.
279   */
280  @Deprecated
281  @Override
282  @DoNotCall("Always throws UnsupportedOperationException")
283  public void removeAll(RangeSet<C> other) {
284    throw new UnsupportedOperationException();
285  }
286
287  /**
288   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
289   *
290   * @throws UnsupportedOperationException always
291   * @deprecated Unsupported operation.
292   */
293  @Deprecated
294  @Override
295  @DoNotCall("Always throws UnsupportedOperationException")
296  public void removeAll(Iterable<Range<C>> other) {
297    throw new UnsupportedOperationException();
298  }
299
300  @Override
301  public ImmutableSet<Range<C>> asRanges() {
302    if (ranges.isEmpty()) {
303      return ImmutableSet.of();
304    }
305    return new RegularImmutableSortedSet<>(ranges, Range.<C>rangeLexOrdering());
306  }
307
308  @Override
309  public ImmutableSet<Range<C>> asDescendingSetOfRanges() {
310    if (ranges.isEmpty()) {
311      return ImmutableSet.of();
312    }
313    return new RegularImmutableSortedSet<>(ranges.reverse(), Range.<C>rangeLexOrdering().reverse());
314  }
315
316  @LazyInit @CheckForNull private transient ImmutableRangeSet<C> complement;
317
318  private final class ComplementRanges extends ImmutableList<Range<C>> {
319    // True if the "positive" range set is empty or bounded below.
320    private final boolean positiveBoundedBelow;
321
322    // True if the "positive" range set is empty or bounded above.
323    private final boolean positiveBoundedAbove;
324
325    private final int size;
326
327    ComplementRanges() {
328      this.positiveBoundedBelow = ranges.get(0).hasLowerBound();
329      this.positiveBoundedAbove = Iterables.getLast(ranges).hasUpperBound();
330
331      int size = ranges.size() - 1;
332      if (positiveBoundedBelow) {
333        size++;
334      }
335      if (positiveBoundedAbove) {
336        size++;
337      }
338      this.size = size;
339    }
340
341    @Override
342    public int size() {
343      return size;
344    }
345
346    @Override
347    public Range<C> get(int index) {
348      checkElementIndex(index, size);
349
350      Cut<C> lowerBound;
351      if (positiveBoundedBelow) {
352        lowerBound = (index == 0) ? Cut.<C>belowAll() : ranges.get(index - 1).upperBound;
353      } else {
354        lowerBound = ranges.get(index).upperBound;
355      }
356
357      Cut<C> upperBound;
358      if (positiveBoundedAbove && index == size - 1) {
359        upperBound = Cut.<C>aboveAll();
360      } else {
361        upperBound = ranges.get(index + (positiveBoundedBelow ? 0 : 1)).lowerBound;
362      }
363
364      return Range.create(lowerBound, upperBound);
365    }
366
367    @Override
368    boolean isPartialView() {
369      return true;
370    }
371
372    // redeclare to help optimizers with b/310253115
373    @SuppressWarnings("RedundantOverride")
374    @Override
375    @J2ktIncompatible // serialization
376    Object writeReplace() {
377      return super.writeReplace();
378    }
379  }
380
381  @Override
382  public ImmutableRangeSet<C> complement() {
383    ImmutableRangeSet<C> result = complement;
384    if (result != null) {
385      return result;
386    } else if (ranges.isEmpty()) {
387      return complement = all();
388    } else if (ranges.size() == 1 && ranges.get(0).equals(Range.all())) {
389      return complement = of();
390    } else {
391      ImmutableList<Range<C>> complementRanges = new ComplementRanges();
392      result = complement = new ImmutableRangeSet<C>(complementRanges, this);
393    }
394    return result;
395  }
396
397  /**
398   * Returns a new range set consisting of the union of this range set and {@code other}.
399   *
400   * <p>This is essentially the same as {@code TreeRangeSet.create(this).addAll(other)} except it
401   * returns an {@code ImmutableRangeSet}.
402   *
403   * @since 21.0
404   */
405  public ImmutableRangeSet<C> union(RangeSet<C> other) {
406    return unionOf(Iterables.concat(asRanges(), other.asRanges()));
407  }
408
409  /**
410   * Returns a new range set consisting of the intersection of this range set and {@code other}.
411   *
412   * <p>This is essentially the same as {@code
413   * TreeRangeSet.create(this).removeAll(other.complement())} except it returns an {@code
414   * ImmutableRangeSet}.
415   *
416   * @since 21.0
417   */
418  public ImmutableRangeSet<C> intersection(RangeSet<C> other) {
419    RangeSet<C> copy = TreeRangeSet.create(this);
420    copy.removeAll(other.complement());
421    return copyOf(copy);
422  }
423
424  /**
425   * Returns a new range set consisting of the difference of this range set and {@code other}.
426   *
427   * <p>This is essentially the same as {@code TreeRangeSet.create(this).removeAll(other)} except it
428   * returns an {@code ImmutableRangeSet}.
429   *
430   * @since 21.0
431   */
432  public ImmutableRangeSet<C> difference(RangeSet<C> other) {
433    RangeSet<C> copy = TreeRangeSet.create(this);
434    copy.removeAll(other);
435    return copyOf(copy);
436  }
437
438  /**
439   * Returns a list containing the nonempty intersections of {@code range} with the ranges in this
440   * range set.
441   */
442  private ImmutableList<Range<C>> intersectRanges(final Range<C> range) {
443    if (ranges.isEmpty() || range.isEmpty()) {
444      return ImmutableList.of();
445    } else if (range.encloses(span())) {
446      return ranges;
447    }
448
449    final int fromIndex;
450    if (range.hasLowerBound()) {
451      fromIndex =
452          SortedLists.binarySearch(
453              ranges,
454              Range.<C>upperBoundFn(),
455              range.lowerBound,
456              KeyPresentBehavior.FIRST_AFTER,
457              KeyAbsentBehavior.NEXT_HIGHER);
458    } else {
459      fromIndex = 0;
460    }
461
462    int toIndex;
463    if (range.hasUpperBound()) {
464      toIndex =
465          SortedLists.binarySearch(
466              ranges,
467              Range.<C>lowerBoundFn(),
468              range.upperBound,
469              KeyPresentBehavior.FIRST_PRESENT,
470              KeyAbsentBehavior.NEXT_HIGHER);
471    } else {
472      toIndex = ranges.size();
473    }
474    final int length = toIndex - fromIndex;
475    if (length == 0) {
476      return ImmutableList.of();
477    } else {
478      return new ImmutableList<Range<C>>() {
479        @Override
480        public int size() {
481          return length;
482        }
483
484        @Override
485        public Range<C> get(int index) {
486          checkElementIndex(index, length);
487          if (index == 0 || index == length - 1) {
488            return ranges.get(index + fromIndex).intersection(range);
489          } else {
490            return ranges.get(index + fromIndex);
491          }
492        }
493
494        @Override
495        boolean isPartialView() {
496          return true;
497        }
498
499        // redeclare to help optimizers with b/310253115
500        @SuppressWarnings("RedundantOverride")
501        @Override
502        @J2ktIncompatible // serialization
503        @GwtIncompatible // serialization
504        Object writeReplace() {
505          return super.writeReplace();
506        }
507      };
508    }
509  }
510
511  /** Returns a view of the intersection of this range set with the given range. */
512  @Override
513  public ImmutableRangeSet<C> subRangeSet(Range<C> range) {
514    if (!isEmpty()) {
515      Range<C> span = span();
516      if (range.encloses(span)) {
517        return this;
518      } else if (range.isConnected(span)) {
519        return new ImmutableRangeSet<C>(intersectRanges(range));
520      }
521    }
522    return of();
523  }
524
525  /**
526   * Returns an {@link ImmutableSortedSet} containing the same values in the given domain
527   * {@linkplain RangeSet#contains contained} by this range set.
528   *
529   * <p><b>Note:</b> {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For
530   * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty
531   * ranges {@code [3..3)} and {@code [4..4)}.
532   *
533   * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet} view of a large
534   * range set (such as {@code ImmutableRangeSet.of(Range.greaterThan(0))}). Certain operations on
535   * such a set can be performed efficiently, but others (such as {@link Set#hashCode} or {@link
536   * Collections#frequency}) can cause major performance problems.
537   *
538   * <p>The returned set's {@link Object#toString} method returns a shorthand form of the set's
539   * contents, such as {@code "[1..100]}"}.
540   *
541   * @throws IllegalArgumentException if neither this range nor the domain has a lower bound, or if
542   *     neither has an upper bound
543   */
544  public ImmutableSortedSet<C> asSet(DiscreteDomain<C> domain) {
545    checkNotNull(domain);
546    if (isEmpty()) {
547      return ImmutableSortedSet.of();
548    }
549    Range<C> span = span().canonical(domain);
550    if (!span.hasLowerBound()) {
551      // according to the spec of canonical, neither this ImmutableRangeSet nor
552      // the range have a lower bound
553      throw new IllegalArgumentException(
554          "Neither the DiscreteDomain nor this range set are bounded below");
555    } else if (!span.hasUpperBound()) {
556      try {
557        domain.maxValue();
558      } catch (NoSuchElementException e) {
559        throw new IllegalArgumentException(
560            "Neither the DiscreteDomain nor this range set are bounded above");
561      }
562    }
563
564    return new AsSet(domain);
565  }
566
567  private final class AsSet extends ImmutableSortedSet<C> {
568    private final DiscreteDomain<C> domain;
569
570    AsSet(DiscreteDomain<C> domain) {
571      super(Ordering.natural());
572      this.domain = domain;
573    }
574
575    @LazyInit @CheckForNull private transient Integer size;
576
577    @Override
578    public int size() {
579      // racy single-check idiom
580      Integer result = size;
581      if (result == null) {
582        long total = 0;
583        for (Range<C> range : ranges) {
584          total += ContiguousSet.create(range, domain).size();
585          if (total >= Integer.MAX_VALUE) {
586            break;
587          }
588        }
589        result = size = Ints.saturatedCast(total);
590      }
591      return result.intValue();
592    }
593
594    @Override
595    public UnmodifiableIterator<C> iterator() {
596      return new AbstractIterator<C>() {
597        final Iterator<Range<C>> rangeItr = ranges.iterator();
598        Iterator<C> elemItr = Iterators.emptyIterator();
599
600        @Override
601        @CheckForNull
602        protected C computeNext() {
603          while (!elemItr.hasNext()) {
604            if (rangeItr.hasNext()) {
605              elemItr = ContiguousSet.create(rangeItr.next(), domain).iterator();
606            } else {
607              return endOfData();
608            }
609          }
610          return elemItr.next();
611        }
612      };
613    }
614
615    @Override
616    @GwtIncompatible("NavigableSet")
617    public UnmodifiableIterator<C> descendingIterator() {
618      return new AbstractIterator<C>() {
619        final Iterator<Range<C>> rangeItr = ranges.reverse().iterator();
620        Iterator<C> elemItr = Iterators.emptyIterator();
621
622        @Override
623        @CheckForNull
624        protected 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(@CheckForNull 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(@CheckForNull 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<C>(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<C>();
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      Collections.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
840          && Iterables.getOnlyElement(mergedRanges).equals(Range.all())) {
841        return all();
842      } else {
843        return new ImmutableRangeSet<C>(mergedRanges);
844      }
845    }
846  }
847
848  private static final class SerializedForm<C extends Comparable> implements Serializable {
849    private final ImmutableList<Range<C>> ranges;
850
851    SerializedForm(ImmutableList<Range<C>> ranges) {
852      this.ranges = ranges;
853    }
854
855    Object readResolve() {
856      if (ranges.isEmpty()) {
857        return of();
858      } else if (ranges.equals(ImmutableList.of(Range.all()))) {
859        return all();
860      } else {
861        return new ImmutableRangeSet<C>(ranges);
862      }
863    }
864  }
865
866  @J2ktIncompatible // java.io.ObjectInputStream
867  Object writeReplace() {
868    return new SerializedForm<C>(ranges);
869  }
870
871  @J2ktIncompatible // java.io.ObjectInputStream
872  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
873    throw new InvalidObjectException("Use SerializedForm");
874  }
875}