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;
028
029/**
030 * A descriptor for a <i>discrete</i> {@code Comparable} domain such as all {@link Integer}
031 * instances. A discrete domain is one that supports the three basic operations: {@link #next},
032 * {@link #previous} and {@link #distance}, according to their specifications. The methods {@link
033 * #minValue} and {@link #maxValue} should also be overridden for bounded types.
034 *
035 * <p>A discrete domain always represents the <i>entire</i> set of values of its type; it cannot
036 * represent partial domains such as "prime integers" or "strings of length 5."
037 *
038 * <p>See the Guava User Guide section on <a href=
039 * "https://github.com/google/guava/wiki/RangesExplained#discrete-domains"> {@code
040 * DiscreteDomain}</a>.
041 *
042 * @author Kevin Bourrillion
043 * @since 10.0
044 */
045@GwtCompatible
046public abstract class DiscreteDomain<C extends Comparable> {
047
048  /**
049   * Returns the discrete domain for values of type {@code Integer}.
050   *
051   * @since 14.0 (since 10.0 as {@code DiscreteDomains.integers()})
052   */
053  public static DiscreteDomain<Integer> integers() {
054    return IntegerDomain.INSTANCE;
055  }
056
057  private static final class IntegerDomain extends DiscreteDomain<Integer> implements Serializable {
058    private static final IntegerDomain INSTANCE = new IntegerDomain();
059
060    IntegerDomain() {
061      super(true);
062    }
063
064    @Override
065    public Integer next(Integer value) {
066      int i = value;
067      return (i == Integer.MAX_VALUE) ? null : i + 1;
068    }
069
070    @Override
071    public Integer previous(Integer value) {
072      int i = value;
073      return (i == Integer.MIN_VALUE) ? null : i - 1;
074    }
075
076    @Override
077    Integer offset(Integer origin, long distance) {
078      checkNonnegative(distance, "distance");
079      return Ints.checkedCast(origin.longValue() + distance);
080    }
081
082    @Override
083    public long distance(Integer start, Integer end) {
084      return (long) end - start;
085    }
086
087    @Override
088    public Integer minValue() {
089      return Integer.MIN_VALUE;
090    }
091
092    @Override
093    public Integer maxValue() {
094      return Integer.MAX_VALUE;
095    }
096
097    private Object readResolve() {
098      return INSTANCE;
099    }
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}