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