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