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