View Javadoc
1   /*
2    * Copyright (C) 2010 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5    * in compliance with the License. You may obtain a copy of the License at
6    *
7    * http://www.apache.org/licenses/LICENSE-2.0
8    *
9    * Unless required by applicable law or agreed to in writing, software distributed under the License
10   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11   * or implied. See the License for the specific language governing permissions and limitations under
12   * the License.
13   */
14  
15  package com.google.common.collect;
16  
17  import static com.google.common.base.Preconditions.checkArgument;
18  import static com.google.common.base.Preconditions.checkNotNull;
19  
20  import com.google.common.annotations.Beta;
21  import com.google.common.annotations.GwtCompatible;
22  import com.google.common.annotations.GwtIncompatible;
23  import java.util.Collections;
24  import java.util.NoSuchElementException;
25  import java.util.Set;
26  
27  /**
28   * A sorted set of contiguous values in a given {@link DiscreteDomain}. Example:
29   *
30   * <pre>{@code
31   * ContiguousSet.create(Range.closed(5, 42), DiscreteDomain.integers())
32   * }</pre>
33   *
34   * <p>Note that because bounded ranges over {@code int} and {@code long} values are so common, this
35   * particular example can be written as just:
36   *
37   * <pre>{@code
38   * ContiguousSet.closed(5, 42)
39   * }</pre>
40   *
41   * <p><b>Warning:</b> Be extremely careful what you do with conceptually large instances (such as
42   * {@code ContiguousSet.create(Range.greaterThan(0), DiscreteDomain.integers()}). Certain
43   * operations on such a set can be performed efficiently, but others (such as {@link Set#hashCode}
44   * or {@link Collections#frequency}) can cause major performance problems.
45   *
46   * @author Gregory Kick
47   * @since 10.0
48   */
49  @GwtCompatible(emulated = true)
50  @SuppressWarnings("rawtypes") // allow ungenerified Comparable types
51  public abstract class ContiguousSet<C extends Comparable> extends ImmutableSortedSet<C> {
52    /**
53     * Returns a {@code ContiguousSet} containing the same values in the given domain
54     * {@linkplain Range#contains contained} by the range.
55     *
56     * @throws IllegalArgumentException if neither range nor the domain has a lower bound, or if
57     *     neither has an upper bound
58     *
59     * @since 13.0
60     */
61    public static <C extends Comparable> ContiguousSet<C> create(
62        Range<C> range, DiscreteDomain<C> domain) {
63      checkNotNull(range);
64      checkNotNull(domain);
65      Range<C> effectiveRange = range;
66      try {
67        if (!range.hasLowerBound()) {
68          effectiveRange = effectiveRange.intersection(Range.atLeast(domain.minValue()));
69        }
70        if (!range.hasUpperBound()) {
71          effectiveRange = effectiveRange.intersection(Range.atMost(domain.maxValue()));
72        }
73      } catch (NoSuchElementException e) {
74        throw new IllegalArgumentException(e);
75      }
76  
77      // Per class spec, we are allowed to throw CCE if necessary
78      boolean empty =
79          effectiveRange.isEmpty()
80              || Range.compareOrThrow(
81                      range.lowerBound.leastValueAbove(domain),
82                      range.upperBound.greatestValueBelow(domain))
83                  > 0;
84  
85      return empty
86          ? new EmptyContiguousSet<C>(domain)
87          : new RegularContiguousSet<C>(effectiveRange, domain);
88    }
89  
90    /**
91     * Returns a nonempty contiguous set containing all {@code int} values from {@code lower}
92     * (inclusive) to {@code upper} (inclusive). (These are the same values contained in {@code
93     * Range.closed(lower, upper)}.)
94     *
95     * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
96     *
97     * @since 23.0
98     */
99    @Beta
100   public static ContiguousSet<Integer> closed(int lower, int upper) {
101     return create(Range.closed(lower, upper), DiscreteDomain.integers());
102   }
103 
104   /**
105    * Returns a nonempty contiguous set containing all {@code long} values from {@code lower}
106    * (inclusive) to {@code upper} (inclusive). (These are the same values contained in {@code
107    * Range.closed(lower, upper)}.)
108    *
109    * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
110    *
111    * @since 23.0
112    */
113   @Beta
114   public static ContiguousSet<Long> closed(long lower, long upper) {
115     return create(Range.closed(lower, upper), DiscreteDomain.longs());
116   }
117 
118   /**
119    * Returns a contiguous set containing all {@code int} values from {@code lower} (inclusive) to
120    * {@code upper} (exclusive). If the endpoints are equal, an empty set is returned. (These are the
121    * same values contained in {@code Range.closedOpen(lower, upper)}.)
122    *
123    * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
124    *
125    * @since 23.0
126    */
127   @Beta
128   public static ContiguousSet<Integer> closedOpen(int lower, int upper) {
129     return create(Range.closedOpen(lower, upper), DiscreteDomain.integers());
130   }
131 
132   /**
133    * Returns a contiguous set containing all {@code long} values from {@code lower} (inclusive) to
134    * {@code upper} (exclusive). If the endpoints are equal, an empty set is returned. (These are the
135    * same values contained in {@code Range.closedOpen(lower, upper)}.)
136    *
137    * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
138    *
139    * @since 23.0
140    */
141   @Beta
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   /**
159    * @since 12.0
160    */
161   @GwtIncompatible // NavigableSet
162   @Override
163   public ContiguousSet<C> headSet(C toElement, boolean inclusive) {
164     return headSetImpl(checkNotNull(toElement), inclusive);
165   }
166 
167   @Override
168   public ContiguousSet<C> subSet(C fromElement, C toElement) {
169     checkNotNull(fromElement);
170     checkNotNull(toElement);
171     checkArgument(comparator().compare(fromElement, toElement) <= 0);
172     return subSetImpl(fromElement, true, toElement, false);
173   }
174 
175   /**
176    * @since 12.0
177    */
178   @GwtIncompatible // NavigableSet
179   @Override
180   public ContiguousSet<C> subSet(
181       C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) {
182     checkNotNull(fromElement);
183     checkNotNull(toElement);
184     checkArgument(comparator().compare(fromElement, toElement) <= 0);
185     return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
186   }
187 
188   @Override
189   public ContiguousSet<C> tailSet(C fromElement) {
190     return tailSetImpl(checkNotNull(fromElement), true);
191   }
192 
193   /**
194    * @since 12.0
195    */
196   @GwtIncompatible // NavigableSet
197   @Override
198   public ContiguousSet<C> tailSet(C fromElement, boolean inclusive) {
199     return tailSetImpl(checkNotNull(fromElement), inclusive);
200   }
201 
202   /*
203    * These methods perform most headSet, subSet, and tailSet logic, besides parameter validation.
204    */
205   // TODO(kevinb): we can probably make these real @Overrides now
206   /* @Override */
207   abstract ContiguousSet<C> headSetImpl(C toElement, boolean inclusive);
208 
209   /* @Override */
210   abstract ContiguousSet<C> subSetImpl(
211       C fromElement, boolean fromInclusive, C toElement, boolean toInclusive);
212 
213   /* @Override */
214   abstract ContiguousSet<C> tailSetImpl(C fromElement, boolean inclusive);
215 
216   /**
217    * Returns the set of values that are contained in both this set and the other.
218    *
219    * <p>This method should always be used instead of
220    * {@link Sets#intersection} for {@link ContiguousSet} instances.
221    */
222   public abstract ContiguousSet<C> intersection(ContiguousSet<C> other);
223 
224   /**
225    * Returns a range, closed on both ends, whose endpoints are the minimum and maximum values
226    * contained in this set.  This is equivalent to {@code range(CLOSED, CLOSED)}.
227    *
228    * @throws NoSuchElementException if this set is empty
229    */
230   public abstract Range<C> range();
231 
232   /**
233    * Returns the minimal range with the given boundary types for which all values in this set are
234    * {@linkplain Range#contains(Comparable) contained} within the range.
235    *
236    * <p>Note that this method will return ranges with unbounded endpoints if {@link BoundType#OPEN}
237    * is requested for a domain minimum or maximum.  For example, if {@code set} was created from the
238    * range {@code [1..Integer.MAX_VALUE]} then {@code set.range(CLOSED, OPEN)} must return
239    * {@code [1..∞)}.
240    *
241    * @throws NoSuchElementException if this set is empty
242    */
243   public abstract Range<C> range(BoundType lowerBoundType, BoundType upperBoundType);
244 
245   @Override
246   @GwtIncompatible // NavigableSet
247   ImmutableSortedSet<C> createDescendingSet() {
248     return new DescendingImmutableSortedSet<C>(this);
249   }
250 
251   /** Returns a short-hand representation of the contents such as {@code "[1..100]"}. */
252   @Override
253   public String toString() {
254     return range().toString();
255   }
256 
257   /**
258    * Not supported. {@code ContiguousSet} instances are constructed with {@link #create}. This
259    * method exists only to hide {@link ImmutableSet#builder} from consumers of {@code
260    * ContiguousSet}.
261    *
262    * @throws UnsupportedOperationException always
263    * @deprecated Use {@link #create}.
264    */
265   @Deprecated
266   public static <E> ImmutableSortedSet.Builder<E> builder() {
267     throw new UnsupportedOperationException();
268   }
269 }