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@GwtCompatible
047@ElementTypesAreNonnullByDefault
048public abstract class DiscreteDomain<C extends Comparable> {
049
050  /**
051   * Returns the discrete domain for values of type {@code Integer}.
052   *
053   * @since 14.0 (since 10.0 as {@code DiscreteDomains.integers()})
054   */
055  public static DiscreteDomain<Integer> integers() {
056    return IntegerDomain.INSTANCE;
057  }
058
059  private static final class IntegerDomain extends DiscreteDomain<Integer> implements Serializable {
060    private static final IntegerDomain INSTANCE = new IntegerDomain();
061
062    IntegerDomain() {
063      super(true);
064    }
065
066    @Override
067    @CheckForNull
068    public Integer next(Integer value) {
069      int i = value;
070      return (i == Integer.MAX_VALUE) ? null : i + 1;
071    }
072
073    @Override
074    @CheckForNull
075    public Integer previous(Integer value) {
076      int i = value;
077      return (i == Integer.MIN_VALUE) ? null : i - 1;
078    }
079
080    @Override
081    Integer offset(Integer origin, long distance) {
082      checkNonnegative(distance, "distance");
083      return Ints.checkedCast(origin.longValue() + distance);
084    }
085
086    @Override
087    public long distance(Integer start, Integer end) {
088      return (long) end - start;
089    }
090
091    @Override
092    public Integer minValue() {
093      return Integer.MIN_VALUE;
094    }
095
096    @Override
097    public Integer maxValue() {
098      return Integer.MAX_VALUE;
099    }
100
101    private Object readResolve() {
102      return INSTANCE;
103    }
104
105    @Override
106    public String toString() {
107      return "DiscreteDomain.integers()";
108    }
109
110    private static final long serialVersionUID = 0;
111  }
112
113  /**
114   * Returns the discrete domain for values of type {@code Long}.
115   *
116   * @since 14.0 (since 10.0 as {@code DiscreteDomains.longs()})
117   */
118  public static DiscreteDomain<Long> longs() {
119    return LongDomain.INSTANCE;
120  }
121
122  private static final class LongDomain extends DiscreteDomain<Long> implements Serializable {
123    private static final LongDomain INSTANCE = new LongDomain();
124
125    LongDomain() {
126      super(true);
127    }
128
129    @Override
130    @CheckForNull
131    public Long next(Long value) {
132      long l = value;
133      return (l == Long.MAX_VALUE) ? null : l + 1;
134    }
135
136    @Override
137    @CheckForNull
138    public Long previous(Long value) {
139      long l = value;
140      return (l == Long.MIN_VALUE) ? null : l - 1;
141    }
142
143    @Override
144    Long offset(Long origin, long distance) {
145      checkNonnegative(distance, "distance");
146      long result = origin + distance;
147      if (result < 0) {
148        checkArgument(origin < 0, "overflow");
149      }
150      return result;
151    }
152
153    @Override
154    public long distance(Long start, Long end) {
155      long result = end - start;
156      if (end > start && result < 0) { // overflow
157        return Long.MAX_VALUE;
158      }
159      if (end < start && result > 0) { // underflow
160        return Long.MIN_VALUE;
161      }
162      return result;
163    }
164
165    @Override
166    public Long minValue() {
167      return Long.MIN_VALUE;
168    }
169
170    @Override
171    public Long maxValue() {
172      return Long.MAX_VALUE;
173    }
174
175    private Object readResolve() {
176      return INSTANCE;
177    }
178
179    @Override
180    public String toString() {
181      return "DiscreteDomain.longs()";
182    }
183
184    private static final long serialVersionUID = 0;
185  }
186
187  /**
188   * Returns the discrete domain for values of type {@code BigInteger}.
189   *
190   * @since 15.0
191   */
192  public static DiscreteDomain<BigInteger> bigIntegers() {
193    return BigIntegerDomain.INSTANCE;
194  }
195
196  private static final class BigIntegerDomain extends DiscreteDomain<BigInteger>
197      implements Serializable {
198    private static final BigIntegerDomain INSTANCE = new BigIntegerDomain();
199
200    BigIntegerDomain() {
201      super(true);
202    }
203
204    private static final BigInteger MIN_LONG = BigInteger.valueOf(Long.MIN_VALUE);
205    private static final BigInteger MAX_LONG = BigInteger.valueOf(Long.MAX_VALUE);
206
207    @Override
208    public BigInteger next(BigInteger value) {
209      return value.add(BigInteger.ONE);
210    }
211
212    @Override
213    public BigInteger previous(BigInteger value) {
214      return value.subtract(BigInteger.ONE);
215    }
216
217    @Override
218    BigInteger offset(BigInteger origin, long distance) {
219      checkNonnegative(distance, "distance");
220      return origin.add(BigInteger.valueOf(distance));
221    }
222
223    @Override
224    public long distance(BigInteger start, BigInteger end) {
225      return end.subtract(start).max(MIN_LONG).min(MAX_LONG).longValue();
226    }
227
228    private Object readResolve() {
229      return INSTANCE;
230    }
231
232    @Override
233    public String toString() {
234      return "DiscreteDomain.bigIntegers()";
235    }
236
237    private static final long serialVersionUID = 0;
238  }
239
240  final boolean supportsFastOffset;
241
242  /** Constructor for use by subclasses. */
243  protected DiscreteDomain() {
244    this(false);
245  }
246
247  /** Private constructor for built-in DiscreteDomains supporting fast offset. */
248  private DiscreteDomain(boolean supportsFastOffset) {
249    this.supportsFastOffset = supportsFastOffset;
250  }
251
252  /**
253   * Returns, conceptually, "origin + distance", or equivalently, the result of calling {@link
254   * #next} on {@code origin} {@code distance} times.
255   */
256  C offset(C origin, long distance) {
257    C current = origin;
258    checkNonnegative(distance, "distance");
259    for (long i = 0; i < distance; i++) {
260      current = next(current);
261      if (current == null) {
262        throw new IllegalArgumentException(
263            "overflowed computing offset(" + origin + ", " + distance + ")");
264      }
265    }
266    return current;
267  }
268
269  /**
270   * Returns the unique least value of type {@code C} that is greater than {@code value}, or {@code
271   * null} if none exists. Inverse operation to {@link #previous}.
272   *
273   * @param value any value of type {@code C}
274   * @return the least value greater than {@code value}, or {@code null} if {@code value} is {@code
275   *     maxValue()}
276   */
277  @CheckForNull
278  public abstract C next(C value);
279
280  /**
281   * Returns the unique greatest value of type {@code C} that is less than {@code value}, or {@code
282   * null} if none exists. Inverse operation to {@link #next}.
283   *
284   * @param value any value of type {@code C}
285   * @return the greatest value less than {@code value}, or {@code null} if {@code value} is {@code
286   *     minValue()}
287   */
288  @CheckForNull
289  public abstract C previous(C value);
290
291  /**
292   * Returns a signed value indicating how many nested invocations of {@link #next} (if positive) or
293   * {@link #previous} (if negative) are needed to reach {@code end} starting from {@code start}.
294   * For example, if {@code end = next(next(next(start)))}, then {@code distance(start, end) == 3}
295   * and {@code distance(end, start) == -3}. As well, {@code distance(a, a)} is always zero.
296   *
297   * <p>Note that this function is necessarily well-defined for any discrete type.
298   *
299   * @return the distance as described above, or {@link Long#MIN_VALUE} or {@link Long#MAX_VALUE} if
300   *     the distance is too small or too large, respectively.
301   */
302  public abstract long distance(C start, C end);
303
304  /**
305   * Returns the minimum value of type {@code C}, if it has one. The minimum value is the unique
306   * value for which {@link Comparable#compareTo(Object)} never returns a positive value for any
307   * input of type {@code C}.
308   *
309   * <p>The default implementation throws {@code NoSuchElementException}.
310   *
311   * @return the minimum value of type {@code C}; never null
312   * @throws NoSuchElementException if the type has no (practical) minimum value; for example,
313   *     {@link java.math.BigInteger}
314   */
315  @CanIgnoreReturnValue
316  public C minValue() {
317    throw new NoSuchElementException();
318  }
319
320  /**
321   * Returns the maximum value of type {@code C}, if it has one. The maximum value is the unique
322   * value for which {@link Comparable#compareTo(Object)} never returns a negative value for any
323   * input of type {@code C}.
324   *
325   * <p>The default implementation throws {@code NoSuchElementException}.
326   *
327   * @return the maximum value of type {@code C}; never null
328   * @throws NoSuchElementException if the type has no (practical) maximum value; for example,
329   *     {@link java.math.BigInteger}
330   */
331  @CanIgnoreReturnValue
332  public C maxValue() {
333    throw new NoSuchElementException();
334  }
335}