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 * "http://code.google.com/p/guava-libraries/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>
058      implements Serializable {
059    private static final IntegerDomain INSTANCE = new IntegerDomain();
060
061    @Override public Integer next(Integer value) {
062      int i = value;
063      return (i == Integer.MAX_VALUE) ? null : i + 1;
064    }
065
066    @Override public Integer previous(Integer value) {
067      int i = value;
068      return (i == Integer.MIN_VALUE) ? null : i - 1;
069    }
070
071    @Override public long distance(Integer start, Integer end) {
072      return (long) end - start;
073    }
074
075    @Override public Integer minValue() {
076      return Integer.MIN_VALUE;
077    }
078
079    @Override public Integer maxValue() {
080      return Integer.MAX_VALUE;
081    }
082
083    private Object readResolve() {
084      return INSTANCE;
085    }
086
087    @Override
088    public String toString() {
089      return "DiscreteDomains.integers()";
090    }
091
092    private static final long serialVersionUID = 0;
093  }
094
095  /**
096   * Returns the discrete domain for values of type {@code Long}.
097   * 
098   * @since 14.0 (since 10.0 as {@code DiscreteDomains.longs()})
099   */
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 "DiscreteDomains.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  // TODO(kevinb): make sure it's tested, and make it public
153  static DiscreteDomain<BigInteger> bigIntegers() {
154    return BigIntegerDomain.INSTANCE;
155  }
156
157  private static final class BigIntegerDomain extends DiscreteDomain<BigInteger>
158      implements Serializable {
159    private static final BigIntegerDomain INSTANCE = new BigIntegerDomain();
160
161    private static final BigInteger MIN_LONG =
162        BigInteger.valueOf(Long.MIN_VALUE);
163    private static final BigInteger MAX_LONG =
164        BigInteger.valueOf(Long.MAX_VALUE);
165
166    @Override public BigInteger next(BigInteger value) {
167      return value.add(BigInteger.ONE);
168    }
169
170    @Override public BigInteger previous(BigInteger value) {
171      return value.subtract(BigInteger.ONE);
172    }
173
174    @Override public long distance(BigInteger start, BigInteger end) {
175      return end.subtract(start).max(MIN_LONG).min(MAX_LONG).longValue();
176    }
177
178    private Object readResolve() {
179      return INSTANCE;
180    }
181
182    @Override
183    public String toString() {
184      return "DiscreteDomains.bigIntegers()";
185    }
186
187    private static final long serialVersionUID = 0;
188  }
189  
190  /** Constructor for use by subclasses. */
191  protected DiscreteDomain() {}
192
193  /**
194   * Returns the unique least value of type {@code C} that is greater than
195   * {@code value}, or {@code null} if none exists. Inverse operation to {@link
196   * #previous}.
197   *
198   * @param value any value of type {@code C}
199   * @return the least value greater than {@code value}, or {@code null} if
200   *     {@code value} is {@code maxValue()}
201   */
202  public abstract C next(C value);
203
204  /**
205   * Returns the unique greatest value of type {@code C} that is less than
206   * {@code value}, or {@code null} if none exists. Inverse operation to {@link
207   * #next}.
208   *
209   * @param value any value of type {@code C}
210   * @return the greatest value less than {@code value}, or {@code null} if
211   *     {@code value} is {@code minValue()}
212   */
213  public abstract C previous(C value);
214
215  /**
216   * Returns a signed value indicating how many nested invocations of {@link
217   * #next} (if positive) or {@link #previous} (if negative) are needed to reach
218   * {@code end} starting from {@code start}. For example, if {@code end =
219   * next(next(next(start)))}, then {@code distance(start, end) == 3} and {@code
220   * distance(end, start) == -3}. As well, {@code distance(a, a)} is always
221   * zero.
222   *
223   * <p>Note that this function is necessarily well-defined for any discrete
224   * type.
225   *
226   * @return the distance as described above, or {@link Long#MIN_VALUE} or
227   *     {@link Long#MAX_VALUE} if the distance is too small or too large,
228   *     respectively.
229   */
230  public abstract long distance(C start, C end);
231
232  /**
233   * Returns the minimum value of type {@code C}, if it has one. The minimum
234   * value is the unique value for which {@link Comparable#compareTo(Object)}
235   * never returns a positive value for any input of type {@code C}.
236   *
237   * <p>The default implementation throws {@code NoSuchElementException}.
238   *
239   * @return the minimum value of type {@code C}; never null
240   * @throws NoSuchElementException if the type has no (practical) minimum
241   *     value; for example, {@link java.math.BigInteger}
242   */
243  public C minValue() {
244    throw new NoSuchElementException();
245  }
246
247  /**
248   * Returns the maximum value of type {@code C}, if it has one. The maximum
249   * value is the unique value for which {@link Comparable#compareTo(Object)}
250   * never returns a negative value for any input of type {@code C}.
251   *
252   * <p>The default implementation throws {@code NoSuchElementException}.
253   *
254   * @return the maximum value of type {@code C}; never null
255   * @throws NoSuchElementException if the type has no (practical) maximum
256   *     value; for example, {@link java.math.BigInteger}
257   */
258  public C maxValue() {
259    throw new NoSuchElementException();
260  }
261  
262}