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