1 /* 2 * Copyright (C) 2009 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15 package com.google.common.collect; 16 17 import static com.google.common.base.Preconditions.checkNotNull; 18 19 import com.google.common.annotations.GwtCompatible; 20 import com.google.common.primitives.Booleans; 21 22 import java.io.Serializable; 23 import java.util.NoSuchElementException; 24 25 import javax.annotation.Nullable; 26 27 /** 28 * Implementation detail for the internal structure of {@link Range} instances. Represents 29 * a unique way of "cutting" a "number line" (actually of instances of type {@code C}, not 30 * necessarily "numbers") into two sections; this can be done below a certain value, above 31 * a certain value, below all values or above all values. With this object defined in this 32 * way, an interval can always be represented by a pair of {@code Cut} instances. 33 * 34 * @author Kevin Bourrillion 35 */ 36 @GwtCompatible 37 abstract class Cut<C extends Comparable> implements Comparable<Cut<C>>, Serializable { 38 final C endpoint; 39 40 Cut(@Nullable C endpoint) { 41 this.endpoint = endpoint; 42 } 43 44 abstract boolean isLessThan(C value); 45 46 abstract BoundType typeAsLowerBound(); 47 abstract BoundType typeAsUpperBound(); 48 49 abstract Cut<C> withLowerBoundType(BoundType boundType, DiscreteDomain<C> domain); 50 abstract Cut<C> withUpperBoundType(BoundType boundType, DiscreteDomain<C> domain); 51 52 abstract void describeAsLowerBound(StringBuilder sb); 53 abstract void describeAsUpperBound(StringBuilder sb); 54 55 abstract C leastValueAbove(DiscreteDomain<C> domain); 56 abstract C greatestValueBelow(DiscreteDomain<C> domain); 57 58 /* 59 * The canonical form is a BelowValue cut whenever possible, otherwise ABOVE_ALL, or 60 * (only in the case of types that are unbounded below) BELOW_ALL. 61 */ 62 Cut<C> canonical(DiscreteDomain<C> domain) { 63 return this; 64 } 65 66 // note: overriden by {BELOW,ABOVE}_ALL 67 @Override 68 public int compareTo(Cut<C> that) { 69 if (that == belowAll()) { 70 return 1; 71 } 72 if (that == aboveAll()) { 73 return -1; 74 } 75 int result = Range.compareOrThrow(endpoint, that.endpoint); 76 if (result != 0) { 77 return result; 78 } 79 // same value. below comes before above 80 return Booleans.compare( 81 this instanceof AboveValue, that instanceof AboveValue); 82 } 83 84 C endpoint() { 85 return endpoint; 86 } 87 88 @SuppressWarnings("unchecked") // catching CCE 89 @Override public boolean equals(Object obj) { 90 if (obj instanceof Cut) { 91 // It might not really be a Cut<C>, but we'll catch a CCE if it's not 92 Cut<C> that = (Cut<C>) obj; 93 try { 94 int compareResult = compareTo(that); 95 return compareResult == 0; 96 } catch (ClassCastException ignored) { 97 } 98 } 99 return false; 100 } 101 102 /* 103 * The implementation neither produces nor consumes any non-null instance of type C, so 104 * casting the type parameter is safe. 105 */ 106 @SuppressWarnings("unchecked") 107 static <C extends Comparable> Cut<C> belowAll() { 108 return (Cut<C>) BelowAll.INSTANCE; 109 } 110 111 private static final long serialVersionUID = 0; 112 113 private static final class BelowAll extends Cut<Comparable<?>> { 114 private static final BelowAll INSTANCE = new BelowAll(); 115 116 private BelowAll() { 117 super(null); 118 } 119 @Override Comparable<?> endpoint() { 120 throw new IllegalStateException("range unbounded on this side"); 121 } 122 @Override boolean isLessThan(Comparable<?> value) { 123 return true; 124 } 125 @Override BoundType typeAsLowerBound() { 126 throw new IllegalStateException(); 127 } 128 @Override BoundType typeAsUpperBound() { 129 throw new AssertionError("this statement should be unreachable"); 130 } 131 @Override Cut<Comparable<?>> withLowerBoundType(BoundType boundType, 132 DiscreteDomain<Comparable<?>> domain) { 133 throw new IllegalStateException(); 134 } 135 @Override Cut<Comparable<?>> withUpperBoundType(BoundType boundType, 136 DiscreteDomain<Comparable<?>> domain) { 137 throw new AssertionError("this statement should be unreachable"); 138 } 139 @Override void describeAsLowerBound(StringBuilder sb) { 140 sb.append("(-\u221e"); 141 } 142 @Override void describeAsUpperBound(StringBuilder sb) { 143 throw new AssertionError(); 144 } 145 @Override Comparable<?> leastValueAbove( 146 DiscreteDomain<Comparable<?>> domain) { 147 return domain.minValue(); 148 } 149 @Override Comparable<?> greatestValueBelow( 150 DiscreteDomain<Comparable<?>> domain) { 151 throw new AssertionError(); 152 } 153 @Override Cut<Comparable<?>> canonical( 154 DiscreteDomain<Comparable<?>> domain) { 155 try { 156 return Cut.<Comparable<?>>belowValue(domain.minValue()); 157 } catch (NoSuchElementException e) { 158 return this; 159 } 160 } 161 @Override public int compareTo(Cut<Comparable<?>> o) { 162 return (o == this) ? 0 : -1; 163 } 164 private Object readResolve() { 165 return INSTANCE; 166 } 167 private static final long serialVersionUID = 0; 168 } 169 170 /* 171 * The implementation neither produces nor consumes any non-null instance of 172 * type C, so casting the type parameter is safe. 173 */ 174 @SuppressWarnings("unchecked") 175 static <C extends Comparable> Cut<C> aboveAll() { 176 return (Cut<C>) AboveAll.INSTANCE; 177 } 178 179 private static final class AboveAll extends Cut<Comparable<?>> { 180 private static final AboveAll INSTANCE = new AboveAll(); 181 182 private AboveAll() { 183 super(null); 184 } 185 @Override Comparable<?> endpoint() { 186 throw new IllegalStateException("range unbounded on this side"); 187 } 188 @Override boolean isLessThan(Comparable<?> value) { 189 return false; 190 } 191 @Override BoundType typeAsLowerBound() { 192 throw new AssertionError("this statement should be unreachable"); 193 } 194 @Override BoundType typeAsUpperBound() { 195 throw new IllegalStateException(); 196 } 197 @Override Cut<Comparable<?>> withLowerBoundType(BoundType boundType, 198 DiscreteDomain<Comparable<?>> domain) { 199 throw new AssertionError("this statement should be unreachable"); 200 } 201 @Override Cut<Comparable<?>> withUpperBoundType(BoundType boundType, 202 DiscreteDomain<Comparable<?>> domain) { 203 throw new IllegalStateException(); 204 } 205 @Override void describeAsLowerBound(StringBuilder sb) { 206 throw new AssertionError(); 207 } 208 @Override void describeAsUpperBound(StringBuilder sb) { 209 sb.append("+\u221e)"); 210 } 211 @Override Comparable<?> leastValueAbove( 212 DiscreteDomain<Comparable<?>> domain) { 213 throw new AssertionError(); 214 } 215 @Override Comparable<?> greatestValueBelow( 216 DiscreteDomain<Comparable<?>> domain) { 217 return domain.maxValue(); 218 } 219 @Override public int compareTo(Cut<Comparable<?>> o) { 220 return (o == this) ? 0 : 1; 221 } 222 private Object readResolve() { 223 return INSTANCE; 224 } 225 private static final long serialVersionUID = 0; 226 } 227 228 static <C extends Comparable> Cut<C> belowValue(C endpoint) { 229 return new BelowValue<C>(endpoint); 230 } 231 232 private static final class BelowValue<C extends Comparable> extends Cut<C> { 233 BelowValue(C endpoint) { 234 super(checkNotNull(endpoint)); 235 } 236 237 @Override boolean isLessThan(C value) { 238 return Range.compareOrThrow(endpoint, value) <= 0; 239 } 240 @Override BoundType typeAsLowerBound() { 241 return BoundType.CLOSED; 242 } 243 @Override BoundType typeAsUpperBound() { 244 return BoundType.OPEN; 245 } 246 @Override Cut<C> withLowerBoundType(BoundType boundType, DiscreteDomain<C> domain) { 247 switch (boundType) { 248 case CLOSED: 249 return this; 250 case OPEN: 251 @Nullable C previous = domain.previous(endpoint); 252 return (previous == null) ? Cut.<C>belowAll() : new AboveValue<C>(previous); 253 default: 254 throw new AssertionError(); 255 } 256 } 257 @Override Cut<C> withUpperBoundType(BoundType boundType, DiscreteDomain<C> domain) { 258 switch (boundType) { 259 case CLOSED: 260 @Nullable C previous = domain.previous(endpoint); 261 return (previous == null) ? Cut.<C>aboveAll() : new AboveValue<C>(previous); 262 case OPEN: 263 return this; 264 default: 265 throw new AssertionError(); 266 } 267 } 268 @Override void describeAsLowerBound(StringBuilder sb) { 269 sb.append('[').append(endpoint); 270 } 271 @Override void describeAsUpperBound(StringBuilder sb) { 272 sb.append(endpoint).append(')'); 273 } 274 @Override C leastValueAbove(DiscreteDomain<C> domain) { 275 return endpoint; 276 } 277 @Override C greatestValueBelow(DiscreteDomain<C> domain) { 278 return domain.previous(endpoint); 279 } 280 @Override public int hashCode() { 281 return endpoint.hashCode(); 282 } 283 private static final long serialVersionUID = 0; 284 } 285 286 static <C extends Comparable> Cut<C> aboveValue(C endpoint) { 287 return new AboveValue<C>(endpoint); 288 } 289 290 private static final class AboveValue<C extends Comparable> extends Cut<C> { 291 AboveValue(C endpoint) { 292 super(checkNotNull(endpoint)); 293 } 294 295 @Override boolean isLessThan(C value) { 296 return Range.compareOrThrow(endpoint, value) < 0; 297 } 298 @Override BoundType typeAsLowerBound() { 299 return BoundType.OPEN; 300 } 301 @Override BoundType typeAsUpperBound() { 302 return BoundType.CLOSED; 303 } 304 @Override Cut<C> withLowerBoundType(BoundType boundType, DiscreteDomain<C> domain) { 305 switch (boundType) { 306 case OPEN: 307 return this; 308 case CLOSED: 309 @Nullable C next = domain.next(endpoint); 310 return (next == null) ? Cut.<C>belowAll() : belowValue(next); 311 default: 312 throw new AssertionError(); 313 } 314 } 315 @Override Cut<C> withUpperBoundType(BoundType boundType, DiscreteDomain<C> domain) { 316 switch (boundType) { 317 case OPEN: 318 @Nullable C next = domain.next(endpoint); 319 return (next == null) ? Cut.<C>aboveAll() : belowValue(next); 320 case CLOSED: 321 return this; 322 default: 323 throw new AssertionError(); 324 } 325 } 326 @Override void describeAsLowerBound(StringBuilder sb) { 327 sb.append('(').append(endpoint); 328 } 329 @Override void describeAsUpperBound(StringBuilder sb) { 330 sb.append(endpoint).append(']'); 331 } 332 @Override C leastValueAbove(DiscreteDomain<C> domain) { 333 return domain.next(endpoint); 334 } 335 @Override C greatestValueBelow(DiscreteDomain<C> domain) { 336 return endpoint; 337 } 338 @Override Cut<C> canonical(DiscreteDomain<C> domain) { 339 C next = leastValueAbove(domain); 340 return (next != null) ? belowValue(next) : Cut.<C>aboveAll(); 341 } 342 @Override public int hashCode() { 343 return ~endpoint.hashCode(); 344 } 345 private static final long serialVersionUID = 0; 346 } 347 } 348
