diff options
Diffstat (limited to 'guava/src/com/google/common/collect/Range.java')
| -rw-r--r-- | guava/src/com/google/common/collect/Range.java | 706 |
1 files changed, 250 insertions, 456 deletions
diff --git a/guava/src/com/google/common/collect/Range.java b/guava/src/com/google/common/collect/Range.java index e70c34f..c6a9189 100644 --- a/guava/src/com/google/common/collect/Range.java +++ b/guava/src/com/google/common/collect/Range.java @@ -17,17 +17,15 @@ package com.google.common.collect; import static com.google.common.base.Preconditions.checkNotNull; +import static com.google.common.collect.Ranges.create; import com.google.common.annotations.Beta; import com.google.common.annotations.GwtCompatible; -import com.google.common.base.Equivalence; -import com.google.common.base.Function; import com.google.common.base.Predicate; import java.io.Serializable; import java.util.Collections; import java.util.Comparator; -import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Set; import java.util.SortedSet; @@ -35,338 +33,94 @@ import java.util.SortedSet; import javax.annotation.Nullable; /** - * A range (or "interval") defines the <i>boundaries</i> around a contiguous span of values of some - * {@code Comparable} type; for example, "integers from 1 to 100 inclusive." Note that it is not - * possible to <i>iterate</i> over these contained values. To do so, pass this range instance and - * an appropriate {@link DiscreteDomain} to {@link ContiguousSet#create}. + * A range, sometimes known as an <i>interval</i>, is a <i>convex</i> + * (informally, "contiguous" or "unbroken") portion of a particular domain. + * Formally, convexity means that for any {@code a <= b <= c}, + * {@code range.contains(a) && range.contains(c)} implies that {@code + * range.contains(b)}. * - * <h3>Types of ranges</h3> + * <p>A range is characterized by its lower and upper <i>bounds</i> (extremes), + * each of which can <i>open</i> (exclusive of its endpoint), <i>closed</i> + * (inclusive of its endpoint), or <i>unbounded</i>. This yields nine basic + * types of ranges: * - * <p>Each end of the range may be bounded or unbounded. If bounded, there is an associated - * <i>endpoint</i> value, and the range is considered to be either <i>open</i> (does not include the - * endpoint) or <i>closed</i> (includes the endpoint) on that side. With three possibilities on each - * side, this yields nine basic types of ranges, enumerated below. (Notation: a square bracket - * ({@code [ ]}) indicates that the range is closed on that side; a parenthesis ({@code ( )}) means - * it is either open or unbounded. The construct {@code {x | statement}} is read "the set of all - * <i>x</i> such that <i>statement</i>.") + * <ul> + * <li>{@code (a..b) = {x | a < x < b}} + * <li>{@code [a..b] = {x | a <= x <= b}} + * <li>{@code [a..b) = {x | a <= x < b}} + * <li>{@code (a..b] = {x | a < x <= b}} + * <li>{@code (a..+∞) = {x | x > a}} + * <li>{@code [a..+∞) = {x | x >= a}} + * <li>{@code (-∞..b) = {x | x < b}} + * <li>{@code (-∞..b] = {x | x <= b}} + * <li>{@code (-∞..+∞) = all values} + * </ul> + * + * (The notation {@code {x | statement}} is read "the set of all <i>x</i> such + * that <i>statement</i>.") * - * <blockquote><table> - * <tr><td><b>Notation</b> <td><b>Definition</b> <td><b>Factory method</b> - * <tr><td>{@code (a..b)} <td>{@code {x | a < x < b}} <td>{@link Range#open open} - * <tr><td>{@code [a..b]} <td>{@code {x | a <= x <= b}}<td>{@link Range#closed closed} - * <tr><td>{@code (a..b]} <td>{@code {x | a < x <= b}} <td>{@link Range#openClosed openClosed} - * <tr><td>{@code [a..b)} <td>{@code {x | a <= x < b}} <td>{@link Range#closedOpen closedOpen} - * <tr><td>{@code (a..+∞)} <td>{@code {x | x > a}} <td>{@link Range#greaterThan greaterThan} - * <tr><td>{@code [a..+∞)} <td>{@code {x | x >= a}} <td>{@link Range#atLeast atLeast} - * <tr><td>{@code (-∞..b)} <td>{@code {x | x < b}} <td>{@link Range#lessThan lessThan} - * <tr><td>{@code (-∞..b]} <td>{@code {x | x <= b}} <td>{@link Range#atMost atMost} - * <tr><td>{@code (-∞..+∞)}<td>{@code {x}} <td>{@link Range#all all} - * </table></blockquote> + * <p>Notice that we use a square bracket ({@code [ ]}) to denote that an range + * is closed on that end, and a parenthesis ({@code ( )}) when it is open or + * unbounded. * - * <p>When both endpoints exist, the upper endpoint may not be less than the lower. The endpoints - * may be equal only if at least one of the bounds is closed: + * <p>The values {@code a} and {@code b} used above are called <i>endpoints</i>. + * The upper endpoint may not be less than the lower endpoint. The endpoints may + * be equal only if at least one of the bounds is closed: * * <ul> - * <li>{@code [a..a]} : a singleton range - * <li>{@code [a..a); (a..a]} : {@linkplain #isEmpty empty} ranges; also valid - * <li>{@code (a..a)} : <b>invalid</b>; an exception will be thrown + * <li>{@code [a..a]} : singleton range + * <li>{@code [a..a); (a..a]} : {@linkplain #isEmpty empty}, but valid + * <li>{@code (a..a)} : <b>invalid</b> * </ul> * - * <h3>Warnings</h3> + * <p>Instances of this type can be obtained using the static factory methods in + * the {@link Ranges} class. * - * <ul> - * <li>Use immutable value types only, if at all possible. If you must use a mutable type, <b>do - * not</b> allow the endpoint instances to mutate after the range is created! - * <li>Your value type's comparison method should be {@linkplain Comparable consistent with equals} - * if at all possible. Otherwise, be aware that concepts used throughout this documentation such - * as "equal", "same", "unique" and so on actually refer to whether {@link Comparable#compareTo - * compareTo} returns zero, not whether {@link Object#equals equals} returns {@code true}. - * <li>A class which implements {@code Comparable<UnrelatedType>} is very broken, and will cause - * undefined horrible things to happen in {@code Range}. For now, the Range API does not prevent - * its use, because this would also rule out all ungenerified (pre-JDK1.5) data types. <b>This - * may change in the future.</b> - * </ul> + * <p>Instances of {@code Range} are immutable. It is strongly encouraged to + * use this class only with immutable data types. When creating a range over a + * mutable type, take great care not to allow the value objects to mutate after + * the range is created. * - * <h3>Other notes</h3> + * <p>In this and other range-related specifications, concepts like "equal", + * "same", "unique" and so on are based on {@link Comparable#compareTo} + * returning zero, not on {@link Object#equals} returning {@code true}. Of + * course, when these methods are kept <i>consistent</i> (as defined in {@link + * Comparable}), this is not an issue. * - * <ul> - * <li>Instances of this type are obtained using the static factory methods in this class. - * <li>Ranges are <i>convex</i>: whenever two values are contained, all values in between them must - * also be contained. More formally, for any {@code c1 <= c2 <= c3} of type {@code C}, {@code - * r.contains(c1) && r.contains(c3)} implies {@code r.contains(c2)}). This means that a {@code - * Range<Integer>} can never be used to represent, say, "all <i>prime</i> numbers from 1 to - * 100." - * <li>When evaluated as a {@link Predicate}, a range yields the same result as invoking {@link - * #contains}. - * <li>Terminology note: a range {@code a} is said to be the <i>maximal</i> range having property - * <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code a.encloses(b)}. - * Likewise, {@code a} is <i>minimal</i> when {@code b.encloses(a)} for all {@code b} having - * property <i>P</i>. See, for example, the definition of {@link #intersection intersection}. - * </ul> + * <p>A range {@code a} is said to be the <i>maximal</i> range having property + * <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code + * a.encloses(b)}. Likewise, {@code a} is <i>minimal</i> when {@code + * b.encloses(a)} for all {@code b} having property <i>P</i>. See, for example, + * the definition of {@link #intersection}. * - * <h3>Further reading</h3> + * <p>This class can be used with any type which implements {@code Comparable}; + * it does not require {@code Comparable<? super C>} because this would be + * incompatible with pre-Java 5 types. If this class is used with a perverse + * {@code Comparable} type ({@code Foo implements Comparable<Bar>} where {@code + * Bar} is not a supertype of {@code Foo}), any of its methods may throw {@link + * ClassCastException}. (There is no good reason for such a type to exist.) * - * <p>See the Guava User Guide article on - * <a href="http://code.google.com/p/guava-libraries/wiki/RangesExplained">{@code Range}</a>. + * <p>When evaluated as a {@link Predicate}, a range yields the same result as + * invoking {@link #contains}. * * @author Kevin Bourrillion * @author Gregory Kick * @since 10.0 */ @GwtCompatible -@SuppressWarnings("rawtypes") -public final class Range<C extends Comparable> implements Predicate<C>, Serializable { - - private static final Function<Range, Cut> LOWER_BOUND_FN = new Function<Range, Cut>() { - @Override - public Cut apply(Range range) { - return range.lowerBound; - } - }; - - @SuppressWarnings("unchecked") - static <C extends Comparable<?>> Function<Range<C>, Cut<C>> lowerBoundFn() { - return (Function) LOWER_BOUND_FN; - } - - private static final Function<Range, Cut> UPPER_BOUND_FN = new Function<Range, Cut>() { - @Override - public Cut apply(Range range) { - return range.upperBound; - } - }; - - @SuppressWarnings("unchecked") - static <C extends Comparable<?>> Function<Range<C>, Cut<C>> upperBoundFn() { - return (Function) UPPER_BOUND_FN; - } - - static final Ordering<Range<?>> RANGE_LEX_ORDERING = new Ordering<Range<?>>() { - @Override - public int compare(Range<?> left, Range<?> right) { - return ComparisonChain.start() - .compare(left.lowerBound, right.lowerBound) - .compare(left.upperBound, right.upperBound) - .result(); - } - }; - - static <C extends Comparable<?>> Range<C> create( - Cut<C> lowerBound, Cut<C> upperBound) { - return new Range<C>(lowerBound, upperBound); - } - - /** - * Returns a range that contains all values strictly greater than {@code - * lower} and strictly less than {@code upper}. - * - * @throws IllegalArgumentException if {@code lower} is greater than <i>or - * equal to</i> {@code upper} - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> open(C lower, C upper) { - return create(Cut.aboveValue(lower), Cut.belowValue(upper)); - } - - /** - * Returns a range that contains all values greater than or equal to - * {@code lower} and less than or equal to {@code upper}. - * - * @throws IllegalArgumentException if {@code lower} is greater than {@code - * upper} - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> closed(C lower, C upper) { - return create(Cut.belowValue(lower), Cut.aboveValue(upper)); - } - - /** - * Returns a range that contains all values greater than or equal to - * {@code lower} and strictly less than {@code upper}. - * - * @throws IllegalArgumentException if {@code lower} is greater than {@code - * upper} - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> closedOpen( - C lower, C upper) { - return create(Cut.belowValue(lower), Cut.belowValue(upper)); - } - - /** - * Returns a range that contains all values strictly greater than {@code - * lower} and less than or equal to {@code upper}. - * - * @throws IllegalArgumentException if {@code lower} is greater than {@code - * upper} - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> openClosed( - C lower, C upper) { - return create(Cut.aboveValue(lower), Cut.aboveValue(upper)); - } - - /** - * Returns a range that contains any value from {@code lower} to {@code - * upper}, where each endpoint may be either inclusive (closed) or exclusive - * (open). - * - * @throws IllegalArgumentException if {@code lower} is greater than {@code - * upper} - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> range( - C lower, BoundType lowerType, C upper, BoundType upperType) { - checkNotNull(lowerType); - checkNotNull(upperType); - - Cut<C> lowerBound = (lowerType == BoundType.OPEN) - ? Cut.aboveValue(lower) - : Cut.belowValue(lower); - Cut<C> upperBound = (upperType == BoundType.OPEN) - ? Cut.belowValue(upper) - : Cut.aboveValue(upper); - return create(lowerBound, upperBound); - } - - /** - * Returns a range that contains all values strictly less than {@code - * endpoint}. - * - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> lessThan(C endpoint) { - return create(Cut.<C>belowAll(), Cut.belowValue(endpoint)); - } - - /** - * Returns a range that contains all values less than or equal to - * {@code endpoint}. - * - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> atMost(C endpoint) { - return create(Cut.<C>belowAll(), Cut.aboveValue(endpoint)); - } - - /** - * Returns a range with no lower bound up to the given endpoint, which may be - * either inclusive (closed) or exclusive (open). - * - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> upTo( - C endpoint, BoundType boundType) { - switch (boundType) { - case OPEN: - return lessThan(endpoint); - case CLOSED: - return atMost(endpoint); - default: - throw new AssertionError(); - } - } - - /** - * Returns a range that contains all values strictly greater than {@code - * endpoint}. - * - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> greaterThan(C endpoint) { - return create(Cut.aboveValue(endpoint), Cut.<C>aboveAll()); - } - - /** - * Returns a range that contains all values greater than or equal to - * {@code endpoint}. - * - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> atLeast(C endpoint) { - return create(Cut.belowValue(endpoint), Cut.<C>aboveAll()); - } - - /** - * Returns a range from the given endpoint, which may be either inclusive - * (closed) or exclusive (open), with no upper bound. - * - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> downTo( - C endpoint, BoundType boundType) { - switch (boundType) { - case OPEN: - return greaterThan(endpoint); - case CLOSED: - return atLeast(endpoint); - default: - throw new AssertionError(); - } - } - - private static final Range<Comparable> ALL = - new Range<Comparable>(Cut.belowAll(), Cut.aboveAll()); - - /** - * Returns a range that contains every value of type {@code C}. - * - * @since 14.0 - */ - @SuppressWarnings("unchecked") - public static <C extends Comparable<?>> Range<C> all() { - return (Range) ALL; - } - - /** - * Returns a range that {@linkplain Range#contains(Comparable) contains} only - * the given value. The returned range is {@linkplain BoundType#CLOSED closed} - * on both ends. - * - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> singleton(C value) { - return closed(value, value); - } - - /** - * Returns the minimal range that - * {@linkplain Range#contains(Comparable) contains} all of the given values. - * The returned range is {@linkplain BoundType#CLOSED closed} on both ends. - * - * @throws ClassCastException if the parameters are not <i>mutually - * comparable</i> - * @throws NoSuchElementException if {@code values} is empty - * @throws NullPointerException if any of {@code values} is null - * @since 14.0 - */ - public static <C extends Comparable<?>> Range<C> encloseAll( - Iterable<C> values) { - checkNotNull(values); - if (values instanceof ContiguousSet) { - return ((ContiguousSet<C>) values).range(); - } - Iterator<C> valueIterator = values.iterator(); - C min = checkNotNull(valueIterator.next()); - C max = min; - while (valueIterator.hasNext()) { - C value = checkNotNull(valueIterator.next()); - min = Ordering.natural().min(min, value); - max = Ordering.natural().max(max, value); - } - return closed(min, max); - } - +@Beta +public final class Range<C extends Comparable> + implements Predicate<C>, Serializable { final Cut<C> lowerBound; final Cut<C> upperBound; - private Range(Cut<C> lowerBound, Cut<C> upperBound) { - if (lowerBound.compareTo(upperBound) > 0 || lowerBound == Cut.<C>aboveAll() - || upperBound == Cut.<C>belowAll()) { - throw new IllegalArgumentException("Invalid range: " + toString(lowerBound, upperBound)); + Range(Cut<C> lowerBound, Cut<C> upperBound) { + if (lowerBound.compareTo(upperBound) > 0) { + throw new IllegalArgumentException( + "Invalid range: " + toString(lowerBound, upperBound)); } - this.lowerBound = checkNotNull(lowerBound); - this.upperBound = checkNotNull(upperBound); + this.lowerBound = lowerBound; + this.upperBound = upperBound; } /** @@ -379,19 +133,20 @@ public final class Range<C extends Comparable> implements Predicate<C>, Serializ /** * Returns the lower endpoint of this range. * - * @throws IllegalStateException if this range is unbounded below (that is, {@link - * #hasLowerBound()} returns {@code false}) + * @throws IllegalStateException if this range is unbounded below (that is, + * {@link #hasLowerBound()} returns {@code false}) */ public C lowerEndpoint() { return lowerBound.endpoint(); } /** - * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if the range includes - * its lower endpoint, {@link BoundType#OPEN} if it does not. + * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if + * the range includes its lower endpoint, {@link BoundType#OPEN} if it does + * not. * - * @throws IllegalStateException if this range is unbounded below (that is, {@link - * #hasLowerBound()} returns {@code false}) + * @throws IllegalStateException if this range is unbounded below (that is, + * {@link #hasLowerBound()} returns {@code false}) */ public BoundType lowerBoundType() { return lowerBound.typeAsLowerBound(); @@ -407,41 +162,42 @@ public final class Range<C extends Comparable> implements Predicate<C>, Serializ /** * Returns the upper endpoint of this range. * - * @throws IllegalStateException if this range is unbounded above (that is, {@link - * #hasUpperBound()} returns {@code false}) + * @throws IllegalStateException if this range is unbounded above (that is, + * {@link #hasUpperBound()} returns {@code false}) */ public C upperEndpoint() { return upperBound.endpoint(); } /** - * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if the range includes - * its upper endpoint, {@link BoundType#OPEN} if it does not. + * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if + * the range includes its upper endpoint, {@link BoundType#OPEN} if it does + * not. * - * @throws IllegalStateException if this range is unbounded above (that is, {@link - * #hasUpperBound()} returns {@code false}) + * @throws IllegalStateException if this range is unbounded above (that is, + * {@link #hasUpperBound()} returns {@code false}) */ public BoundType upperBoundType() { return upperBound.typeAsUpperBound(); } /** - * Returns {@code true} if this range is of the form {@code [v..v)} or {@code (v..v]}. (This does - * not encompass ranges of the form {@code (v..v)}, because such ranges are <i>invalid</i> and - * can't be constructed at all.) + * Returns {@code true} if this range is of the form {@code [v..v)} or {@code + * (v..v]}. (This does not encompass ranges of the form {@code (v..v)}, + * because such ranges are <i>invalid</i> and can't be constructed at all.) * - * <p>Note that certain discrete ranges such as the integer range {@code (3..4)} are <b>not</b> - * considered empty, even though they contain no actual values. In these cases, it may be - * helpful to preprocess ranges with {@link #canonical(DiscreteDomain)}. + * <p>Note that certain discrete ranges such as the integer range {@code + * (3..4)} are <b>not</b> considered empty, even though they contain no actual + * values. */ public boolean isEmpty() { return lowerBound.equals(upperBound); } /** - * Returns {@code true} if {@code value} is within the bounds of this range. For example, on the - * range {@code [0..2)}, {@code contains(1)} returns {@code true}, while {@code contains(2)} - * returns {@code false}. + * Returns {@code true} if {@code value} is within the bounds of this + * range. For example, on the range {@code [0..2)}, {@code contains(1)} + * returns {@code true}, while {@code contains(2)} returns {@code false}. */ public boolean contains(C value) { checkNotNull(value); @@ -450,16 +206,17 @@ public final class Range<C extends Comparable> implements Predicate<C>, Serializ } /** - * Equivalent to {@link #contains}; provided only to satisfy the {@link Predicate} interface. When - * using a reference of type {@code Range}, always invoke {@link #contains} directly instead. + * Equivalent to {@link #contains}; provided only to satisfy the {@link + * Predicate} interface. When using a reference of type {@code Range}, always + * invoke {@link #contains} directly instead. */ @Override public boolean apply(C input) { return contains(input); } /** - * Returns {@code true} if every element in {@code values} is {@linkplain #contains contained} in - * this range. + * Returns {@code true} if every element in {@code values} is {@linkplain + * #contains contained} in this range. */ public boolean containsAll(Iterable<? extends C> values) { if (Iterables.isEmpty(values)) { @@ -484,27 +241,42 @@ public final class Range<C extends Comparable> implements Predicate<C>, Serializ } /** - * Returns {@code true} if the bounds of {@code other} do not extend outside the bounds of this - * range. Examples: + * Returns {@code true} if the bounds of {@code other} do not extend outside + * the bounds of this range. Examples: * * <ul> * <li>{@code [3..6]} encloses {@code [4..5]} * <li>{@code (3..6)} encloses {@code (3..6)} - * <li>{@code [3..6]} encloses {@code [4..4)} (even though the latter is empty) + * <li>{@code [3..6]} encloses {@code [4..4)} (even though the latter is + * empty) * <li>{@code (3..6]} does not enclose {@code [3..6]} - * <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains every value - * contained by the latter range) - * <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains every value - * contained by the latter range) + * <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains + * every value contained by the latter range) + * <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains + * every value contained by the latter range) * </ul> * - * Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies {@code a.contains(v)}, - * but as the last two examples illustrate, the converse is not always true. + * Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies + * {@code a.contains(v)}, but as the last two examples illustrate, the + * converse is not always true. * - * <p>Being reflexive, antisymmetric and transitive, the {@code encloses} relation defines a - * <i>partial order</i> over ranges. There exists a unique {@linkplain Range#all maximal} range - * according to this relation, and also numerous {@linkplain #isEmpty minimal} ranges. Enclosure - * also implies {@linkplain #isConnected connectedness}. + * <p>The encloses relation has the following properties: + * + * <ul> + * <li>reflexive: {@code a.encloses(a)} is always true + * <li>antisymmetric: {@code a.encloses(b) && b.encloses(a)} implies {@code + * a.equals(b)} + * <li>transitive: {@code a.encloses(b) && b.encloses(c)} implies {@code + * a.encloses(c)} + * <li>not a total ordering: {@code !a.encloses(b)} does not imply {@code + * b.encloses(a)} + * <li>there exists a {@linkplain Ranges#all maximal} range, for which + * {@code encloses} is always true + * <li>there also exist {@linkplain #isEmpty minimal} ranges, for + * which {@code encloses(b)} is always false when {@code !equals(b)} + * <li>if {@code a.encloses(b)}, then {@link #isConnected a.isConnected(b)} + * is {@code true}. + * </ul> */ public boolean encloses(Range<C> other) { return lowerBound.compareTo(other.lowerBound) <= 0 @@ -512,133 +284,160 @@ public final class Range<C extends Comparable> implements Predicate<C>, Serializ } /** - * Returns {@code true} if there exists a (possibly empty) range which is {@linkplain #encloses - * enclosed} by both this range and {@code other}. + * Returns the maximal range {@linkplain #encloses enclosed} by both this + * range and {@code other}, if such a range exists. + * + * <p>For example, the intersection of {@code [1..5]} and {@code (3..7)} is + * {@code (3..5]}. The resulting range may be empty; for example, + * {@code [1..5)} intersected with {@code [5..7)} yields the empty range + * {@code [5..5)}. + * + * <p>Generally, the intersection exists if and only if this range and + * {@code other} are {@linkplain #isConnected connected}. + * + * <p>The intersection operation has the following properties: * - * <p>For example, * <ul> - * <li>{@code [2, 4)} and {@code [5, 7)} are not connected - * <li>{@code [2, 4)} and {@code [3, 5)} are connected, because both enclose {@code [3, 4)} - * <li>{@code [2, 4)} and {@code [4, 6)} are connected, because both enclose the empty range - * {@code [4, 4)} + * <li>commutative: {@code a.intersection(b)} produces the same result as + * {@code b.intersection(a)} + * <li>associative: {@code a.intersection(b).intersection(c)} produces the + * same result as {@code a.intersection(b.intersection(c))} + * <li>idempotent: {@code a.intersection(a)} equals {@code a} + * <li>identity ({@link Ranges#all}): {@code a.intersection(Ranges.all())} + * equals {@code a} * </ul> * - * <p>Note that this range and {@code other} have a well-defined {@linkplain #span union} and - * {@linkplain #intersection intersection} (as a single, possibly-empty range) if and only if this - * method returns {@code true}. - * - * <p>The connectedness relation is both reflexive and symmetric, but does not form an {@linkplain - * Equivalence equivalence relation} as it is not transitive. - * - * <p>Note that certain discrete ranges are not considered connected, even though there are no - * elements "between them." For example, {@code [3, 5]} is not considered connected to {@code - * [6, 10]}. In these cases, it may be desirable for both input ranges to be preprocessed with - * {@link #canonical(DiscreteDomain)} before testing for connectedness. + * @throws IllegalArgumentException if no range exists that is enclosed by + * both these ranges */ - public boolean isConnected(Range<C> other) { - return lowerBound.compareTo(other.upperBound) <= 0 - && other.lowerBound.compareTo(upperBound) <= 0; + public Range<C> intersection(Range<C> other) { + Cut<C> newLower = Ordering.natural().max(lowerBound, other.lowerBound); + Cut<C> newUpper = Ordering.natural().min(upperBound, other.upperBound); + return create(newLower, newUpper); } /** - * Returns the maximal range {@linkplain #encloses enclosed} by both this range and {@code - * connectedRange}, if such a range exists. - * - * <p>For example, the intersection of {@code [1..5]} and {@code (3..7)} is {@code (3..5]}. The - * resulting range may be empty; for example, {@code [1..5)} intersected with {@code [5..7)} - * yields the empty range {@code [5..5)}. - * - * <p>The intersection exists if and only if the two ranges are {@linkplain #isConnected - * connected}. - * - * <p>The intersection operation is commutative, associative and idempotent, and its identity - * element is {@link Range#all}). + * Returns {@code true} if there exists a (possibly empty) range which is + * {@linkplain #encloses enclosed} by both this range and {@code other}. + * + * <p>For example, + * <ul> + * <li>{@code [2, 4)} and {@code [5, 7)} are not connected + * <li>{@code [2, 4)} and {@code [3, 5)} are connected, because both enclose + * {@code [3, 4)} + * <li>{@code [2, 4)} and {@code [4, 6)} are connected, because both enclose + * the empty range {@code [4, 4)} + * </ul> + * + * <p>Note that this range and {@code other} have a well-defined {@linkplain + * #span union} and {@linkplain #intersection intersection} (as a single, + * possibly-empty range) if and only if this method returns {@code true}. + * + * <p>The connectedness relation has the following properties: * - * @throws IllegalArgumentException if {@code isConnected(connectedRange)} is {@code false} + * <ul> + * <li>symmetric: {@code a.isConnected(b)} produces the same result as + * {@code b.isConnected(a)} + * <li>reflexive: {@code a.isConnected(a)} returns {@code true} + * </ul> */ - public Range<C> intersection(Range<C> connectedRange) { - int lowerCmp = lowerBound.compareTo(connectedRange.lowerBound); - int upperCmp = upperBound.compareTo(connectedRange.upperBound); - if (lowerCmp >= 0 && upperCmp <= 0) { - return this; - } else if (lowerCmp <= 0 && upperCmp >= 0) { - return connectedRange; - } else { - Cut<C> newLower = (lowerCmp >= 0) ? lowerBound : connectedRange.lowerBound; - Cut<C> newUpper = (upperCmp <= 0) ? upperBound : connectedRange.upperBound; - return create(newLower, newUpper); - } + public boolean isConnected(Range<C> other) { + return lowerBound.compareTo(other.upperBound) <= 0 + && other.lowerBound.compareTo(upperBound) <= 0; } /** - * Returns the minimal range that {@linkplain #encloses encloses} both this range and {@code - * other}. For example, the span of {@code [1..3]} and {@code (5..7)} is {@code [1..7)}. + * Returns the minimal range that {@linkplain #encloses encloses} both this + * range and {@code other}. For example, the span of {@code [1..3]} and + * {@code (5..7)} is {@code [1..7)}. Note that the span may contain values + * that are not contained by either original range. * - * <p><i>If</i> the input ranges are {@linkplain #isConnected connected}, the returned range can - * also be called their <i>union</i>. If they are not, note that the span might contain values - * that are not contained in either input range. + * <p>The span operation has the following properties: * - * <p>Like {@link #intersection(Range) intersection}, this operation is commutative, associative - * and idempotent. Unlike it, it is always well-defined for any two input ranges. + * <ul> + * <li>closed: the range {@code a.span(b)} exists for all ranges {@code a} and + * {@code b} + * <li>commutative: {@code a.span(b)} equals {@code b.span(a)} + * <li>associative: {@code a.span(b).span(c)} equals {@code a.span(b.span(c))} + * <li>idempotent: {@code a.span(a)} equals {@code a} + * </ul> + * + * <p>Note that the returned range is also called the <i>union</i> of this + * range and {@code other} if and only if the ranges are + * {@linkplain #isConnected connected}. */ public Range<C> span(Range<C> other) { - int lowerCmp = lowerBound.compareTo(other.lowerBound); - int upperCmp = upperBound.compareTo(other.upperBound); - if (lowerCmp <= 0 && upperCmp >= 0) { - return this; - } else if (lowerCmp >= 0 && upperCmp <= 0) { - return other; - } else { - Cut<C> newLower = (lowerCmp <= 0) ? lowerBound : other.lowerBound; - Cut<C> newUpper = (upperCmp >= 0) ? upperBound : other.upperBound; - return create(newLower, newUpper); - } + Cut<C> newLower = Ordering.natural().min(lowerBound, other.lowerBound); + Cut<C> newUpper = Ordering.natural().max(upperBound, other.upperBound); + return create(newLower, newUpper); } /** - * Returns an {@link ContiguousSet} containing the same values in the given domain - * {@linkplain Range#contains contained} by this range. + * Returns an {@link ImmutableSortedSet} containing the same values in the + * given domain {@linkplain Range#contains contained} by this range. * - * <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>Note:</b> {@code a.asSet().equals(b.asSet())} 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 (such as {@code 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><b>Warning:</b> Be extremely careful what you do with the {@code asSet} + * view of a large range (such as {@code Ranges.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]}"}. + * <p>The returned set's {@link Object#toString} method returns a short-hand + * form of 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 - * @deprecated Use {@code ContiguousSet.create(range, domain)} instead. + * @throws IllegalArgumentException if neither this range nor the domain has a + * lower bound, or if neither has an upper bound */ // TODO(kevinb): commit in spec to which methods are efficient? - @Beta @GwtCompatible(serializable = false) - @Deprecated public ContiguousSet<C> asSet(DiscreteDomain<C> domain) { - return ContiguousSet.create(this, domain); + checkNotNull(domain); + Range<C> effectiveRange = this; + try { + if (!hasLowerBound()) { + effectiveRange = effectiveRange.intersection( + Ranges.atLeast(domain.minValue())); + } + if (!hasUpperBound()) { + effectiveRange = effectiveRange.intersection( + Ranges.atMost(domain.maxValue())); + } + } catch (NoSuchElementException e) { + throw new IllegalArgumentException(e); + } + + // Per class spec, we are allowed to throw CCE if necessary + boolean empty = effectiveRange.isEmpty() + || compareOrThrow( + lowerBound.leastValueAbove(domain), + upperBound.greatestValueBelow(domain)) > 0; + + return empty + ? new EmptyContiguousSet<C>(domain) + : new RegularContiguousSet<C>(effectiveRange, domain); } /** - * Returns the canonical form of this range in the given domain. The canonical form has the - * following properties: + * Returns the canonical form of this range in the given domain. The canonical + * form has the following properties: * * <ul> - * <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for all {@code v} (in other - * words, {@code ContiguousSet.create(a.canonical(domain), domain).equals( - * ContiguousSet.create(a, domain))} + * <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for + * all {@code v} (in other words, {@code + * a.canonical(domain).asSet(domain).equals(a.asSet(domain))} * <li>uniqueness: unless {@code a.isEmpty()}, - * {@code ContiguousSet.create(a, domain).equals(ContiguousSet.create(b, domain))} implies + * {@code a.asSet(domain).equals(b.asSet(domain))} implies * {@code a.canonical(domain).equals(b.canonical(domain))} - * <li>idempotence: {@code a.canonical(domain).canonical(domain).equals(a.canonical(domain))} + * <li>idempotence: {@code + * a.canonical(domain).canonical(domain).equals(a.canonical(domain))} * </ul> * - * Furthermore, this method guarantees that the range returned will be one of the following - * canonical forms: + * Furthermore, this method guarantees that the range returned will be one + * of the following canonical forms: * * <ul> * <li>[start..end) @@ -651,15 +450,18 @@ public final class Range<C extends Comparable> implements Predicate<C>, Serializ checkNotNull(domain); Cut<C> lower = lowerBound.canonical(domain); Cut<C> upper = upperBound.canonical(domain); - return (lower == lowerBound && upper == upperBound) ? this : create(lower, upper); + return (lower == lowerBound && upper == upperBound) + ? this : create(lower, upper); } /** - * Returns {@code true} if {@code object} is a range having the same endpoints and bound types as - * this range. Note that discrete ranges such as {@code (1..4)} and {@code [2..3]} are <b>not</b> - * equal to one another, despite the fact that they each contain precisely the same set of values. - * Similarly, empty ranges are not equal unless they have exactly the same representation, so - * {@code [3..3)}, {@code (3..3]}, {@code (4..4]} are all unequal. + * Returns {@code true} if {@code object} is a range having the same + * endpoints and bound types as this range. Note that discrete ranges + * such as {@code (1..4)} and {@code [2..3]} are <b>not</b> equal to one + * another, despite the fact that they each contain precisely the same set of + * values. Similarly, empty ranges are not equal unless they have exactly + * the same representation, so {@code [3..3)}, {@code (3..3]}, {@code (4..4]} + * are all unequal. */ @Override public boolean equals(@Nullable Object object) { if (object instanceof Range) { @@ -676,8 +478,8 @@ public final class Range<C extends Comparable> implements Predicate<C>, Serializ } /** - * Returns a string representation of this range, such as {@code "[3..5)"} (other examples are - * listed in the class documentation). + * Returns a string representation of this range, such as {@code "[3..5)"} + * (other examples are listed in the class documentation). */ @Override public String toString() { return toString(lowerBound, upperBound); @@ -698,14 +500,6 @@ public final class Range<C extends Comparable> implements Predicate<C>, Serializ return (SortedSet<T>) iterable; } - Object readResolve() { - if (this.equals(ALL)) { - return all(); - } else { - return this; - } - } - @SuppressWarnings("unchecked") // this method may throw CCE static int compareOrThrow(Comparable left, Comparable right) { return left.compareTo(right); |