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