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