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