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