View Javadoc
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 javax.annotation.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>Instances of this type are obtained using the static factory methods in this class.
95   *   <li>Ranges are <i>convex</i>: whenever two values are contained, all values in between them
96   *       must also be contained. More formally, for any {@code c1 <= c2 <= c3} of type {@code C},
97   *       {@code r.contains(c1) && r.contains(c3)} implies {@code r.contains(c2)}). This means that a
98   *       {@code Range<Integer>} can never be used to represent, say, "all <i>prime</i> numbers from
99   *       1 to 100."
100  *   <li>When evaluated as a {@link Predicate}, a range yields the same result as invoking {@link
101  *       #contains}.
102  *   <li>Terminology note: a range {@code a} is said to be the <i>maximal</i> range having property
103  *       <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code a.encloses(b)}.
104  *       Likewise, {@code a} is <i>minimal</i> when {@code b.encloses(a)} for all {@code b} having
105  *       property <i>P</i>. See, for example, the definition of {@link #intersection intersection}.
106  * </ul>
107  *
108  * <h3>Further reading</h3>
109  *
110  * <p>See the Guava User Guide article on <a
111  * href="https://github.com/google/guava/wiki/RangesExplained">{@code Range}</a>.
112  *
113  * @author Kevin Bourrillion
114  * @author Gregory Kick
115  * @since 10.0
116  */
117 @GwtCompatible
118 @SuppressWarnings("rawtypes")
119 public final class Range<C extends Comparable> extends RangeGwtSerializationDependencies
120     implements Predicate<C>, Serializable {
121 
122   static class LowerBoundFn implements Function<Range, Cut> {
123     static final LowerBoundFn INSTANCE = new LowerBoundFn();
124     @Override
125     public Cut apply(Range range) {
126       return range.lowerBound;
127     }
128   }
129 
130   static class UpperBoundFn implements Function<Range, Cut> {
131     static final UpperBoundFn INSTANCE = new UpperBoundFn();
132     @Override
133     public Cut apply(Range range) {
134       return range.upperBound;
135     }
136   }
137 
138   @SuppressWarnings("unchecked")
139   static <C extends Comparable<?>> Function<Range<C>, Cut<C>> lowerBoundFn() {
140     return (Function) LowerBoundFn.INSTANCE;
141   }
142 
143   @SuppressWarnings("unchecked")
144   static <C extends Comparable<?>> Function<Range<C>, Cut<C>> upperBoundFn() {
145     return (Function) UpperBoundFn.INSTANCE;
146   }
147 
148   static <C extends Comparable<?>> Ordering<Range<C>> rangeLexOrdering() {
149     return (Ordering<Range<C>>) (Ordering) RangeLexOrdering.INSTANCE;
150   }
151 
152   static <C extends Comparable<?>> Range<C> create(Cut<C> lowerBound, Cut<C> upperBound) {
153     return new Range<C>(lowerBound, upperBound);
154   }
155 
156   /**
157    * Returns a range that contains all values strictly greater than {@code
158    * lower} and strictly less than {@code upper}.
159    *
160    * @throws IllegalArgumentException if {@code lower} is greater than <i>or
161    *     equal to</i> {@code upper}
162    * @since 14.0
163    */
164   public static <C extends Comparable<?>> Range<C> open(C lower, C upper) {
165     return create(Cut.aboveValue(lower), Cut.belowValue(upper));
166   }
167 
168   /**
169    * Returns a range that contains all values greater than or equal to
170    * {@code lower} and less than or equal to {@code upper}.
171    *
172    * @throws IllegalArgumentException if {@code lower} is greater than {@code
173    *     upper}
174    * @since 14.0
175    */
176   public static <C extends Comparable<?>> Range<C> closed(C lower, C upper) {
177     return create(Cut.belowValue(lower), Cut.aboveValue(upper));
178   }
179 
180   /**
181    * Returns a range that contains all values greater than or equal to
182    * {@code lower} and strictly less than {@code upper}.
183    *
184    * @throws IllegalArgumentException if {@code lower} is greater than {@code
185    *     upper}
186    * @since 14.0
187    */
188   public static <C extends Comparable<?>> Range<C> closedOpen(C lower, C upper) {
189     return create(Cut.belowValue(lower), Cut.belowValue(upper));
190   }
191 
192   /**
193    * Returns a range that contains all values strictly greater than {@code
194    * lower} and less than or equal to {@code upper}.
195    *
196    * @throws IllegalArgumentException if {@code lower} is greater than {@code
197    *     upper}
198    * @since 14.0
199    */
200   public static <C extends Comparable<?>> Range<C> openClosed(C lower, C upper) {
201     return create(Cut.aboveValue(lower), Cut.aboveValue(upper));
202   }
203 
204   /**
205    * Returns a range that contains any value from {@code lower} to {@code
206    * upper}, where each endpoint may be either inclusive (closed) or exclusive
207    * (open).
208    *
209    * @throws IllegalArgumentException if {@code lower} is greater than {@code
210    *     upper}
211    * @since 14.0
212    */
213   public static <C extends Comparable<?>> Range<C> range(
214       C lower, BoundType lowerType, C upper, BoundType upperType) {
215     checkNotNull(lowerType);
216     checkNotNull(upperType);
217 
218     Cut<C> lowerBound =
219         (lowerType == BoundType.OPEN) ? Cut.aboveValue(lower) : Cut.belowValue(lower);
220     Cut<C> upperBound =
221         (upperType == BoundType.OPEN) ? Cut.belowValue(upper) : Cut.aboveValue(upper);
222     return create(lowerBound, upperBound);
223   }
224 
225   /**
226    * Returns a range that contains all values strictly less than {@code
227    * endpoint}.
228    *
229    * @since 14.0
230    */
231   public static <C extends Comparable<?>> Range<C> lessThan(C endpoint) {
232     return create(Cut.<C>belowAll(), Cut.belowValue(endpoint));
233   }
234 
235   /**
236    * Returns a range that contains all values less than or equal to
237    * {@code endpoint}.
238    *
239    * @since 14.0
240    */
241   public static <C extends Comparable<?>> Range<C> atMost(C endpoint) {
242     return create(Cut.<C>belowAll(), Cut.aboveValue(endpoint));
243   }
244 
245   /**
246    * Returns a range with no lower bound up to the given endpoint, which may be
247    * either inclusive (closed) or exclusive (open).
248    *
249    * @since 14.0
250    */
251   public static <C extends Comparable<?>> Range<C> upTo(C endpoint, BoundType boundType) {
252     switch (boundType) {
253       case OPEN:
254         return lessThan(endpoint);
255       case CLOSED:
256         return atMost(endpoint);
257       default:
258         throw new AssertionError();
259     }
260   }
261 
262   /**
263    * Returns a range that contains all values strictly greater than {@code
264    * 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
274    * {@code endpoint}.
275    *
276    * @since 14.0
277    */
278   public static <C extends Comparable<?>> Range<C> atLeast(C endpoint) {
279     return create(Cut.belowValue(endpoint), Cut.<C>aboveAll());
280   }
281 
282   /**
283    * Returns a range from the given endpoint, which may be either inclusive
284    * (closed) or exclusive (open), with no upper bound.
285    *
286    * @since 14.0
287    */
288   public static <C extends Comparable<?>> Range<C> downTo(C endpoint, BoundType boundType) {
289     switch (boundType) {
290       case OPEN:
291         return greaterThan(endpoint);
292       case CLOSED:
293         return atLeast(endpoint);
294       default:
295         throw new AssertionError();
296     }
297   }
298 
299   private static final Range<Comparable> ALL = new Range<>(Cut.belowAll(), Cut.aboveAll());
300 
301   /**
302    * Returns a range that contains every value of type {@code C}.
303    *
304    * @since 14.0
305    */
306   @SuppressWarnings("unchecked")
307   public static <C extends Comparable<?>> Range<C> all() {
308     return (Range) ALL;
309   }
310 
311   /**
312    * Returns a range that {@linkplain Range#contains(Comparable) contains} only
313    * the given value. The returned range is {@linkplain BoundType#CLOSED closed}
314    * on both ends.
315    *
316    * @since 14.0
317    */
318   public static <C extends Comparable<?>> Range<C> singleton(C value) {
319     return closed(value, value);
320   }
321 
322   /**
323    * Returns the minimal range that
324    * {@linkplain Range#contains(Comparable) contains} all of the given values.
325    * The returned range is {@linkplain BoundType#CLOSED closed} on both ends.
326    *
327    * @throws ClassCastException if the parameters are not <i>mutually
328    *     comparable</i>
329    * @throws NoSuchElementException if {@code values} is empty
330    * @throws NullPointerException if any of {@code values} is null
331    * @since 14.0
332    */
333   public static <C extends Comparable<?>> Range<C> encloseAll(Iterable<C> values) {
334     checkNotNull(values);
335     if (values instanceof SortedSet) {
336       SortedSet<? extends C> set = cast(values);
337       Comparator<?> comparator = set.comparator();
338       if (Ordering.natural().equals(comparator) || comparator == null) {
339         return closed(set.first(), set.last());
340       }
341     }
342     Iterator<C> valueIterator = values.iterator();
343     C min = checkNotNull(valueIterator.next());
344     C max = min;
345     while (valueIterator.hasNext()) {
346       C value = checkNotNull(valueIterator.next());
347       min = Ordering.natural().min(min, value);
348       max = Ordering.natural().max(max, value);
349     }
350     return closed(min, max);
351   }
352 
353   final Cut<C> lowerBound;
354   final Cut<C> upperBound;
355 
356   private Range(Cut<C> lowerBound, Cut<C> upperBound) {
357     this.lowerBound = checkNotNull(lowerBound);
358     this.upperBound = checkNotNull(upperBound);
359     if (lowerBound.compareTo(upperBound) > 0
360         || lowerBound == Cut.<C>aboveAll()
361         || upperBound == Cut.<C>belowAll()) {
362       throw new IllegalArgumentException("Invalid range: " + toString(lowerBound, upperBound));
363     }
364   }
365 
366   /**
367    * Returns {@code true} if this range has a lower endpoint.
368    */
369   public boolean hasLowerBound() {
370     return lowerBound != Cut.belowAll();
371   }
372 
373   /**
374    * Returns the lower endpoint of this range.
375    *
376    * @throws IllegalStateException if this range is unbounded below (that is, {@link
377    *     #hasLowerBound()} returns {@code false})
378    */
379   public C lowerEndpoint() {
380     return lowerBound.endpoint();
381   }
382 
383   /**
384    * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if the range includes
385    * its lower endpoint, {@link BoundType#OPEN} if it does not.
386    *
387    * @throws IllegalStateException if this range is unbounded below (that is, {@link
388    *     #hasLowerBound()} returns {@code false})
389    */
390   public BoundType lowerBoundType() {
391     return lowerBound.typeAsLowerBound();
392   }
393 
394   /**
395    * Returns {@code true} if this range has an upper endpoint.
396    */
397   public boolean hasUpperBound() {
398     return upperBound != Cut.aboveAll();
399   }
400 
401   /**
402    * Returns the upper endpoint of this range.
403    *
404    * @throws IllegalStateException if this range is unbounded above (that is, {@link
405    *     #hasUpperBound()} returns {@code false})
406    */
407   public C upperEndpoint() {
408     return upperBound.endpoint();
409   }
410 
411   /**
412    * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if the range includes
413    * its upper endpoint, {@link BoundType#OPEN} if it does not.
414    *
415    * @throws IllegalStateException if this range is unbounded above (that is, {@link
416    *     #hasUpperBound()} returns {@code false})
417    */
418   public BoundType upperBoundType() {
419     return upperBound.typeAsUpperBound();
420   }
421 
422   /**
423    * Returns {@code true} if this range is of the form {@code [v..v)} or {@code (v..v]}. (This does
424    * not encompass ranges of the form {@code (v..v)}, because such ranges are <i>invalid</i> and
425    * can't be constructed at all.)
426    *
427    * <p>Note that certain discrete ranges such as the integer range {@code (3..4)} are <b>not</b>
428    * considered empty, even though they contain no actual values.  In these cases, it may be
429    * helpful to preprocess ranges with {@link #canonical(DiscreteDomain)}.
430    */
431   public boolean isEmpty() {
432     return lowerBound.equals(upperBound);
433   }
434 
435   /**
436    * Returns {@code true} if {@code value} is within the bounds of this range. For example, on the
437    * range {@code [0..2)}, {@code contains(1)} returns {@code true}, while {@code contains(2)}
438    * returns {@code false}.
439    */
440   public boolean contains(C value) {
441     checkNotNull(value);
442     // let this throw CCE if there is some trickery going on
443     return lowerBound.isLessThan(value) && !upperBound.isLessThan(value);
444   }
445 
446   /**
447    * @deprecated Provided only to satisfy the {@link Predicate} interface; use {@link #contains}
448    *     instead.
449    */
450   @Deprecated
451   @Override
452   public boolean apply(C input) {
453     return contains(input);
454   }
455 
456   /**
457    * Returns {@code true} if every element in {@code values} is {@linkplain #contains contained} in
458    * this range.
459    */
460   public boolean containsAll(Iterable<? extends C> values) {
461     if (Iterables.isEmpty(values)) {
462       return true;
463     }
464 
465     // this optimizes testing equality of two range-backed sets
466     if (values instanceof SortedSet) {
467       SortedSet<? extends C> set = cast(values);
468       Comparator<?> comparator = set.comparator();
469       if (Ordering.natural().equals(comparator) || comparator == null) {
470         return contains(set.first()) && contains(set.last());
471       }
472     }
473 
474     for (C value : values) {
475       if (!contains(value)) {
476         return false;
477       }
478     }
479     return true;
480   }
481 
482   /**
483    * Returns {@code true} if the bounds of {@code other} do not extend outside the bounds of this
484    * range. Examples:
485    *
486    * <ul>
487    * <li>{@code [3..6]} encloses {@code [4..5]}
488    * <li>{@code (3..6)} encloses {@code (3..6)}
489    * <li>{@code [3..6]} encloses {@code [4..4)} (even though the latter is empty)
490    * <li>{@code (3..6]} does not enclose {@code [3..6]}
491    * <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains every value
492    *     contained by the latter range)
493    * <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains every value
494    *     contained by the latter range)
495    * </ul>
496    *
497    * <p>Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies
498    * {@code a.contains(v)}, but as the last two examples illustrate, the converse is not always
499    * true.
500    *
501    * <p>Being reflexive, antisymmetric and transitive, the {@code encloses} relation defines a
502    * <i>partial order</i> over ranges. There exists a unique {@linkplain Range#all maximal} range
503    * according to this relation, and also numerous {@linkplain #isEmpty minimal} ranges. Enclosure
504    * also implies {@linkplain #isConnected connectedness}.
505    */
506   public boolean encloses(Range<C> other) {
507     return lowerBound.compareTo(other.lowerBound) <= 0
508         && upperBound.compareTo(other.upperBound) >= 0;
509   }
510 
511   /**
512    * Returns {@code true} if there exists a (possibly empty) range which is {@linkplain #encloses
513    * enclosed} by both this range and {@code other}.
514    *
515    * <p>For example,
516    * <ul>
517    * <li>{@code [2, 4)} and {@code [5, 7)} are not connected
518    * <li>{@code [2, 4)} and {@code [3, 5)} are connected, because both enclose {@code [3, 4)}
519    * <li>{@code [2, 4)} and {@code [4, 6)} are connected, because both enclose the empty range
520    *     {@code [4, 4)}
521    * </ul>
522    *
523    * <p>Note that this range and {@code other} have a well-defined {@linkplain #span union} and
524    * {@linkplain #intersection intersection} (as a single, possibly-empty range) if and only if this
525    * method returns {@code true}.
526    *
527    * <p>The connectedness relation is both reflexive and symmetric, but does not form an {@linkplain
528    * Equivalence equivalence relation} as it is not transitive.
529    *
530    * <p>Note that certain discrete ranges are not considered connected, even though there are no
531    * elements "between them."  For example, {@code [3, 5]} is not considered connected to {@code
532    * [6, 10]}.  In these cases, it may be desirable for both input ranges to be preprocessed with
533    * {@link #canonical(DiscreteDomain)} before testing for connectedness.
534    */
535   public boolean isConnected(Range<C> other) {
536     return lowerBound.compareTo(other.upperBound) <= 0
537         && other.lowerBound.compareTo(upperBound) <= 0;
538   }
539 
540   /**
541    * Returns the maximal range {@linkplain #encloses enclosed} by both this range and {@code
542    * connectedRange}, if such a range exists.
543    *
544    * <p>For example, the intersection of {@code [1..5]} and {@code (3..7)} is {@code (3..5]}. The
545    * resulting range may be empty; for example, {@code [1..5)} intersected with {@code [5..7)}
546    * yields the empty range {@code [5..5)}.
547    *
548    * <p>The intersection exists if and only if the two ranges are {@linkplain #isConnected
549    * connected}.
550    *
551    * <p>The intersection operation is commutative, associative and idempotent, and its identity
552    * element is {@link Range#all}).
553    *
554    * @throws IllegalArgumentException if {@code isConnected(connectedRange)} is {@code false}
555    */
556   public Range<C> intersection(Range<C> connectedRange) {
557     int lowerCmp = lowerBound.compareTo(connectedRange.lowerBound);
558     int upperCmp = upperBound.compareTo(connectedRange.upperBound);
559     if (lowerCmp >= 0 && upperCmp <= 0) {
560       return this;
561     } else if (lowerCmp <= 0 && upperCmp >= 0) {
562       return connectedRange;
563     } else {
564       Cut<C> newLower = (lowerCmp >= 0) ? lowerBound : connectedRange.lowerBound;
565       Cut<C> newUpper = (upperCmp <= 0) ? upperBound : connectedRange.upperBound;
566       return create(newLower, newUpper);
567     }
568   }
569 
570   /**
571    * Returns the minimal range that {@linkplain #encloses encloses} both this range and {@code
572    * other}. For example, the span of {@code [1..3]} and {@code (5..7)} is {@code [1..7)}.
573    *
574    * <p><i>If</i> the input ranges are {@linkplain #isConnected connected}, the returned range can
575    * also be called their <i>union</i>. If they are not, note that the span might contain values
576    * that are not contained in either input range.
577    *
578    * <p>Like {@link #intersection(Range) intersection}, this operation is commutative, associative
579    * and idempotent. Unlike it, it is always well-defined for any two input ranges.
580    */
581   public Range<C> span(Range<C> other) {
582     int lowerCmp = lowerBound.compareTo(other.lowerBound);
583     int upperCmp = upperBound.compareTo(other.upperBound);
584     if (lowerCmp <= 0 && upperCmp >= 0) {
585       return this;
586     } else if (lowerCmp >= 0 && upperCmp <= 0) {
587       return other;
588     } else {
589       Cut<C> newLower = (lowerCmp <= 0) ? lowerBound : other.lowerBound;
590       Cut<C> newUpper = (upperCmp >= 0) ? upperBound : other.upperBound;
591       return create(newLower, newUpper);
592     }
593   }
594 
595   /**
596    * Returns the canonical form of this range in the given domain. The canonical form has the
597    * following properties:
598    *
599    * <ul>
600    * <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for all {@code v} (in other
601    *     words, {@code ContiguousSet.create(a.canonical(domain), domain).equals(
602    *     ContiguousSet.create(a, domain))}
603    * <li>uniqueness: unless {@code a.isEmpty()},
604    *     {@code ContiguousSet.create(a, domain).equals(ContiguousSet.create(b, domain))} implies
605    *     {@code a.canonical(domain).equals(b.canonical(domain))}
606    * <li>idempotence: {@code a.canonical(domain).canonical(domain).equals(a.canonical(domain))}
607    * </ul>
608    *
609    * <p>Furthermore, this method guarantees that the range returned will be one of the following
610    * canonical forms:
611    *
612    * <ul>
613    * <li>[start..end)
614    * <li>[start..+∞)
615    * <li>(-∞..end) (only if type {@code C} is unbounded below)
616    * <li>(-∞..+∞) (only if type {@code C} is unbounded below)
617    * </ul>
618    */
619   public Range<C> canonical(DiscreteDomain<C> domain) {
620     checkNotNull(domain);
621     Cut<C> lower = lowerBound.canonical(domain);
622     Cut<C> upper = upperBound.canonical(domain);
623     return (lower == lowerBound && upper == upperBound) ? this : create(lower, upper);
624   }
625 
626   /**
627    * Returns {@code true} if {@code object} is a range having the same endpoints and bound types as
628    * this range. Note that discrete ranges such as {@code (1..4)} and {@code [2..3]} are <b>not</b>
629    * equal to one another, despite the fact that they each contain precisely the same set of values.
630    * Similarly, empty ranges are not equal unless they have exactly the same representation, so
631    * {@code [3..3)}, {@code (3..3]}, {@code (4..4]} are all unequal.
632    */
633   @Override
634   public boolean equals(@Nullable Object object) {
635     if (object instanceof Range) {
636       Range<?> other = (Range<?>) object;
637       return lowerBound.equals(other.lowerBound) && upperBound.equals(other.upperBound);
638     }
639     return false;
640   }
641 
642   /** Returns a hash code for this range. */
643   @Override
644   public int hashCode() {
645     return lowerBound.hashCode() * 31 + upperBound.hashCode();
646   }
647 
648   /**
649    * Returns a string representation of this range, such as {@code "[3..5)"} (other examples are
650    * listed in the class documentation).
651    */
652   @Override
653   public String toString() {
654     return toString(lowerBound, upperBound);
655   }
656 
657   private static String toString(Cut<?> lowerBound, Cut<?> upperBound) {
658     StringBuilder sb = new StringBuilder(16);
659     lowerBound.describeAsLowerBound(sb);
660     sb.append("..");
661     upperBound.describeAsUpperBound(sb);
662     return sb.toString();
663   }
664 
665   /**
666    * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
667    */
668   private static <T> SortedSet<T> cast(Iterable<T> iterable) {
669     return (SortedSet<T>) iterable;
670   }
671 
672   Object readResolve() {
673     if (this.equals(ALL)) {
674       return all();
675     } else {
676       return this;
677     }
678   }
679 
680   @SuppressWarnings("unchecked") // this method may throw CCE
681   static int compareOrThrow(Comparable left, Comparable right) {
682     return left.compareTo(right);
683   }
684 
685   /**
686    * Needed to serialize sorted collections of Ranges.
687    */
688   private static class RangeLexOrdering extends Ordering<Range<?>> implements Serializable {
689     static final Ordering<Range<?>> INSTANCE = new RangeLexOrdering();
690 
691     @Override
692     public int compare(Range<?> left, Range<?> right) {
693       return ComparisonChain.start()
694           .compare(left.lowerBound, right.lowerBound)
695           .compare(left.upperBound, right.upperBound)
696           .result();
697     }
698 
699     private static final long serialVersionUID = 0;
700   }
701 
702   private static final long serialVersionUID = 0;
703 }