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
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020
021import com.google.common.annotations.GwtCompatible;
022import com.google.common.base.Equivalence;
023import com.google.common.base.Function;
024import com.google.common.base.Predicate;
025
026import java.io.Serializable;
027import java.util.Comparator;
028import java.util.Iterator;
029import java.util.NoSuchElementException;
030import java.util.SortedSet;
031
032import javax.annotation.Nullable;
033
034/**
035 * A range (or "interval") defines the <i>boundaries</i> around a contiguous span of values of some
036 * {@code Comparable} type; for example, "integers from 1 to 100 inclusive." Note that it is not
037 * possible to <i>iterate</i> over these contained values. To do so, pass this range instance and
038 * an appropriate {@link DiscreteDomain} to {@link ContiguousSet#create}.
039 *
040 * <h3>Types of ranges</h3>
041 *
042 * <p>Each end of the range may be bounded or unbounded. If bounded, there is an associated
043 * <i>endpoint</i> value, and the range is considered to be either <i>open</i> (does not include the
044 * endpoint) or <i>closed</i> (includes the endpoint) on that side. With three possibilities on each
045 * side, this yields nine basic types of ranges, enumerated below. (Notation: a square bracket
046 * ({@code [ ]}) indicates that the range is closed on that side; a parenthesis ({@code ( )}) means
047 * it is either open or unbounded. The construct {@code {x | statement}} is read "the set of all
048 * <i>x</i> such that <i>statement</i>.")
049 *
050 * <blockquote><table>
051 * <tr><td><b>Notation</b> <td><b>Definition</b>        <td><b>Factory method</b>
052 * <tr><td>{@code (a..b)}  <td>{@code {x | a < x < b}}  <td>{@link Range#open open}
053 * <tr><td>{@code [a..b]}  <td>{@code {x | a <= x <= b}}<td>{@link Range#closed closed}
054 * <tr><td>{@code (a..b]}  <td>{@code {x | a < x <= b}} <td>{@link Range#openClosed openClosed}
055 * <tr><td>{@code [a..b)}  <td>{@code {x | a <= x < b}} <td>{@link Range#closedOpen closedOpen}
056 * <tr><td>{@code (a..+∞)} <td>{@code {x | x > a}}      <td>{@link Range#greaterThan greaterThan}
057 * <tr><td>{@code [a..+∞)} <td>{@code {x | x >= a}}     <td>{@link Range#atLeast atLeast}
058 * <tr><td>{@code (-∞..b)} <td>{@code {x | x < b}}      <td>{@link Range#lessThan lessThan}
059 * <tr><td>{@code (-∞..b]} <td>{@code {x | x <= b}}     <td>{@link Range#atMost atMost}
060 * <tr><td>{@code (-∞..+∞)}<td>{@code {x}}              <td>{@link Range#all all}
061 * </table></blockquote>
062 *
063 * <p>When both endpoints exist, the upper endpoint may not be less than the lower. The endpoints
064 * may be equal only if at least one of the bounds is closed:
065 *
066 * <ul>
067 * <li>{@code [a..a]} : a singleton range
068 * <li>{@code [a..a); (a..a]} : {@linkplain #isEmpty empty} ranges; also valid
069 * <li>{@code (a..a)} : <b>invalid</b>; an exception will be thrown
070 * </ul>
071 *
072 * <h3>Warnings</h3>
073 *
074 * <ul>
075 * <li>Use immutable value types only, if at all possible. If you must use a mutable type, <b>do
076 *     not</b> allow the endpoint instances to mutate after the range is created!
077 * <li>Your value type's comparison method should be {@linkplain Comparable consistent with equals}
078 *     if at all possible. Otherwise, be aware that concepts used throughout this documentation such
079 *     as "equal", "same", "unique" and so on actually refer to whether {@link Comparable#compareTo
080 *     compareTo} returns zero, not whether {@link Object#equals equals} returns {@code true}.
081 * <li>A class which implements {@code Comparable<UnrelatedType>} is very broken, and will cause
082 *     undefined horrible things to happen in {@code Range}. For now, the Range API does not prevent
083 *     its use, because this would also rule out all ungenerified (pre-JDK1.5) data types. <b>This
084 *     may change in the future.</b>
085 * </ul>
086 *
087 * <h3>Other notes</h3>
088 *
089 * <ul>
090 * <li>Instances of this type are obtained using the static factory methods in this class.
091 * <li>Ranges are <i>convex</i>: whenever two values are contained, all values in between them must
092 *     also be contained. More formally, for any {@code c1 <= c2 <= c3} of type {@code C}, {@code
093 *     r.contains(c1) && r.contains(c3)} implies {@code r.contains(c2)}). This means that a {@code
094 *     Range<Integer>} can never be used to represent, say, "all <i>prime</i> numbers from 1 to
095 *     100."
096 * <li>When evaluated as a {@link Predicate}, a range yields the same result as invoking {@link
097 *     #contains}.
098 * <li>Terminology note: a range {@code a} is said to be the <i>maximal</i> range having property
099 *     <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code a.encloses(b)}.
100 *     Likewise, {@code a} is <i>minimal</i> when {@code b.encloses(a)} for all {@code b} having
101 *     property <i>P</i>. See, for example, the definition of {@link #intersection intersection}.
102 * </ul>
103 *
104 * <h3>Further reading</h3>
105 *
106 * <p>See the Guava User Guide article on
107 * <a href="http://code.google.com/p/guava-libraries/wiki/RangesExplained">{@code Range}</a>.
108 *
109 * @author Kevin Bourrillion
110 * @author Gregory Kick
111 * @since 10.0
112 */
113@GwtCompatible
114@SuppressWarnings("rawtypes")
115public final class Range<C extends Comparable> implements Predicate<C>, Serializable {
116
117  private static final Function<Range, Cut> LOWER_BOUND_FN = new Function<Range, Cut>() {
118    @Override
119    public Cut apply(Range range) {
120      return range.lowerBound;
121    }
122  };
123
124  @SuppressWarnings("unchecked")
125  static <C extends Comparable<?>> Function<Range<C>, Cut<C>> lowerBoundFn() {
126    return (Function) LOWER_BOUND_FN;
127  }
128
129  private static final Function<Range, Cut> UPPER_BOUND_FN = new Function<Range, Cut>() {
130    @Override
131    public Cut apply(Range range) {
132      return range.upperBound;
133    }
134  };
135
136  @SuppressWarnings("unchecked")
137  static <C extends Comparable<?>> Function<Range<C>, Cut<C>> upperBoundFn() {
138    return (Function) UPPER_BOUND_FN;
139  }
140
141  static final Ordering<Range<?>> RANGE_LEX_ORDERING = new Ordering<Range<?>>() {
142    @Override
143    public int compare(Range<?> left, Range<?> right) {
144      return ComparisonChain.start()
145          .compare(left.lowerBound, right.lowerBound)
146          .compare(left.upperBound, right.upperBound)
147          .result();
148    }
149  };
150
151  static <C extends Comparable<?>> Range<C> create(
152      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(
189      C lower, C upper) {
190    return create(Cut.belowValue(lower), Cut.belowValue(upper));
191  }
192
193  /**
194   * Returns a range that contains all values strictly greater than {@code
195   * lower} and less than or equal to {@code upper}.
196   *
197   * @throws IllegalArgumentException if {@code lower} is greater than {@code
198   *     upper}
199   * @since 14.0
200   */
201  public static <C extends Comparable<?>> Range<C> openClosed(
202      C lower, C upper) {
203    return create(Cut.aboveValue(lower), Cut.aboveValue(upper));
204  }
205
206  /**
207   * Returns a range that contains any value from {@code lower} to {@code
208   * upper}, where each endpoint may be either inclusive (closed) or exclusive
209   * (open).
210   *
211   * @throws IllegalArgumentException if {@code lower} is greater than {@code
212   *     upper}
213   * @since 14.0
214   */
215  public static <C extends Comparable<?>> Range<C> range(
216      C lower, BoundType lowerType, C upper, BoundType upperType) {
217    checkNotNull(lowerType);
218    checkNotNull(upperType);
219
220    Cut<C> lowerBound = (lowerType == BoundType.OPEN)
221        ? Cut.aboveValue(lower)
222        : Cut.belowValue(lower);
223    Cut<C> upperBound = (upperType == BoundType.OPEN)
224        ? Cut.belowValue(upper)
225        : Cut.aboveValue(upper);
226    return create(lowerBound, upperBound);
227  }
228
229  /**
230   * Returns a range that contains all values strictly less than {@code
231   * endpoint}.
232   *
233   * @since 14.0
234   */
235  public static <C extends Comparable<?>> Range<C> lessThan(C endpoint) {
236    return create(Cut.<C>belowAll(), Cut.belowValue(endpoint));
237  }
238
239  /**
240   * Returns a range that contains all values less than or equal to
241   * {@code endpoint}.
242   *
243   * @since 14.0
244   */
245  public static <C extends Comparable<?>> Range<C> atMost(C endpoint) {
246    return create(Cut.<C>belowAll(), Cut.aboveValue(endpoint));
247  }
248
249  /**
250   * Returns a range with no lower bound up to the given endpoint, which may be
251   * either inclusive (closed) or exclusive (open).
252   *
253   * @since 14.0
254   */
255  public static <C extends Comparable<?>> Range<C> upTo(
256      C endpoint, BoundType boundType) {
257    switch (boundType) {
258      case OPEN:
259        return lessThan(endpoint);
260      case CLOSED:
261        return atMost(endpoint);
262      default:
263        throw new AssertionError();
264    }
265  }
266
267  /**
268   * Returns a range that contains all values strictly greater than {@code
269   * endpoint}.
270   *
271   * @since 14.0
272   */
273  public static <C extends Comparable<?>> Range<C> greaterThan(C endpoint) {
274    return create(Cut.aboveValue(endpoint), Cut.<C>aboveAll());
275  }
276
277  /**
278   * Returns a range that contains all values greater than or equal to
279   * {@code endpoint}.
280   *
281   * @since 14.0
282   */
283  public static <C extends Comparable<?>> Range<C> atLeast(C endpoint) {
284    return create(Cut.belowValue(endpoint), Cut.<C>aboveAll());
285  }
286
287  /**
288   * Returns a range from the given endpoint, which may be either inclusive
289   * (closed) or exclusive (open), with no upper bound.
290   *
291   * @since 14.0
292   */
293  public static <C extends Comparable<?>> Range<C> downTo(
294      C endpoint, BoundType boundType) {
295    switch (boundType) {
296      case OPEN:
297        return greaterThan(endpoint);
298      case CLOSED:
299        return atLeast(endpoint);
300      default:
301        throw new AssertionError();
302    }
303  }
304
305  private static final Range<Comparable> ALL =
306      new Range<Comparable>(Cut.belowAll(), Cut.aboveAll());
307
308  /**
309   * Returns a range that contains every value of type {@code C}.
310   *
311   * @since 14.0
312   */
313  @SuppressWarnings("unchecked")
314  public static <C extends Comparable<?>> Range<C> all() {
315    return (Range) ALL;
316  }
317
318  /**
319   * Returns a range that {@linkplain Range#contains(Comparable) contains} only
320   * the given value. The returned range is {@linkplain BoundType#CLOSED closed}
321   * on both ends.
322   *
323   * @since 14.0
324   */
325  public static <C extends Comparable<?>> Range<C> singleton(C value) {
326    return closed(value, value);
327  }
328
329   /**
330   * Returns the minimal range that
331   * {@linkplain Range#contains(Comparable) contains} all of the given values.
332   * The returned range is {@linkplain BoundType#CLOSED closed} on both ends.
333   *
334   * @throws ClassCastException if the parameters are not <i>mutually
335   *     comparable</i>
336   * @throws NoSuchElementException if {@code values} is empty
337   * @throws NullPointerException if any of {@code values} is null
338   * @since 14.0
339   */
340  public static <C extends Comparable<?>> Range<C> encloseAll(
341      Iterable<C> values) {
342    checkNotNull(values);
343    if (values instanceof ContiguousSet) {
344      return ((ContiguousSet<C>) values).range();
345    }
346    Iterator<C> valueIterator = values.iterator();
347    C min = checkNotNull(valueIterator.next());
348    C max = min;
349    while (valueIterator.hasNext()) {
350      C value = checkNotNull(valueIterator.next());
351      min = Ordering.natural().min(min, value);
352      max = Ordering.natural().max(max, value);
353    }
354    return closed(min, max);
355  }
356
357  final Cut<C> lowerBound;
358  final Cut<C> upperBound;
359
360  private Range(Cut<C> lowerBound, Cut<C> upperBound) {
361    if (lowerBound.compareTo(upperBound) > 0 || lowerBound == Cut.<C>aboveAll()
362        || upperBound == Cut.<C>belowAll()) {
363      throw new IllegalArgumentException("Invalid range: " + toString(lowerBound, upperBound));
364    }
365    this.lowerBound = checkNotNull(lowerBound);
366    this.upperBound = checkNotNull(upperBound);
367  }
368
369  /**
370   * Returns {@code true} if this range has a lower endpoint.
371   */
372  public boolean hasLowerBound() {
373    return lowerBound != Cut.belowAll();
374  }
375
376  /**
377   * Returns the lower endpoint of this range.
378   *
379   * @throws IllegalStateException if this range is unbounded below (that is, {@link
380   *     #hasLowerBound()} returns {@code false})
381   */
382  public C lowerEndpoint() {
383    return lowerBound.endpoint();
384  }
385
386  /**
387   * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if the range includes
388   * its lower endpoint, {@link BoundType#OPEN} if it does not.
389   *
390   * @throws IllegalStateException if this range is unbounded below (that is, {@link
391   *     #hasLowerBound()} returns {@code false})
392   */
393  public BoundType lowerBoundType() {
394    return lowerBound.typeAsLowerBound();
395  }
396
397  /**
398   * Returns {@code true} if this range has an upper endpoint.
399   */
400  public boolean hasUpperBound() {
401    return upperBound != Cut.aboveAll();
402  }
403
404  /**
405   * Returns the upper endpoint of this range.
406   *
407   * @throws IllegalStateException if this range is unbounded above (that is, {@link
408   *     #hasUpperBound()} returns {@code false})
409   */
410  public C upperEndpoint() {
411    return upperBound.endpoint();
412  }
413
414  /**
415   * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if the range includes
416   * its upper endpoint, {@link BoundType#OPEN} if it does not.
417   *
418   * @throws IllegalStateException if this range is unbounded above (that is, {@link
419   *     #hasUpperBound()} returns {@code false})
420   */
421  public BoundType upperBoundType() {
422    return upperBound.typeAsUpperBound();
423  }
424
425  /**
426   * Returns {@code true} if this range is of the form {@code [v..v)} or {@code (v..v]}. (This does
427   * not encompass ranges of the form {@code (v..v)}, because such ranges are <i>invalid</i> and
428   * can't be constructed at all.)
429   *
430   * <p>Note that certain discrete ranges such as the integer range {@code (3..4)} are <b>not</b>
431   * considered empty, even though they contain no actual values.  In these cases, it may be
432   * helpful to preprocess ranges with {@link #canonical(DiscreteDomain)}.
433   */
434  public boolean isEmpty() {
435    return lowerBound.equals(upperBound);
436  }
437
438  /**
439   * Returns {@code true} if {@code value} is within the bounds of this range. For example, on the
440   * range {@code [0..2)}, {@code contains(1)} returns {@code true}, while {@code contains(2)}
441   * returns {@code false}.
442   */
443  public boolean contains(C value) {
444    checkNotNull(value);
445    // let this throw CCE if there is some trickery going on
446    return lowerBound.isLessThan(value) && !upperBound.isLessThan(value);
447  }
448
449  /**
450   * @deprecated Provided only to satisfy the {@link Predicate} interface; use {@link #contains}
451   *     instead.
452   */
453  @Deprecated
454  @Override
455  public boolean apply(C input) {
456    return contains(input);
457  }
458
459  /**
460   * Returns {@code true} if every element in {@code values} is {@linkplain #contains contained} in
461   * this range.
462   */
463  public boolean containsAll(Iterable<? extends C> values) {
464    if (Iterables.isEmpty(values)) {
465      return true;
466    }
467
468    // this optimizes testing equality of two range-backed sets
469    if (values instanceof SortedSet) {
470      SortedSet<? extends C> set = cast(values);
471      Comparator<?> comparator = set.comparator();
472      if (Ordering.natural().equals(comparator) || comparator == null) {
473        return contains(set.first()) && contains(set.last());
474      }
475    }
476
477    for (C value : values) {
478      if (!contains(value)) {
479        return false;
480      }
481    }
482    return true;
483  }
484
485  /**
486   * Returns {@code true} if the bounds of {@code other} do not extend outside the bounds of this
487   * range. Examples:
488   *
489   * <ul>
490   * <li>{@code [3..6]} encloses {@code [4..5]}
491   * <li>{@code (3..6)} encloses {@code (3..6)}
492   * <li>{@code [3..6]} encloses {@code [4..4)} (even though the latter is empty)
493   * <li>{@code (3..6]} does not enclose {@code [3..6]}
494   * <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains every value
495   *     contained by the latter range)
496   * <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains every value
497   *     contained by the latter range)
498   * </ul>
499   *
500   * <p>Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies
501   * {@code a.contains(v)}, but as the last two examples illustrate, the converse is not always
502   * true.
503   *
504   * <p>Being reflexive, antisymmetric and transitive, the {@code encloses} relation defines a
505   * <i>partial order</i> over ranges. There exists a unique {@linkplain Range#all maximal} range
506   * according to this relation, and also numerous {@linkplain #isEmpty minimal} ranges. Enclosure
507   * also implies {@linkplain #isConnected connectedness}.
508   */
509  public boolean encloses(Range<C> other) {
510    return lowerBound.compareTo(other.lowerBound) <= 0
511        && upperBound.compareTo(other.upperBound) >= 0;
512  }
513
514  /**
515   * Returns {@code true} if there exists a (possibly empty) range which is {@linkplain #encloses
516   * enclosed} by both this range and {@code other}.
517   *
518   * <p>For example,
519   * <ul>
520   * <li>{@code [2, 4)} and {@code [5, 7)} are not connected
521   * <li>{@code [2, 4)} and {@code [3, 5)} are connected, because both enclose {@code [3, 4)}
522   * <li>{@code [2, 4)} and {@code [4, 6)} are connected, because both enclose the empty range
523   *     {@code [4, 4)}
524   * </ul>
525   *
526   * <p>Note that this range and {@code other} have a well-defined {@linkplain #span union} and
527   * {@linkplain #intersection intersection} (as a single, possibly-empty range) if and only if this
528   * method returns {@code true}.
529   *
530   * <p>The connectedness relation is both reflexive and symmetric, but does not form an {@linkplain
531   * Equivalence equivalence relation} as it is not transitive.
532   *
533   * <p>Note that certain discrete ranges are not considered connected, even though there are no
534   * elements "between them."  For example, {@code [3, 5]} is not considered connected to {@code
535   * [6, 10]}.  In these cases, it may be desirable for both input ranges to be preprocessed with
536   * {@link #canonical(DiscreteDomain)} before testing for connectedness.
537   */
538  public boolean isConnected(Range<C> other) {
539    return lowerBound.compareTo(other.upperBound) <= 0
540        && other.lowerBound.compareTo(upperBound) <= 0;
541  }
542
543  /**
544   * Returns the maximal range {@linkplain #encloses enclosed} by both this range and {@code
545   * connectedRange}, if such a range exists.
546   *
547   * <p>For example, the intersection of {@code [1..5]} and {@code (3..7)} is {@code (3..5]}. The
548   * resulting range may be empty; for example, {@code [1..5)} intersected with {@code [5..7)}
549   * yields the empty range {@code [5..5)}.
550   *
551   * <p>The intersection exists if and only if the two ranges are {@linkplain #isConnected
552   * connected}.
553   *
554   * <p>The intersection operation is commutative, associative and idempotent, and its identity
555   * element is {@link Range#all}).
556   *
557   * @throws IllegalArgumentException if {@code isConnected(connectedRange)} is {@code false}
558   */
559  public Range<C> intersection(Range<C> connectedRange) {
560    int lowerCmp = lowerBound.compareTo(connectedRange.lowerBound);
561    int upperCmp = upperBound.compareTo(connectedRange.upperBound);
562    if (lowerCmp >= 0 && upperCmp <= 0) {
563      return this;
564    } else if (lowerCmp <= 0 && upperCmp >= 0) {
565      return connectedRange;
566    } else {
567      Cut<C> newLower = (lowerCmp >= 0) ? lowerBound : connectedRange.lowerBound;
568      Cut<C> newUpper = (upperCmp <= 0) ? upperBound : connectedRange.upperBound;
569      return create(newLower, newUpper);
570    }
571  }
572
573  /**
574   * Returns the minimal range that {@linkplain #encloses encloses} both this range and {@code
575   * other}. For example, the span of {@code [1..3]} and {@code (5..7)} is {@code [1..7)}.
576   *
577   * <p><i>If</i> the input ranges are {@linkplain #isConnected connected}, the returned range can
578   * also be called their <i>union</i>. If they are not, note that the span might contain values
579   * that are not contained in either input range.
580   *
581   * <p>Like {@link #intersection(Range) intersection}, this operation is commutative, associative
582   * and idempotent. Unlike it, it is always well-defined for any two input ranges.
583   */
584  public Range<C> span(Range<C> other) {
585    int lowerCmp = lowerBound.compareTo(other.lowerBound);
586    int upperCmp = upperBound.compareTo(other.upperBound);
587    if (lowerCmp <= 0 && upperCmp >= 0) {
588      return this;
589    } else if (lowerCmp >= 0 && upperCmp <= 0) {
590      return other;
591    } else {
592      Cut<C> newLower = (lowerCmp <= 0) ? lowerBound : other.lowerBound;
593      Cut<C> newUpper = (upperCmp >= 0) ? upperBound : other.upperBound;
594      return create(newLower, newUpper);
595    }
596  }
597
598  /**
599   * Returns the canonical form of this range in the given domain. The canonical form has the
600   * following properties:
601   *
602   * <ul>
603   * <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for all {@code v} (in other
604   *     words, {@code ContiguousSet.create(a.canonical(domain), domain).equals(
605   *     ContiguousSet.create(a, domain))}
606   * <li>uniqueness: unless {@code a.isEmpty()},
607   *     {@code ContiguousSet.create(a, domain).equals(ContiguousSet.create(b, domain))} implies
608   *     {@code a.canonical(domain).equals(b.canonical(domain))}
609   * <li>idempotence: {@code a.canonical(domain).canonical(domain).equals(a.canonical(domain))}
610   * </ul>
611   *
612   * <p>Furthermore, this method guarantees that the range returned will be one of the following
613   * canonical forms:
614   *
615   * <ul>
616   * <li>[start..end)
617   * <li>[start..+∞)
618   * <li>(-∞..end) (only if type {@code C} is unbounded below)
619   * <li>(-∞..+∞) (only if type {@code C} is unbounded below)
620   * </ul>
621   */
622  public Range<C> canonical(DiscreteDomain<C> domain) {
623    checkNotNull(domain);
624    Cut<C> lower = lowerBound.canonical(domain);
625    Cut<C> upper = upperBound.canonical(domain);
626    return (lower == lowerBound && upper == upperBound) ? this : create(lower, upper);
627  }
628
629  /**
630   * Returns {@code true} if {@code object} is a range having the same endpoints and bound types as
631   * this range. Note that discrete ranges such as {@code (1..4)} and {@code [2..3]} are <b>not</b>
632   * equal to one another, despite the fact that they each contain precisely the same set of values.
633   * Similarly, empty ranges are not equal unless they have exactly the same representation, so
634   * {@code [3..3)}, {@code (3..3]}, {@code (4..4]} are all unequal.
635   */
636  @Override public boolean equals(@Nullable Object object) {
637    if (object instanceof Range) {
638      Range<?> other = (Range<?>) object;
639      return lowerBound.equals(other.lowerBound)
640          && upperBound.equals(other.upperBound);
641    }
642    return false;
643  }
644
645  /** Returns a hash code for this range. */
646  @Override public int hashCode() {
647    return lowerBound.hashCode() * 31 + upperBound.hashCode();
648  }
649
650  /**
651   * Returns a string representation of this range, such as {@code "[3..5)"} (other examples are
652   * listed in the class documentation).
653   */
654  @Override public String toString() {
655    return toString(lowerBound, upperBound);
656  }
657
658  private static String toString(Cut<?> lowerBound, Cut<?> upperBound) {
659    StringBuilder sb = new StringBuilder(16);
660    lowerBound.describeAsLowerBound(sb);
661    sb.append('\u2025');
662    upperBound.describeAsUpperBound(sb);
663    return sb.toString();
664  }
665
666  /**
667   * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
668   */
669  private static <T> SortedSet<T> cast(Iterable<T> iterable) {
670    return (SortedSet<T>) iterable;
671  }
672
673  Object readResolve() {
674    if (this.equals(ALL)) {
675      return all();
676    } else {
677      return this;
678    }
679  }
680
681  @SuppressWarnings("unchecked") // this method may throw CCE
682  static int compareOrThrow(Comparable left, Comparable right) {
683    return left.compareTo(right);
684  }
685
686  private static final long serialVersionUID = 0;
687}