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