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    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