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