001/*
002 * Copyright (C) 2010 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.collect;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019
020import com.google.common.annotations.Beta;
021import com.google.common.annotations.GwtCompatible;
022import com.google.common.annotations.GwtIncompatible;
023import com.google.errorprone.annotations.DoNotCall;
024import java.util.Collections;
025import java.util.NoSuchElementException;
026import java.util.Set;
027
028/**
029 * A sorted set of contiguous values in a given {@link DiscreteDomain}. Example:
030 *
031 * <pre>{@code
032 * ContiguousSet.create(Range.closed(5, 42), DiscreteDomain.integers())
033 * }</pre>
034 *
035 * <p>Note that because bounded ranges over {@code int} and {@code long} values are so common, this
036 * particular example can be written as just:
037 *
038 * <pre>{@code
039 * ContiguousSet.closed(5, 42)
040 * }</pre>
041 *
042 * <p><b>Warning:</b> Be extremely careful what you do with conceptually large instances (such as
043 * {@code ContiguousSet.create(Range.greaterThan(0), DiscreteDomain.integers()}). Certain operations
044 * on such a set can be performed efficiently, but others (such as {@link Set#hashCode} or {@link
045 * Collections#frequency}) can cause major performance problems.
046 *
047 * @author Gregory Kick
048 * @since 10.0
049 */
050@GwtCompatible(emulated = true)
051@SuppressWarnings("rawtypes") // allow ungenerified Comparable types
052public abstract class ContiguousSet<C extends Comparable> extends ImmutableSortedSet<C> {
053  /**
054   * Returns a {@code ContiguousSet} containing the same values in the given domain {@linkplain
055   * Range#contains contained} by the range.
056   *
057   * @throws IllegalArgumentException if neither range nor the domain has a lower bound, or if
058   *     neither has an upper bound
059   * @since 13.0
060   */
061  public static <C extends Comparable> ContiguousSet<C> create(
062      Range<C> range, DiscreteDomain<C> domain) {
063    checkNotNull(range);
064    checkNotNull(domain);
065    Range<C> effectiveRange = range;
066    try {
067      if (!range.hasLowerBound()) {
068        effectiveRange = effectiveRange.intersection(Range.atLeast(domain.minValue()));
069      }
070      if (!range.hasUpperBound()) {
071        effectiveRange = effectiveRange.intersection(Range.atMost(domain.maxValue()));
072      }
073    } catch (NoSuchElementException e) {
074      throw new IllegalArgumentException(e);
075    }
076
077    // Per class spec, we are allowed to throw CCE if necessary
078    boolean empty =
079        effectiveRange.isEmpty()
080            || Range.compareOrThrow(
081                    range.lowerBound.leastValueAbove(domain),
082                    range.upperBound.greatestValueBelow(domain))
083                > 0;
084
085    return empty
086        ? new EmptyContiguousSet<C>(domain)
087        : new RegularContiguousSet<C>(effectiveRange, domain);
088  }
089
090  /**
091   * Returns a nonempty contiguous set containing all {@code int} values from {@code lower}
092   * (inclusive) to {@code upper} (inclusive). (These are the same values contained in {@code
093   * Range.closed(lower, upper)}.)
094   *
095   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
096   * @since 23.0
097   */
098  @Beta
099  public static ContiguousSet<Integer> closed(int lower, int upper) {
100    return create(Range.closed(lower, upper), DiscreteDomain.integers());
101  }
102
103  /**
104   * Returns a nonempty contiguous set containing all {@code long} values from {@code lower}
105   * (inclusive) to {@code upper} (inclusive). (These are the same values contained in {@code
106   * Range.closed(lower, upper)}.)
107   *
108   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
109   * @since 23.0
110   */
111  @Beta
112  public static ContiguousSet<Long> closed(long lower, long upper) {
113    return create(Range.closed(lower, upper), DiscreteDomain.longs());
114  }
115
116  /**
117   * Returns a contiguous set containing all {@code int} values from {@code lower} (inclusive) to
118   * {@code upper} (exclusive). If the endpoints are equal, an empty set is returned. (These are the
119   * same values contained in {@code Range.closedOpen(lower, upper)}.)
120   *
121   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
122   * @since 23.0
123   */
124  @Beta
125  public static ContiguousSet<Integer> closedOpen(int lower, int upper) {
126    return create(Range.closedOpen(lower, upper), DiscreteDomain.integers());
127  }
128
129  /**
130   * Returns a contiguous set containing all {@code long} values from {@code lower} (inclusive) to
131   * {@code upper} (exclusive). If the endpoints are equal, an empty set is returned. (These are the
132   * same values contained in {@code Range.closedOpen(lower, upper)}.)
133   *
134   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
135   * @since 23.0
136   */
137  @Beta
138  public static ContiguousSet<Long> closedOpen(long lower, long upper) {
139    return create(Range.closedOpen(lower, upper), DiscreteDomain.longs());
140  }
141
142  final DiscreteDomain<C> domain;
143
144  ContiguousSet(DiscreteDomain<C> domain) {
145    super(Ordering.natural());
146    this.domain = domain;
147  }
148
149  @Override
150  public ContiguousSet<C> headSet(C toElement) {
151    return headSetImpl(checkNotNull(toElement), false);
152  }
153
154  /** @since 12.0 */
155  @GwtIncompatible // NavigableSet
156  @Override
157  public ContiguousSet<C> headSet(C toElement, boolean inclusive) {
158    return headSetImpl(checkNotNull(toElement), inclusive);
159  }
160
161  @Override
162  public ContiguousSet<C> subSet(C fromElement, C toElement) {
163    checkNotNull(fromElement);
164    checkNotNull(toElement);
165    checkArgument(comparator().compare(fromElement, toElement) <= 0);
166    return subSetImpl(fromElement, true, toElement, false);
167  }
168
169  /** @since 12.0 */
170  @GwtIncompatible // NavigableSet
171  @Override
172  public ContiguousSet<C> subSet(
173      C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) {
174    checkNotNull(fromElement);
175    checkNotNull(toElement);
176    checkArgument(comparator().compare(fromElement, toElement) <= 0);
177    return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
178  }
179
180  @Override
181  public ContiguousSet<C> tailSet(C fromElement) {
182    return tailSetImpl(checkNotNull(fromElement), true);
183  }
184
185  /** @since 12.0 */
186  @GwtIncompatible // NavigableSet
187  @Override
188  public ContiguousSet<C> tailSet(C fromElement, boolean inclusive) {
189    return tailSetImpl(checkNotNull(fromElement), inclusive);
190  }
191
192  /*
193   * These methods perform most headSet, subSet, and tailSet logic, besides parameter validation.
194   */
195  @SuppressWarnings("MissingOverride") // Supermethod does not exist under GWT.
196  abstract ContiguousSet<C> headSetImpl(C toElement, boolean inclusive);
197
198  @SuppressWarnings("MissingOverride") // Supermethod does not exist under GWT.
199  abstract ContiguousSet<C> subSetImpl(
200      C fromElement, boolean fromInclusive, C toElement, boolean toInclusive);
201
202  @SuppressWarnings("MissingOverride") // Supermethod does not exist under GWT.
203  abstract ContiguousSet<C> tailSetImpl(C fromElement, boolean inclusive);
204
205  /**
206   * Returns the set of values that are contained in both this set and the other.
207   *
208   * <p>This method should always be used instead of {@link Sets#intersection} for {@link
209   * ContiguousSet} instances.
210   */
211  public abstract ContiguousSet<C> intersection(ContiguousSet<C> other);
212
213  /**
214   * Returns a range, closed on both ends, whose endpoints are the minimum and maximum values
215   * contained in this set. This is equivalent to {@code range(CLOSED, CLOSED)}.
216   *
217   * @throws NoSuchElementException if this set is empty
218   */
219  public abstract Range<C> range();
220
221  /**
222   * Returns the minimal range with the given boundary types for which all values in this set are
223   * {@linkplain Range#contains(Comparable) contained} within the range.
224   *
225   * <p>Note that this method will return ranges with unbounded endpoints if {@link BoundType#OPEN}
226   * is requested for a domain minimum or maximum. For example, if {@code set} was created from the
227   * range {@code [1..Integer.MAX_VALUE]} then {@code set.range(CLOSED, OPEN)} must return {@code
228   * [1..∞)}.
229   *
230   * @throws NoSuchElementException if this set is empty
231   */
232  public abstract Range<C> range(BoundType lowerBoundType, BoundType upperBoundType);
233
234  @Override
235  @GwtIncompatible // NavigableSet
236  ImmutableSortedSet<C> createDescendingSet() {
237    return new DescendingImmutableSortedSet<C>(this);
238  }
239
240  /** Returns a short-hand representation of the contents such as {@code "[1..100]"}. */
241  @Override
242  public String toString() {
243    return range().toString();
244  }
245
246  /**
247   * Not supported. {@code ContiguousSet} instances are constructed with {@link #create}. This
248   * method exists only to hide {@link ImmutableSet#builder} from consumers of {@code
249   * ContiguousSet}.
250   *
251   * @throws UnsupportedOperationException always
252   * @deprecated Use {@link #create}.
253   */
254  @Deprecated
255  @DoNotCall("Always throws UnsupportedOperationException")
256  public static <E> ImmutableSortedSet.Builder<E> builder() {
257    throw new UnsupportedOperationException();
258  }
259}