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 org.checkerframework.checker.nullness.compatqual.NullableDecl;
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 an
036 * 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 *
050 * <table>
051 * <caption>Range Types</caption>
052 * <tr><th>Notation        <th>Definition               <th>Factory method
053 * <tr><td>{@code (a..b)}  <td>{@code {x | a < x < b}}  <td>{@link Range#open open}
054 * <tr><td>{@code [a..b]}  <td>{@code {x | a <= x <= b}}<td>{@link Range#closed closed}
055 * <tr><td>{@code (a..b]}  <td>{@code {x | a < x <= b}} <td>{@link Range#openClosed openClosed}
056 * <tr><td>{@code [a..b)}  <td>{@code {x | a <= x < b}} <td>{@link Range#closedOpen closedOpen}
057 * <tr><td>{@code (a..+∞)} <td>{@code {x | x > a}}      <td>{@link Range#greaterThan greaterThan}
058 * <tr><td>{@code [a..+∞)} <td>{@code {x | x >= a}}     <td>{@link Range#atLeast atLeast}
059 * <tr><td>{@code (-∞..b)} <td>{@code {x | x < b}}      <td>{@link Range#lessThan lessThan}
060 * <tr><td>{@code (-∞..b]} <td>{@code {x | x <= b}}     <td>{@link Range#atMost atMost}
061 * <tr><td>{@code (-∞..+∞)}<td>{@code {x}}              <td>{@link Range#all all}
062 * </table>
063 *
064 * </blockquote>
065 *
066 * <p>When both endpoints exist, the upper endpoint may not be less than the lower. The endpoints
067 * may be equal only if at least one of the bounds is closed:
068 *
069 * <ul>
070 *   <li>{@code [a..a]} : a singleton range
071 *   <li>{@code [a..a); (a..a]} : {@linkplain #isEmpty empty} ranges; also valid
072 *   <li>{@code (a..a)} : <b>invalid</b>; an exception will be thrown
073 * </ul>
074 *
075 * <h3>Warnings</h3>
076 *
077 * <ul>
078 *   <li>Use immutable value types only, if at all possible. If you must use a mutable type, <b>do
079 *       not</b> allow the endpoint instances to mutate after the range is created!
080 *   <li>Your value type's comparison method should be {@linkplain Comparable consistent with
081 *       equals} if at all possible. Otherwise, be aware that concepts used throughout this
082 *       documentation such as "equal", "same", "unique" and so on actually refer to whether {@link
083 *       Comparable#compareTo compareTo} returns zero, not whether {@link Object#equals equals}
084 *       returns {@code true}.
085 *   <li>A class which implements {@code Comparable<UnrelatedType>} is very broken, and will cause
086 *       undefined horrible things to happen in {@code Range}. For now, the Range API does not
087 *       prevent its use, because this would also rule out all ungenerified (pre-JDK1.5) data types.
088 *       <b>This may change in the future.</b>
089 * </ul>
090 *
091 * <h3>Other notes</h3>
092 *
093 * <ul>
094 *   <li>Instances of this type are obtained using the static factory methods in this class.
095 *   <li>Ranges are <i>convex</i>: whenever two values are contained, all values in between them
096 *       must also be contained. More formally, for any {@code c1 <= c2 <= c3} of type {@code C},
097 *       {@code r.contains(c1) && r.contains(c3)} implies {@code r.contains(c2)}). This means that a
098 *       {@code Range<Integer>} can never be used to represent, say, "all <i>prime</i> numbers from
099 *       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")
119public 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
125    @Override
126    public Cut apply(Range range) {
127      return range.lowerBound;
128    }
129  }
130
131  static class UpperBoundFn implements Function<Range, Cut> {
132    static final UpperBoundFn INSTANCE = new UpperBoundFn();
133
134    @Override
135    public Cut apply(Range range) {
136      return range.upperBound;
137    }
138  }
139
140  @SuppressWarnings("unchecked")
141  static <C extends Comparable<?>> Function<Range<C>, Cut<C>> lowerBoundFn() {
142    return (Function) LowerBoundFn.INSTANCE;
143  }
144
145  @SuppressWarnings("unchecked")
146  static <C extends Comparable<?>> Function<Range<C>, Cut<C>> upperBoundFn() {
147    return (Function) UpperBoundFn.INSTANCE;
148  }
149
150  static <C extends Comparable<?>> Ordering<Range<C>> rangeLexOrdering() {
151    return (Ordering<Range<C>>) (Ordering) RangeLexOrdering.INSTANCE;
152  }
153
154  static <C extends Comparable<?>> Range<C> create(Cut<C> lowerBound, Cut<C> upperBound) {
155    return new Range<C>(lowerBound, upperBound);
156  }
157
158  /**
159   * Returns a range that contains all values strictly greater than {@code lower} and strictly less
160   * than {@code upper}.
161   *
162   * @throws IllegalArgumentException if {@code lower} is greater than <i>or equal to</i> {@code
163   *     upper}
164   * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable
165   * @since 14.0
166   */
167  public static <C extends Comparable<?>> Range<C> open(C lower, C upper) {
168    return create(Cut.aboveValue(lower), Cut.belowValue(upper));
169  }
170
171  /**
172   * Returns a range that contains all values greater than or equal to {@code lower} and less than
173   * or equal to {@code upper}.
174   *
175   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
176   * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable
177   * @since 14.0
178   */
179  public static <C extends Comparable<?>> Range<C> closed(C lower, C upper) {
180    return create(Cut.belowValue(lower), Cut.aboveValue(upper));
181  }
182
183  /**
184   * Returns a range that contains all values greater than or equal to {@code lower} and strictly
185   * less than {@code upper}.
186   *
187   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
188   * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable
189   * @since 14.0
190   */
191  public static <C extends Comparable<?>> Range<C> closedOpen(C lower, C upper) {
192    return create(Cut.belowValue(lower), Cut.belowValue(upper));
193  }
194
195  /**
196   * Returns a range that contains all values strictly greater than {@code lower} and less than or
197   * equal to {@code upper}.
198   *
199   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
200   * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable
201   * @since 14.0
202   */
203  public static <C extends Comparable<?>> Range<C> openClosed(C lower, C upper) {
204    return create(Cut.aboveValue(lower), Cut.aboveValue(upper));
205  }
206
207  /**
208   * Returns a range that contains any value from {@code lower} to {@code upper}, where each
209   * endpoint may be either inclusive (closed) or exclusive (open).
210   *
211   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
212   * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable
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 =
221        (lowerType == BoundType.OPEN) ? Cut.aboveValue(lower) : Cut.belowValue(lower);
222    Cut<C> upperBound =
223        (upperType == BoundType.OPEN) ? Cut.belowValue(upper) : Cut.aboveValue(upper);
224    return create(lowerBound, upperBound);
225  }
226
227  /**
228   * Returns a range that contains all values strictly less than {@code endpoint}.
229   *
230   * @since 14.0
231   */
232  public static <C extends Comparable<?>> Range<C> lessThan(C endpoint) {
233    return create(Cut.<C>belowAll(), Cut.belowValue(endpoint));
234  }
235
236  /**
237   * Returns a range that contains all values less than or equal to {@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 either inclusive
247   * (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 endpoint}.
264   *
265   * @since 14.0
266   */
267  public static <C extends Comparable<?>> Range<C> greaterThan(C endpoint) {
268    return create(Cut.aboveValue(endpoint), Cut.<C>aboveAll());
269  }
270
271  /**
272   * Returns a range that contains all values greater than or equal to {@code endpoint}.
273   *
274   * @since 14.0
275   */
276  public static <C extends Comparable<?>> Range<C> atLeast(C endpoint) {
277    return create(Cut.belowValue(endpoint), Cut.<C>aboveAll());
278  }
279
280  /**
281   * Returns a range from the given endpoint, which may be either inclusive (closed) or exclusive
282   * (open), with no upper bound.
283   *
284   * @since 14.0
285   */
286  public static <C extends Comparable<?>> Range<C> downTo(C endpoint, BoundType boundType) {
287    switch (boundType) {
288      case OPEN:
289        return greaterThan(endpoint);
290      case CLOSED:
291        return atLeast(endpoint);
292      default:
293        throw new AssertionError();
294    }
295  }
296
297  private static final Range<Comparable> ALL = new Range<>(Cut.belowAll(), Cut.aboveAll());
298
299  /**
300   * Returns a range that contains every value of type {@code C}.
301   *
302   * @since 14.0
303   */
304  @SuppressWarnings("unchecked")
305  public static <C extends Comparable<?>> Range<C> all() {
306    return (Range) ALL;
307  }
308
309  /**
310   * Returns a range that {@linkplain Range#contains(Comparable) contains} only the given value. The
311   * returned range is {@linkplain BoundType#CLOSED closed} on both ends.
312   *
313   * @since 14.0
314   */
315  public static <C extends Comparable<?>> Range<C> singleton(C value) {
316    return closed(value, value);
317  }
318
319  /**
320   * Returns the minimal range that {@linkplain Range#contains(Comparable) contains} all of the
321   * given values. The returned range is {@linkplain BoundType#CLOSED closed} on both ends.
322   *
323   * @throws ClassCastException if the values are not mutually comparable
324   * @throws NoSuchElementException if {@code values} is empty
325   * @throws NullPointerException if any of {@code values} is null
326   * @since 14.0
327   */
328  public static <C extends Comparable<?>> Range<C> encloseAll(Iterable<C> values) {
329    checkNotNull(values);
330    if (values instanceof SortedSet) {
331      SortedSet<? extends C> set = cast(values);
332      Comparator<?> comparator = set.comparator();
333      if (Ordering.natural().equals(comparator) || comparator == null) {
334        return closed(set.first(), set.last());
335      }
336    }
337    Iterator<C> valueIterator = values.iterator();
338    C min = checkNotNull(valueIterator.next());
339    C max = min;
340    while (valueIterator.hasNext()) {
341      C value = checkNotNull(valueIterator.next());
342      min = Ordering.natural().min(min, value);
343      max = Ordering.natural().max(max, value);
344    }
345    return closed(min, max);
346  }
347
348  final Cut<C> lowerBound;
349  final Cut<C> upperBound;
350
351  private Range(Cut<C> lowerBound, Cut<C> upperBound) {
352    this.lowerBound = checkNotNull(lowerBound);
353    this.upperBound = checkNotNull(upperBound);
354    if (lowerBound.compareTo(upperBound) > 0
355        || lowerBound == Cut.<C>aboveAll()
356        || upperBound == Cut.<C>belowAll()) {
357      throw new IllegalArgumentException("Invalid range: " + toString(lowerBound, upperBound));
358    }
359  }
360
361  /** Returns {@code true} if this range has a lower endpoint. */
362  public boolean hasLowerBound() {
363    return lowerBound != Cut.belowAll();
364  }
365
366  /**
367   * Returns the lower endpoint of this range.
368   *
369   * @throws IllegalStateException if this range is unbounded below (that is, {@link
370   *     #hasLowerBound()} returns {@code false})
371   */
372  public C lowerEndpoint() {
373    return lowerBound.endpoint();
374  }
375
376  /**
377   * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if the range includes
378   * its lower endpoint, {@link BoundType#OPEN} if it does not.
379   *
380   * @throws IllegalStateException if this range is unbounded below (that is, {@link
381   *     #hasLowerBound()} returns {@code false})
382   */
383  public BoundType lowerBoundType() {
384    return lowerBound.typeAsLowerBound();
385  }
386
387  /** Returns {@code true} if this range has an upper endpoint. */
388  public boolean hasUpperBound() {
389    return upperBound != Cut.aboveAll();
390  }
391
392  /**
393   * Returns the upper endpoint of this range.
394   *
395   * @throws IllegalStateException if this range is unbounded above (that is, {@link
396   *     #hasUpperBound()} returns {@code false})
397   */
398  public C upperEndpoint() {
399    return upperBound.endpoint();
400  }
401
402  /**
403   * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if the range includes
404   * its upper endpoint, {@link BoundType#OPEN} if it does not.
405   *
406   * @throws IllegalStateException if this range is unbounded above (that is, {@link
407   *     #hasUpperBound()} returns {@code false})
408   */
409  public BoundType upperBoundType() {
410    return upperBound.typeAsUpperBound();
411  }
412
413  /**
414   * Returns {@code true} if this range is of the form {@code [v..v)} or {@code (v..v]}. (This does
415   * not encompass ranges of the form {@code (v..v)}, because such ranges are <i>invalid</i> and
416   * can't be constructed at all.)
417   *
418   * <p>Note that certain discrete ranges such as the integer range {@code (3..4)} are <b>not</b>
419   * considered empty, even though they contain no actual values. In these cases, it may be helpful
420   * to preprocess ranges with {@link #canonical(DiscreteDomain)}.
421   */
422  public boolean isEmpty() {
423    return lowerBound.equals(upperBound);
424  }
425
426  /**
427   * Returns {@code true} if {@code value} is within the bounds of this range. For example, on the
428   * range {@code [0..2)}, {@code contains(1)} returns {@code true}, while {@code contains(2)}
429   * returns {@code false}.
430   */
431  public boolean contains(C value) {
432    checkNotNull(value);
433    // let this throw CCE if there is some trickery going on
434    return lowerBound.isLessThan(value) && !upperBound.isLessThan(value);
435  }
436
437  /**
438   * @deprecated Provided only to satisfy the {@link Predicate} interface; use {@link #contains}
439   *     instead.
440   */
441  @Deprecated
442  @Override
443  public boolean apply(C input) {
444    return contains(input);
445  }
446
447  /**
448   * Returns {@code true} if every element in {@code values} is {@linkplain #contains contained} in
449   * this range.
450   */
451  public boolean containsAll(Iterable<? extends C> values) {
452    if (Iterables.isEmpty(values)) {
453      return true;
454    }
455
456    // this optimizes testing equality of two range-backed sets
457    if (values instanceof SortedSet) {
458      SortedSet<? extends C> set = cast(values);
459      Comparator<?> comparator = set.comparator();
460      if (Ordering.natural().equals(comparator) || comparator == null) {
461        return contains(set.first()) && contains(set.last());
462      }
463    }
464
465    for (C value : values) {
466      if (!contains(value)) {
467        return false;
468      }
469    }
470    return true;
471  }
472
473  /**
474   * Returns {@code true} if the bounds of {@code other} do not extend outside the bounds of this
475   * range. Examples:
476   *
477   * <ul>
478   *   <li>{@code [3..6]} encloses {@code [4..5]}
479   *   <li>{@code (3..6)} encloses {@code (3..6)}
480   *   <li>{@code [3..6]} encloses {@code [4..4)} (even though the latter is empty)
481   *   <li>{@code (3..6]} does not enclose {@code [3..6]}
482   *   <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains every value
483   *       contained by the latter range)
484   *   <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains every value
485   *       contained by the latter range)
486   * </ul>
487   *
488   * <p>Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies {@code
489   * a.contains(v)}, but as the last two examples illustrate, the converse is not always 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   *
507   * <ul>
508   *   <li>{@code [2, 4)} and {@code [5, 7)} are not connected
509   *   <li>{@code [2, 4)} and {@code [3, 5)} are connected, because both enclose {@code [3, 4)}
510   *   <li>{@code [2, 4)} and {@code [4, 6)} are connected, because both enclose the empty range
511   *       {@code [4, 4)}
512   * </ul>
513   *
514   * <p>Note that this range and {@code other} have a well-defined {@linkplain #span union} and
515   * {@linkplain #intersection intersection} (as a single, possibly-empty range) if and only if this
516   * method returns {@code true}.
517   *
518   * <p>The connectedness relation is both reflexive and symmetric, but does not form an {@linkplain
519   * Equivalence equivalence relation} as it is not transitive.
520   *
521   * <p>Note that certain discrete ranges are not considered connected, even though there are no
522   * elements "between them." For example, {@code [3, 5]} is not considered connected to {@code [6,
523   * 10]}. In these cases, it may be desirable for both input ranges to be preprocessed with {@link
524   * #canonical(DiscreteDomain)} before testing for connectedness.
525   */
526  public boolean isConnected(Range<C> other) {
527    return lowerBound.compareTo(other.upperBound) <= 0
528        && other.lowerBound.compareTo(upperBound) <= 0;
529  }
530
531  /**
532   * Returns the maximal range {@linkplain #encloses enclosed} by both this range and {@code
533   * connectedRange}, if such a range exists.
534   *
535   * <p>For example, the intersection of {@code [1..5]} and {@code (3..7)} is {@code (3..5]}. The
536   * resulting range may be empty; for example, {@code [1..5)} intersected with {@code [5..7)}
537   * yields the empty range {@code [5..5)}.
538   *
539   * <p>The intersection exists if and only if the two ranges are {@linkplain #isConnected
540   * connected}.
541   *
542   * <p>The intersection operation is commutative, associative and idempotent, and its identity
543   * element is {@link Range#all}).
544   *
545   * @throws IllegalArgumentException if {@code isConnected(connectedRange)} is {@code false}
546   */
547  public Range<C> intersection(Range<C> connectedRange) {
548    int lowerCmp = lowerBound.compareTo(connectedRange.lowerBound);
549    int upperCmp = upperBound.compareTo(connectedRange.upperBound);
550    if (lowerCmp >= 0 && upperCmp <= 0) {
551      return this;
552    } else if (lowerCmp <= 0 && upperCmp >= 0) {
553      return connectedRange;
554    } else {
555      Cut<C> newLower = (lowerCmp >= 0) ? lowerBound : connectedRange.lowerBound;
556      Cut<C> newUpper = (upperCmp <= 0) ? upperBound : connectedRange.upperBound;
557      return create(newLower, newUpper);
558    }
559  }
560
561  /**
562   * Returns the maximal range lying between this range and {@code otherRange}, if such a range
563   * exists. The resulting range may be empty if the two ranges are adjacent but non-overlapping.
564   *
565   * <p>For example, the gap of {@code [1..5]} and {@code (7..10)} is {@code (5..7]}. The resulting
566   * range may be empty; for example, the gap between {@code [1..5)} {@code [5..7)} yields the empty
567   * range {@code [5..5)}.
568   *
569   * <p>The gap exists if and only if the two ranges are either disconnected or immediately adjacent
570   * (any intersection must be an empty range).
571   *
572   * <p>The gap operation is commutative.
573   *
574   * @throws IllegalArgumentException if this range and {@code otherRange} have a nonempty
575   *     intersection
576   * @since 27.0
577   */
578  public Range<C> gap(Range<C> otherRange) {
579    boolean isThisFirst = this.lowerBound.compareTo(otherRange.lowerBound) < 0;
580    Range<C> firstRange = isThisFirst ? this : otherRange;
581    Range<C> secondRange = isThisFirst ? otherRange : this;
582    return create(firstRange.upperBound, secondRange.lowerBound);
583  }
584
585  /**
586   * Returns the minimal range that {@linkplain #encloses encloses} both this range and {@code
587   * other}. For example, the span of {@code [1..3]} and {@code (5..7)} is {@code [1..7)}.
588   *
589   * <p><i>If</i> the input ranges are {@linkplain #isConnected connected}, the returned range can
590   * also be called their <i>union</i>. If they are not, note that the span might contain values
591   * that are not contained in either input range.
592   *
593   * <p>Like {@link #intersection(Range) intersection}, this operation is commutative, associative
594   * and idempotent. Unlike it, it is always well-defined for any two input ranges.
595   */
596  public Range<C> span(Range<C> other) {
597    int lowerCmp = lowerBound.compareTo(other.lowerBound);
598    int upperCmp = upperBound.compareTo(other.upperBound);
599    if (lowerCmp <= 0 && upperCmp >= 0) {
600      return this;
601    } else if (lowerCmp >= 0 && upperCmp <= 0) {
602      return other;
603    } else {
604      Cut<C> newLower = (lowerCmp <= 0) ? lowerBound : other.lowerBound;
605      Cut<C> newUpper = (upperCmp >= 0) ? upperBound : other.upperBound;
606      return create(newLower, newUpper);
607    }
608  }
609
610  /**
611   * Returns the canonical form of this range in the given domain. The canonical form has the
612   * following properties:
613   *
614   * <ul>
615   *   <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for all {@code v} (in
616   *       other words, {@code ContiguousSet.create(a.canonical(domain), domain).equals(
617   *       ContiguousSet.create(a, domain))}
618   *   <li>uniqueness: unless {@code a.isEmpty()}, {@code ContiguousSet.create(a,
619   *       domain).equals(ContiguousSet.create(b, domain))} implies {@code
620   *       a.canonical(domain).equals(b.canonical(domain))}
621   *   <li>idempotence: {@code a.canonical(domain).canonical(domain).equals(a.canonical(domain))}
622   * </ul>
623   *
624   * <p>Furthermore, this method guarantees that the range returned will be one of the following
625   * canonical forms:
626   *
627   * <ul>
628   *   <li>[start..end)
629   *   <li>[start..+∞)
630   *   <li>(-∞..end) (only if type {@code C} is unbounded below)
631   *   <li>(-∞..+∞) (only if type {@code C} is unbounded below)
632   * </ul>
633   */
634  public Range<C> canonical(DiscreteDomain<C> domain) {
635    checkNotNull(domain);
636    Cut<C> lower = lowerBound.canonical(domain);
637    Cut<C> upper = upperBound.canonical(domain);
638    return (lower == lowerBound && upper == upperBound) ? this : create(lower, upper);
639  }
640
641  /**
642   * Returns {@code true} if {@code object} is a range having the same endpoints and bound types as
643   * this range. Note that discrete ranges such as {@code (1..4)} and {@code [2..3]} are <b>not</b>
644   * equal to one another, despite the fact that they each contain precisely the same set of values.
645   * Similarly, empty ranges are not equal unless they have exactly the same representation, so
646   * {@code [3..3)}, {@code (3..3]}, {@code (4..4]} are all unequal.
647   */
648  @Override
649  public boolean equals(@NullableDecl Object object) {
650    if (object instanceof Range) {
651      Range<?> other = (Range<?>) object;
652      return lowerBound.equals(other.lowerBound) && upperBound.equals(other.upperBound);
653    }
654    return false;
655  }
656
657  /** Returns a hash code for this range. */
658  @Override
659  public int hashCode() {
660    return lowerBound.hashCode() * 31 + upperBound.hashCode();
661  }
662
663  /**
664   * Returns a string representation of this range, such as {@code "[3..5)"} (other examples are
665   * listed in the class documentation).
666   */
667  @Override
668  public String toString() {
669    return toString(lowerBound, upperBound);
670  }
671
672  private static String toString(Cut<?> lowerBound, Cut<?> upperBound) {
673    StringBuilder sb = new StringBuilder(16);
674    lowerBound.describeAsLowerBound(sb);
675    sb.append("..");
676    upperBound.describeAsUpperBound(sb);
677    return sb.toString();
678  }
679
680  /** Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 */
681  private static <T> SortedSet<T> cast(Iterable<T> iterable) {
682    return (SortedSet<T>) iterable;
683  }
684
685  Object readResolve() {
686    if (this.equals(ALL)) {
687      return all();
688    } else {
689      return this;
690    }
691  }
692
693  @SuppressWarnings("unchecked") // this method may throw CCE
694  static int compareOrThrow(Comparable left, Comparable right) {
695    return left.compareTo(right);
696  }
697
698  /** Needed to serialize sorted collections of Ranges. */
699  private static class RangeLexOrdering extends Ordering<Range<?>> implements Serializable {
700    static final Ordering<Range<?>> INSTANCE = new RangeLexOrdering();
701
702    @Override
703    public int compare(Range<?> left, Range<?> right) {
704      return ComparisonChain.start()
705          .compare(left.lowerBound, right.lowerBound)
706          .compare(left.upperBound, right.upperBound)
707          .result();
708    }
709
710    private static final long serialVersionUID = 0;
711  }
712
713  private static final long serialVersionUID = 0;
714}