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
17package com.google.common.collect;
18
19import com.google.common.annotations.Beta;
20import com.google.common.annotations.GwtCompatible;
21
22import java.io.Serializable;
23import java.math.BigInteger;
24import java.util.NoSuchElementException;
25
26/**
27 * A descriptor for a <i>discrete</i> {@code Comparable} domain such as all
28 * {@link Integer} instances. A discrete domain is one that supports the three basic
29 * operations: {@link #next}, {@link #previous} and {@link #distance}, according
30 * to their specifications. The methods {@link #minValue} and {@link #maxValue}
31 * should also be overridden for bounded types.
32 *
33 * <p>A discrete domain always represents the <i>entire</i> set of values of its
34 * type; it cannot represent partial domains such as "prime integers" or
35 * "strings of length 5."
36 *
37 * <p>See the Guava User Guide section on <a href=
38 * "http://code.google.com/p/guava-libraries/wiki/RangesExplained#Discrete_Domains">
39 * {@code DiscreteDomain}</a>.
40 *
41 * @author Kevin Bourrillion
42 * @since 10.0
43 */
44@GwtCompatible
45@Beta
46public 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>
58      implements Serializable {
59    private static final IntegerDomain INSTANCE = new IntegerDomain();
60
61    @Override public Integer next(Integer value) {
62      int i = value;
63      return (i == Integer.MAX_VALUE) ? null : i + 1;
64    }
65
66    @Override public Integer previous(Integer value) {
67      int i = value;
68      return (i == Integer.MIN_VALUE) ? null : i - 1;
69    }
70
71    @Override public long distance(Integer start, Integer end) {
72      return (long) end - start;
73    }
74
75    @Override public Integer minValue() {
76      return Integer.MIN_VALUE;
77    }
78
79    @Override public Integer maxValue() {
80      return Integer.MAX_VALUE;
81    }
82
83    private Object readResolve() {
84      return INSTANCE;
85    }
86
87    @Override
88    public String toString() {
89      return "DiscreteDomain.integers()";
90    }
91
92    private static final long serialVersionUID = 0;
93  }
94
95  /**
96   * Returns the discrete domain for values of type {@code Long}.
97   *
98   * @since 14.0 (since 10.0 as {@code DiscreteDomains.longs()})
99   */
100  public static DiscreteDomain<Long> longs() {
101    return LongDomain.INSTANCE;
102  }
103
104  private static final class LongDomain extends DiscreteDomain<Long>
105      implements Serializable {
106    private static final LongDomain INSTANCE = new LongDomain();
107
108    @Override public Long next(Long value) {
109      long l = value;
110      return (l == Long.MAX_VALUE) ? null : l + 1;
111    }
112
113    @Override public Long previous(Long value) {
114      long l = value;
115      return (l == Long.MIN_VALUE) ? null : l - 1;
116    }
117
118    @Override public long distance(Long start, Long end) {
119      long result = end - start;
120      if (end > start && result < 0) { // overflow
121        return Long.MAX_VALUE;
122      }
123      if (end < start && result > 0) { // underflow
124        return Long.MIN_VALUE;
125      }
126      return result;
127    }
128
129    @Override public Long minValue() {
130      return Long.MIN_VALUE;
131    }
132
133    @Override public Long maxValue() {
134      return Long.MAX_VALUE;
135    }
136
137    private Object readResolve() {
138      return INSTANCE;
139    }
140
141    @Override
142    public String toString() {
143      return "DiscreteDomain.longs()";
144    }
145
146    private static final long serialVersionUID = 0;
147  }
148
149  /**
150   * Returns the discrete domain for values of type {@code BigInteger}.
151   *
152   * @since 15.0
153   */
154  public static DiscreteDomain<BigInteger> bigIntegers() {
155    return BigIntegerDomain.INSTANCE;
156  }
157
158  private static final class BigIntegerDomain extends DiscreteDomain<BigInteger>
159      implements Serializable {
160    private static final BigIntegerDomain INSTANCE = new BigIntegerDomain();
161
162    private static final BigInteger MIN_LONG =
163        BigInteger.valueOf(Long.MIN_VALUE);
164    private static final BigInteger MAX_LONG =
165        BigInteger.valueOf(Long.MAX_VALUE);
166
167    @Override public BigInteger next(BigInteger value) {
168      return value.add(BigInteger.ONE);
169    }
170
171    @Override public BigInteger previous(BigInteger value) {
172      return value.subtract(BigInteger.ONE);
173    }
174
175    @Override public long distance(BigInteger start, BigInteger end) {
176      return end.subtract(start).max(MIN_LONG).min(MAX_LONG).longValue();
177    }
178
179    private Object readResolve() {
180      return INSTANCE;
181    }
182
183    @Override
184    public String toString() {
185      return "DiscreteDomain.bigIntegers()";
186    }
187
188    private static final long serialVersionUID = 0;
189  }
190
191  /** Constructor for use by subclasses. */
192  protected DiscreteDomain() {}
193
194  /**
195   * Returns the unique least value of type {@code C} that is greater than
196   * {@code value}, or {@code null} if none exists. Inverse operation to {@link
197   * #previous}.
198   *
199   * @param value any value of type {@code C}
200   * @return the least value greater than {@code value}, or {@code null} if
201   *     {@code value} is {@code maxValue()}
202   */
203  public abstract C next(C value);
204
205  /**
206   * Returns the unique greatest value of type {@code C} that is less than
207   * {@code value}, or {@code null} if none exists. Inverse operation to {@link
208   * #next}.
209   *
210   * @param value any value of type {@code C}
211   * @return the greatest value less than {@code value}, or {@code null} if
212   *     {@code value} is {@code minValue()}
213   */
214  public abstract C previous(C value);
215
216  /**
217   * Returns a signed value indicating how many nested invocations of {@link
218   * #next} (if positive) or {@link #previous} (if negative) are needed to reach
219   * {@code end} starting from {@code start}. For example, if {@code end =
220   * next(next(next(start)))}, then {@code distance(start, end) == 3} and {@code
221   * distance(end, start) == -3}. As well, {@code distance(a, a)} is always
222   * zero.
223   *
224   * <p>Note that this function is necessarily well-defined for any discrete
225   * type.
226   *
227   * @return the distance as described above, or {@link Long#MIN_VALUE} or
228   *     {@link Long#MAX_VALUE} if the distance is too small or too large,
229   *     respectively.
230   */
231  public abstract long distance(C start, C end);
232
233  /**
234   * Returns the minimum value of type {@code C}, if it has one. The minimum
235   * value is the unique value for which {@link Comparable#compareTo(Object)}
236   * never returns a positive value for any input of type {@code C}.
237   *
238   * <p>The default implementation throws {@code NoSuchElementException}.
239   *
240   * @return the minimum value of type {@code C}; never null
241   * @throws NoSuchElementException if the type has no (practical) minimum
242   *     value; for example, {@link java.math.BigInteger}
243   */
244  public C minValue() {
245    throw new NoSuchElementException();
246  }
247
248  /**
249   * Returns the maximum value of type {@code C}, if it has one. The maximum
250   * value is the unique value for which {@link Comparable#compareTo(Object)}
251   * never returns a negative value for any input of type {@code C}.
252   *
253   * <p>The default implementation throws {@code NoSuchElementException}.
254   *
255   * @return the maximum value of type {@code C}; never null
256   * @throws NoSuchElementException if the type has no (practical) maximum
257   *     value; for example, {@link java.math.BigInteger}
258   */
259  public C maxValue() {
260    throw new NoSuchElementException();
261  }
262
263}
264