| /* |
| * 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 com.google.common.annotations.Beta; |
| import com.google.common.annotations.GwtIncompatible; |
| 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.concurrent.LazyInit; |
| 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 org.checkerframework.checker.nullness.qual.MonotonicNonNull; |
| import org.checkerframework.checker.nullness.qual.Nullable; |
| |
| /** |
| * A {@link RangeSet} whose contents will never change, with many other important properties |
| * detailed at {@link ImmutableCollection}. |
| * |
| * @author Louis Wasserman |
| * @since 14.0 |
| */ |
| @Beta |
| @GwtIncompatible |
| 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. */ |
| @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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 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 short-hand 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; |
| } |
| |
| private transient @MonotonicNonNull 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 |
| 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 |
| 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(@Nullable 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(Object target) { |
| if (contains(target)) { |
| @SuppressWarnings("unchecked") // if it's contained, it's definitely a C |
| C c = (C) 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 |
| Object writeReplace() { |
| return new AsSetSerializedForm<C>(ranges, domain); |
| } |
| } |
| |
| 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); |
| } |
| } |
| } |
| |
| Object writeReplace() { |
| return new SerializedForm<C>(ranges); |
| } |
| } |
