View Javadoc
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  import java.io.Serializable;
22  import java.util.NoSuchElementException;
23  import javax.annotation.Nullable;
24  
25  /**
26   * Implementation detail for the internal structure of {@link Range} instances. Represents
27   * a unique way of "cutting" a "number line" (actually of instances of type {@code C}, not
28   * necessarily "numbers") into two sections; this can be done below a certain value, above
29   * a certain value, below all values or above all values. With this object defined in this
30   * way, an interval can always be represented by a pair of {@code Cut} instances.
31   *
32   * @author Kevin Bourrillion
33   */
34  @GwtCompatible
35  abstract class Cut<C extends Comparable> implements Comparable<Cut<C>>, Serializable {
36    final C endpoint;
37  
38    Cut(@Nullable C endpoint) {
39      this.endpoint = endpoint;
40    }
41  
42    abstract boolean isLessThan(C value);
43  
44    abstract BoundType typeAsLowerBound();
45  
46    abstract BoundType typeAsUpperBound();
47  
48    abstract Cut<C> withLowerBoundType(BoundType boundType, DiscreteDomain<C> domain);
49  
50    abstract Cut<C> withUpperBoundType(BoundType boundType, DiscreteDomain<C> domain);
51  
52    abstract void describeAsLowerBound(StringBuilder sb);
53  
54    abstract void describeAsUpperBound(StringBuilder sb);
55  
56    abstract C leastValueAbove(DiscreteDomain<C> domain);
57  
58    abstract C greatestValueBelow(DiscreteDomain<C> domain);
59  
60    /*
61     * The canonical form is a BelowValue cut whenever possible, otherwise ABOVE_ALL, or
62     * (only in the case of types that are unbounded below) BELOW_ALL.
63     */
64    Cut<C> canonical(DiscreteDomain<C> domain) {
65      return this;
66    }
67  
68    // note: overridden by {BELOW,ABOVE}_ALL
69    @Override
70    public int compareTo(Cut<C> that) {
71      if (that == belowAll()) {
72        return 1;
73      }
74      if (that == aboveAll()) {
75        return -1;
76      }
77      int result = Range.compareOrThrow(endpoint, that.endpoint);
78      if (result != 0) {
79        return result;
80      }
81      // same value. below comes before above
82      return Booleans.compare(this instanceof AboveValue, that instanceof AboveValue);
83    }
84  
85    C endpoint() {
86      return endpoint;
87    }
88  
89    @SuppressWarnings("unchecked") // catching CCE
90    @Override
91    public boolean equals(Object obj) {
92      if (obj instanceof Cut) {
93        // It might not really be a Cut<C>, but we'll catch a CCE if it's not
94        Cut<C> that = (Cut<C>) obj;
95        try {
96          int compareResult = compareTo(that);
97          return compareResult == 0;
98        } catch (ClassCastException ignored) {
99        }
100     }
101     return false;
102   }
103 
104   // Prevent "missing hashCode" warning by explicitly forcing subclasses implement it
105   @Override public abstract int hashCode();
106 
107   /*
108    * The implementation neither produces nor consumes any non-null instance of type C, so
109    * casting the type parameter is safe.
110    */
111   @SuppressWarnings("unchecked")
112   static <C extends Comparable> Cut<C> belowAll() {
113     return (Cut<C>) BelowAll.INSTANCE;
114   }
115 
116   private static final long serialVersionUID = 0;
117 
118   private static final class BelowAll extends Cut<Comparable<?>> {
119     private static final BelowAll INSTANCE = new BelowAll();
120 
121     private BelowAll() {
122       super(null);
123     }
124 
125     @Override
126     Comparable<?> endpoint() {
127       throw new IllegalStateException("range unbounded on this side");
128     }
129 
130     @Override
131     boolean isLessThan(Comparable<?> value) {
132       return true;
133     }
134 
135     @Override
136     BoundType typeAsLowerBound() {
137       throw new IllegalStateException();
138     }
139 
140     @Override
141     BoundType typeAsUpperBound() {
142       throw new AssertionError("this statement should be unreachable");
143     }
144 
145     @Override
146     Cut<Comparable<?>> withLowerBoundType(
147         BoundType boundType, DiscreteDomain<Comparable<?>> domain) {
148       throw new IllegalStateException();
149     }
150 
151     @Override
152     Cut<Comparable<?>> withUpperBoundType(
153         BoundType boundType, DiscreteDomain<Comparable<?>> domain) {
154       throw new AssertionError("this statement should be unreachable");
155     }
156 
157     @Override
158     void describeAsLowerBound(StringBuilder sb) {
159       sb.append("(-\u221e");
160     }
161 
162     @Override
163     void describeAsUpperBound(StringBuilder sb) {
164       throw new AssertionError();
165     }
166 
167     @Override
168     Comparable<?> leastValueAbove(DiscreteDomain<Comparable<?>> domain) {
169       return domain.minValue();
170     }
171 
172     @Override
173     Comparable<?> greatestValueBelow(DiscreteDomain<Comparable<?>> domain) {
174       throw new AssertionError();
175     }
176 
177     @Override
178     Cut<Comparable<?>> canonical(DiscreteDomain<Comparable<?>> domain) {
179       try {
180         return Cut.<Comparable<?>>belowValue(domain.minValue());
181       } catch (NoSuchElementException e) {
182         return this;
183       }
184     }
185 
186     @Override
187     public int compareTo(Cut<Comparable<?>> o) {
188       return (o == this) ? 0 : -1;
189     }
190 
191     @Override
192     public int hashCode() {
193       return System.identityHashCode(this);
194     }
195 
196     @Override
197     public String toString() {
198       return "-\u221e";
199     }
200 
201     private Object readResolve() {
202       return INSTANCE;
203     }
204 
205     private static final long serialVersionUID = 0;
206   }
207 
208   /*
209    * The implementation neither produces nor consumes any non-null instance of
210    * type C, so casting the type parameter is safe.
211    */
212   @SuppressWarnings("unchecked")
213   static <C extends Comparable> Cut<C> aboveAll() {
214     return (Cut<C>) AboveAll.INSTANCE;
215   }
216 
217   private static final class AboveAll extends Cut<Comparable<?>> {
218     private static final AboveAll INSTANCE = new AboveAll();
219 
220     private AboveAll() {
221       super(null);
222     }
223 
224     @Override
225     Comparable<?> endpoint() {
226       throw new IllegalStateException("range unbounded on this side");
227     }
228 
229     @Override
230     boolean isLessThan(Comparable<?> value) {
231       return false;
232     }
233 
234     @Override
235     BoundType typeAsLowerBound() {
236       throw new AssertionError("this statement should be unreachable");
237     }
238 
239     @Override
240     BoundType typeAsUpperBound() {
241       throw new IllegalStateException();
242     }
243 
244     @Override
245     Cut<Comparable<?>> withLowerBoundType(
246         BoundType boundType, DiscreteDomain<Comparable<?>> domain) {
247       throw new AssertionError("this statement should be unreachable");
248     }
249 
250     @Override
251     Cut<Comparable<?>> withUpperBoundType(
252         BoundType boundType, DiscreteDomain<Comparable<?>> domain) {
253       throw new IllegalStateException();
254     }
255 
256     @Override
257     void describeAsLowerBound(StringBuilder sb) {
258       throw new AssertionError();
259     }
260 
261     @Override
262     void describeAsUpperBound(StringBuilder sb) {
263       sb.append("+\u221e)");
264     }
265 
266     @Override
267     Comparable<?> leastValueAbove(DiscreteDomain<Comparable<?>> domain) {
268       throw new AssertionError();
269     }
270 
271     @Override
272     Comparable<?> greatestValueBelow(DiscreteDomain<Comparable<?>> domain) {
273       return domain.maxValue();
274     }
275 
276     @Override
277     public int compareTo(Cut<Comparable<?>> o) {
278       return (o == this) ? 0 : 1;
279     }
280 
281     @Override
282     public int hashCode() {
283       return System.identityHashCode(this);
284     }
285 
286     @Override
287     public String toString() {
288       return "+\u221e";
289     }
290 
291     private Object readResolve() {
292       return INSTANCE;
293     }
294 
295     private static final long serialVersionUID = 0;
296   }
297 
298   static <C extends Comparable> Cut<C> belowValue(C endpoint) {
299     return new BelowValue<C>(endpoint);
300   }
301 
302   private static final class BelowValue<C extends Comparable> extends Cut<C> {
303     BelowValue(C endpoint) {
304       super(checkNotNull(endpoint));
305     }
306 
307     @Override
308     boolean isLessThan(C value) {
309       return Range.compareOrThrow(endpoint, value) <= 0;
310     }
311 
312     @Override
313     BoundType typeAsLowerBound() {
314       return BoundType.CLOSED;
315     }
316 
317     @Override
318     BoundType typeAsUpperBound() {
319       return BoundType.OPEN;
320     }
321 
322     @Override
323     Cut<C> withLowerBoundType(BoundType boundType, DiscreteDomain<C> domain) {
324       switch (boundType) {
325         case CLOSED:
326           return this;
327         case OPEN:
328           @Nullable C previous = domain.previous(endpoint);
329           return (previous == null) ? Cut.<C>belowAll() : new AboveValue<C>(previous);
330         default:
331           throw new AssertionError();
332       }
333     }
334 
335     @Override
336     Cut<C> withUpperBoundType(BoundType boundType, DiscreteDomain<C> domain) {
337       switch (boundType) {
338         case CLOSED:
339           @Nullable C previous = domain.previous(endpoint);
340           return (previous == null) ? Cut.<C>aboveAll() : new AboveValue<C>(previous);
341         case OPEN:
342           return this;
343         default:
344           throw new AssertionError();
345       }
346     }
347 
348     @Override
349     void describeAsLowerBound(StringBuilder sb) {
350       sb.append('[').append(endpoint);
351     }
352 
353     @Override
354     void describeAsUpperBound(StringBuilder sb) {
355       sb.append(endpoint).append(')');
356     }
357 
358     @Override
359     C leastValueAbove(DiscreteDomain<C> domain) {
360       return endpoint;
361     }
362 
363     @Override
364     C greatestValueBelow(DiscreteDomain<C> domain) {
365       return domain.previous(endpoint);
366     }
367 
368     @Override
369     public int hashCode() {
370       return endpoint.hashCode();
371     }
372 
373     @Override
374     public String toString() {
375       return "\\" + endpoint + "/";
376     }
377 
378     private static final long serialVersionUID = 0;
379   }
380 
381   static <C extends Comparable> Cut<C> aboveValue(C endpoint) {
382     return new AboveValue<C>(endpoint);
383   }
384 
385   private static final class AboveValue<C extends Comparable> extends Cut<C> {
386     AboveValue(C endpoint) {
387       super(checkNotNull(endpoint));
388     }
389 
390     @Override
391     boolean isLessThan(C value) {
392       return Range.compareOrThrow(endpoint, value) < 0;
393     }
394 
395     @Override
396     BoundType typeAsLowerBound() {
397       return BoundType.OPEN;
398     }
399 
400     @Override
401     BoundType typeAsUpperBound() {
402       return BoundType.CLOSED;
403     }
404 
405     @Override
406     Cut<C> withLowerBoundType(BoundType boundType, DiscreteDomain<C> domain) {
407       switch (boundType) {
408         case OPEN:
409           return this;
410         case CLOSED:
411           @Nullable C next = domain.next(endpoint);
412           return (next == null) ? Cut.<C>belowAll() : belowValue(next);
413         default:
414           throw new AssertionError();
415       }
416     }
417 
418     @Override
419     Cut<C> withUpperBoundType(BoundType boundType, DiscreteDomain<C> domain) {
420       switch (boundType) {
421         case OPEN:
422           @Nullable C next = domain.next(endpoint);
423           return (next == null) ? Cut.<C>aboveAll() : belowValue(next);
424         case CLOSED:
425           return this;
426         default:
427           throw new AssertionError();
428       }
429     }
430 
431     @Override
432     void describeAsLowerBound(StringBuilder sb) {
433       sb.append('(').append(endpoint);
434     }
435 
436     @Override
437     void describeAsUpperBound(StringBuilder sb) {
438       sb.append(endpoint).append(']');
439     }
440 
441     @Override
442     C leastValueAbove(DiscreteDomain<C> domain) {
443       return domain.next(endpoint);
444     }
445 
446     @Override
447     C greatestValueBelow(DiscreteDomain<C> domain) {
448       return endpoint;
449     }
450 
451     @Override
452     Cut<C> canonical(DiscreteDomain<C> domain) {
453       C next = leastValueAbove(domain);
454       return (next != null) ? belowValue(next) : Cut.<C>aboveAll();
455     }
456 
457     @Override
458     public int hashCode() {
459       return ~endpoint.hashCode();
460     }
461 
462     @Override
463     public String toString() {
464       return "/" + endpoint + "\\";
465     }
466 
467     private static final long serialVersionUID = 0;
468   }
469 }