    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
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkNotNull;
    020    import static com.google.common.collect.Ranges.create;
    021
    022    import com.google.common.annotations.Beta;
    023    import com.google.common.annotations.GwtCompatible;
    024    import com.google.common.base.Predicate;
    025
    026    import java.io.Serializable;
    027    import java.util.Collections;
    028    import java.util.Comparator;
    029    import java.util.NoSuchElementException;
    030    import java.util.Set;
    031    import java.util.SortedSet;
    032
    033    import javax.annotation.Nullable;
    034
    035    /**
    036     * A range, sometimes known as an <i>interval</i>, is a <i>convex</i>
    037     * (informally, "contiguous" or "unbroken") portion of a particular domain.
    038     * Formally, convexity means that for any {@code a <= b <= c},
    039     * {@code range.contains(a) && range.contains(c)} implies that {@code
    040     * range.contains(b)}.
    041     *
    042     * <p>A range is characterized by its lower and upper <i>bounds</i> (extremes),
    043     * each of which can <i>open</i> (exclusive of its endpoint), <i>closed</i>
    044     * (inclusive of its endpoint), or <i>unbounded</i>. This yields nine basic
    045     * types of ranges:
    046     *
    047     * <ul>
    048     * <li>{@code (a..b) = {x | a < x < b}}
    049     * <li>{@code [a..b] = {x | a <= x <= b}}
    050     * <li>{@code [a..b) = {x | a <= x < b}}
    051     * <li>{@code (a..b] = {x | a < x <= b}}
    052     * <li>{@code (a..+∞) = {x | x > a}}
    053     * <li>{@code [a..+∞) = {x | x >= a}}
    054     * <li>{@code (-∞..b) = {x | x < b}}
    055     * <li>{@code (-∞..b] = {x | x <= b}}
    056     * <li>{@code (-∞..+∞) = all values}
    057     * </ul>
    058     *
    059     * (The notation {@code {x | statement}} is read "the set of all <i>x</i> such
    060     * that <i>statement</i>.")
    061     *
    062     * <p>Notice that we use a square bracket ({@code [ ]}) to denote that an range
    063     * is closed on that end, and a parenthesis ({@code ( )}) when it is open or
    064     * unbounded.
    065     *
    066     * <p>The values {@code a} and {@code b} used above are called <i>endpoints</i>.
    067     * The upper endpoint may not be less than the lower endpoint. The endpoints may
    068     * be equal only if at least one of the bounds is closed:
    069     *
    070     * <ul>
    071     * <li>{@code [a..a]} : singleton range
    072     * <li>{@code [a..a); (a..a]} : {@linkplain #isEmpty empty}, but valid
    073     * <li>{@code (a..a)} : <b>invalid</b>
    074     * </ul>
    075     *
    076     * <p>Instances of this type can be obtained using the static factory methods in
    077     * the {@link Ranges} class.
    078     *
    079     * <p>Instances of {@code Range} are immutable. It is strongly encouraged to
    080     * use this class only with immutable data types. When creating a range over a
    081     * mutable type, take great care not to allow the value objects to mutate after
    082     * the range is created.
    083     *
    084     * <p>In this and other range-related specifications, concepts like "equal",
    085     * "same", "unique" and so on are based on {@link Comparable#compareTo}
    086     * returning zero, not on {@link Object#equals} returning {@code true}. Of
    087     * course, when these methods are kept <i>consistent</i> (as defined in {@link
    088     * Comparable}), this is not an issue.
    089     *
    090     * <p>A range {@code a} is said to be the <i>maximal</i> range having property
    091     * <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code
    092     * a.encloses(b)}. Likewise, {@code a} is <i>minimal</i> when {@code
    093     * b.encloses(a)} for all {@code b} having property <i>P</i>. See, for example,
    094     * the definition of {@link #intersection}.
    095     *
    096     * <p>This class can be used with any type which implements {@code Comparable};
    097     * it does not require {@code Comparable<? super C>} because this would be
    098     * incompatible with pre-Java 5 types. If this class is used with a perverse
    099     * {@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
    112    public 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    }