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.Beta;
022import com.google.common.annotations.GwtCompatible;
023import com.google.common.base.Equivalence;
024import com.google.common.base.Function;
025import com.google.common.base.Predicate;
026
027import java.io.Serializable;
028import java.util.Collections;
029import java.util.Comparator;
030import java.util.Iterator;
031import java.util.NoSuchElementException;
032import java.util.Set;
033import java.util.SortedSet;
034
035import javax.annotation.Nullable;
036
037/**
038 * A range (or "interval") defines the <i>boundaries</i> around a contiguous span of values of some
039 * {@code Comparable} type; for example, "integers from 1 to 100 inclusive." Note that it is not
040 * possible to <i>iterate</i> over these contained values. To do so, pass this range instance and
041 * an appropriate {@link DiscreteDomain} to {@link ContiguousSet#create}.
042 *
043 * <h3>Types of ranges</h3>
044 *
045 * <p>Each end of the range may be bounded or unbounded. If bounded, there is an associated
046 * <i>endpoint</i> value, and the range is considered to be either <i>open</i> (does not include the
047 * endpoint) or <i>closed</i> (includes the endpoint) on that side. With three possibilities on each
048 * side, this yields nine basic types of ranges, enumerated below. (Notation: a square bracket
049 * ({@code [ ]}) indicates that the range is closed on that side; a parenthesis ({@code ( )}) means
050 * it is either open or unbounded. The construct {@code {x | statement}} is read "the set of all
051 * <i>x</i> such that <i>statement</i>.")
052 *
053 * <blockquote><table>
054 * <tr><td><b>Notation</b> <td><b>Definition</b>        <td><b>Factory method</b>
055 * <tr><td>{@code (a..b)}  <td>{@code {x | a < x < b}}  <td>{@link Range#open open}
056 * <tr><td>{@code [a..b]}  <td>{@code {x | a <= x <= b}}<td>{@link Range#closed closed}
057 * <tr><td>{@code (a..b]}  <td>{@code {x | a < x <= b}} <td>{@link Range#openClosed openClosed}
058 * <tr><td>{@code [a..b)}  <td>{@code {x | a <= x < b}} <td>{@link Range#closedOpen closedOpen}
059 * <tr><td>{@code (a..+∞)} <td>{@code {x | x > a}}      <td>{@link Range#greaterThan greaterThan}
060 * <tr><td>{@code [a..+∞)} <td>{@code {x | x >= a}}     <td>{@link Range#atLeast atLeast}
061 * <tr><td>{@code (-∞..b)} <td>{@code {x | x < b}}      <td>{@link Range#lessThan lessThan}
062 * <tr><td>{@code (-∞..b]} <td>{@code {x | x <= b}}     <td>{@link Range#atMost atMost}
063 * <tr><td>{@code (-∞..+∞)}<td>{@code {x}}              <td>{@link Range#all all}
064 * </table></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 equals}
081 *     if at all possible. Otherwise, be aware that concepts used throughout this documentation such
082 *     as "equal", "same", "unique" and so on actually refer to whether {@link Comparable#compareTo
083 *     compareTo} returns zero, not whether {@link Object#equals equals} returns {@code true}.
084 * <li>A class which implements {@code Comparable<UnrelatedType>} is very broken, and will cause
085 *     undefined horrible things to happen in {@code Range}. For now, the Range API does not prevent
086 *     its use, because this would also rule out all ungenerified (pre-JDK1.5) data types. <b>This
087 *     may change in the future.</b>
088 * </ul>
089 *
090 * <h3>Other notes</h3>
091 *
092 * <ul>
093 * <li>Instances of this type are obtained using the static factory methods in this class.
094 * <li>Ranges are <i>convex</i>: whenever two values are contained, all values in between them must
095 *     also be contained. More formally, for any {@code c1 <= c2 <= c3} of type {@code C}, {@code
096 *     r.contains(c1) && r.contains(c3)} implies {@code r.contains(c2)}). This means that a {@code
097 *     Range<Integer>} can never be used to represent, say, "all <i>prime</i> numbers from 1 to
098 *     100."
099 * <li>When evaluated as a {@link Predicate}, a range yields the same result as invoking {@link
100 *     #contains}.
101 * <li>Terminology note: a range {@code a} is said to be the <i>maximal</i> range having property
102 *     <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code a.encloses(b)}.
103 *     Likewise, {@code a} is <i>minimal</i> when {@code b.encloses(a)} for all {@code b} having
104 *     property <i>P</i>. See, for example, the definition of {@link #intersection intersection}.
105 * </ul>
106 *
107 * <h3>Further reading</h3>
108 *
109 * <p>See the Guava User Guide article on
110 * <a href="http://code.google.com/p/guava-libraries/wiki/RangesExplained">{@code Range}</a>.
111 *
112 * @author Kevin Bourrillion
113 * @author Gregory Kick
114 * @since 10.0
115 */
116@GwtCompatible
117@SuppressWarnings("rawtypes")
118public final class Range<C extends Comparable> implements Predicate<C>, Serializable {
119
120  private static final Function<Range, Cut> LOWER_BOUND_FN = new Function<Range, Cut>() {
121    @Override
122    public Cut apply(Range range) {
123      return range.lowerBound;
124    }
125  };
126
127  @SuppressWarnings("unchecked")
128  static <C extends Comparable<?>> Function<Range<C>, Cut<C>> lowerBoundFn() {
129    return (Function) LOWER_BOUND_FN;
130  }
131
132  private static final Function<Range, Cut> UPPER_BOUND_FN = new Function<Range, Cut>() {
133    @Override
134    public Cut apply(Range range) {
135      return range.upperBound;
136    }
137  };
138
139  @SuppressWarnings("unchecked")
140  static <C extends Comparable<?>> Function<Range<C>, Cut<C>> upperBoundFn() {
141    return (Function) UPPER_BOUND_FN;
142  }
143
144  static final Ordering<Range<?>> RANGE_LEX_ORDERING = new Ordering<Range<?>>() {
145    @Override
146    public int compare(Range<?> left, Range<?> right) {
147      return ComparisonChain.start()
148          .compare(left.lowerBound, right.lowerBound)
149          .compare(left.upperBound, right.upperBound)
150          .result();
151    }
152  };
153
154  static <C extends Comparable<?>> Range<C> create(
155      Cut<C> lowerBound, Cut<C> upperBound) {
156    return new Range<C>(lowerBound, upperBound);
157  }
158
159  /**
160   * Returns a range that contains all values strictly greater than {@code
161   * lower} and strictly less than {@code upper}.
162   *
163   * @throws IllegalArgumentException if {@code lower} is greater than <i>or
164   *     equal to</i> {@code upper}
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
173   * {@code lower} and less than or equal to {@code upper}.
174   *
175   * @throws IllegalArgumentException if {@code lower} is greater than {@code
176   *     upper}
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
185   * {@code lower} and strictly less than {@code upper}.
186   *
187   * @throws IllegalArgumentException if {@code lower} is greater than {@code
188   *     upper}
189   * @since 14.0
190   */
191  public static <C extends Comparable<?>> Range<C> closedOpen(
192      C lower, C upper) {
193    return create(Cut.belowValue(lower), Cut.belowValue(upper));
194  }
195
196  /**
197   * Returns a range that contains all values strictly greater than {@code
198   * lower} and less than or equal to {@code upper}.
199   *
200   * @throws IllegalArgumentException if {@code lower} is greater than {@code
201   *     upper}
202   * @since 14.0
203   */
204  public static <C extends Comparable<?>> Range<C> openClosed(
205      C lower, C upper) {
206    return create(Cut.aboveValue(lower), Cut.aboveValue(upper));
207  }
208
209  /**
210   * Returns a range that contains any value from {@code lower} to {@code
211   * upper}, where each endpoint may be either inclusive (closed) or exclusive
212   * (open).
213   *
214   * @throws IllegalArgumentException if {@code lower} is greater than {@code
215   *     upper}
216   * @since 14.0
217   */
218  public static <C extends Comparable<?>> Range<C> range(
219      C lower, BoundType lowerType, C upper, BoundType upperType) {
220    checkNotNull(lowerType);
221    checkNotNull(upperType);
222
223    Cut<C> lowerBound = (lowerType == BoundType.OPEN)
224        ? Cut.aboveValue(lower)
225        : Cut.belowValue(lower);
226    Cut<C> upperBound = (upperType == BoundType.OPEN)
227        ? Cut.belowValue(upper)
228        : Cut.aboveValue(upper);
229    return create(lowerBound, upperBound);
230  }
231
232  /**
233   * Returns a range that contains all values strictly less than {@code
234   * endpoint}.
235   *
236   * @since 14.0
237   */
238  public static <C extends Comparable<?>> Range<C> lessThan(C endpoint) {
239    return create(Cut.<C>belowAll(), Cut.belowValue(endpoint));
240  }
241
242  /**
243   * Returns a range that contains all values less than or equal to
244   * {@code endpoint}.
245   *
246   * @since 14.0
247   */
248  public static <C extends Comparable<?>> Range<C> atMost(C endpoint) {
249    return create(Cut.<C>belowAll(), Cut.aboveValue(endpoint));
250  }
251
252  /**
253   * Returns a range with no lower bound up to the given endpoint, which may be
254   * either inclusive (closed) or exclusive (open).
255   *
256   * @since 14.0
257   */
258  public static <C extends Comparable<?>> Range<C> upTo(
259      C endpoint, BoundType boundType) {
260    switch (boundType) {
261      case OPEN:
262        return lessThan(endpoint);
263      case CLOSED:
264        return atMost(endpoint);
265      default:
266        throw new AssertionError();
267    }
268  }
269
270  /**
271   * Returns a range that contains all values strictly greater than {@code
272   * endpoint}.
273   *
274   * @since 14.0
275   */
276  public static <C extends Comparable<?>> Range<C> greaterThan(C endpoint) {
277    return create(Cut.aboveValue(endpoint), Cut.<C>aboveAll());
278  }
279
280  /**
281   * Returns a range that contains all values greater than or equal to
282   * {@code endpoint}.
283   *
284   * @since 14.0
285   */
286  public static <C extends Comparable<?>> Range<C> atLeast(C endpoint) {
287    return create(Cut.belowValue(endpoint), Cut.<C>aboveAll());
288  }
289
290  /**
291   * Returns a range from the given endpoint, which may be either inclusive
292   * (closed) or exclusive (open), with no upper bound.
293   *
294   * @since 14.0
295   */
296  public static <C extends Comparable<?>> Range<C> downTo(
297      C endpoint, BoundType boundType) {
298    switch (boundType) {
299      case OPEN:
300        return greaterThan(endpoint);
301      case CLOSED:
302        return atLeast(endpoint);
303      default:
304        throw new AssertionError();
305    }
306  }
307
308  private static final Range<Comparable> ALL =
309      new Range<Comparable>(Cut.belowAll(), Cut.aboveAll());
310
311  /**
312   * Returns a range that contains every value of type {@code C}.
313   *
314   * @since 14.0
315   */
316  @SuppressWarnings("unchecked")
317  public static <C extends Comparable<?>> Range<C> all() {
318    return (Range) ALL;
319  }
320
321  /**
322   * Returns a range that {@linkplain Range#contains(Comparable) contains} only
323   * the given value. The returned range is {@linkplain BoundType#CLOSED closed}
324   * on both ends.
325   *
326   * @since 14.0
327   */
328  public static <C extends Comparable<?>> Range<C> singleton(C value) {
329    return closed(value, value);
330  }
331
332   /**
333   * Returns the minimal range that
334   * {@linkplain Range#contains(Comparable) contains} all of the given values.
335   * The returned range is {@linkplain BoundType#CLOSED closed} on both ends.
336   *
337   * @throws ClassCastException if the parameters are not <i>mutually
338   *     comparable</i>
339   * @throws NoSuchElementException if {@code values} is empty
340   * @throws NullPointerException if any of {@code values} is null
341   * @since 14.0
342   */
343  public static <C extends Comparable<?>> Range<C> encloseAll(
344      Iterable<C> values) {
345    checkNotNull(values);
346    if (values instanceof ContiguousSet) {
347      return ((ContiguousSet<C>) values).range();
348    }
349    Iterator<C> valueIterator = values.iterator();
350    C min = checkNotNull(valueIterator.next());
351    C max = min;
352    while (valueIterator.hasNext()) {
353      C value = checkNotNull(valueIterator.next());
354      min = Ordering.natural().min(min, value);
355      max = Ordering.natural().max(max, value);
356    }
357    return closed(min, max);
358  }
359
360  final Cut<C> lowerBound;
361  final Cut<C> upperBound;
362
363  private Range(Cut<C> lowerBound, Cut<C> upperBound) {
364    if (lowerBound.compareTo(upperBound) > 0 || lowerBound == Cut.<C>aboveAll()
365        || upperBound == Cut.<C>belowAll()) {
366      throw new IllegalArgumentException("Invalid range: " + toString(lowerBound, upperBound));
367    }
368    this.lowerBound = checkNotNull(lowerBound);
369    this.upperBound = checkNotNull(upperBound);
370  }
371
372  /**
373   * Returns {@code true} if this range has a lower endpoint.
374   */
375  public boolean hasLowerBound() {
376    return lowerBound != Cut.belowAll();
377  }
378
379  /**
380   * Returns the lower endpoint of this range.
381   *
382   * @throws IllegalStateException if this range is unbounded below (that is, {@link
383   *     #hasLowerBound()} returns {@code false})
384   */
385  public C lowerEndpoint() {
386    return lowerBound.endpoint();
387  }
388
389  /**
390   * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if the range includes
391   * its lower endpoint, {@link BoundType#OPEN} if it does not.
392   *
393   * @throws IllegalStateException if this range is unbounded below (that is, {@link
394   *     #hasLowerBound()} returns {@code false})
395   */
396  public BoundType lowerBoundType() {
397    return lowerBound.typeAsLowerBound();
398  }
399
400  /**
401   * Returns {@code true} if this range has an upper endpoint.
402   */
403  public boolean hasUpperBound() {
404    return upperBound != Cut.aboveAll();
405  }
406
407  /**
408   * Returns the upper endpoint of this range.
409   *
410   * @throws IllegalStateException if this range is unbounded above (that is, {@link
411   *     #hasUpperBound()} returns {@code false})
412   */
413  public C upperEndpoint() {
414    return upperBound.endpoint();
415  }
416
417  /**
418   * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if the range includes
419   * its upper endpoint, {@link BoundType#OPEN} if it does not.
420   *
421   * @throws IllegalStateException if this range is unbounded above (that is, {@link
422   *     #hasUpperBound()} returns {@code false})
423   */
424  public BoundType upperBoundType() {
425    return upperBound.typeAsUpperBound();
426  }
427
428  /**
429   * Returns {@code true} if this range is of the form {@code [v..v)} or {@code (v..v]}. (This does
430   * not encompass ranges of the form {@code (v..v)}, because such ranges are <i>invalid</i> and
431   * can't be constructed at all.)
432   *
433   * <p>Note that certain discrete ranges such as the integer range {@code (3..4)} are <b>not</b>
434   * considered empty, even though they contain no actual values.  In these cases, it may be 
435   * helpful to preprocess ranges with {@link #canonical(DiscreteDomain)}.
436   */
437  public boolean isEmpty() {
438    return lowerBound.equals(upperBound);
439  }
440
441  /**
442   * Returns {@code true} if {@code value} is within the bounds of this range. For example, on the
443   * range {@code [0..2)}, {@code contains(1)} returns {@code true}, while {@code contains(2)}
444   * returns {@code false}.
445   */
446  public boolean contains(C value) {
447    checkNotNull(value);
448    // let this throw CCE if there is some trickery going on
449    return lowerBound.isLessThan(value) && !upperBound.isLessThan(value);
450  }
451
452  /**
453   * Equivalent to {@link #contains}; provided only to satisfy the {@link Predicate} interface. When
454   * using a reference of type {@code Range}, always invoke {@link #contains} directly instead.
455   */
456  @Override public boolean apply(C input) {
457    return contains(input);
458  }
459
460  /**
461   * Returns {@code true} if every element in {@code values} is {@linkplain #contains contained} in
462   * this range.
463   */
464  public boolean containsAll(Iterable<? extends C> values) {
465    if (Iterables.isEmpty(values)) {
466      return true;
467    }
468
469    // this optimizes testing equality of two range-backed sets
470    if (values instanceof SortedSet) {
471      SortedSet<? extends C> set = cast(values);
472      Comparator<?> comparator = set.comparator();
473      if (Ordering.natural().equals(comparator) || comparator == null) {
474        return contains(set.first()) && contains(set.last());
475      }
476    }
477
478    for (C value : values) {
479      if (!contains(value)) {
480        return false;
481      }
482    }
483    return true;
484  }
485
486  /**
487   * Returns {@code true} if the bounds of {@code other} do not extend outside the bounds of this
488   * range. Examples:
489   *
490   * <ul>
491   * <li>{@code [3..6]} encloses {@code [4..5]}
492   * <li>{@code (3..6)} encloses {@code (3..6)}
493   * <li>{@code [3..6]} encloses {@code [4..4)} (even though the latter is empty)
494   * <li>{@code (3..6]} does not enclose {@code [3..6]}
495   * <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains every value
496   *     contained by the latter range)
497   * <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains every value
498   *     contained by the latter range)
499   * </ul>
500   *
501   * Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies {@code a.contains(v)},
502   * but as the last two examples illustrate, the converse is not always 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 an {@link ContiguousSet} containing the same values in the given domain
600   * {@linkplain Range#contains contained} by this range.
601   *
602   * <p><b>Note:</b> {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For
603   * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty
604   * ranges {@code [3..3)} and {@code [4..4)}.
605   *
606   * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet} view of a large
607   * range (such as {@code Range.greaterThan(0)}). Certain operations on such a set can be
608   * performed efficiently, but others (such as {@link Set#hashCode} or {@link
609   * Collections#frequency}) can cause major performance problems.
610   *
611   * <p>The returned set's {@link Object#toString} method returns a short-hand form of the set's
612   * contents, such as {@code "[1..100]}"}.
613   *
614   * @throws IllegalArgumentException if neither this range nor the domain has a lower bound, or if
615   *     neither has an upper bound
616   * @deprecated Use {@code ContiguousSet.create(range, domain)} instead.
617   */
618  // TODO(kevinb): commit in spec to which methods are efficient?
619  @Beta
620  @GwtCompatible(serializable = false)
621  @Deprecated
622  public ContiguousSet<C> asSet(DiscreteDomain<C> domain) {
623    return ContiguousSet.create(this, domain);
624  }
625
626  /**
627   * Returns the canonical form of this range in the given domain. The canonical form has the
628   * following properties:
629   *
630   * <ul>
631   * <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for all {@code v} (in other
632   *     words, {@code ContiguousSet.create(a.canonical(domain), domain).equals(
633   *     ContiguousSet.create(a, domain))}
634   * <li>uniqueness: unless {@code a.isEmpty()},
635   *     {@code ContiguousSet.create(a, domain).equals(ContiguousSet.create(b, domain))} implies
636   *     {@code a.canonical(domain).equals(b.canonical(domain))}
637   * <li>idempotence: {@code a.canonical(domain).canonical(domain).equals(a.canonical(domain))}
638   * </ul>
639   *
640   * Furthermore, this method guarantees that the range returned will be one of the following
641   * canonical forms:
642   *
643   * <ul>
644   * <li>[start..end)
645   * <li>[start..+∞)
646   * <li>(-∞..end) (only if type {@code C} is unbounded below)
647   * <li>(-∞..+∞) (only if type {@code C} is unbounded below)
648   * </ul>
649   */
650  public Range<C> canonical(DiscreteDomain<C> domain) {
651    checkNotNull(domain);
652    Cut<C> lower = lowerBound.canonical(domain);
653    Cut<C> upper = upperBound.canonical(domain);
654    return (lower == lowerBound && upper == upperBound) ? this : create(lower, upper);
655  }
656
657  /**
658   * Returns {@code true} if {@code object} is a range having the same endpoints and bound types as
659   * this range. Note that discrete ranges such as {@code (1..4)} and {@code [2..3]} are <b>not</b>
660   * equal to one another, despite the fact that they each contain precisely the same set of values.
661   * Similarly, empty ranges are not equal unless they have exactly the same representation, so
662   * {@code [3..3)}, {@code (3..3]}, {@code (4..4]} are all unequal.
663   */
664  @Override public boolean equals(@Nullable Object object) {
665    if (object instanceof Range) {
666      Range<?> other = (Range<?>) object;
667      return lowerBound.equals(other.lowerBound)
668          && upperBound.equals(other.upperBound);
669    }
670    return false;
671  }
672
673  /** Returns a hash code for this range. */
674  @Override public int hashCode() {
675    return lowerBound.hashCode() * 31 + upperBound.hashCode();
676  }
677
678  /**
679   * Returns a string representation of this range, such as {@code "[3..5)"} (other examples are
680   * listed in the class documentation).
681   */
682  @Override public String toString() {
683    return toString(lowerBound, upperBound);
684  }
685
686  private static String toString(Cut<?> lowerBound, Cut<?> upperBound) {
687    StringBuilder sb = new StringBuilder(16);
688    lowerBound.describeAsLowerBound(sb);
689    sb.append('\u2025');
690    upperBound.describeAsUpperBound(sb);
691    return sb.toString();
692  }
693
694  /**
695   * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
696   */
697  private static <T> SortedSet<T> cast(Iterable<T> iterable) {
698    return (SortedSet<T>) iterable;
699  }
700
701  Object readResolve() {
702    if (this.equals(ALL)) {
703      return all();
704    } else {
705      return this;
706    }
707  }
708
709  @SuppressWarnings("unchecked") // this method may throw CCE
710  static int compareOrThrow(Comparable left, Comparable right) {
711    return left.compareTo(right);
712  }
713
714  private static final long serialVersionUID = 0;
715}