001 /*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkNotNull;
020 import static com.google.common.collect.Ranges.create;
021
022 import com.google.common.annotations.Beta;
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.base.Equivalence;
025 import com.google.common.base.Predicate;
026
027 import java.io.Serializable;
028 import java.util.Collections;
029 import java.util.Comparator;
030 import java.util.NoSuchElementException;
031 import java.util.Set;
032 import java.util.SortedSet;
033
034 import javax.annotation.Nullable;
035
036 /**
037 * A range (or "interval") defines the <i>boundaries</i> around a contiguous span of values of some
038 * {@code Comparable} type; for example, "integers from 1 to 100 inclusive." Note that it is not
039 * possible to <i>iterate</i> over these contained values unless an appropriate {@link
040 * DiscreteDomain} can be provided to the {@link #asSet asSet} method.
041 *
042 * <h3>Types of ranges</h3>
043 *
044 * <p>Each end of the range may be bounded or unbounded. If bounded, there is an associated
045 * <i>endpoint</i> value, and the range is considered to be either <i>open</i> (does not include the
046 * endpoint) or <i>closed</i> (includes the endpoint) on that side. With three possibilities on each
047 * side, this yields nine basic types of ranges, enumerated below. (Notation: a square bracket
048 * ({@code [ ]}) indicates that the range is closed on that side; a parenthesis ({@code ( )}) means
049 * it is either open or unbounded. The construct {@code {x | statement}} is read "the set of all
050 * <i>x</i> such that <i>statement</i>.")
051 *
052 * <blockquote><table>
053 * <tr><td><b>Notation</b> <td><b>Definition</b> <td><b>Factory method</b>
054 * <tr><td>{@code (a..b)} <td>{@code {x | a < x < b}} <td>{@link Ranges#open open}
055 * <tr><td>{@code [a..b]} <td>{@code {x | a <= x <= b}}<td>{@link Ranges#closed closed}
056 * <tr><td>{@code (a..b]} <td>{@code {x | a < x <= b}} <td>{@link Ranges#openClosed openClosed}
057 * <tr><td>{@code [a..b)} <td>{@code {x | a <= x < b}} <td>{@link Ranges#closedOpen closedOpen}
058 * <tr><td>{@code (a..+∞)} <td>{@code {x | x > a}} <td>{@link Ranges#greaterThan greaterThan}
059 * <tr><td>{@code [a..+∞)} <td>{@code {x | x >= a}} <td>{@link Ranges#atLeast atLeast}
060 * <tr><td>{@code (-∞..b)} <td>{@code {x | x < b}} <td>{@link Ranges#lessThan lessThan}
061 * <tr><td>{@code (-∞..b]} <td>{@code {x | x <= b}} <td>{@link Ranges#atMost atMost}
062 * <tr><td>{@code (-∞..+∞)}<td>{@code {x}} <td>{@link Ranges#all all}
063 * </table></blockquote>
064 *
065 * <p>When both endpoints exist, the upper endpoint may not be less than the lower. The endpoints
066 * may be equal only if at least one of the bounds is closed:
067 *
068 * <ul>
069 * <li>{@code [a..a]} : a singleton range
070 * <li>{@code [a..a); (a..a]} : {@linkplain #isEmpty empty} ranges; also valid
071 * <li>{@code (a..a)} : <b>invalid</b>; an exception will be thrown
072 * </ul>
073 *
074 * <h3>Warnings</h3>
075 *
076 * <ul>
077 * <li>Use immutable value types only, if at all possible. If you must use a mutable type, <b>do
078 * not</b> allow the endpoint instances to mutate after the range is created!
079 * <li>Your value type's comparison method should be {@linkplain Comparable consistent with equals}
080 * if at all possible. Otherwise, be aware that concepts used throughout this documentation such
081 * as "equal", "same", "unique" and so on actually refer to whether {@link Comparable#compareTo
082 * compareTo} returns zero, not whether {@link Object#equals equals} returns {@code true}.
083 * <li>A class which implements {@code Comparable<UnrelatedType>} is very broken, and will cause
084 * undefined horrible things to happen in {@code Range}. For now, the Range API does not prevent
085 * its use, because this would also rule out all ungenerified (pre-JDK1.5) data types. <b>This
086 * may change in the future.</b>
087 * </ul>
088 *
089 * <h3>Other notes</h3>
090 *
091 * <ul>
092 * <li>Instances of this type are obtained using the static factory methods in the {@link Ranges}
093 * class.
094 * <li>Ranges are <i>convex</i>: whenever two values are contained, all values in between them must
095 * also be contained. More formally, for any {@code c1 <= c2 <= c3} of type {@code C}, {@code
096 * r.contains(c1) && r.contains(c3)} implies {@code r.contains(c2)}). This means that a {@code
097 * Range<Integer>} can never be used to represent, say, "all <i>prime</i> numbers from 1 to
098 * 100."
099 * <li>When evaluated as a {@link Predicate}, a range yields the same result as invoking {@link
100 * #contains}.
101 * <li>Terminology note: a range {@code a} is said to be the <i>maximal</i> range having property
102 * <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code a.encloses(b)}.
103 * Likewise, {@code a} is <i>minimal</i> when {@code b.encloses(a)} for all {@code b} having
104 * property <i>P</i>. See, for example, the definition of {@link #intersection intersection}.
105 * </ul>
106 *
107 * <h3>Further reading</h3>
108 *
109 * <p>See the Guava User Guide article on
110 * <a href="http://code.google.com/p/guava-libraries/wiki/RangesExplained">{@code Range}</a>.
111 *
112 * @author Kevin Bourrillion
113 * @author Gregory Kick
114 * @since 10.0
115 */
116 @GwtCompatible
117 @Beta
118 public final class Range<C extends Comparable> implements Predicate<C>, Serializable {
119 final Cut<C> lowerBound;
120 final Cut<C> upperBound;
121
122 Range(Cut<C> lowerBound, Cut<C> upperBound) {
123 if (lowerBound.compareTo(upperBound) > 0) {
124 throw new IllegalArgumentException("Invalid range: " + toString(lowerBound, upperBound));
125 }
126 this.lowerBound = lowerBound;
127 this.upperBound = upperBound;
128 }
129
130 /**
131 * Returns {@code true} if this range has a lower endpoint.
132 */
133 public boolean hasLowerBound() {
134 return lowerBound != Cut.belowAll();
135 }
136
137 /**
138 * Returns the lower endpoint of this range.
139 *
140 * @throws IllegalStateException if this range is unbounded below (that is, {@link
141 * #hasLowerBound()} returns {@code false})
142 */
143 public C lowerEndpoint() {
144 return lowerBound.endpoint();
145 }
146
147 /**
148 * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if the range includes
149 * its lower endpoint, {@link BoundType#OPEN} if it does not.
150 *
151 * @throws IllegalStateException if this range is unbounded below (that is, {@link
152 * #hasLowerBound()} returns {@code false})
153 */
154 public BoundType lowerBoundType() {
155 return lowerBound.typeAsLowerBound();
156 }
157
158 /**
159 * Returns {@code true} if this range has an upper endpoint.
160 */
161 public boolean hasUpperBound() {
162 return upperBound != Cut.aboveAll();
163 }
164
165 /**
166 * Returns the upper endpoint of this range.
167 *
168 * @throws IllegalStateException if this range is unbounded above (that is, {@link
169 * #hasUpperBound()} returns {@code false})
170 */
171 public C upperEndpoint() {
172 return upperBound.endpoint();
173 }
174
175 /**
176 * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if the range includes
177 * its upper endpoint, {@link BoundType#OPEN} if it does not.
178 *
179 * @throws IllegalStateException if this range is unbounded above (that is, {@link
180 * #hasUpperBound()} returns {@code false})
181 */
182 public BoundType upperBoundType() {
183 return upperBound.typeAsUpperBound();
184 }
185
186 /**
187 * Returns {@code true} if this range is of the form {@code [v..v)} or {@code (v..v]}. (This does
188 * not encompass ranges of the form {@code (v..v)}, because such ranges are <i>invalid</i> and
189 * can't be constructed at all.)
190 *
191 * <p>Note that certain discrete ranges such as the integer range {@code (3..4)} are <b>not</b>
192 * considered empty, even though they contain no actual values.
193 */
194 public boolean isEmpty() {
195 return lowerBound.equals(upperBound);
196 }
197
198 /**
199 * Returns {@code true} if {@code value} is within the bounds of this range. For example, on the
200 * range {@code [0..2)}, {@code contains(1)} returns {@code true}, while {@code contains(2)}
201 * returns {@code false}.
202 */
203 public boolean contains(C value) {
204 checkNotNull(value);
205 // let this throw CCE if there is some trickery going on
206 return lowerBound.isLessThan(value) && !upperBound.isLessThan(value);
207 }
208
209 /**
210 * Equivalent to {@link #contains}; provided only to satisfy the {@link Predicate} interface. When
211 * using a reference of type {@code Range}, always invoke {@link #contains} directly instead.
212 */
213 @Override public boolean apply(C input) {
214 return contains(input);
215 }
216
217 /**
218 * Returns {@code true} if every element in {@code values} is {@linkplain #contains contained} in
219 * this range.
220 */
221 public boolean containsAll(Iterable<? extends C> values) {
222 if (Iterables.isEmpty(values)) {
223 return true;
224 }
225
226 // this optimizes testing equality of two range-backed sets
227 if (values instanceof SortedSet) {
228 SortedSet<? extends C> set = cast(values);
229 Comparator<?> comparator = set.comparator();
230 if (Ordering.natural().equals(comparator) || comparator == null) {
231 return contains(set.first()) && contains(set.last());
232 }
233 }
234
235 for (C value : values) {
236 if (!contains(value)) {
237 return false;
238 }
239 }
240 return true;
241 }
242
243 /**
244 * Returns {@code true} if the bounds of {@code other} do not extend outside the bounds of this
245 * range. Examples:
246 *
247 * <ul>
248 * <li>{@code [3..6]} encloses {@code [4..5]}
249 * <li>{@code (3..6)} encloses {@code (3..6)}
250 * <li>{@code [3..6]} encloses {@code [4..4)} (even though the latter is empty)
251 * <li>{@code (3..6]} does not enclose {@code [3..6]}
252 * <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains every value
253 * contained by the latter range)
254 * <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains every value
255 * contained by the latter range)
256 * </ul>
257 *
258 * Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies {@code a.contains(v)},
259 * but as the last two examples illustrate, the converse is not always true.
260 *
261 * <p>Being reflexive, antisymmetric and transitive, the {@code encloses} relation defines a
262 * <i>partial order</i> over ranges. There exists a unique {@linkplain Ranges#all maximal} range
263 * according to this relation, and also numerous {@linkplain #isEmpty minimal} ranges. Enclosure
264 * also implies {@linkplain #isConnected connectedness}.
265 */
266 public boolean encloses(Range<C> other) {
267 return lowerBound.compareTo(other.lowerBound) <= 0
268 && upperBound.compareTo(other.upperBound) >= 0;
269 }
270
271 /**
272 * Returns {@code true} if there exists a (possibly empty) range which is {@linkplain #encloses
273 * enclosed} by both this range and {@code other}.
274 *
275 * <p>For example,
276 * <ul>
277 * <li>{@code [2, 4)} and {@code [5, 7)} are not connected
278 * <li>{@code [2, 4)} and {@code [3, 5)} are connected, because both enclose {@code [3, 4)}
279 * <li>{@code [2, 4)} and {@code [4, 6)} are connected, because both enclose the empty range
280 * {@code [4, 4)}
281 * </ul>
282 *
283 * <p>Note that this range and {@code other} have a well-defined {@linkplain #span union} and
284 * {@linkplain #intersection intersection} (as a single, possibly-empty range) if and only if this
285 * method returns {@code true}.
286 *
287 * <p>The connectedness relation is both reflexive and symmetric, but does not form an {@linkplain
288 * Equivalence equivalence relation} as it is not transitive.
289 */
290 public boolean isConnected(Range<C> other) {
291 return lowerBound.compareTo(other.upperBound) <= 0
292 && other.lowerBound.compareTo(upperBound) <= 0;
293 }
294
295 /**
296 * Returns the maximal range {@linkplain #encloses enclosed} by both this range and {@code
297 * connectedRange}, if such a range exists.
298 *
299 * <p>For example, the intersection of {@code [1..5]} and {@code (3..7)} is {@code (3..5]}. The
300 * resulting range may be empty; for example, {@code [1..5)} intersected with {@code [5..7)}
301 * yields the empty range {@code [5..5)}.
302 *
303 * <p>The intersection exists if and only if the two ranges are {@linkplain #isConnected
304 * connected}.
305 *
306 * <p>The intersection operation is commutative, associative and idempotent, and its identity
307 * element is {@link Ranges#all}).
308 *
309 * @throws IllegalArgumentException if {@code isConnected(connectedRange)} is {@code false}
310 */
311 public Range<C> intersection(Range<C> connectedRange) {
312 Cut<C> newLower = Ordering.natural().max(lowerBound, connectedRange.lowerBound);
313 Cut<C> newUpper = Ordering.natural().min(upperBound, connectedRange.upperBound);
314 return create(newLower, newUpper);
315 }
316
317 /**
318 * Returns the minimal range that {@linkplain #encloses encloses} both this range and {@code
319 * other}. For example, the span of {@code [1..3]} and {@code (5..7)} is {@code [1..7)}.
320 *
321 * <p><i>If</i> the input ranges are {@linkplain #isConnected connected}, the returned range can
322 * also be called their <i>union</i>. If they are not, note that the span might contain values
323 * that are not contained in either input range.
324 *
325 * <p>Like {@link #intersection(Range) intersection}, this operation is commutative, associative
326 * and idempotent. Unlike it, it is always well-defined for any two input ranges.
327 */
328 public Range<C> span(Range<C> other) {
329 Cut<C> newLower = Ordering.natural().min(lowerBound, other.lowerBound);
330 Cut<C> newUpper = Ordering.natural().max(upperBound, other.upperBound);
331 return create(newLower, newUpper);
332 }
333
334 /**
335 * Returns an {@link ImmutableSortedSet} containing the same values in the given domain
336 * {@linkplain Range#contains contained} by this range.
337 *
338 * <p><b>Note:</b> {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For
339 * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty
340 * ranges {@code [3..3)} and {@code [4..4)}.
341 *
342 * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet} view of a large
343 * range (such as {@code Ranges.greaterThan(0)}). Certain operations on such a set can be
344 * performed efficiently, but others (such as {@link Set#hashCode} or {@link
345 * Collections#frequency}) can cause major performance problems.
346 *
347 * <p>The returned set's {@link Object#toString} method returns a short-hand form of the set's
348 * contents, such as {@code "[1..100]}"}.
349 *
350 * @throws IllegalArgumentException if neither this range nor the domain has a lower bound, or if
351 * neither has an upper bound
352 */
353 // TODO(kevinb): commit in spec to which methods are efficient?
354 @GwtCompatible(serializable = false)
355 public ContiguousSet<C> asSet(DiscreteDomain<C> domain) {
356 checkNotNull(domain);
357 Range<C> effectiveRange = this;
358 try {
359 if (!hasLowerBound()) {
360 effectiveRange = effectiveRange.intersection(Ranges.atLeast(domain.minValue()));
361 }
362 if (!hasUpperBound()) {
363 effectiveRange = effectiveRange.intersection(Ranges.atMost(domain.maxValue()));
364 }
365 } catch (NoSuchElementException e) {
366 throw new IllegalArgumentException(e);
367 }
368
369 // Per class spec, we are allowed to throw CCE if necessary
370 boolean empty = effectiveRange.isEmpty()
371 || compareOrThrow(
372 lowerBound.leastValueAbove(domain),
373 upperBound.greatestValueBelow(domain)) > 0;
374
375 return empty
376 ? new EmptyContiguousSet<C>(domain)
377 : new RegularContiguousSet<C>(effectiveRange, domain);
378 }
379
380 /**
381 * Returns the canonical form of this range in the given domain. The canonical form has the
382 * following properties:
383 *
384 * <ul>
385 * <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for all {@code v} (in other
386 * words, {@code a.canonical(domain).asSet(domain).equals(a.asSet(domain))}
387 * <li>uniqueness: unless {@code a.isEmpty()}, {@code a.asSet(domain).equals(b.asSet(domain))}
388 * implies {@code a.canonical(domain).equals(b.canonical(domain))}
389 * <li>idempotence: {@code a.canonical(domain).canonical(domain).equals(a.canonical(domain))}
390 * </ul>
391 *
392 * Furthermore, this method guarantees that the range returned will be one of the following
393 * canonical forms:
394 *
395 * <ul>
396 * <li>[start..end)
397 * <li>[start..+∞)
398 * <li>(-∞..end) (only if type {@code C} is unbounded below)
399 * <li>(-∞..+∞) (only if type {@code C} is unbounded below)
400 * </ul>
401 */
402 public Range<C> canonical(DiscreteDomain<C> domain) {
403 checkNotNull(domain);
404 Cut<C> lower = lowerBound.canonical(domain);
405 Cut<C> upper = upperBound.canonical(domain);
406 return (lower == lowerBound && upper == upperBound) ? this : create(lower, upper);
407 }
408
409 /**
410 * Returns {@code true} if {@code object} is a range having the same endpoints and bound types as
411 * this range. Note that discrete ranges such as {@code (1..4)} and {@code [2..3]} are <b>not</b>
412 * equal to one another, despite the fact that they each contain precisely the same set of values.
413 * Similarly, empty ranges are not equal unless they have exactly the same representation, so
414 * {@code [3..3)}, {@code (3..3]}, {@code (4..4]} are all unequal.
415 */
416 @Override public boolean equals(@Nullable Object object) {
417 if (object instanceof Range) {
418 Range<?> other = (Range<?>) object;
419 return lowerBound.equals(other.lowerBound)
420 && upperBound.equals(other.upperBound);
421 }
422 return false;
423 }
424
425 /** Returns a hash code for this range. */
426 @Override public int hashCode() {
427 return lowerBound.hashCode() * 31 + upperBound.hashCode();
428 }
429
430 /**
431 * Returns a string representation of this range, such as {@code "[3..5)"} (other examples are
432 * listed in the class documentation).
433 */
434 @Override public String toString() {
435 return toString(lowerBound, upperBound);
436 }
437
438 private static String toString(Cut<?> lowerBound, Cut<?> upperBound) {
439 StringBuilder sb = new StringBuilder(16);
440 lowerBound.describeAsLowerBound(sb);
441 sb.append('\u2025');
442 upperBound.describeAsUpperBound(sb);
443 return sb.toString();
444 }
445
446 /**
447 * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
448 */
449 private static <T> SortedSet<T> cast(Iterable<T> iterable) {
450 return (SortedSet<T>) iterable;
451 }
452
453 @SuppressWarnings("unchecked") // this method may throw CCE
454 static int compareOrThrow(Comparable left, Comparable right) {
455 return left.compareTo(right);
456 }
457
458 private static final long serialVersionUID = 0;
459 }