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