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