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 com.google.common.annotations.Beta;
020import com.google.common.annotations.GwtCompatible;
021
022import java.io.Serializable;
023import java.math.BigInteger;
024import java.util.NoSuchElementException;
025
026/**
027 * A descriptor for a <i>discrete</i> {@code Comparable} domain such as all
028 * {@link Integer} instances. A discrete domain is one that supports the three basic
029 * operations: {@link #next}, {@link #previous} and {@link #distance}, according
030 * to their specifications. The methods {@link #minValue} and {@link #maxValue}
031 * should also be overridden for bounded types.
032 *
033 * <p>A discrete domain always represents the <i>entire</i> set of values of its
034 * type; it cannot represent partial domains such as "prime integers" or
035 * "strings of length 5."
036 *
037 * <p>See the Guava User Guide section on <a href=
038 * "https://github.com/google/guava/wiki/RangesExplained#discrete-domains">
039 * {@code DiscreteDomain}</a>.
040 *
041 * @author Kevin Bourrillion
042 * @since 10.0
043 */
044@GwtCompatible
045@Beta
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    @Override
061    public Integer next(Integer value) {
062      int i = value;
063      return (i == Integer.MAX_VALUE) ? null : i + 1;
064    }
065
066    @Override
067    public Integer previous(Integer value) {
068      int i = value;
069      return (i == Integer.MIN_VALUE) ? null : i - 1;
070    }
071
072    @Override
073    public long distance(Integer start, Integer end) {
074      return (long) end - start;
075    }
076
077    @Override
078    public Integer minValue() {
079      return Integer.MIN_VALUE;
080    }
081
082    @Override
083    public Integer maxValue() {
084      return Integer.MAX_VALUE;
085    }
086
087    private Object readResolve() {
088      return INSTANCE;
089    }
090
091    @Override
092    public String toString() {
093      return "DiscreteDomain.integers()";
094    }
095
096    private static final long serialVersionUID = 0;
097  }
098
099  /**
100   * Returns the discrete domain for values of type {@code Long}.
101   *
102   * @since 14.0 (since 10.0 as {@code DiscreteDomains.longs()})
103   */
104  public static DiscreteDomain<Long> longs() {
105    return LongDomain.INSTANCE;
106  }
107
108  private static final class LongDomain extends DiscreteDomain<Long> implements Serializable {
109    private static final LongDomain INSTANCE = new LongDomain();
110
111    @Override
112    public Long next(Long value) {
113      long l = value;
114      return (l == Long.MAX_VALUE) ? null : l + 1;
115    }
116
117    @Override
118    public Long previous(Long value) {
119      long l = value;
120      return (l == Long.MIN_VALUE) ? null : l - 1;
121    }
122
123    @Override
124    public long distance(Long start, Long end) {
125      long result = end - start;
126      if (end > start && result < 0) { // overflow
127        return Long.MAX_VALUE;
128      }
129      if (end < start && result > 0) { // underflow
130        return Long.MIN_VALUE;
131      }
132      return result;
133    }
134
135    @Override
136    public Long minValue() {
137      return Long.MIN_VALUE;
138    }
139
140    @Override
141    public Long maxValue() {
142      return Long.MAX_VALUE;
143    }
144
145    private Object readResolve() {
146      return INSTANCE;
147    }
148
149    @Override
150    public String toString() {
151      return "DiscreteDomain.longs()";
152    }
153
154    private static final long serialVersionUID = 0;
155  }
156
157  /**
158   * Returns the discrete domain for values of type {@code BigInteger}.
159   *
160   * @since 15.0
161   */
162  public static DiscreteDomain<BigInteger> bigIntegers() {
163    return BigIntegerDomain.INSTANCE;
164  }
165
166  private static final class BigIntegerDomain extends DiscreteDomain<BigInteger>
167      implements Serializable {
168    private static final BigIntegerDomain INSTANCE = new BigIntegerDomain();
169
170    private static final BigInteger MIN_LONG = BigInteger.valueOf(Long.MIN_VALUE);
171    private static final BigInteger MAX_LONG = BigInteger.valueOf(Long.MAX_VALUE);
172
173    @Override
174    public BigInteger next(BigInteger value) {
175      return value.add(BigInteger.ONE);
176    }
177
178    @Override
179    public BigInteger previous(BigInteger value) {
180      return value.subtract(BigInteger.ONE);
181    }
182
183    @Override
184    public long distance(BigInteger start, BigInteger end) {
185      return end
186          .subtract(start)
187          .max(MIN_LONG)
188          .min(MAX_LONG)
189          .longValue();
190    }
191
192    private Object readResolve() {
193      return INSTANCE;
194    }
195
196    @Override
197    public String toString() {
198      return "DiscreteDomain.bigIntegers()";
199    }
200
201    private static final long serialVersionUID = 0;
202  }
203
204  /** Constructor for use by subclasses. */
205  protected DiscreteDomain() {}
206
207  /**
208   * Returns the unique least value of type {@code C} that is greater than
209   * {@code value}, or {@code null} if none exists. Inverse operation to {@link
210   * #previous}.
211   *
212   * @param value any value of type {@code C}
213   * @return the least value greater than {@code value}, or {@code null} if
214   *     {@code value} is {@code maxValue()}
215   */
216  public abstract C next(C value);
217
218  /**
219   * Returns the unique greatest value of type {@code C} that is less than
220   * {@code value}, or {@code null} if none exists. Inverse operation to {@link
221   * #next}.
222   *
223   * @param value any value of type {@code C}
224   * @return the greatest value less than {@code value}, or {@code null} if
225   *     {@code value} is {@code minValue()}
226   */
227  public abstract C previous(C value);
228
229  /**
230   * Returns a signed value indicating how many nested invocations of {@link
231   * #next} (if positive) or {@link #previous} (if negative) are needed to reach
232   * {@code end} starting from {@code start}. For example, if {@code end =
233   * next(next(next(start)))}, then {@code distance(start, end) == 3} and {@code
234   * distance(end, start) == -3}. As well, {@code distance(a, a)} is always
235   * zero.
236   *
237   * <p>Note that this function is necessarily well-defined for any discrete
238   * type.
239   *
240   * @return the distance as described above, or {@link Long#MIN_VALUE} or
241   *     {@link Long#MAX_VALUE} if the distance is too small or too large,
242   *     respectively.
243   */
244  public abstract long distance(C start, C end);
245
246  /**
247   * Returns the minimum value of type {@code C}, if it has one. The minimum
248   * value is the unique value for which {@link Comparable#compareTo(Object)}
249   * never returns a positive value for any input of type {@code C}.
250   *
251   * <p>The default implementation throws {@code NoSuchElementException}.
252   *
253   * @return the minimum value of type {@code C}; never null
254   * @throws NoSuchElementException if the type has no (practical) minimum
255   *     value; for example, {@link java.math.BigInteger}
256   */
257  public C minValue() {
258    throw new NoSuchElementException();
259  }
260
261  /**
262   * Returns the maximum value of type {@code C}, if it has one. The maximum
263   * value is the unique value for which {@link Comparable#compareTo(Object)}
264   * never returns a negative value for any input of type {@code C}.
265   *
266   * <p>The default implementation throws {@code NoSuchElementException}.
267   *
268   * @return the maximum value of type {@code C}; never null
269   * @throws NoSuchElementException if the type has no (practical) maximum
270   *     value; for example, {@link java.math.BigInteger}
271   */
272  public C maxValue() {
273    throw new NoSuchElementException();
274  }
275}