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 com.google.errorprone.annotations.DoNotCall;
24 import java.util.Collections;
25 import java.util.NoSuchElementException;
26 import java.util.Set;
27
28 /**
29 * A sorted set of contiguous values in a given {@link DiscreteDomain}. Example:
30 *
31 * <pre>{@code
32 * ContiguousSet.create(Range.closed(5, 42), DiscreteDomain.integers())
33 * }</pre>
34 *
35 * <p>Note that because bounded ranges over {@code int} and {@code long} values are so common, this
36 * particular example can be written as just:
37 *
38 * <pre>{@code
39 * ContiguousSet.closed(5, 42)
40 * }</pre>
41 *
42 * <p><b>Warning:</b> Be extremely careful what you do with conceptually large instances (such as
43 * {@code ContiguousSet.create(Range.greaterThan(0), DiscreteDomain.integers()}). Certain operations
44 * on such a set can be performed efficiently, but others (such as {@link Set#hashCode} or {@link
45 * Collections#frequency}) can cause major performance problems.
46 *
47 * @author Gregory Kick
48 * @since 10.0
49 */
50 @GwtCompatible(emulated = true)
51 @SuppressWarnings("rawtypes") // allow ungenerified Comparable types
52 public abstract class ContiguousSet<C extends Comparable> extends ImmutableSortedSet<C> {
53 /**
54 * Returns a {@code ContiguousSet} containing the same values in the given domain {@linkplain
55 * Range#contains contained} by the range.
56 *
57 * @throws IllegalArgumentException if neither range nor the domain has a lower bound, or if
58 * neither has an upper bound
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 * @since 23.0
97 */
98 @Beta
99 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 }