1 /*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20
21 import com.google.common.annotations.GwtCompatible;
22 import com.google.common.base.Equivalence;
23 import com.google.common.base.Function;
24 import com.google.common.base.Predicate;
25 import java.io.Serializable;
26 import java.util.Comparator;
27 import java.util.Iterator;
28 import java.util.NoSuchElementException;
29 import java.util.SortedSet;
30 import org.checkerframework.checker.nullness.qual.Nullable;
31
32 /**
33 * A range (or "interval") defines the <i>boundaries</i> around a contiguous span of values of some
34 * {@code Comparable} type; for example, "integers from 1 to 100 inclusive." Note that it is not
35 * possible to <i>iterate</i> over these contained values. To do so, pass this range instance and an
36 * appropriate {@link DiscreteDomain} to {@link ContiguousSet#create}.
37 *
38 * <h3>Types of ranges</h3>
39 *
40 * <p>Each end of the range may be bounded or unbounded. If bounded, there is an associated
41 * <i>endpoint</i> value, and the range is considered to be either <i>open</i> (does not include the
42 * endpoint) or <i>closed</i> (includes the endpoint) on that side. With three possibilities on each
43 * side, this yields nine basic types of ranges, enumerated below. (Notation: a square bracket
44 * ({@code [ ]}) indicates that the range is closed on that side; a parenthesis ({@code ( )}) means
45 * it is either open or unbounded. The construct {@code {x | statement}} is read "the set of all
46 * <i>x</i> such that <i>statement</i>.")
47 *
48 * <blockquote>
49 *
50 * <table>
51 * <caption>Range Types</caption>
52 * <tr><th>Notation <th>Definition <th>Factory method
53 * <tr><td>{@code (a..b)} <td>{@code {x | a < x < b}} <td>{@link Range#open open}
54 * <tr><td>{@code [a..b]} <td>{@code {x | a <= x <= b}}<td>{@link Range#closed closed}
55 * <tr><td>{@code (a..b]} <td>{@code {x | a < x <= b}} <td>{@link Range#openClosed openClosed}
56 * <tr><td>{@code [a..b)} <td>{@code {x | a <= x < b}} <td>{@link Range#closedOpen closedOpen}
57 * <tr><td>{@code (a..+?)} <td>{@code {x | x > a}} <td>{@link Range#greaterThan greaterThan}
58 * <tr><td>{@code [a..+?)} <td>{@code {x | x >= a}} <td>{@link Range#atLeast atLeast}
59 * <tr><td>{@code (-?..b)} <td>{@code {x | x < b}} <td>{@link Range#lessThan lessThan}
60 * <tr><td>{@code (-?..b]} <td>{@code {x | x <= b}} <td>{@link Range#atMost atMost}
61 * <tr><td>{@code (-?..+?)}<td>{@code {x}} <td>{@link Range#all all}
62 * </table>
63 *
64 * </blockquote>
65 *
66 * <p>When both endpoints exist, the upper endpoint may not be less than the lower. The endpoints
67 * may be equal only if at least one of the bounds is closed:
68 *
69 * <ul>
70 * <li>{@code [a..a]} : a singleton range
71 * <li>{@code [a..a); (a..a]} : {@linkplain #isEmpty empty} ranges; also valid
72 * <li>{@code (a..a)} : <b>invalid</b>; an exception will be thrown
73 * </ul>
74 *
75 * <h3>Warnings</h3>
76 *
77 * <ul>
78 * <li>Use immutable value types only, if at all possible. If you must use a mutable type, <b>do
79 * not</b> allow the endpoint instances to mutate after the range is created!
80 * <li>Your value type's comparison method should be {@linkplain Comparable consistent with
81 * equals} if at all possible. Otherwise, be aware that concepts used throughout this
82 * documentation such as "equal", "same", "unique" and so on actually refer to whether {@link
83 * Comparable#compareTo compareTo} returns zero, not whether {@link Object#equals equals}
84 * returns {@code true}.
85 * <li>A class which implements {@code Comparable<UnrelatedType>} is very broken, and will cause
86 * undefined horrible things to happen in {@code Range}. For now, the Range API does not
87 * prevent its use, because this would also rule out all ungenerified (pre-JDK1.5) data types.
88 * <b>This may change in the future.</b>
89 * </ul>
90 *
91 * <h3>Other notes</h3>
92 *
93 * <ul>
94 * <li>All ranges are shallow-immutable.
95 * <li>Instances of this type are obtained using the static factory methods in this class.
96 * <li>Ranges are <i>convex</i>: whenever two values are contained, all values in between them
97 * must also be contained. More formally, for any {@code c1 <= c2 <= c3} of type {@code C},
98 * {@code r.contains(c1) && r.contains(c3)} implies {@code r.contains(c2)}). This means that a
99 * {@code Range<Integer>} can never be used to represent, say, "all <i>prime</i> numbers from
100 * 1 to 100."
101 * <li>When evaluated as a {@link Predicate}, a range yields the same result as invoking {@link
102 * #contains}.
103 * <li>Terminology note: a range {@code a} is said to be the <i>maximal</i> range having property
104 * <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code a.encloses(b)}.
105 * Likewise, {@code a} is <i>minimal</i> when {@code b.encloses(a)} for all {@code b} having
106 * property <i>P</i>. See, for example, the definition of {@link #intersection intersection}.
107 * </ul>
108 *
109 * <h3>Further reading</h3>
110 *
111 * <p>See the Guava User Guide article on <a
112 * href="https://github.com/google/guava/wiki/RangesExplained">{@code Range}</a>.
113 *
114 * @author Kevin Bourrillion
115 * @author Gregory Kick
116 * @since 10.0
117 */
118 @GwtCompatible
119 @SuppressWarnings("rawtypes")
120 public final class Range<C extends Comparable> extends RangeGwtSerializationDependencies
121 implements Predicate<C>, Serializable {
122
123 static class LowerBoundFn implements Function<Range, Cut> {
124 static final LowerBoundFn INSTANCE = new LowerBoundFn();
125
126 @Override
127 public Cut apply(Range range) {
128 return range.lowerBound;
129 }
130 }
131
132 static class UpperBoundFn implements Function<Range, Cut> {
133 static final UpperBoundFn INSTANCE = new UpperBoundFn();
134
135 @Override
136 public Cut apply(Range range) {
137 return range.upperBound;
138 }
139 }
140
141 @SuppressWarnings("unchecked")
142 static <C extends Comparable<?>> Function<Range<C>, Cut<C>> lowerBoundFn() {
143 return (Function) LowerBoundFn.INSTANCE;
144 }
145
146 @SuppressWarnings("unchecked")
147 static <C extends Comparable<?>> Function<Range<C>, Cut<C>> upperBoundFn() {
148 return (Function) UpperBoundFn.INSTANCE;
149 }
150
151 static <C extends Comparable<?>> Ordering<Range<C>> rangeLexOrdering() {
152 return (Ordering<Range<C>>) (Ordering) RangeLexOrdering.INSTANCE;
153 }
154
155 static <C extends Comparable<?>> Range<C> create(Cut<C> lowerBound, Cut<C> upperBound) {
156 return new Range<C>(lowerBound, upperBound);
157 }
158
159 /**
160 * Returns a range that contains all values strictly greater than {@code lower} and strictly less
161 * than {@code upper}.
162 *
163 * @throws IllegalArgumentException if {@code lower} is greater than <i>or equal to</i> {@code
164 * upper}
165 * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable
166 * @since 14.0
167 */
168 public static <C extends Comparable<?>> Range<C> open(C lower, C upper) {
169 return create(Cut.aboveValue(lower), Cut.belowValue(upper));
170 }
171
172 /**
173 * Returns a range that contains all values greater than or equal to {@code lower} and less than
174 * or equal to {@code upper}.
175 *
176 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
177 * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable
178 * @since 14.0
179 */
180 public static <C extends Comparable<?>> Range<C> closed(C lower, C upper) {
181 return create(Cut.belowValue(lower), Cut.aboveValue(upper));
182 }
183
184 /**
185 * Returns a range that contains all values greater than or equal to {@code lower} and strictly
186 * less than {@code upper}.
187 *
188 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
189 * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable
190 * @since 14.0
191 */
192 public static <C extends Comparable<?>> Range<C> closedOpen(C lower, C upper) {
193 return create(Cut.belowValue(lower), Cut.belowValue(upper));
194 }
195
196 /**
197 * Returns a range that contains all values strictly greater than {@code lower} and less than or
198 * equal to {@code upper}.
199 *
200 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
201 * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable
202 * @since 14.0
203 */
204 public static <C extends Comparable<?>> Range<C> openClosed(C lower, C upper) {
205 return create(Cut.aboveValue(lower), Cut.aboveValue(upper));
206 }
207
208 /**
209 * Returns a range that contains any value from {@code lower} to {@code upper}, where each
210 * endpoint may be either inclusive (closed) or exclusive (open).
211 *
212 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
213 * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable
214 * @since 14.0
215 */
216 public static <C extends Comparable<?>> Range<C> range(
217 C lower, BoundType lowerType, C upper, BoundType upperType) {
218 checkNotNull(lowerType);
219 checkNotNull(upperType);
220
221 Cut<C> lowerBound =
222 (lowerType == BoundType.OPEN) ? Cut.aboveValue(lower) : Cut.belowValue(lower);
223 Cut<C> upperBound =
224 (upperType == BoundType.OPEN) ? Cut.belowValue(upper) : Cut.aboveValue(upper);
225 return create(lowerBound, upperBound);
226 }
227
228 /**
229 * Returns a range that contains all values strictly less than {@code endpoint}.
230 *
231 * @since 14.0
232 */
233 public static <C extends Comparable<?>> Range<C> lessThan(C endpoint) {
234 return create(Cut.<C>belowAll(), Cut.belowValue(endpoint));
235 }
236
237 /**
238 * Returns a range that contains all values less than or equal to {@code endpoint}.
239 *
240 * @since 14.0
241 */
242 public static <C extends Comparable<?>> Range<C> atMost(C endpoint) {
243 return create(Cut.<C>belowAll(), Cut.aboveValue(endpoint));
244 }
245
246 /**
247 * Returns a range with no lower bound up to the given endpoint, which may be either inclusive
248 * (closed) or exclusive (open).
249 *
250 * @since 14.0
251 */
252 public static <C extends Comparable<?>> Range<C> upTo(C endpoint, BoundType boundType) {
253 switch (boundType) {
254 case OPEN:
255 return lessThan(endpoint);
256 case CLOSED:
257 return atMost(endpoint);
258 default:
259 throw new AssertionError();
260 }
261 }
262
263 /**
264 * Returns a range that contains all values strictly greater than {@code endpoint}.
265 *
266 * @since 14.0
267 */
268 public static <C extends Comparable<?>> Range<C> greaterThan(C endpoint) {
269 return create(Cut.aboveValue(endpoint), Cut.<C>aboveAll());
270 }
271
272 /**
273 * Returns a range that contains all values greater than or equal to {@code endpoint}.
274 *
275 * @since 14.0
276 */
277 public static <C extends Comparable<?>> Range<C> atLeast(C endpoint) {
278 return create(Cut.belowValue(endpoint), Cut.<C>aboveAll());
279 }
280
281 /**
282 * Returns a range from the given endpoint, which may be either inclusive (closed) or exclusive
283 * (open), with no upper bound.
284 *
285 * @since 14.0
286 */
287 public static <C extends Comparable<?>> Range<C> downTo(C endpoint, BoundType boundType) {
288 switch (boundType) {
289 case OPEN:
290 return greaterThan(endpoint);
291 case CLOSED:
292 return atLeast(endpoint);
293 default:
294 throw new AssertionError();
295 }
296 }
297
298 private static final Range<Comparable> ALL = new Range<>(Cut.belowAll(), Cut.aboveAll());
299
300 /**
301 * Returns a range that contains every value of type {@code C}.
302 *
303 * @since 14.0
304 */
305 @SuppressWarnings("unchecked")
306 public static <C extends Comparable<?>> Range<C> all() {
307 return (Range) ALL;
308 }
309
310 /**
311 * Returns a range that {@linkplain Range#contains(Comparable) contains} only the given value. The
312 * returned range is {@linkplain BoundType#CLOSED closed} on both ends.
313 *
314 * @since 14.0
315 */
316 public static <C extends Comparable<?>> Range<C> singleton(C value) {
317 return closed(value, value);
318 }
319
320 /**
321 * Returns the minimal range that {@linkplain Range#contains(Comparable) contains} all of the
322 * given values. The returned range is {@linkplain BoundType#CLOSED closed} on both ends.
323 *
324 * @throws ClassCastException if the values are not mutually comparable
325 * @throws NoSuchElementException if {@code values} is empty
326 * @throws NullPointerException if any of {@code values} is null
327 * @since 14.0
328 */
329 public static <C extends Comparable<?>> Range<C> encloseAll(Iterable<C> values) {
330 checkNotNull(values);
331 if (values instanceof SortedSet) {
332 SortedSet<? extends C> set = cast(values);
333 Comparator<?> comparator = set.comparator();
334 if (Ordering.natural().equals(comparator) || comparator == null) {
335 return closed(set.first(), set.last());
336 }
337 }
338 Iterator<C> valueIterator = values.iterator();
339 C min = checkNotNull(valueIterator.next());
340 C max = min;
341 while (valueIterator.hasNext()) {
342 C value = checkNotNull(valueIterator.next());
343 min = Ordering.natural().min(min, value);
344 max = Ordering.natural().max(max, value);
345 }
346 return closed(min, max);
347 }
348
349 final Cut<C> lowerBound;
350 final Cut<C> upperBound;
351
352 private Range(Cut<C> lowerBound, Cut<C> upperBound) {
353 this.lowerBound = checkNotNull(lowerBound);
354 this.upperBound = checkNotNull(upperBound);
355 if (lowerBound.compareTo(upperBound) > 0
356 || lowerBound == Cut.<C>aboveAll()
357 || upperBound == Cut.<C>belowAll()) {
358 throw new IllegalArgumentException("Invalid range: " + toString(lowerBound, upperBound));
359 }
360 }
361
362 /** Returns {@code true} if this range has a lower endpoint. */
363 public boolean hasLowerBound() {
364 return lowerBound != Cut.belowAll();
365 }
366
367 /**
368 * Returns the lower endpoint of this range.
369 *
370 * @throws IllegalStateException if this range is unbounded below (that is, {@link
371 * #hasLowerBound()} returns {@code false})
372 */
373 public C lowerEndpoint() {
374 return lowerBound.endpoint();
375 }
376
377 /**
378 * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if the range includes
379 * its lower endpoint, {@link BoundType#OPEN} if it does not.
380 *
381 * @throws IllegalStateException if this range is unbounded below (that is, {@link
382 * #hasLowerBound()} returns {@code false})
383 */
384 public BoundType lowerBoundType() {
385 return lowerBound.typeAsLowerBound();
386 }
387
388 /** Returns {@code true} if this range has an upper endpoint. */
389 public boolean hasUpperBound() {
390 return upperBound != Cut.aboveAll();
391 }
392
393 /**
394 * Returns the upper endpoint of this range.
395 *
396 * @throws IllegalStateException if this range is unbounded above (that is, {@link
397 * #hasUpperBound()} returns {@code false})
398 */
399 public C upperEndpoint() {
400 return upperBound.endpoint();
401 }
402
403 /**
404 * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if the range includes
405 * its upper endpoint, {@link BoundType#OPEN} if it does not.
406 *
407 * @throws IllegalStateException if this range is unbounded above (that is, {@link
408 * #hasUpperBound()} returns {@code false})
409 */
410 public BoundType upperBoundType() {
411 return upperBound.typeAsUpperBound();
412 }
413
414 /**
415 * Returns {@code true} if this range is of the form {@code [v..v)} or {@code (v..v]}. (This does
416 * not encompass ranges of the form {@code (v..v)}, because such ranges are <i>invalid</i> and
417 * can't be constructed at all.)
418 *
419 * <p>Note that certain discrete ranges such as the integer range {@code (3..4)} are <b>not</b>
420 * considered empty, even though they contain no actual values. In these cases, it may be helpful
421 * to preprocess ranges with {@link #canonical(DiscreteDomain)}.
422 */
423 public boolean isEmpty() {
424 return lowerBound.equals(upperBound);
425 }
426
427 /**
428 * Returns {@code true} if {@code value} is within the bounds of this range. For example, on the
429 * range {@code [0..2)}, {@code contains(1)} returns {@code true}, while {@code contains(2)}
430 * returns {@code false}.
431 */
432 public boolean contains(C value) {
433 checkNotNull(value);
434 // let this throw CCE if there is some trickery going on
435 return lowerBound.isLessThan(value) && !upperBound.isLessThan(value);
436 }
437
438 /**
439 * @deprecated Provided only to satisfy the {@link Predicate} interface; use {@link #contains}
440 * instead.
441 */
442 @Deprecated
443 @Override
444 public boolean apply(C input) {
445 return contains(input);
446 }
447
448 /**
449 * Returns {@code true} if every element in {@code values} is {@linkplain #contains contained} in
450 * this range.
451 */
452 public boolean containsAll(Iterable<? extends C> values) {
453 if (Iterables.isEmpty(values)) {
454 return true;
455 }
456
457 // this optimizes testing equality of two range-backed sets
458 if (values instanceof SortedSet) {
459 SortedSet<? extends C> set = cast(values);
460 Comparator<?> comparator = set.comparator();
461 if (Ordering.natural().equals(comparator) || comparator == null) {
462 return contains(set.first()) && contains(set.last());
463 }
464 }
465
466 for (C value : values) {
467 if (!contains(value)) {
468 return false;
469 }
470 }
471 return true;
472 }
473
474 /**
475 * Returns {@code true} if the bounds of {@code other} do not extend outside the bounds of this
476 * range. Examples:
477 *
478 * <ul>
479 * <li>{@code [3..6]} encloses {@code [4..5]}
480 * <li>{@code (3..6)} encloses {@code (3..6)}
481 * <li>{@code [3..6]} encloses {@code [4..4)} (even though the latter is empty)
482 * <li>{@code (3..6]} does not enclose {@code [3..6]}
483 * <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains every value
484 * contained by the latter range)
485 * <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains every value
486 * contained by the latter range)
487 * </ul>
488 *
489 * <p>Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies {@code
490 * a.contains(v)}, but as the last two examples illustrate, the converse is not always true.
491 *
492 * <p>Being reflexive, antisymmetric and transitive, the {@code encloses} relation defines a
493 * <i>partial order</i> over ranges. There exists a unique {@linkplain Range#all maximal} range
494 * according to this relation, and also numerous {@linkplain #isEmpty minimal} ranges. Enclosure
495 * also implies {@linkplain #isConnected connectedness}.
496 */
497 public boolean encloses(Range<C> other) {
498 return lowerBound.compareTo(other.lowerBound) <= 0
499 && upperBound.compareTo(other.upperBound) >= 0;
500 }
501
502 /**
503 * Returns {@code true} if there exists a (possibly empty) range which is {@linkplain #encloses
504 * enclosed} by both this range and {@code other}.
505 *
506 * <p>For example,
507 *
508 * <ul>
509 * <li>{@code [2, 4)} and {@code [5, 7)} are not connected
510 * <li>{@code [2, 4)} and {@code [3, 5)} are connected, because both enclose {@code [3, 4)}
511 * <li>{@code [2, 4)} and {@code [4, 6)} are connected, because both enclose the empty range
512 * {@code [4, 4)}
513 * </ul>
514 *
515 * <p>Note that this range and {@code other} have a well-defined {@linkplain #span union} and
516 * {@linkplain #intersection intersection} (as a single, possibly-empty range) if and only if this
517 * method returns {@code true}.
518 *
519 * <p>The connectedness relation is both reflexive and symmetric, but does not form an {@linkplain
520 * Equivalence equivalence relation} as it is not transitive.
521 *
522 * <p>Note that certain discrete ranges are not considered connected, even though there are no
523 * elements "between them." For example, {@code [3, 5]} is not considered connected to {@code [6,
524 * 10]}. In these cases, it may be desirable for both input ranges to be preprocessed with {@link
525 * #canonical(DiscreteDomain)} before testing for connectedness.
526 */
527 public boolean isConnected(Range<C> other) {
528 return lowerBound.compareTo(other.upperBound) <= 0
529 && other.lowerBound.compareTo(upperBound) <= 0;
530 }
531
532 /**
533 * Returns the maximal range {@linkplain #encloses enclosed} by both this range and {@code
534 * connectedRange}, if such a range exists.
535 *
536 * <p>For example, the intersection of {@code [1..5]} and {@code (3..7)} is {@code (3..5]}. The
537 * resulting range may be empty; for example, {@code [1..5)} intersected with {@code [5..7)}
538 * yields the empty range {@code [5..5)}.
539 *
540 * <p>The intersection exists if and only if the two ranges are {@linkplain #isConnected
541 * connected}.
542 *
543 * <p>The intersection operation is commutative, associative and idempotent, and its identity
544 * element is {@link Range#all}).
545 *
546 * @throws IllegalArgumentException if {@code isConnected(connectedRange)} is {@code false}
547 */
548 public Range<C> intersection(Range<C> connectedRange) {
549 int lowerCmp = lowerBound.compareTo(connectedRange.lowerBound);
550 int upperCmp = upperBound.compareTo(connectedRange.upperBound);
551 if (lowerCmp >= 0 && upperCmp <= 0) {
552 return this;
553 } else if (lowerCmp <= 0 && upperCmp >= 0) {
554 return connectedRange;
555 } else {
556 Cut<C> newLower = (lowerCmp >= 0) ? lowerBound : connectedRange.lowerBound;
557 Cut<C> newUpper = (upperCmp <= 0) ? upperBound : connectedRange.upperBound;
558 return create(newLower, newUpper);
559 }
560 }
561
562 /**
563 * Returns the maximal range lying between this range and {@code otherRange}, if such a range
564 * exists. The resulting range may be empty if the two ranges are adjacent but non-overlapping.
565 *
566 * <p>For example, the gap of {@code [1..5]} and {@code (7..10)} is {@code (5..7]}. The resulting
567 * range may be empty; for example, the gap between {@code [1..5)} {@code [5..7)} yields the empty
568 * range {@code [5..5)}.
569 *
570 * <p>The gap exists if and only if the two ranges are either disconnected or immediately adjacent
571 * (any intersection must be an empty range).
572 *
573 * <p>The gap operation is commutative.
574 *
575 * @throws IllegalArgumentException if this range and {@code otherRange} have a nonempty
576 * intersection
577 * @since 27.0
578 */
579 public Range<C> gap(Range<C> otherRange) {
580 /*
581 * For an explanation of the basic principle behind this check, see
582 * https://stackoverflow.com/a/35754308/28465
583 *
584 * In that explanation's notation, our `overlap` check would be `x1 < y2 && y1 < x2`. We've
585 * flipped one part of the check so that we're using "less than" in both cases (rather than a
586 * mix of "less than" and "greater than"). We've also switched to "strictly less than" rather
587 * than "less than or equal to" because of *handwave* the difference between "endpoints of
588 * inclusive ranges" and "Cuts."
589 */
590 if (lowerBound.compareTo(otherRange.upperBound) < 0
591 && otherRange.lowerBound.compareTo(upperBound) < 0) {
592 throw new IllegalArgumentException(
593 "Ranges have a nonempty intersection: " + this + ", " + otherRange);
594 }
595
596 boolean isThisFirst = this.lowerBound.compareTo(otherRange.lowerBound) < 0;
597 Range<C> firstRange = isThisFirst ? this : otherRange;
598 Range<C> secondRange = isThisFirst ? otherRange : this;
599 return create(firstRange.upperBound, secondRange.lowerBound);
600 }
601
602 /**
603 * Returns the minimal range that {@linkplain #encloses encloses} both this range and {@code
604 * other}. For example, the span of {@code [1..3]} and {@code (5..7)} is {@code [1..7)}.
605 *
606 * <p><i>If</i> the input ranges are {@linkplain #isConnected connected}, the returned range can
607 * also be called their <i>union</i>. If they are not, note that the span might contain values
608 * that are not contained in either input range.
609 *
610 * <p>Like {@link #intersection(Range) intersection}, this operation is commutative, associative
611 * and idempotent. Unlike it, it is always well-defined for any two input ranges.
612 */
613 public Range<C> span(Range<C> other) {
614 int lowerCmp = lowerBound.compareTo(other.lowerBound);
615 int upperCmp = upperBound.compareTo(other.upperBound);
616 if (lowerCmp <= 0 && upperCmp >= 0) {
617 return this;
618 } else if (lowerCmp >= 0 && upperCmp <= 0) {
619 return other;
620 } else {
621 Cut<C> newLower = (lowerCmp <= 0) ? lowerBound : other.lowerBound;
622 Cut<C> newUpper = (upperCmp >= 0) ? upperBound : other.upperBound;
623 return create(newLower, newUpper);
624 }
625 }
626
627 /**
628 * Returns the canonical form of this range in the given domain. The canonical form has the
629 * following properties:
630 *
631 * <ul>
632 * <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for all {@code v} (in
633 * other words, {@code ContiguousSet.create(a.canonical(domain), domain).equals(
634 * ContiguousSet.create(a, domain))}
635 * <li>uniqueness: unless {@code a.isEmpty()}, {@code ContiguousSet.create(a,
636 * domain).equals(ContiguousSet.create(b, domain))} implies {@code
637 * a.canonical(domain).equals(b.canonical(domain))}
638 * <li>idempotence: {@code a.canonical(domain).canonical(domain).equals(a.canonical(domain))}
639 * </ul>
640 *
641 * <p>Furthermore, this method guarantees that the range returned will be one of the following
642 * canonical forms:
643 *
644 * <ul>
645 * <li>[start..end)
646 * <li>[start..+?)
647 * <li>(-?..end) (only if type {@code C} is unbounded below)
648 * <li>(-?..+?) (only if type {@code C} is unbounded below)
649 * </ul>
650 */
651 public Range<C> canonical(DiscreteDomain<C> domain) {
652 checkNotNull(domain);
653 Cut<C> lower = lowerBound.canonical(domain);
654 Cut<C> upper = upperBound.canonical(domain);
655 return (lower == lowerBound && upper == upperBound) ? this : create(lower, upper);
656 }
657
658 /**
659 * Returns {@code true} if {@code object} is a range having the same endpoints and bound types as
660 * this range. Note that discrete ranges such as {@code (1..4)} and {@code [2..3]} are <b>not</b>
661 * equal to one another, despite the fact that they each contain precisely the same set of values.
662 * Similarly, empty ranges are not equal unless they have exactly the same representation, so
663 * {@code [3..3)}, {@code (3..3]}, {@code (4..4]} are all unequal.
664 */
665 @Override
666 public boolean equals(@Nullable Object object) {
667 if (object instanceof Range) {
668 Range<?> other = (Range<?>) object;
669 return lowerBound.equals(other.lowerBound) && upperBound.equals(other.upperBound);
670 }
671 return false;
672 }
673
674 /** Returns a hash code for this range. */
675 @Override
676 public int hashCode() {
677 return lowerBound.hashCode() * 31 + upperBound.hashCode();
678 }
679
680 /**
681 * Returns a string representation of this range, such as {@code "[3..5)"} (other examples are
682 * listed in the class documentation).
683 */
684 @Override
685 public String toString() {
686 return toString(lowerBound, upperBound);
687 }
688
689 private static String toString(Cut<?> lowerBound, Cut<?> upperBound) {
690 StringBuilder sb = new StringBuilder(16);
691 lowerBound.describeAsLowerBound(sb);
692 sb.append("..");
693 upperBound.describeAsUpperBound(sb);
694 return sb.toString();
695 }
696
697 /** Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 */
698 private static <T> SortedSet<T> cast(Iterable<T> iterable) {
699 return (SortedSet<T>) iterable;
700 }
701
702 Object readResolve() {
703 if (this.equals(ALL)) {
704 return all();
705 } else {
706 return this;
707 }
708 }
709
710 @SuppressWarnings("unchecked") // this method may throw CCE
711 static int compareOrThrow(Comparable left, Comparable right) {
712 return left.compareTo(right);
713 }
714
715 /** Needed to serialize sorted collections of Ranges. */
716 private static class RangeLexOrdering extends Ordering<Range<?>> implements Serializable {
717 static final Ordering<Range<?>> INSTANCE = new RangeLexOrdering();
718
719 @Override
720 public int compare(Range<?> left, Range<?> right) {
721 return ComparisonChain.start()
722 .compare(left.lowerBound, right.lowerBound)
723 .compare(left.upperBound, right.upperBound)
724 .result();
725 }
726
727 private static final long serialVersionUID = 0;
728 }
729
730 private static final long serialVersionUID = 0;
731 }