path: root/guava/src/com/google/common/collect/ImmutableRangeSet.java

/*
 * Copyright (C) 2012 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkElementIndex;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER;
import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER;
import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT;
import static java.util.Objects.requireNonNull;

import com.google.common.annotations.GwtIncompatible;
import com.google.common.annotations.J2ktIncompatible;
import com.google.common.collect.SortedLists.KeyAbsentBehavior;
import com.google.common.collect.SortedLists.KeyPresentBehavior;
import com.google.common.primitives.Ints;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.errorprone.annotations.DoNotCall;
import com.google.errorprone.annotations.concurrent.LazyInit;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.Serializable;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.stream.Collector;
import javax.annotation.CheckForNull;

/**
 * A {@link RangeSet} whose contents will never change, with many other important properties
 * detailed at {@link ImmutableCollection}.
 *
 * @author Louis Wasserman
 * @since 14.0
 */
@GwtIncompatible
@ElementTypesAreNonnullByDefault
public final class ImmutableRangeSet<C extends Comparable> extends AbstractRangeSet<C>
    implements Serializable {

  private static final ImmutableRangeSet<Comparable<?>> EMPTY =
      new ImmutableRangeSet<>(ImmutableList.<Range<Comparable<?>>>of());

  private static final ImmutableRangeSet<Comparable<?>> ALL =
      new ImmutableRangeSet<>(ImmutableList.of(Range.<Comparable<?>>all()));

  /**
   * Returns a {@code Collector} that accumulates the input elements into a new {@code
   * ImmutableRangeSet}. As in {@link Builder}, overlapping ranges are not permitted and adjacent
   * ranges will be merged.
   *
   * @since 23.1
   */
  public static <E extends Comparable<? super E>>
      Collector<Range<E>, ?, ImmutableRangeSet<E>> toImmutableRangeSet() {
    return CollectCollectors.toImmutableRangeSet();
  }

  /**
   * Returns an empty immutable range set.
   *
   * <p><b>Performance note:</b> the instance returned is a singleton.
   */
  @SuppressWarnings("unchecked")
  public static <C extends Comparable> ImmutableRangeSet<C> of() {
    return (ImmutableRangeSet<C>) EMPTY;
  }

  /**
   * Returns an immutable range set containing the specified single range. If {@link Range#isEmpty()
   * range.isEmpty()}, this is equivalent to {@link ImmutableRangeSet#of()}.
   */
  public static <C extends Comparable> ImmutableRangeSet<C> of(Range<C> range) {
    checkNotNull(range);
    if (range.isEmpty()) {
      return of();
    } else if (range.equals(Range.all())) {
      return all();
    } else {
      return new ImmutableRangeSet<C>(ImmutableList.of(range));
    }
  }

  /** Returns an immutable range set containing the single range {@link Range#all()}. */
  @SuppressWarnings("unchecked")
  static <C extends Comparable> ImmutableRangeSet<C> all() {
    return (ImmutableRangeSet<C>) ALL;
  }

  /** Returns an immutable copy of the specified {@code RangeSet}. */
  public static <C extends Comparable> ImmutableRangeSet<C> copyOf(RangeSet<C> rangeSet) {
    checkNotNull(rangeSet);
    if (rangeSet.isEmpty()) {
      return of();
    } else if (rangeSet.encloses(Range.<C>all())) {
      return all();
    }

    if (rangeSet instanceof ImmutableRangeSet) {
      ImmutableRangeSet<C> immutableRangeSet = (ImmutableRangeSet<C>) rangeSet;
      if (!immutableRangeSet.isPartialView()) {
        return immutableRangeSet;
      }
    }
    return new ImmutableRangeSet<C>(ImmutableList.copyOf(rangeSet.asRanges()));
  }

  /**
   * Returns an {@code ImmutableRangeSet} containing each of the specified disjoint ranges.
   * Overlapping ranges and empty ranges are forbidden, though adjacent ranges are permitted and
   * will be merged.
   *
   * @throws IllegalArgumentException if any ranges overlap or are empty
   * @since 21.0
   */
  public static <C extends Comparable<?>> ImmutableRangeSet<C> copyOf(Iterable<Range<C>> ranges) {
    return new ImmutableRangeSet.Builder<C>().addAll(ranges).build();
  }

  /**
   * Returns an {@code ImmutableRangeSet} representing the union of the specified ranges.
   *
   * <p>This is the smallest {@code RangeSet} which encloses each of the specified ranges. Duplicate
   * or connected ranges are permitted, and will be coalesced in the result.
   *
   * @since 21.0
   */
  public static <C extends Comparable<?>> ImmutableRangeSet<C> unionOf(Iterable<Range<C>> ranges) {
    return copyOf(TreeRangeSet.create(ranges));
  }

  ImmutableRangeSet(ImmutableList<Range<C>> ranges) {
    this.ranges = ranges;
  }

  private ImmutableRangeSet(ImmutableList<Range<C>> ranges, ImmutableRangeSet<C> complement) {
    this.ranges = ranges;
    this.complement = complement;
  }

  private final transient ImmutableList<Range<C>> ranges;

  @Override
  public boolean intersects(Range<C> otherRange) {
    int ceilingIndex =
        SortedLists.binarySearch(
            ranges,
            Range.<C>lowerBoundFn(),
            otherRange.lowerBound,
            Ordering.natural(),
            ANY_PRESENT,
            NEXT_HIGHER);
    if (ceilingIndex < ranges.size()
        && ranges.get(ceilingIndex).isConnected(otherRange)
        && !ranges.get(ceilingIndex).intersection(otherRange).isEmpty()) {
      return true;
    }
    return ceilingIndex > 0
        && ranges.get(ceilingIndex - 1).isConnected(otherRange)
        && !ranges.get(ceilingIndex - 1).intersection(otherRange).isEmpty();
  }

  @Override
  public boolean encloses(Range<C> otherRange) {
    int index =
        SortedLists.binarySearch(
            ranges,
            Range.<C>lowerBoundFn(),
            otherRange.lowerBound,
            Ordering.natural(),
            ANY_PRESENT,
            NEXT_LOWER);
    return index != -1 && ranges.get(index).encloses(otherRange);
  }

  @Override
  @CheckForNull
  public Range<C> rangeContaining(C value) {
    int index =
        SortedLists.binarySearch(
            ranges,
            Range.<C>lowerBoundFn(),
            Cut.belowValue(value),
            Ordering.natural(),
            ANY_PRESENT,
            NEXT_LOWER);
    if (index != -1) {
      Range<C> range = ranges.get(index);
      return range.contains(value) ? range : null;
    }
    return null;
  }

  @Override
  public Range<C> span() {
    if (ranges.isEmpty()) {
      throw new NoSuchElementException();
    }
    return Range.create(ranges.get(0).lowerBound, ranges.get(ranges.size() - 1).upperBound);
  }

  @Override
  public boolean isEmpty() {
    return ranges.isEmpty();
  }

  /**
   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @Deprecated
  @Override
  @DoNotCall("Always throws UnsupportedOperationException")
  public void add(Range<C> range) {
    throw new UnsupportedOperationException();
  }

  /**
   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @Deprecated
  @Override
  @DoNotCall("Always throws UnsupportedOperationException")
  public void addAll(RangeSet<C> other) {
    throw new UnsupportedOperationException();
  }

  /**
   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @Deprecated
  @Override
  @DoNotCall("Always throws UnsupportedOperationException")
  public void addAll(Iterable<Range<C>> other) {
    throw new UnsupportedOperationException();
  }

  /**
   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @Deprecated
  @Override
  @DoNotCall("Always throws UnsupportedOperationException")
  public void remove(Range<C> range) {
    throw new UnsupportedOperationException();
  }

  /**
   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @Deprecated
  @Override
  @DoNotCall("Always throws UnsupportedOperationException")
  public void removeAll(RangeSet<C> other) {
    throw new UnsupportedOperationException();
  }

  /**
   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @Deprecated
  @Override
  @DoNotCall("Always throws UnsupportedOperationException")
  public void removeAll(Iterable<Range<C>> other) {
    throw new UnsupportedOperationException();
  }

  @Override
  public ImmutableSet<Range<C>> asRanges() {
    if (ranges.isEmpty()) {
      return ImmutableSet.of();
    }
    return new RegularImmutableSortedSet<>(ranges, Range.<C>rangeLexOrdering());
  }

  @Override
  public ImmutableSet<Range<C>> asDescendingSetOfRanges() {
    if (ranges.isEmpty()) {
      return ImmutableSet.of();
    }
    return new RegularImmutableSortedSet<>(ranges.reverse(), Range.<C>rangeLexOrdering().reverse());
  }

  @LazyInit @CheckForNull private transient ImmutableRangeSet<C> complement;

  private final class ComplementRanges extends ImmutableList<Range<C>> {
    // True if the "positive" range set is empty or bounded below.
    private final boolean positiveBoundedBelow;

    // True if the "positive" range set is empty or bounded above.
    private final boolean positiveBoundedAbove;

    private final int size;

    ComplementRanges() {
      this.positiveBoundedBelow = ranges.get(0).hasLowerBound();
      this.positiveBoundedAbove = Iterables.getLast(ranges).hasUpperBound();

      int size = ranges.size() - 1;
      if (positiveBoundedBelow) {
        size++;
      }
      if (positiveBoundedAbove) {
        size++;
      }
      this.size = size;
    }

    @Override
    public int size() {
      return size;
    }

    @Override
    public Range<C> get(int index) {
      checkElementIndex(index, size);

      Cut<C> lowerBound;
      if (positiveBoundedBelow) {
        lowerBound = (index == 0) ? Cut.<C>belowAll() : ranges.get(index - 1).upperBound;
      } else {
        lowerBound = ranges.get(index).upperBound;
      }

      Cut<C> upperBound;
      if (positiveBoundedAbove && index == size - 1) {
        upperBound = Cut.<C>aboveAll();
      } else {
        upperBound = ranges.get(index + (positiveBoundedBelow ? 0 : 1)).lowerBound;
      }

      return Range.create(lowerBound, upperBound);
    }

    @Override
    boolean isPartialView() {
      return true;
    }
  }

  @Override
  public ImmutableRangeSet<C> complement() {
    ImmutableRangeSet<C> result = complement;
    if (result != null) {
      return result;
    } else if (ranges.isEmpty()) {
      return complement = all();
    } else if (ranges.size() == 1 && ranges.get(0).equals(Range.all())) {
      return complement = of();
    } else {
      ImmutableList<Range<C>> complementRanges = new ComplementRanges();
      result = complement = new ImmutableRangeSet<C>(complementRanges, this);
    }
    return result;
  }

  /**
   * Returns a new range set consisting of the union of this range set and {@code other}.
   *
   * <p>This is essentially the same as {@code TreeRangeSet.create(this).addAll(other)} except it
   * returns an {@code ImmutableRangeSet}.
   *
   * @since 21.0
   */
  public ImmutableRangeSet<C> union(RangeSet<C> other) {
    return unionOf(Iterables.concat(asRanges(), other.asRanges()));
  }

  /**
   * Returns a new range set consisting of the intersection of this range set and {@code other}.
   *
   * <p>This is essentially the same as {@code
   * TreeRangeSet.create(this).removeAll(other.complement())} except it returns an {@code
   * ImmutableRangeSet}.
   *
   * @since 21.0
   */
  public ImmutableRangeSet<C> intersection(RangeSet<C> other) {
    RangeSet<C> copy = TreeRangeSet.create(this);
    copy.removeAll(other.complement());
    return copyOf(copy);
  }

  /**
   * Returns a new range set consisting of the difference of this range set and {@code other}.
   *
   * <p>This is essentially the same as {@code TreeRangeSet.create(this).removeAll(other)} except it
   * returns an {@code ImmutableRangeSet}.
   *
   * @since 21.0
   */
  public ImmutableRangeSet<C> difference(RangeSet<C> other) {
    RangeSet<C> copy = TreeRangeSet.create(this);
    copy.removeAll(other);
    return copyOf(copy);
  }

  /**
   * Returns a list containing the nonempty intersections of {@code range} with the ranges in this
   * range set.
   */
  private ImmutableList<Range<C>> intersectRanges(final Range<C> range) {
    if (ranges.isEmpty() || range.isEmpty()) {
      return ImmutableList.of();
    } else if (range.encloses(span())) {
      return ranges;
    }

    final int fromIndex;
    if (range.hasLowerBound()) {
      fromIndex =
          SortedLists.binarySearch(
              ranges,
              Range.<C>upperBoundFn(),
              range.lowerBound,
              KeyPresentBehavior.FIRST_AFTER,
              KeyAbsentBehavior.NEXT_HIGHER);
    } else {
      fromIndex = 0;
    }

    int toIndex;
    if (range.hasUpperBound()) {
      toIndex =
          SortedLists.binarySearch(
              ranges,
              Range.<C>lowerBoundFn(),
              range.upperBound,
              KeyPresentBehavior.FIRST_PRESENT,
              KeyAbsentBehavior.NEXT_HIGHER);
    } else {
      toIndex = ranges.size();
    }
    final int length = toIndex - fromIndex;
    if (length == 0) {
      return ImmutableList.of();
    } else {
      return new ImmutableList<Range<C>>() {
        @Override
        public int size() {
          return length;
        }

        @Override
        public Range<C> get(int index) {
          checkElementIndex(index, length);
          if (index == 0 || index == length - 1) {
            return ranges.get(index + fromIndex).intersection(range);
          } else {
            return ranges.get(index + fromIndex);
          }
        }

        @Override
        boolean isPartialView() {
          return true;
        }
      };
    }
  }

  /** Returns a view of the intersection of this range set with the given range. */
  @Override
  public ImmutableRangeSet<C> subRangeSet(Range<C> range) {
    if (!isEmpty()) {
      Range<C> span = span();
      if (range.encloses(span)) {
        return this;
      } else if (range.isConnected(span)) {
        return new ImmutableRangeSet<C>(intersectRanges(range));
      }
    }
    return of();
  }

  /**
   * Returns an {@link ImmutableSortedSet} containing the same values in the given domain
   * {@linkplain RangeSet#contains contained} by this range set.
   *
   * <p><b>Note:</b> {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For
   * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty
   * ranges {@code [3..3)} and {@code [4..4)}.
   *
   * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet} view of a large
   * range set (such as {@code ImmutableRangeSet.of(Range.greaterThan(0))}). Certain operations on
   * such a set can be performed efficiently, but others (such as {@link Set#hashCode} or {@link
   * Collections#frequency}) can cause major performance problems.
   *
   * <p>The returned set's {@link Object#toString} method returns a shorthand form of the set's
   * contents, such as {@code "[1..100]}"}.
   *
   * @throws IllegalArgumentException if neither this range nor the domain has a lower bound, or if
   *     neither has an upper bound
   */
  public ImmutableSortedSet<C> asSet(DiscreteDomain<C> domain) {
    checkNotNull(domain);
    if (isEmpty()) {
      return ImmutableSortedSet.of();
    }
    Range<C> span = span().canonical(domain);
    if (!span.hasLowerBound()) {
      // according to the spec of canonical, neither this ImmutableRangeSet nor
      // the range have a lower bound
      throw new IllegalArgumentException(
          "Neither the DiscreteDomain nor this range set are bounded below");
    } else if (!span.hasUpperBound()) {
      try {
        domain.maxValue();
      } catch (NoSuchElementException e) {
        throw new IllegalArgumentException(
            "Neither the DiscreteDomain nor this range set are bounded above");
      }
    }

    return new AsSet(domain);
  }

  private final class AsSet extends ImmutableSortedSet<C> {
    private final DiscreteDomain<C> domain;

    AsSet(DiscreteDomain<C> domain) {
      super(Ordering.natural());
      this.domain = domain;
    }

    @LazyInit @CheckForNull private transient Integer size;

    @Override
    public int size() {
      // racy single-check idiom
      Integer result = size;
      if (result == null) {
        long total = 0;
        for (Range<C> range : ranges) {
          total += ContiguousSet.create(range, domain).size();
          if (total >= Integer.MAX_VALUE) {
            break;
          }
        }
        result = size = Ints.saturatedCast(total);
      }
      return result.intValue();
    }

    @Override
    public UnmodifiableIterator<C> iterator() {
      return new AbstractIterator<C>() {
        final Iterator<Range<C>> rangeItr = ranges.iterator();
        Iterator<C> elemItr = Iterators.emptyIterator();

        @Override
        @CheckForNull
        protected C computeNext() {
          while (!elemItr.hasNext()) {
            if (rangeItr.hasNext()) {
              elemItr = ContiguousSet.create(rangeItr.next(), domain).iterator();
            } else {
              return endOfData();
            }
          }
          return elemItr.next();
        }
      };
    }

    @Override
    @GwtIncompatible("NavigableSet")
    public UnmodifiableIterator<C> descendingIterator() {
      return new AbstractIterator<C>() {
        final Iterator<Range<C>> rangeItr = ranges.reverse().iterator();
        Iterator<C> elemItr = Iterators.emptyIterator();

        @Override
        @CheckForNull
        protected C computeNext() {
          while (!elemItr.hasNext()) {
            if (rangeItr.hasNext()) {
              elemItr = ContiguousSet.create(rangeItr.next(), domain).descendingIterator();
            } else {
              return endOfData();
            }
          }
          return elemItr.next();
        }
      };
    }

    ImmutableSortedSet<C> subSet(Range<C> range) {
      return subRangeSet(range).asSet(domain);
    }

    @Override
    ImmutableSortedSet<C> headSetImpl(C toElement, boolean inclusive) {
      return subSet(Range.upTo(toElement, BoundType.forBoolean(inclusive)));
    }

    @Override
    ImmutableSortedSet<C> subSetImpl(
        C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) {
      if (!fromInclusive && !toInclusive && Range.compareOrThrow(fromElement, toElement) == 0) {
        return ImmutableSortedSet.of();
      }
      return subSet(
          Range.range(
              fromElement, BoundType.forBoolean(fromInclusive),
              toElement, BoundType.forBoolean(toInclusive)));
    }

    @Override
    ImmutableSortedSet<C> tailSetImpl(C fromElement, boolean inclusive) {
      return subSet(Range.downTo(fromElement, BoundType.forBoolean(inclusive)));
    }

    @Override
    public boolean contains(@CheckForNull Object o) {
      if (o == null) {
        return false;
      }
      try {
        @SuppressWarnings("unchecked") // we catch CCE's
        C c = (C) o;
        return ImmutableRangeSet.this.contains(c);
      } catch (ClassCastException e) {
        return false;
      }
    }

    @Override
    int indexOf(@CheckForNull Object target) {
      if (contains(target)) {
        @SuppressWarnings("unchecked") // if it's contained, it's definitely a C
        C c = (C) requireNonNull(target);
        long total = 0;
        for (Range<C> range : ranges) {
          if (range.contains(c)) {
            return Ints.saturatedCast(total + ContiguousSet.create(range, domain).indexOf(c));
          } else {
            total += ContiguousSet.create(range, domain).size();
          }
        }
        throw new AssertionError("impossible");
      }
      return -1;
    }

    @Override
    ImmutableSortedSet<C> createDescendingSet() {
      return new DescendingImmutableSortedSet<C>(this);
    }

    @Override
    boolean isPartialView() {
      return ranges.isPartialView();
    }

    @Override
    public String toString() {
      return ranges.toString();
    }

    @Override
    @J2ktIncompatible // serialization
    Object writeReplace() {
      return new AsSetSerializedForm<C>(ranges, domain);
    }

    @J2ktIncompatible // java.io.ObjectInputStream
    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
      throw new InvalidObjectException("Use SerializedForm");
    }
  }

  private static class AsSetSerializedForm<C extends Comparable> implements Serializable {
    private final ImmutableList<Range<C>> ranges;
    private final DiscreteDomain<C> domain;

    AsSetSerializedForm(ImmutableList<Range<C>> ranges, DiscreteDomain<C> domain) {
      this.ranges = ranges;
      this.domain = domain;
    }

    Object readResolve() {
      return new ImmutableRangeSet<C>(ranges).asSet(domain);
    }
  }

  /**
   * Returns {@code true} if this immutable range set's implementation contains references to
   * user-created objects that aren't accessible via this range set's methods. This is generally
   * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid
   * memory leaks.
   */
  boolean isPartialView() {
    return ranges.isPartialView();
  }

  /** Returns a new builder for an immutable range set. */
  public static <C extends Comparable<?>> Builder<C> builder() {
    return new Builder<C>();
  }

  /**
   * A builder for immutable range sets.
   *
   * @since 14.0
   */
  public static class Builder<C extends Comparable<?>> {
    private final List<Range<C>> ranges;

    public Builder() {
      this.ranges = Lists.newArrayList();
    }

    // TODO(lowasser): consider adding union, in addition to add, that does allow overlap

    /**
     * Add the specified range to this builder. Adjacent ranges are permitted and will be merged,
     * but overlapping ranges will cause an exception when {@link #build()} is called.
     *
     * @throws IllegalArgumentException if {@code range} is empty
     */
    @CanIgnoreReturnValue
    public Builder<C> add(Range<C> range) {
      checkArgument(!range.isEmpty(), "range must not be empty, but was %s", range);
      ranges.add(range);
      return this;
    }

    /**
     * Add all ranges from the specified range set to this builder. Adjacent ranges are permitted
     * and will be merged, but overlapping ranges will cause an exception when {@link #build()} is
     * called.
     */
    @CanIgnoreReturnValue
    public Builder<C> addAll(RangeSet<C> ranges) {
      return addAll(ranges.asRanges());
    }

    /**
     * Add all of the specified ranges to this builder. Adjacent ranges are permitted and will be
     * merged, but overlapping ranges will cause an exception when {@link #build()} is called.
     *
     * @throws IllegalArgumentException if any inserted ranges are empty
     * @since 21.0
     */
    @CanIgnoreReturnValue
    public Builder<C> addAll(Iterable<Range<C>> ranges) {
      for (Range<C> range : ranges) {
        add(range);
      }
      return this;
    }

    @CanIgnoreReturnValue
    Builder<C> combine(Builder<C> builder) {
      addAll(builder.ranges);
      return this;
    }

    /**
     * Returns an {@code ImmutableRangeSet} containing the ranges added to this builder.
     *
     * @throws IllegalArgumentException if any input ranges have nonempty overlap
     */
    public ImmutableRangeSet<C> build() {
      ImmutableList.Builder<Range<C>> mergedRangesBuilder =
          new ImmutableList.Builder<>(ranges.size());
      Collections.sort(ranges, Range.<C>rangeLexOrdering());
      PeekingIterator<Range<C>> peekingItr = Iterators.peekingIterator(ranges.iterator());
      while (peekingItr.hasNext()) {
        Range<C> range = peekingItr.next();
        while (peekingItr.hasNext()) {
          Range<C> nextRange = peekingItr.peek();
          if (range.isConnected(nextRange)) {
            checkArgument(
                range.intersection(nextRange).isEmpty(),
                "Overlapping ranges not permitted but found %s overlapping %s",
                range,
                nextRange);
            range = range.span(peekingItr.next());
          } else {
            break;
          }
        }
        mergedRangesBuilder.add(range);
      }
      ImmutableList<Range<C>> mergedRanges = mergedRangesBuilder.build();
      if (mergedRanges.isEmpty()) {
        return of();
      } else if (mergedRanges.size() == 1
          && Iterables.getOnlyElement(mergedRanges).equals(Range.all())) {
        return all();
      } else {
        return new ImmutableRangeSet<C>(mergedRanges);
      }
    }
  }

  private static final class SerializedForm<C extends Comparable> implements Serializable {
    private final ImmutableList<Range<C>> ranges;

    SerializedForm(ImmutableList<Range<C>> ranges) {
      this.ranges = ranges;
    }

    Object readResolve() {
      if (ranges.isEmpty()) {
        return of();
      } else if (ranges.equals(ImmutableList.of(Range.all()))) {
        return all();
      } else {
        return new ImmutableRangeSet<C>(ranges);
      }
    }
  }

  @J2ktIncompatible // java.io.ObjectInputStream
  Object writeReplace() {
    return new SerializedForm<C>(ranges);
  }

  @J2ktIncompatible // java.io.ObjectInputStream
  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
    throw new InvalidObjectException("Use SerializedForm");
  }
}