1 /*
2 * Copyright (C) 2009 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
21
22 import com.google.common.annotations.GwtCompatible;
23 import com.google.common.primitives.Ints;
24 import com.google.errorprone.annotations.CanIgnoreReturnValue;
25 import java.io.Serializable;
26 import java.math.BigInteger;
27 import java.util.NoSuchElementException;
28
29 /**
30 * A descriptor for a <i>discrete</i> {@code Comparable} domain such as all {@link Integer}
31 * instances. A discrete domain is one that supports the three basic operations: {@link #next},
32 * {@link #previous} and {@link #distance}, according to their specifications. The methods {@link
33 * #minValue} and {@link #maxValue} should also be overridden for bounded types.
34 *
35 * <p>A discrete domain always represents the <i>entire</i> set of values of its type; it cannot
36 * represent partial domains such as "prime integers" or "strings of length 5."
37 *
38 * <p>See the Guava User Guide section on <a href=
39 * "https://github.com/google/guava/wiki/RangesExplained#discrete-domains"> {@code
40 * DiscreteDomain}</a>.
41 *
42 * @author Kevin Bourrillion
43 * @since 10.0
44 */
45 @GwtCompatible
46 public abstract class DiscreteDomain<C extends Comparable> {
47
48 /**
49 * Returns the discrete domain for values of type {@code Integer}.
50 *
51 * @since 14.0 (since 10.0 as {@code DiscreteDomains.integers()})
52 */
53 public static DiscreteDomain<Integer> integers() {
54 return IntegerDomain.INSTANCE;
55 }
56
57 private static final class IntegerDomain extends DiscreteDomain<Integer> implements Serializable {
58 private static final IntegerDomain INSTANCE = new IntegerDomain();
59
60 IntegerDomain() {
61 super(true);
62 }
63
64 @Override
65 public Integer next(Integer value) {
66 int i = value;
67 return (i == Integer.MAX_VALUE) ? null : i + 1;
68 }
69
70 @Override
71 public Integer previous(Integer value) {
72 int i = value;
73 return (i == Integer.MIN_VALUE) ? null : i - 1;
74 }
75
76 @Override
77 Integer offset(Integer origin, long distance) {
78 checkNonnegative(distance, "distance");
79 return Ints.checkedCast(origin.longValue() + distance);
80 }
81
82 @Override
83 public long distance(Integer start, Integer end) {
84 return (long) end - start;
85 }
86
87 @Override
88 public Integer minValue() {
89 return Integer.MIN_VALUE;
90 }
91
92 @Override
93 public Integer maxValue() {
94 return Integer.MAX_VALUE;
95 }
96
97 private Object readResolve() {
98 return INSTANCE;
99 }
100
101 @Override
102 public String toString() {
103 return "DiscreteDomain.integers()";
104 }
105
106 private static final long serialVersionUID = 0;
107 }
108
109 /**
110 * Returns the discrete domain for values of type {@code Long}.
111 *
112 * @since 14.0 (since 10.0 as {@code DiscreteDomains.longs()})
113 */
114 public static DiscreteDomain<Long> longs() {
115 return LongDomain.INSTANCE;
116 }
117
118 private static final class LongDomain extends DiscreteDomain<Long> implements Serializable {
119 private static final LongDomain INSTANCE = new LongDomain();
120
121 LongDomain() {
122 super(true);
123 }
124
125 @Override
126 public Long next(Long value) {
127 long l = value;
128 return (l == Long.MAX_VALUE) ? null : l + 1;
129 }
130
131 @Override
132 public Long previous(Long value) {
133 long l = value;
134 return (l == Long.MIN_VALUE) ? null : l - 1;
135 }
136
137 @Override
138 Long offset(Long origin, long distance) {
139 checkNonnegative(distance, "distance");
140 long result = origin + distance;
141 if (result < 0) {
142 checkArgument(origin < 0, "overflow");
143 }
144 return result;
145 }
146
147 @Override
148 public long distance(Long start, Long end) {
149 long result = end - start;
150 if (end > start && result < 0) { // overflow
151 return Long.MAX_VALUE;
152 }
153 if (end < start && result > 0) { // underflow
154 return Long.MIN_VALUE;
155 }
156 return result;
157 }
158
159 @Override
160 public Long minValue() {
161 return Long.MIN_VALUE;
162 }
163
164 @Override
165 public Long maxValue() {
166 return Long.MAX_VALUE;
167 }
168
169 private Object readResolve() {
170 return INSTANCE;
171 }
172
173 @Override
174 public String toString() {
175 return "DiscreteDomain.longs()";
176 }
177
178 private static final long serialVersionUID = 0;
179 }
180
181 /**
182 * Returns the discrete domain for values of type {@code BigInteger}.
183 *
184 * @since 15.0
185 */
186 public static DiscreteDomain<BigInteger> bigIntegers() {
187 return BigIntegerDomain.INSTANCE;
188 }
189
190 private static final class BigIntegerDomain extends DiscreteDomain<BigInteger>
191 implements Serializable {
192 private static final BigIntegerDomain INSTANCE = new BigIntegerDomain();
193
194 BigIntegerDomain() {
195 super(true);
196 }
197
198 private static final BigInteger MIN_LONG = BigInteger.valueOf(Long.MIN_VALUE);
199 private static final BigInteger MAX_LONG = BigInteger.valueOf(Long.MAX_VALUE);
200
201 @Override
202 public BigInteger next(BigInteger value) {
203 return value.add(BigInteger.ONE);
204 }
205
206 @Override
207 public BigInteger previous(BigInteger value) {
208 return value.subtract(BigInteger.ONE);
209 }
210
211 @Override
212 BigInteger offset(BigInteger origin, long distance) {
213 checkNonnegative(distance, "distance");
214 return origin.add(BigInteger.valueOf(distance));
215 }
216
217 @Override
218 public long distance(BigInteger start, BigInteger end) {
219 return end.subtract(start).max(MIN_LONG).min(MAX_LONG).longValue();
220 }
221
222 private Object readResolve() {
223 return INSTANCE;
224 }
225
226 @Override
227 public String toString() {
228 return "DiscreteDomain.bigIntegers()";
229 }
230
231 private static final long serialVersionUID = 0;
232 }
233
234 final boolean supportsFastOffset;
235
236 /** Constructor for use by subclasses. */
237 protected DiscreteDomain() {
238 this(false);
239 }
240
241 /** Private constructor for built-in DiscreteDomains supporting fast offset. */
242 private DiscreteDomain(boolean supportsFastOffset) {
243 this.supportsFastOffset = supportsFastOffset;
244 }
245
246 /**
247 * Returns, conceptually, "origin + distance", or equivalently, the result of calling {@link
248 * #next} on {@code origin} {@code distance} times.
249 */
250 C offset(C origin, long distance) {
251 checkNonnegative(distance, "distance");
252 for (long i = 0; i < distance; i++) {
253 origin = next(origin);
254 }
255 return origin;
256 }
257
258 /**
259 * Returns the unique least value of type {@code C} that is greater than {@code value}, or {@code
260 * null} if none exists. Inverse operation to {@link #previous}.
261 *
262 * @param value any value of type {@code C}
263 * @return the least value greater than {@code value}, or {@code null} if {@code value} is {@code
264 * maxValue()}
265 */
266 public abstract C next(C value);
267
268 /**
269 * Returns the unique greatest value of type {@code C} that is less than {@code value}, or {@code
270 * null} if none exists. Inverse operation to {@link #next}.
271 *
272 * @param value any value of type {@code C}
273 * @return the greatest value less than {@code value}, or {@code null} if {@code value} is {@code
274 * minValue()}
275 */
276 public abstract C previous(C value);
277
278 /**
279 * Returns a signed value indicating how many nested invocations of {@link #next} (if positive) or
280 * {@link #previous} (if negative) are needed to reach {@code end} starting from {@code start}.
281 * For example, if {@code end = next(next(next(start)))}, then {@code distance(start, end) == 3}
282 * and {@code distance(end, start) == -3}. As well, {@code distance(a, a)} is always zero.
283 *
284 * <p>Note that this function is necessarily well-defined for any discrete type.
285 *
286 * @return the distance as described above, or {@link Long#MIN_VALUE} or {@link Long#MAX_VALUE} if
287 * the distance is too small or too large, respectively.
288 */
289 public abstract long distance(C start, C end);
290
291 /**
292 * Returns the minimum value of type {@code C}, if it has one. The minimum value is the unique
293 * value for which {@link Comparable#compareTo(Object)} never returns a positive value for any
294 * input of type {@code C}.
295 *
296 * <p>The default implementation throws {@code NoSuchElementException}.
297 *
298 * @return the minimum value of type {@code C}; never null
299 * @throws NoSuchElementException if the type has no (practical) minimum value; for example,
300 * {@link java.math.BigInteger}
301 */
302 @CanIgnoreReturnValue
303 public C minValue() {
304 throw new NoSuchElementException();
305 }
306
307 /**
308 * Returns the maximum value of type {@code C}, if it has one. The maximum value is the unique
309 * value for which {@link Comparable#compareTo(Object)} never returns a negative value for any
310 * input of type {@code C}.
311 *
312 * <p>The default implementation throws {@code NoSuchElementException}.
313 *
314 * @return the maximum value of type {@code C}; never null
315 * @throws NoSuchElementException if the type has no (practical) maximum value; for example,
316 * {@link java.math.BigInteger}
317 */
318 @CanIgnoreReturnValue
319 public C maxValue() {
320 throw new NoSuchElementException();
321 }
322 }