001/*
002 * Copyright (C) 2009 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.collect.CollectPreconditions.checkNonnegative;
021
022import com.google.common.annotations.GwtCompatible;
023import com.google.common.primitives.Ints;
024import com.google.errorprone.annotations.CanIgnoreReturnValue;
025import java.io.Serializable;
026import java.math.BigInteger;
027import java.util.NoSuchElementException;
028import javax.annotation.CheckForNull;
029
030/**
031 * A descriptor for a <i>discrete</i> {@code Comparable} domain such as all {@link Integer}
032 * instances. A discrete domain is one that supports the three basic operations: {@link #next},
033 * {@link #previous} and {@link #distance}, according to their specifications. The methods {@link
034 * #minValue} and {@link #maxValue} should also be overridden for bounded types.
035 *
036 * <p>A discrete domain always represents the <i>entire</i> set of values of its type; it cannot
037 * represent partial domains such as "prime integers" or "strings of length 5."
038 *
039 * <p>See the Guava User Guide section on <a href=
040 * "https://github.com/google/guava/wiki/RangesExplained#discrete-domains">{@code
041 * DiscreteDomain}</a>.
042 *
043 * @author Kevin Bourrillion
044 * @since 10.0
045 */
046@SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989
047@GwtCompatible
048@ElementTypesAreNonnullByDefault
049public abstract class DiscreteDomain<C extends Comparable> {
050
051  /**
052   * Returns the discrete domain for values of type {@code Integer}.
053   *
054   * <p>This method always returns the same object. That object is serializable; deserializing it
055   * results in the same object too.
056   *
057   * @since 14.0 (since 10.0 as {@code DiscreteDomains.integers()})
058   */
059  public static DiscreteDomain<Integer> integers() {
060    return IntegerDomain.INSTANCE;
061  }
062
063  private static final class IntegerDomain extends DiscreteDomain<Integer> implements Serializable {
064    private static final IntegerDomain INSTANCE = new IntegerDomain();
065
066    IntegerDomain() {
067      super(true);
068    }
069
070    @Override
071    @CheckForNull
072    public Integer next(Integer value) {
073      int i = value;
074      return (i == Integer.MAX_VALUE) ? null : i + 1;
075    }
076
077    @Override
078    @CheckForNull
079    public Integer previous(Integer value) {
080      int i = value;
081      return (i == Integer.MIN_VALUE) ? null : i - 1;
082    }
083
084    @Override
085    Integer offset(Integer origin, long distance) {
086      checkNonnegative(distance, "distance");
087      return Ints.checkedCast(origin.longValue() + distance);
088    }
089
090    @Override
091    public long distance(Integer start, Integer end) {
092      return (long) end - start;
093    }
094
095    @Override
096    public Integer minValue() {
097      return Integer.MIN_VALUE;
098    }
099
100    @Override
101    public Integer maxValue() {
102      return Integer.MAX_VALUE;
103    }
104
105    private Object readResolve() {
106      return INSTANCE;
107    }
108
109    @Override
110    public String toString() {
111      return "DiscreteDomain.integers()";
112    }
113
114    private static final long serialVersionUID = 0;
115  }
116
117  /**
118   * Returns the discrete domain for values of type {@code Long}.
119   *
120   * <p>This method always returns the same object. That object is serializable; deserializing it
121   * results in the same object too.
122   *
123   * @since 14.0 (since 10.0 as {@code DiscreteDomains.longs()})
124   */
125  public static DiscreteDomain<Long> longs() {
126    return LongDomain.INSTANCE;
127  }
128
129  private static final class LongDomain extends DiscreteDomain<Long> implements Serializable {
130    private static final LongDomain INSTANCE = new LongDomain();
131
132    LongDomain() {
133      super(true);
134    }
135
136    @Override
137    @CheckForNull
138    public Long next(Long value) {
139      long l = value;
140      return (l == Long.MAX_VALUE) ? null : l + 1;
141    }
142
143    @Override
144    @CheckForNull
145    public Long previous(Long value) {
146      long l = value;
147      return (l == Long.MIN_VALUE) ? null : l - 1;
148    }
149
150    @Override
151    Long offset(Long origin, long distance) {
152      checkNonnegative(distance, "distance");
153      long result = origin + distance;
154      if (result < 0) {
155        checkArgument(origin < 0, "overflow");
156      }
157      return result;
158    }
159
160    @Override
161    public long distance(Long start, Long end) {
162      long result = end - start;
163      if (end > start && result < 0) { // overflow
164        return Long.MAX_VALUE;
165      }
166      if (end < start && result > 0) { // underflow
167        return Long.MIN_VALUE;
168      }
169      return result;
170    }
171
172    @Override
173    public Long minValue() {
174      return Long.MIN_VALUE;
175    }
176
177    @Override
178    public Long maxValue() {
179      return Long.MAX_VALUE;
180    }
181
182    private Object readResolve() {
183      return INSTANCE;
184    }
185
186    @Override
187    public String toString() {
188      return "DiscreteDomain.longs()";
189    }
190
191    private static final long serialVersionUID = 0;
192  }
193
194  /**
195   * Returns the discrete domain for values of type {@code BigInteger}.
196   *
197   * <p>This method always returns the same object. That object is serializable; deserializing it
198   * results in the same object too.
199   *
200   * @since 15.0
201   */
202  public static DiscreteDomain<BigInteger> bigIntegers() {
203    return BigIntegerDomain.INSTANCE;
204  }
205
206  private static final class BigIntegerDomain extends DiscreteDomain<BigInteger>
207      implements Serializable {
208    private static final BigIntegerDomain INSTANCE = new BigIntegerDomain();
209
210    BigIntegerDomain() {
211      super(true);
212    }
213
214    private static final BigInteger MIN_LONG = BigInteger.valueOf(Long.MIN_VALUE);
215    private static final BigInteger MAX_LONG = BigInteger.valueOf(Long.MAX_VALUE);
216
217    @Override
218    public BigInteger next(BigInteger value) {
219      return value.add(BigInteger.ONE);
220    }
221
222    @Override
223    public BigInteger previous(BigInteger value) {
224      return value.subtract(BigInteger.ONE);
225    }
226
227    @Override
228    BigInteger offset(BigInteger origin, long distance) {
229      checkNonnegative(distance, "distance");
230      return origin.add(BigInteger.valueOf(distance));
231    }
232
233    @Override
234    public long distance(BigInteger start, BigInteger end) {
235      return end.subtract(start).max(MIN_LONG).min(MAX_LONG).longValue();
236    }
237
238    private Object readResolve() {
239      return INSTANCE;
240    }
241
242    @Override
243    public String toString() {
244      return "DiscreteDomain.bigIntegers()";
245    }
246
247    private static final long serialVersionUID = 0;
248  }
249
250  final boolean supportsFastOffset;
251
252  /** Constructor for use by subclasses. */
253  protected DiscreteDomain() {
254    this(false);
255  }
256
257  /** Private constructor for built-in DiscreteDomains supporting fast offset. */
258  private DiscreteDomain(boolean supportsFastOffset) {
259    this.supportsFastOffset = supportsFastOffset;
260  }
261
262  /**
263   * Returns, conceptually, "origin + distance", or equivalently, the result of calling {@link
264   * #next} on {@code origin} {@code distance} times.
265   */
266  C offset(C origin, long distance) {
267    C current = origin;
268    checkNonnegative(distance, "distance");
269    for (long i = 0; i < distance; i++) {
270      current = next(current);
271      if (current == null) {
272        throw new IllegalArgumentException(
273            "overflowed computing offset(" + origin + ", " + distance + ")");
274      }
275    }
276    return current;
277  }
278
279  /**
280   * Returns the unique least value of type {@code C} that is greater than {@code value}, or {@code
281   * null} if none exists. Inverse operation to {@link #previous}.
282   *
283   * @param value any value of type {@code C}
284   * @return the least value greater than {@code value}, or {@code null} if {@code value} is {@code
285   *     maxValue()}
286   */
287  @CheckForNull
288  public abstract C next(C value);
289
290  /**
291   * Returns the unique greatest value of type {@code C} that is less than {@code value}, or {@code
292   * null} if none exists. Inverse operation to {@link #next}.
293   *
294   * @param value any value of type {@code C}
295   * @return the greatest value less than {@code value}, or {@code null} if {@code value} is {@code
296   *     minValue()}
297   */
298  @CheckForNull
299  public abstract C previous(C value);
300
301  /**
302   * Returns a signed value indicating how many nested invocations of {@link #next} (if positive) or
303   * {@link #previous} (if negative) are needed to reach {@code end} starting from {@code start}.
304   * For example, if {@code end = next(next(next(start)))}, then {@code distance(start, end) == 3}
305   * and {@code distance(end, start) == -3}. As well, {@code distance(a, a)} is always zero.
306   *
307   * <p>Note that this function is necessarily well-defined for any discrete type.
308   *
309   * @return the distance as described above, or {@link Long#MIN_VALUE} or {@link Long#MAX_VALUE} if
310   *     the distance is too small or too large, respectively.
311   */
312  public abstract long distance(C start, C end);
313
314  /**
315   * Returns the minimum value of type {@code C}, if it has one. The minimum value is the unique
316   * value for which {@link Comparable#compareTo(Object)} never returns a positive value for any
317   * input of type {@code C}.
318   *
319   * <p>The default implementation throws {@code NoSuchElementException}.
320   *
321   * @return the minimum value of type {@code C}; never null
322   * @throws NoSuchElementException if the type has no (practical) minimum value; for example,
323   *     {@link java.math.BigInteger}
324   */
325  @CanIgnoreReturnValue
326  public C minValue() {
327    throw new NoSuchElementException();
328  }
329
330  /**
331   * Returns the maximum value of type {@code C}, if it has one. The maximum value is the unique
332   * value for which {@link Comparable#compareTo(Object)} never returns a negative value for any
333   * input of type {@code C}.
334   *
335   * <p>The default implementation throws {@code NoSuchElementException}.
336   *
337   * @return the maximum value of type {@code C}; never null
338   * @throws NoSuchElementException if the type has no (practical) maximum value; for example,
339   *     {@link java.math.BigInteger}
340   */
341  @CanIgnoreReturnValue
342  public C maxValue() {
343    throw new NoSuchElementException();
344  }
345}