/*
* 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_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 java.io.
Serializable;
import java.util.
Collections;
import java.util.
Iterator;
import java.util.
NoSuchElementException;
import java.util.
Set;
import javax.annotation.
Nullable;
/**
* An efficient immutable implementation of a {@link RangeSet}.
*
* @author Louis Wasserman
* @since 14.0
*/
@
Beta
public final class
ImmutableRangeSet<C extends
Comparable> extends
AbstractRangeSet<C>
implements
Serializable {
private static final
ImmutableRangeSet<
Comparable<?>>
EMPTY =
new
ImmutableRangeSet<
Comparable<?>>(
ImmutableList.<
Range<
Comparable<?>>>
of());
private static final
ImmutableRangeSet<
Comparable<?>>
ALL =
new
ImmutableRangeSet<
Comparable<?>>(
ImmutableList.
of(
Range.<
Comparable<?>>
all()));
/**
* 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 single range {@link Range#all()}.
*/
@
SuppressWarnings("unchecked")
static <C extends
Comparable>
ImmutableRangeSet<C>
all() {
return (
ImmutableRangeSet<C>)
ALL;
}
/**
* 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 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()));
}
ImmutableRangeSet(
ImmutableList<
Range<C>>
ranges) {
this.
ranges =
ranges;
}
private
ImmutableRangeSet(
ImmutableList<
Range<C>>
ranges,
ImmutableRangeSet<C>
complement) {
this.
ranges =
ranges;
this.
complement =
complement;
}
private transient final
ImmutableList<
Range<C>>
ranges;
@
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();
}
@
Override
public void
add(
Range<C>
range) {
throw new
UnsupportedOperationException();
}
@
Override
public void
addAll(
RangeSet<C>
other) {
throw new
UnsupportedOperationException();
}
@
Override
public void
remove(
Range<C>
range) {
throw new
UnsupportedOperationException();
}
@
Override
public void
removeAll(
RangeSet<C>
other) {
throw new
UnsupportedOperationException();
}
@
Override
public
ImmutableSet<
Range<C>>
asRanges() {
if (
ranges.
isEmpty()) {
return
ImmutableSet.
of();
}
return new
RegularImmutableSortedSet<
Range<C>>(
ranges,
Range.
RANGE_LEX_ORDERING);
}
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 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
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
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.
*/
public static class
Builder<C extends
Comparable<?>> {
private final
RangeSet<C>
rangeSet;
public
Builder() {
this.
rangeSet =
TreeRangeSet.
create();
}
/**
* Add the specified range to this builder. Adjacent/abutting ranges are permitted, but
* empty ranges, or ranges with nonempty overlap, are forbidden.
*
* @throws IllegalArgumentException if {@code range} is empty or has nonempty intersection with
* any ranges already added to the builder
*/
public
Builder<C>
add(
Range<C>
range) {
if (
range.
isEmpty()) {
throw new
IllegalArgumentException("range must not be empty, but was " +
range);
} else if (!
rangeSet.
complement().
encloses(
range)) {
for (
Range<C>
currentRange :
rangeSet.
asRanges()) {
checkArgument(
!
currentRange.
isConnected(
range) ||
currentRange.
intersection(
range).
isEmpty(),
"Ranges may not overlap, but received %s and %s",
currentRange,
range);
}
throw new
AssertionError("should have thrown an IAE above");
}
rangeSet.
add(
range);
return this;
}
/**
* Add all ranges from the specified range set to this builder. Duplicate or connected ranges
* are permitted, and will be merged in the resulting immutable range set.
*/
public
Builder<C>
addAll(
RangeSet<C>
ranges) {
for (
Range<C>
range :
ranges.
asRanges()) {
add(
range);
}
return this;
}
/**
* Returns an {@code ImmutableRangeSet} containing the ranges added to this builder.
*/
public
ImmutableRangeSet<C>
build() {
return
copyOf(
rangeSet);
}
}
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);
}
}