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
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkNotNull;
18
19import com.google.common.annotations.GwtCompatible;
20import com.google.common.primitives.Booleans;
21
22import java.io.Serializable;
23import java.util.NoSuchElementException;
24
25import 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
37abstract 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    @Override public String toString() {
165      return "-\u221e";
166    }
167    private Object readResolve() {
168      return INSTANCE;
169    }
170    private static final long serialVersionUID = 0;
171  }
172
173  /*
174   * The implementation neither produces nor consumes any non-null instance of
175   * type C, so casting the type parameter is safe.
176   */
177  @SuppressWarnings("unchecked")
178  static <C extends Comparable> Cut<C> aboveAll() {
179    return (Cut<C>) AboveAll.INSTANCE;
180  }
181
182  private static final class AboveAll extends Cut<Comparable<?>> {
183    private static final AboveAll INSTANCE = new AboveAll();
184
185    private AboveAll() {
186      super(null);
187    }
188    @Override Comparable<?> endpoint() {
189      throw new IllegalStateException("range unbounded on this side");
190    }
191    @Override boolean isLessThan(Comparable<?> value) {
192      return false;
193    }
194    @Override BoundType typeAsLowerBound() {
195      throw new AssertionError("this statement should be unreachable");
196    }
197    @Override BoundType typeAsUpperBound() {
198      throw new IllegalStateException();
199    }
200    @Override Cut<Comparable<?>> withLowerBoundType(BoundType boundType,
201        DiscreteDomain<Comparable<?>> domain) {
202      throw new AssertionError("this statement should be unreachable");
203    }
204    @Override Cut<Comparable<?>> withUpperBoundType(BoundType boundType,
205        DiscreteDomain<Comparable<?>> domain) {
206      throw new IllegalStateException();
207    }
208    @Override void describeAsLowerBound(StringBuilder sb) {
209      throw new AssertionError();
210    }
211    @Override void describeAsUpperBound(StringBuilder sb) {
212      sb.append("+\u221e)");
213    }
214    @Override Comparable<?> leastValueAbove(
215        DiscreteDomain<Comparable<?>> domain) {
216      throw new AssertionError();
217    }
218    @Override Comparable<?> greatestValueBelow(
219        DiscreteDomain<Comparable<?>> domain) {
220      return domain.maxValue();
221    }
222    @Override public int compareTo(Cut<Comparable<?>> o) {
223      return (o == this) ? 0 : 1;
224    }
225    @Override public String toString() {
226      return "+\u221e";
227    }
228    private Object readResolve() {
229      return INSTANCE;
230    }
231    private static final long serialVersionUID = 0;
232  }
233
234  static <C extends Comparable> Cut<C> belowValue(C endpoint) {
235    return new BelowValue<C>(endpoint);
236  }
237
238  private static final class BelowValue<C extends Comparable> extends Cut<C> {
239    BelowValue(C endpoint) {
240      super(checkNotNull(endpoint));
241    }
242
243    @Override boolean isLessThan(C value) {
244      return Range.compareOrThrow(endpoint, value) <= 0;
245    }
246    @Override BoundType typeAsLowerBound() {
247      return BoundType.CLOSED;
248    }
249    @Override BoundType typeAsUpperBound() {
250      return BoundType.OPEN;
251    }
252    @Override Cut<C> withLowerBoundType(BoundType boundType, DiscreteDomain<C> domain) {
253      switch (boundType) {
254        case CLOSED:
255          return this;
256        case OPEN:
257          @Nullable C previous = domain.previous(endpoint);
258          return (previous == null) ? Cut.<C>belowAll() : new AboveValue<C>(previous);
259        default:
260          throw new AssertionError();
261      }
262    }
263    @Override Cut<C> withUpperBoundType(BoundType boundType, DiscreteDomain<C> domain) {
264      switch (boundType) {
265        case CLOSED:
266          @Nullable C previous = domain.previous(endpoint);
267          return (previous == null) ? Cut.<C>aboveAll() : new AboveValue<C>(previous);
268        case OPEN:
269          return this;
270        default:
271          throw new AssertionError();
272      }
273    }
274    @Override void describeAsLowerBound(StringBuilder sb) {
275      sb.append('[').append(endpoint);
276    }
277    @Override void describeAsUpperBound(StringBuilder sb) {
278      sb.append(endpoint).append(')');
279    }
280    @Override C leastValueAbove(DiscreteDomain<C> domain) {
281      return endpoint;
282    }
283    @Override C greatestValueBelow(DiscreteDomain<C> domain) {
284      return domain.previous(endpoint);
285    }
286    @Override public int hashCode() {
287      return endpoint.hashCode();
288    }
289    @Override public String toString() {
290      return "\\" + endpoint + "/";
291    }
292    private static final long serialVersionUID = 0;
293  }
294
295  static <C extends Comparable> Cut<C> aboveValue(C endpoint) {
296    return new AboveValue<C>(endpoint);
297  }
298
299  private static final class AboveValue<C extends Comparable> extends Cut<C> {
300    AboveValue(C endpoint) {
301      super(checkNotNull(endpoint));
302    }
303
304    @Override boolean isLessThan(C value) {
305      return Range.compareOrThrow(endpoint, value) < 0;
306    }
307    @Override BoundType typeAsLowerBound() {
308      return BoundType.OPEN;
309    }
310    @Override BoundType typeAsUpperBound() {
311      return BoundType.CLOSED;
312    }
313    @Override Cut<C> withLowerBoundType(BoundType boundType, DiscreteDomain<C> domain) {
314      switch (boundType) {
315        case OPEN:
316          return this;
317        case CLOSED:
318          @Nullable C next = domain.next(endpoint);
319          return (next == null) ? Cut.<C>belowAll() : belowValue(next);
320        default:
321          throw new AssertionError();
322      }
323    }
324    @Override Cut<C> withUpperBoundType(BoundType boundType, DiscreteDomain<C> domain) {
325      switch (boundType) {
326        case OPEN:
327          @Nullable C next = domain.next(endpoint);
328          return (next == null) ? Cut.<C>aboveAll() : belowValue(next);
329        case CLOSED:
330          return this;
331        default:
332          throw new AssertionError();
333      }
334    }
335    @Override void describeAsLowerBound(StringBuilder sb) {
336      sb.append('(').append(endpoint);
337    }
338    @Override void describeAsUpperBound(StringBuilder sb) {
339      sb.append(endpoint).append(']');
340    }
341    @Override C leastValueAbove(DiscreteDomain<C> domain) {
342      return domain.next(endpoint);
343    }
344    @Override C greatestValueBelow(DiscreteDomain<C> domain) {
345      return endpoint;
346    }
347    @Override Cut<C> canonical(DiscreteDomain<C> domain) {
348      C next = leastValueAbove(domain);
349      return (next != null) ? belowValue(next) : Cut.<C>aboveAll();
350    }
351    @Override public int hashCode() {
352      return ~endpoint.hashCode();
353    }
354    @Override public String toString() {
355      return "/" + endpoint + "\\";
356    }
357    private static final long serialVersionUID = 0;
358  }
359}
360