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;
020import static com.google.common.collect.Ranges.create;
021
022import com.google.common.annotations.Beta;
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.base.Equivalence;
025import com.google.common.base.Predicate;
026
027import java.io.Serializable;
028import java.util.Collections;
029import java.util.Comparator;
030import java.util.Set;
031import java.util.SortedSet;
032
033import javax.annotation.Nullable;
034
035/**
036 * A range (or "interval") defines the <i>boundaries</i> around a contiguous span of values of some
037 * {@code Comparable} type; for example, "integers from 1 to 100 inclusive." Note that it is not
038 * possible to <i>iterate</i> over these contained values unless an appropriate {@link
039 * DiscreteDomain} can be provided to the {@link #asSet asSet} method.
040 *
041 * <h3>Types of ranges</h3>
042 *
043 * <p>Each end of the range may be bounded or unbounded. If bounded, there is an associated
044 * <i>endpoint</i> value, and the range is considered to be either <i>open</i> (does not include the
045 * endpoint) or <i>closed</i> (includes the endpoint) on that side. With three possibilities on each
046 * side, this yields nine basic types of ranges, enumerated below. (Notation: a square bracket
047 * ({@code [ ]}) indicates that the range is closed on that side; a parenthesis ({@code ( )}) means
048 * it is either open or unbounded. The construct {@code {x | statement}} is read "the set of all
049 * <i>x</i> such that <i>statement</i>.")
050 *
051 * <blockquote><table>
052 * <tr><td><b>Notation</b> <td><b>Definition</b>        <td><b>Factory method</b>
053 * <tr><td>{@code (a..b)}  <td>{@code {x | a < x < b}}  <td>{@link Ranges#open open}
054 * <tr><td>{@code [a..b]}  <td>{@code {x | a <= x <= b}}<td>{@link Ranges#closed closed}
055 * <tr><td>{@code (a..b]}  <td>{@code {x | a < x <= b}} <td>{@link Ranges#openClosed openClosed}
056 * <tr><td>{@code [a..b)}  <td>{@code {x | a <= x < b}} <td>{@link Ranges#closedOpen closedOpen}
057 * <tr><td>{@code (a..+∞)} <td>{@code {x | x > a}}      <td>{@link Ranges#greaterThan greaterThan}
058 * <tr><td>{@code [a..+∞)} <td>{@code {x | x >= a}}     <td>{@link Ranges#atLeast atLeast}
059 * <tr><td>{@code (-∞..b)} <td>{@code {x | x < b}}      <td>{@link Ranges#lessThan lessThan}
060 * <tr><td>{@code (-∞..b]} <td>{@code {x | x <= b}}     <td>{@link Ranges#atMost atMost}
061 * <tr><td>{@code (-∞..+∞)}<td>{@code {x}}              <td>{@link Ranges#all all}
062 * </table></blockquote>
063 *
064 * <p>When both endpoints exist, the upper endpoint may not be less than the lower. The endpoints
065 * may be equal only if at least one of the bounds is closed:
066 *
067 * <ul>
068 * <li>{@code [a..a]} : a singleton range
069 * <li>{@code [a..a); (a..a]} : {@linkplain #isEmpty empty} ranges; also valid
070 * <li>{@code (a..a)} : <b>invalid</b>; an exception will be thrown
071 * </ul>
072 *
073 * <h3>Warnings</h3>
074 *
075 * <ul>
076 * <li>Use immutable value types only, if at all possible. If you must use a mutable type, <b>do
077 *     not</b> allow the endpoint instances to mutate after the range is created!
078 * <li>Your value type's comparison method should be {@linkplain Comparable consistent with equals}
079 *     if at all possible. Otherwise, be aware that concepts used throughout this documentation such
080 *     as "equal", "same", "unique" and so on actually refer to whether {@link Comparable#compareTo
081 *     compareTo} returns zero, not whether {@link Object#equals equals} returns {@code true}.
082 * <li>A class which implements {@code Comparable<UnrelatedType>} is very broken, and will cause
083 *     undefined horrible things to happen in {@code Range}. For now, the Range API does not prevent
084 *     its use, because this would also rule out all ungenerified (pre-JDK1.5) data types. <b>This
085 *     may change in the future.</b>
086 * </ul>
087 *
088 * <h3>Other notes</h3>
089 *
090 * <ul>
091 * <li>Instances of this type are obtained using the static factory methods in the {@link Ranges}
092 *     class.
093 * <li>Ranges are <i>convex</i>: whenever two values are contained, all values in between them must
094 *     also be contained. More formally, for any {@code c1 <= c2 <= c3} of type {@code C}, {@code
095 *     r.contains(c1) && r.contains(c3)} implies {@code r.contains(c2)}). This means that a {@code
096 *     Range<Integer>} can never be used to represent, say, "all <i>prime</i> numbers from 1 to
097 *     100."
098 * <li>When evaluated as a {@link Predicate}, a range yields the same result as invoking {@link
099 *     #contains}.
100 * <li>Terminology note: a range {@code a} is said to be the <i>maximal</i> range having property
101 *     <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code a.encloses(b)}.
102 *     Likewise, {@code a} is <i>minimal</i> when {@code b.encloses(a)} for all {@code b} having
103 *     property <i>P</i>. See, for example, the definition of {@link #intersection intersection}.
104 * </ul>
105 *
106 * <h3>Further reading</h3>
107 *
108 * <p>See the Guava User Guide article on
109 * <a href="http://code.google.com/p/guava-libraries/wiki/RangesExplained">{@code Range}</a>.
110 *
111 * @author Kevin Bourrillion
112 * @author Gregory Kick
113 * @since 10.0
114 */
115@Beta
116@GwtCompatible
117@SuppressWarnings("rawtypes")
118public final class Range<C extends Comparable> implements Predicate<C>, Serializable {
119  final Cut<C> lowerBound;
120  final Cut<C> upperBound;
121
122  Range(Cut<C> lowerBound, Cut<C> upperBound) {
123    if (lowerBound.compareTo(upperBound) > 0) {
124      throw new IllegalArgumentException("Invalid range: " + toString(lowerBound, upperBound));
125    }
126    this.lowerBound = lowerBound;
127    this.upperBound = upperBound;
128  }
129
130  /**
131   * Returns {@code true} if this range has a lower endpoint.
132   */
133  public boolean hasLowerBound() {
134    return lowerBound != Cut.belowAll();
135  }
136
137  /**
138   * Returns the lower endpoint of this range.
139   *
140   * @throws IllegalStateException if this range is unbounded below (that is, {@link
141   *     #hasLowerBound()} returns {@code false})
142   */
143  public C lowerEndpoint() {
144    return lowerBound.endpoint();
145  }
146
147  /**
148   * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if the range includes
149   * its lower endpoint, {@link BoundType#OPEN} if it does not.
150   *
151   * @throws IllegalStateException if this range is unbounded below (that is, {@link
152   *     #hasLowerBound()} returns {@code false})
153   */
154  public BoundType lowerBoundType() {
155    return lowerBound.typeAsLowerBound();
156  }
157
158  /**
159   * Returns {@code true} if this range has an upper endpoint.
160   */
161  public boolean hasUpperBound() {
162    return upperBound != Cut.aboveAll();
163  }
164
165  /**
166   * Returns the upper endpoint of this range.
167   *
168   * @throws IllegalStateException if this range is unbounded above (that is, {@link
169   *     #hasUpperBound()} returns {@code false})
170   */
171  public C upperEndpoint() {
172    return upperBound.endpoint();
173  }
174
175  /**
176   * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if the range includes
177   * its upper endpoint, {@link BoundType#OPEN} if it does not.
178   *
179   * @throws IllegalStateException if this range is unbounded above (that is, {@link
180   *     #hasUpperBound()} returns {@code false})
181   */
182  public BoundType upperBoundType() {
183    return upperBound.typeAsUpperBound();
184  }
185
186  /**
187   * Returns {@code true} if this range is of the form {@code [v..v)} or {@code (v..v]}. (This does
188   * not encompass ranges of the form {@code (v..v)}, because such ranges are <i>invalid</i> and
189   * can't be constructed at all.)
190   *
191   * <p>Note that certain discrete ranges such as the integer range {@code (3..4)} are <b>not</b>
192   * considered empty, even though they contain no actual values.
193   */
194  public boolean isEmpty() {
195    return lowerBound.equals(upperBound);
196  }
197
198  /**
199   * Returns {@code true} if {@code value} is within the bounds of this range. For example, on the
200   * range {@code [0..2)}, {@code contains(1)} returns {@code true}, while {@code contains(2)}
201   * returns {@code false}.
202   */
203  public boolean contains(C value) {
204    checkNotNull(value);
205    // let this throw CCE if there is some trickery going on
206    return lowerBound.isLessThan(value) && !upperBound.isLessThan(value);
207  }
208
209  /**
210   * Equivalent to {@link #contains}; provided only to satisfy the {@link Predicate} interface. When
211   * using a reference of type {@code Range}, always invoke {@link #contains} directly instead.
212   */
213  @Override public boolean apply(C input) {
214    return contains(input);
215  }
216
217  /**
218   * Returns {@code true} if every element in {@code values} is {@linkplain #contains contained} in
219   * this range.
220   */
221  public boolean containsAll(Iterable<? extends C> values) {
222    if (Iterables.isEmpty(values)) {
223      return true;
224    }
225
226    // this optimizes testing equality of two range-backed sets
227    if (values instanceof SortedSet) {
228      SortedSet<? extends C> set = cast(values);
229      Comparator<?> comparator = set.comparator();
230      if (Ordering.natural().equals(comparator) || comparator == null) {
231        return contains(set.first()) && contains(set.last());
232      }
233    }
234
235    for (C value : values) {
236      if (!contains(value)) {
237        return false;
238      }
239    }
240    return true;
241  }
242
243  /**
244   * Returns {@code true} if the bounds of {@code other} do not extend outside the bounds of this
245   * range. Examples:
246   *
247   * <ul>
248   * <li>{@code [3..6]} encloses {@code [4..5]}
249   * <li>{@code (3..6)} encloses {@code (3..6)}
250   * <li>{@code [3..6]} encloses {@code [4..4)} (even though the latter is empty)
251   * <li>{@code (3..6]} does not enclose {@code [3..6]}
252   * <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains every value
253   *     contained by the latter range)
254   * <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains every value
255   *     contained by the latter range)
256   * </ul>
257   *
258   * Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies {@code a.contains(v)},
259   * but as the last two examples illustrate, the converse is not always true.
260   *
261   * <p>Being reflexive, antisymmetric and transitive, the {@code encloses} relation defines a
262   * <i>partial order</i> over ranges. There exists a unique {@linkplain Ranges#all maximal} range
263   * according to this relation, and also numerous {@linkplain #isEmpty minimal} ranges. Enclosure
264   * also implies {@linkplain #isConnected connectedness}.
265   */
266  public boolean encloses(Range<C> other) {
267    return lowerBound.compareTo(other.lowerBound) <= 0
268        && upperBound.compareTo(other.upperBound) >= 0;
269  }
270
271  /**
272   * Returns {@code true} if there exists a (possibly empty) range which is {@linkplain #encloses
273   * enclosed} by both this range and {@code other}.
274   *
275   * <p>For example,
276   * <ul>
277   * <li>{@code [2, 4)} and {@code [5, 7)} are not connected
278   * <li>{@code [2, 4)} and {@code [3, 5)} are connected, because both enclose {@code [3, 4)}
279   * <li>{@code [2, 4)} and {@code [4, 6)} are connected, because both enclose the empty range
280   *     {@code [4, 4)}
281   * </ul>
282   *
283   * <p>Note that this range and {@code other} have a well-defined {@linkplain #span union} and
284   * {@linkplain #intersection intersection} (as a single, possibly-empty range) if and only if this
285   * method returns {@code true}.
286   *
287   * <p>The connectedness relation is both reflexive and symmetric, but does not form an {@linkplain
288   * Equivalence equivalence relation} as it is not transitive.
289   */
290  public boolean isConnected(Range<C> other) {
291    return lowerBound.compareTo(other.upperBound) <= 0
292        && other.lowerBound.compareTo(upperBound) <= 0;
293  }
294
295  /**
296   * Returns the maximal range {@linkplain #encloses enclosed} by both this range and {@code
297   * connectedRange}, if such a range exists.
298   *
299   * <p>For example, the intersection of {@code [1..5]} and {@code (3..7)} is {@code (3..5]}. The
300   * resulting range may be empty; for example, {@code [1..5)} intersected with {@code [5..7)}
301   * yields the empty range {@code [5..5)}.
302   *
303   * <p>The intersection exists if and only if the two ranges are {@linkplain #isConnected
304   * connected}.
305   *
306   * <p>The intersection operation is commutative, associative and idempotent, and its identity
307   * element is {@link Ranges#all}).
308   *
309   * @throws IllegalArgumentException if {@code isConnected(connectedRange)} is {@code false}
310   */
311  public Range<C> intersection(Range<C> connectedRange) {
312    Cut<C> newLower = Ordering.natural().max(lowerBound, connectedRange.lowerBound);
313    Cut<C> newUpper = Ordering.natural().min(upperBound, connectedRange.upperBound);
314    return create(newLower, newUpper);
315  }
316
317  /**
318   * Returns the minimal range that {@linkplain #encloses encloses} both this range and {@code
319   * other}. For example, the span of {@code [1..3]} and {@code (5..7)} is {@code [1..7)}.
320   *
321   * <p><i>If</i> the input ranges are {@linkplain #isConnected connected}, the returned range can
322   * also be called their <i>union</i>. If they are not, note that the span might contain values
323   * that are not contained in either input range.
324   *
325   * <p>Like {@link #intersection(Range) intersection}, this operation is commutative, associative
326   * and idempotent. Unlike it, it is always well-defined for any two input ranges.
327   */
328  public Range<C> span(Range<C> other) {
329    Cut<C> newLower = Ordering.natural().min(lowerBound, other.lowerBound);
330    Cut<C> newUpper = Ordering.natural().max(upperBound, other.upperBound);
331    return create(newLower, newUpper);
332  }
333
334  /**
335   * Returns an {@link ContiguousSet} containing the same values in the given domain
336   * {@linkplain Range#contains contained} by this range.
337   *
338   * <p><b>Note:</b> {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For
339   * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty
340   * ranges {@code [3..3)} and {@code [4..4)}.
341   *
342   * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet} view of a large
343   * range (such as {@code Ranges.greaterThan(0)}). Certain operations on such a set can be
344   * performed efficiently, but others (such as {@link Set#hashCode} or {@link
345   * Collections#frequency}) can cause major performance problems.
346   *
347   * <p>The returned set's {@link Object#toString} method returns a short-hand form of the set's
348   * contents, such as {@code "[1..100]}"}.
349   *
350   * @throws IllegalArgumentException if neither this range nor the domain has a lower bound, or if
351   *     neither has an upper bound
352   */
353  // TODO(kevinb): commit in spec to which methods are efficient?
354  @GwtCompatible(serializable = false)
355  public ContiguousSet<C> asSet(DiscreteDomain<C> domain) {
356    return ContiguousSet.create(this, domain);
357  }
358
359  /**
360   * Returns the canonical form of this range in the given domain. The canonical form has the
361   * following properties:
362   *
363   * <ul>
364   * <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for all {@code v} (in other
365   *     words, {@code a.canonical(domain).asSet(domain).equals(a.asSet(domain))}
366   * <li>uniqueness: unless {@code a.isEmpty()}, {@code a.asSet(domain).equals(b.asSet(domain))}
367   *     implies {@code a.canonical(domain).equals(b.canonical(domain))}
368   * <li>idempotence: {@code a.canonical(domain).canonical(domain).equals(a.canonical(domain))}
369   * </ul>
370   *
371   * Furthermore, this method guarantees that the range returned will be one of the following
372   * canonical forms:
373   *
374   * <ul>
375   * <li>[start..end)
376   * <li>[start..+∞)
377   * <li>(-∞..end) (only if type {@code C} is unbounded below)
378   * <li>(-∞..+∞) (only if type {@code C} is unbounded below)
379   * </ul>
380   */
381  public Range<C> canonical(DiscreteDomain<C> domain) {
382    checkNotNull(domain);
383    Cut<C> lower = lowerBound.canonical(domain);
384    Cut<C> upper = upperBound.canonical(domain);
385    return (lower == lowerBound && upper == upperBound) ? this : create(lower, upper);
386  }
387
388  /**
389   * Returns {@code true} if {@code object} is a range having the same endpoints and bound types as
390   * this range. Note that discrete ranges such as {@code (1..4)} and {@code [2..3]} are <b>not</b>
391   * equal to one another, despite the fact that they each contain precisely the same set of values.
392   * Similarly, empty ranges are not equal unless they have exactly the same representation, so
393   * {@code [3..3)}, {@code (3..3]}, {@code (4..4]} are all unequal.
394   */
395  @Override public boolean equals(@Nullable Object object) {
396    if (object instanceof Range) {
397      Range<?> other = (Range<?>) object;
398      return lowerBound.equals(other.lowerBound)
399          && upperBound.equals(other.upperBound);
400    }
401    return false;
402  }
403
404  /** Returns a hash code for this range. */
405  @Override public int hashCode() {
406    return lowerBound.hashCode() * 31 + upperBound.hashCode();
407  }
408
409  /**
410   * Returns a string representation of this range, such as {@code "[3..5)"} (other examples are
411   * listed in the class documentation).
412   */
413  @Override public String toString() {
414    return toString(lowerBound, upperBound);
415  }
416
417  private static String toString(Cut<?> lowerBound, Cut<?> upperBound) {
418    StringBuilder sb = new StringBuilder(16);
419    lowerBound.describeAsLowerBound(sb);
420    sb.append('\u2025');
421    upperBound.describeAsUpperBound(sb);
422    return sb.toString();
423  }
424
425  /**
426   * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
427   */
428  private static <T> SortedSet<T> cast(Iterable<T> iterable) {
429    return (SortedSet<T>) iterable;
430  }
431
432  @SuppressWarnings("unchecked") // this method may throw CCE
433  static int compareOrThrow(Comparable left, Comparable right) {
434    return left.compareTo(right);
435  }
436
437  private static final long serialVersionUID = 0;
438}