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