1/*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkNotNull;
20import static com.google.common.collect.Ranges.create;
21
22import com.google.common.annotations.Beta;
23import com.google.common.annotations.GwtCompatible;
24import com.google.common.base.Predicate;
25
26import java.io.Serializable;
27import java.util.Collections;
28import java.util.Comparator;
29import java.util.NoSuchElementException;
30import java.util.Set;
31import java.util.SortedSet;
32
33import javax.annotation.Nullable;
34
35/**
36 * A range, sometimes known as an <i>interval</i>, is a <i>convex</i>
37 * (informally, "contiguous" or "unbroken") portion of a particular domain.
38 * Formally, convexity means that for any {@code a <= b <= c},
39 * {@code range.contains(a) && range.contains(c)} implies that {@code
40 * range.contains(b)}.
41 *
42 * <p>A range is characterized by its lower and upper <i>bounds</i> (extremes),
43 * each of which can <i>open</i> (exclusive of its endpoint), <i>closed</i>
44 * (inclusive of its endpoint), or <i>unbounded</i>. This yields nine basic
45 * types of ranges:
46 *
47 * <ul>
48 * <li>{@code (a..b) = {x | a < x < b}}
49 * <li>{@code [a..b] = {x | a <= x <= b}}
50 * <li>{@code [a..b) = {x | a <= x < b}}
51 * <li>{@code (a..b] = {x | a < x <= b}}
52 * <li>{@code (a..+â) = {x | x > a}}
53 * <li>{@code [a..+â) = {x | x >= a}}
54 * <li>{@code (-â..b) = {x | x < b}}
55 * <li>{@code (-â..b] = {x | x <= b}}
56 * <li>{@code (-â..+â) = all values}
57 * </ul>
58 *
59 * (The notation {@code {x | statement}} is read "the set of all <i>x</i> such
60 * that <i>statement</i>.")
61 *
62 * <p>Notice that we use a square bracket ({@code [ ]}) to denote that an range
63 * is closed on that end, and a parenthesis ({@code ( )}) when it is open or
64 * unbounded.
65 *
66 * <p>The values {@code a} and {@code b} used above are called <i>endpoints</i>.
67 * The upper endpoint may not be less than the lower endpoint. The endpoints may
68 * be equal only if at least one of the bounds is closed:
69 *
70 * <ul>
71 * <li>{@code [a..a]} : singleton range
72 * <li>{@code [a..a); (a..a]} : {@linkplain #isEmpty empty}, but valid
73 * <li>{@code (a..a)} : <b>invalid</b>
74 * </ul>
75 *
76 * <p>Instances of this type can be obtained using the static factory methods in
77 * the {@link Ranges} class.
78 *
79 * <p>Instances of {@code Range} are immutable. It is strongly encouraged to
80 * use this class only with immutable data types. When creating a range over a
81 * mutable type, take great care not to allow the value objects to mutate after
82 * the range is created.
83 *
84 * <p>In this and other range-related specifications, concepts like "equal",
85 * "same", "unique" and so on are based on {@link Comparable#compareTo}
86 * returning zero, not on {@link Object#equals} returning {@code true}. Of
87 * course, when these methods are kept <i>consistent</i> (as defined in {@link
88 * Comparable}), this is not an issue.
89 *
90 * <p>A range {@code a} is said to be the <i>maximal</i> range having property
91 * <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code
92 * a.encloses(b)}. Likewise, {@code a} is <i>minimal</i> when {@code
93 * b.encloses(a)} for all {@code b} having property <i>P</i>. See, for example,
94 * the definition of {@link #intersection}.
95 *
96 * <p>This class can be used with any type which implements {@code Comparable};
97 * it does not require {@code Comparable<? super C>} because this would be
98 * incompatible with pre-Java 5 types. If this class is used with a perverse
99 * {@code Comparable} type ({@code Foo implements Comparable<Bar>} where {@code
100 * Bar} is not a supertype of {@code Foo}), any of its methods may throw {@link
101 * ClassCastException}. (There is no good reason for such a type to exist.)
102 *
103 * <p>When evaluated as a {@link Predicate}, a range yields the same result as
104 * invoking {@link #contains}.
105 *
106 * @author Kevin Bourrillion
107 * @author Gregory Kick
108 * @since 10.0
109 */
110@GwtCompatible
111@Beta
112public final class Range<C extends Comparable>
113    implements Predicate<C>, Serializable {
114  final Cut<C> lowerBound;
115  final Cut<C> upperBound;
116
117  Range(Cut<C> lowerBound, Cut<C> upperBound) {
118    if (lowerBound.compareTo(upperBound) > 0) {
119      throw new IllegalArgumentException(
120          "Invalid range: " + toString(lowerBound, upperBound));
121    }
122    this.lowerBound = lowerBound;
123    this.upperBound = upperBound;
124  }
125
126  /**
127   * Returns {@code true} if this range has a lower endpoint.
128   */
129  public boolean hasLowerBound() {
130    return lowerBound != Cut.belowAll();
131  }
132
133  /**
134   * Returns the lower endpoint of this range.
135   *
136   * @throws IllegalStateException if this range is unbounded below (that is,
137   *     {@link #hasLowerBound()} returns {@code false})
138   */
139  public C lowerEndpoint() {
140    return lowerBound.endpoint();
141  }
142
143  /**
144   * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if
145   * the range includes its lower endpoint, {@link BoundType#OPEN} if it does
146   * not.
147   *
148   * @throws IllegalStateException if this range is unbounded below (that is,
149   *     {@link #hasLowerBound()} returns {@code false})
150   */
151  public BoundType lowerBoundType() {
152    return lowerBound.typeAsLowerBound();
153  }
154
155  /**
156   * Returns {@code true} if this range has an upper endpoint.
157   */
158  public boolean hasUpperBound() {
159    return upperBound != Cut.aboveAll();
160  }
161
162  /**
163   * Returns the upper endpoint of this range.
164   *
165   * @throws IllegalStateException if this range is unbounded above (that is,
166   *     {@link #hasUpperBound()} returns {@code false})
167   */
168  public C upperEndpoint() {
169    return upperBound.endpoint();
170  }
171
172  /**
173   * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if
174   * the range includes its upper endpoint, {@link BoundType#OPEN} if it does
175   * not.
176   *
177   * @throws IllegalStateException if this range is unbounded above (that is,
178   *     {@link #hasUpperBound()} returns {@code false})
179   */
180  public BoundType upperBoundType() {
181    return upperBound.typeAsUpperBound();
182  }
183
184  /**
185   * Returns {@code true} if this range is of the form {@code [v..v)} or {@code
186   * (v..v]}. (This does not encompass ranges of the form {@code (v..v)},
187   * because such ranges are <i>invalid</i> and can't be constructed at all.)
188   *
189   * <p>Note that certain discrete ranges such as the integer range {@code
190   * (3..4)} are <b>not</b> considered empty, even though they contain no actual
191   * values.
192   */
193  public boolean isEmpty() {
194    return lowerBound.equals(upperBound);
195  }
196
197  /**
198   * Returns {@code true} if {@code value} is within the bounds of this
199   * range. For example, on the range {@code [0..2)}, {@code contains(1)}
200   * returns {@code true}, while {@code contains(2)} returns {@code false}.
201   */
202  public boolean contains(C value) {
203    checkNotNull(value);
204    // let this throw CCE if there is some trickery going on
205    return lowerBound.isLessThan(value) && !upperBound.isLessThan(value);
206  }
207
208  /**
209   * Equivalent to {@link #contains}; provided only to satisfy the {@link
210   * Predicate} interface. When using a reference of type {@code Range}, always
211   * 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
219   * #contains contained} in 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
245   * the bounds of this 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
251   *     empty)
252   * <li>{@code (3..6]} does not enclose {@code [3..6]}
253   * <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains
254   *     every value contained by the latter range)
255   * <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains
256   *     every value contained by the latter range)
257   * </ul>
258   *
259   * Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies
260   * {@code a.contains(v)}, but as the last two examples illustrate, the
261   * converse is not always true.
262   *
263   * <p>The encloses relation has the following properties:
264   *
265   * <ul>
266   * <li>reflexive: {@code a.encloses(a)} is always true
267   * <li>antisymmetric: {@code a.encloses(b) && b.encloses(a)} implies {@code
268   *     a.equals(b)}
269   * <li>transitive: {@code a.encloses(b) && b.encloses(c)} implies {@code
270   *     a.encloses(c)}
271   * <li>not a total ordering: {@code !a.encloses(b)} does not imply {@code
272   *     b.encloses(a)}
273   * <li>there exists a {@linkplain Ranges#all maximal} range, for which
274   *     {@code encloses} is always true
275   * <li>there also exist {@linkplain #isEmpty minimal} ranges, for
276   *     which {@code encloses(b)} is always false when {@code !equals(b)}
277   * <li>if {@code a.encloses(b)}, then {@link #isConnected a.isConnected(b)}
278   *     is {@code true}.
279   * </ul>
280   */
281  public boolean encloses(Range<C> other) {
282    return lowerBound.compareTo(other.lowerBound) <= 0
283        && upperBound.compareTo(other.upperBound) >= 0;
284  }
285
286  /**
287   * Returns the maximal range {@linkplain #encloses enclosed} by both this
288   * range and {@code other}, if such a range exists.
289   *
290   * <p>For example, the intersection of {@code [1..5]} and {@code (3..7)} is
291   * {@code (3..5]}. The resulting range may be empty; for example,
292   * {@code [1..5)} intersected with {@code [5..7)} yields the empty range
293   * {@code [5..5)}.
294   *
295   * <p>Generally, the intersection exists if and only if this range and
296   * {@code other} are {@linkplain #isConnected connected}.
297   *
298   * <p>The intersection operation has the following properties:
299   *
300   * <ul>
301   * <li>commutative: {@code a.intersection(b)} produces the same result as
302   *     {@code b.intersection(a)}
303   * <li>associative: {@code a.intersection(b).intersection(c)} produces the
304   *     same result as {@code a.intersection(b.intersection(c))}
305   * <li>idempotent: {@code a.intersection(a)} equals {@code a}
306   * <li>identity ({@link Ranges#all}): {@code a.intersection(Ranges.all())}
307   *     equals {@code a}
308   * </ul>
309   *
310   * @throws IllegalArgumentException if no range exists that is enclosed by
311   *     both these ranges
312   */
313  public Range<C> intersection(Range<C> other) {
314    Cut<C> newLower = Ordering.natural().max(lowerBound, other.lowerBound);
315    Cut<C> newUpper = Ordering.natural().min(upperBound, other.upperBound);
316    return create(newLower, newUpper);
317  }
318
319  /**
320   * Returns {@code true} if there exists a (possibly empty) range which is
321   * {@linkplain #encloses enclosed} by both this range and {@code other}.
322   *
323   * <p>For example,
324   * <ul>
325   * <li>{@code [2, 4)} and {@code [5, 7)} are not connected
326   * <li>{@code [2, 4)} and {@code [3, 5)} are connected, because both enclose
327   *     {@code [3, 4)}
328   * <li>{@code [2, 4)} and {@code [4, 6)} are connected, because both enclose
329   *     the empty range {@code [4, 4)}
330   * </ul>
331   *
332   * <p>Note that this range and {@code other} have a well-defined {@linkplain
333   * #span union} and {@linkplain #intersection intersection} (as a single,
334   * possibly-empty range) if and only if this method returns {@code true}.
335   *
336   * <p>The connectedness relation has the following properties:
337   *
338   * <ul>
339   * <li>symmetric: {@code a.isConnected(b)} produces the same result as
340   *     {@code b.isConnected(a)}
341   * <li>reflexive: {@code a.isConnected(a)} returns {@code true}
342   * </ul>
343   */
344  public boolean isConnected(Range<C> other) {
345    return lowerBound.compareTo(other.upperBound) <= 0
346        && other.lowerBound.compareTo(upperBound) <= 0;
347  }
348
349  /**
350   * Returns the minimal range that {@linkplain #encloses encloses} both this
351   * range and {@code other}. For example, the span of {@code [1..3]} and
352   * {@code (5..7)} is {@code [1..7)}. Note that the span may contain values
353   * that are not contained by either original range.
354   *
355   * <p>The span operation has the following properties:
356   *
357   * <ul>
358   * <li>closed: the range {@code a.span(b)} exists for all ranges {@code a} and
359   *     {@code b}
360   * <li>commutative: {@code a.span(b)} equals {@code b.span(a)}
361   * <li>associative: {@code a.span(b).span(c)} equals {@code a.span(b.span(c))}
362   * <li>idempotent: {@code a.span(a)} equals {@code a}
363   * </ul>
364   *
365   * <p>Note that the returned range is also called the <i>union</i> of this
366   * range and {@code other} if and only if the ranges are
367   * {@linkplain #isConnected connected}.
368   */
369  public Range<C> span(Range<C> other) {
370    Cut<C> newLower = Ordering.natural().min(lowerBound, other.lowerBound);
371    Cut<C> newUpper = Ordering.natural().max(upperBound, other.upperBound);
372    return create(newLower, newUpper);
373  }
374
375  /**
376   * Returns an {@link ImmutableSortedSet} containing the same values in the
377   * given domain {@linkplain Range#contains contained} by this range.
378   *
379   * <p><b>Note:</b> {@code a.asSet().equals(b.asSet())} does not imply {@code
380   * a.equals(b)}! For example, {@code a} and {@code b} could be {@code [2..4]}
381   * and {@code (1..5)}, or the empty ranges {@code [3..3)} and {@code [4..4)}.
382   *
383   * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet}
384   * view of a large range (such as {@code Ranges.greaterThan(0)}). Certain
385   * operations on such a set can be performed efficiently, but others (such as
386   * {@link Set#hashCode} or {@link Collections#frequency}) can cause major
387   * performance problems.
388   *
389   * <p>The returned set's {@link Object#toString} method returns a short-hand
390   * form of set's contents such as {@code "[1..100]}"}.
391   *
392   * @throws IllegalArgumentException if neither this range nor the domain has a
393   *     lower bound, or if neither has an upper bound
394   */
395  // TODO(kevinb): commit in spec to which methods are efficient?
396  @GwtCompatible(serializable = false)
397  public ContiguousSet<C> asSet(DiscreteDomain<C> domain) {
398    checkNotNull(domain);
399    Range<C> effectiveRange = this;
400    try {
401      if (!hasLowerBound()) {
402        effectiveRange = effectiveRange.intersection(
403            Ranges.atLeast(domain.minValue()));
404      }
405      if (!hasUpperBound()) {
406        effectiveRange = effectiveRange.intersection(
407            Ranges.atMost(domain.maxValue()));
408      }
409    } catch (NoSuchElementException e) {
410      throw new IllegalArgumentException(e);
411    }
412
413    // Per class spec, we are allowed to throw CCE if necessary
414    boolean empty = effectiveRange.isEmpty()
415        || compareOrThrow(
416            lowerBound.leastValueAbove(domain),
417            upperBound.greatestValueBelow(domain)) > 0;
418
419    return empty
420        ? new EmptyContiguousSet<C>(domain)
421        : new RegularContiguousSet<C>(effectiveRange, domain);
422  }
423
424  /**
425   * Returns the canonical form of this range in the given domain. The canonical
426   * form has the following properties:
427   *
428   * <ul>
429   * <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for
430   *     all {@code v} (in other words, {@code
431   *     a.canonical(domain).asSet(domain).equals(a.asSet(domain))}
432   * <li>uniqueness: unless {@code a.isEmpty()},
433   *     {@code a.asSet(domain).equals(b.asSet(domain))} implies
434   *     {@code a.canonical(domain).equals(b.canonical(domain))}
435   * <li>idempotence: {@code
436   *     a.canonical(domain).canonical(domain).equals(a.canonical(domain))}
437   * </ul>
438   *
439   * Furthermore, this method guarantees that the range returned will be one
440   * of the following canonical forms:
441   *
442   * <ul>
443   * <li>[start..end)
444   * <li>[start..+â)
445   * <li>(-â..end) (only if type {@code C} is unbounded below)
446   * <li>(-â..+â) (only if type {@code C} is unbounded below)
447   * </ul>
448   */
449  public Range<C> canonical(DiscreteDomain<C> domain) {
450    checkNotNull(domain);
451    Cut<C> lower = lowerBound.canonical(domain);
452    Cut<C> upper = upperBound.canonical(domain);
453    return (lower == lowerBound && upper == upperBound)
454        ? this : create(lower, upper);
455  }
456
457  /**
458   * Returns {@code true} if {@code object} is a range having the same
459   * endpoints and bound types as this range. Note that discrete ranges
460   * such as {@code (1..4)} and {@code [2..3]} are <b>not</b> equal to one
461   * another, despite the fact that they each contain precisely the same set of
462   * values. Similarly, empty ranges are not equal unless they have exactly
463   * the same representation, so {@code [3..3)}, {@code (3..3]}, {@code (4..4]}
464   * are all unequal.
465   */
466  @Override public boolean equals(@Nullable Object object) {
467    if (object instanceof Range) {
468      Range<?> other = (Range<?>) object;
469      return lowerBound.equals(other.lowerBound)
470          && upperBound.equals(other.upperBound);
471    }
472    return false;
473  }
474
475  /** Returns a hash code for this range. */
476  @Override public int hashCode() {
477    return lowerBound.hashCode() * 31 + upperBound.hashCode();
478  }
479
480  /**
481   * Returns a string representation of this range, such as {@code "[3..5)"}
482   * (other examples are listed in the class documentation).
483   */
484  @Override public String toString() {
485    return toString(lowerBound, upperBound);
486  }
487
488  private static String toString(Cut<?> lowerBound, Cut<?> upperBound) {
489    StringBuilder sb = new StringBuilder(16);
490    lowerBound.describeAsLowerBound(sb);
491    sb.append('\u2025');
492    upperBound.describeAsUpperBound(sb);
493    return sb.toString();
494  }
495
496  /**
497   * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
498   */
499  private static <T> SortedSet<T> cast(Iterable<T> iterable) {
500    return (SortedSet<T>) iterable;
501  }
502
503  @SuppressWarnings("unchecked") // this method may throw CCE
504  static int compareOrThrow(Comparable left, Comparable right) {
505    return left.compareTo(right);
506  }
507
508  private static final long serialVersionUID = 0;
509}
510