1 /*
2 * Copyright (C) 2011 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
10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
11 * express or implied. See the License for the specific language governing permissions and
12 * limitations under the License.
13 */
14
15 package com.google.common.collect;
16
17 import static com.google.common.base.Preconditions.checkArgument;
18 import static com.google.common.base.Preconditions.checkNotNull;
19 import static com.google.common.collect.BoundType.CLOSED;
20 import static com.google.common.collect.BoundType.OPEN;
21 import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT;
22
23 import com.google.common.annotations.GwtCompatible;
24 import com.google.common.base.Objects;
25 import java.io.Serializable;
26 import java.util.Comparator;
27 import javax.annotation.CheckForNull;
28 import org.checkerframework.checker.nullness.qual.Nullable;
29
30 /**
31 * A generalized interval on any ordering, for internal use. Supports {@code null}. Unlike {@link
32 * Range}, this allows the use of an arbitrary comparator. This is designed for use in the
33 * implementation of subcollections of sorted collection types.
34 *
35 * <p>Whenever possible, use {@code Range} instead, which is better supported.
36 *
37 * @author Louis Wasserman
38 */
39 @GwtCompatible(serializable = true)
40 @ElementTypesAreNonnullByDefault
41 final class GeneralRange<T extends @Nullable Object> implements Serializable {
42 /** Converts a Range to a GeneralRange. */
43 static <T extends Comparable> GeneralRange<T> from(Range<T> range) {
44 T lowerEndpoint = range.hasLowerBound() ? range.lowerEndpoint() : null;
45 BoundType lowerBoundType = range.hasLowerBound() ? range.lowerBoundType() : OPEN;
46
47 T upperEndpoint = range.hasUpperBound() ? range.upperEndpoint() : null;
48 BoundType upperBoundType = range.hasUpperBound() ? range.upperBoundType() : OPEN;
49 return new GeneralRange<T>(
50 Ordering.natural(),
51 range.hasLowerBound(),
52 lowerEndpoint,
53 lowerBoundType,
54 range.hasUpperBound(),
55 upperEndpoint,
56 upperBoundType);
57 }
58
59 /** Returns the whole range relative to the specified comparator. */
60 static <T extends @Nullable Object> GeneralRange<T> all(Comparator<? super T> comparator) {
61 return new GeneralRange<T>(comparator, false, null, OPEN, false, null, OPEN);
62 }
63
64 /**
65 * Returns everything above the endpoint relative to the specified comparator, with the specified
66 * endpoint behavior.
67 */
68 static <T extends @Nullable Object> GeneralRange<T> downTo(
69 Comparator<? super T> comparator, @ParametricNullness T endpoint, BoundType boundType) {
70 return new GeneralRange<T>(comparator, true, endpoint, boundType, false, null, OPEN);
71 }
72
73 /**
74 * Returns everything below the endpoint relative to the specified comparator, with the specified
75 * endpoint behavior.
76 */
77 static <T extends @Nullable Object> GeneralRange<T> upTo(
78 Comparator<? super T> comparator, @ParametricNullness T endpoint, BoundType boundType) {
79 return new GeneralRange<T>(comparator, false, null, OPEN, true, endpoint, boundType);
80 }
81
82 /**
83 * Returns everything between the endpoints relative to the specified comparator, with the
84 * specified endpoint behavior.
85 */
86 static <T extends @Nullable Object> GeneralRange<T> range(
87 Comparator<? super T> comparator,
88 @ParametricNullness T lower,
89 BoundType lowerType,
90 @ParametricNullness T upper,
91 BoundType upperType) {
92 return new GeneralRange<T>(comparator, true, lower, lowerType, true, upper, upperType);
93 }
94
95 private final Comparator<? super T> comparator;
96 private final boolean hasLowerBound;
97 @CheckForNull private final T lowerEndpoint;
98 private final BoundType lowerBoundType;
99 private final boolean hasUpperBound;
100 @CheckForNull private final T upperEndpoint;
101 private final BoundType upperBoundType;
102
103 private GeneralRange(
104 Comparator<? super T> comparator,
105 boolean hasLowerBound,
106 @CheckForNull T lowerEndpoint,
107 BoundType lowerBoundType,
108 boolean hasUpperBound,
109 @CheckForNull T upperEndpoint,
110 BoundType upperBoundType) {
111 this.comparator = checkNotNull(comparator);
112 this.hasLowerBound = hasLowerBound;
113 this.hasUpperBound = hasUpperBound;
114 this.lowerEndpoint = lowerEndpoint;
115 this.lowerBoundType = checkNotNull(lowerBoundType);
116 this.upperEndpoint = upperEndpoint;
117 this.upperBoundType = checkNotNull(upperBoundType);
118
119 // Trigger any exception that the comparator would throw for the endpoints.
120 /*
121 * uncheckedCastNullableTToT is safe as long as the callers are careful to pass a "real" T
122 * whenever they pass `true` for the matching `has*Bound` parameter.
123 */
124 if (hasLowerBound) {
125 comparator.compare(
126 uncheckedCastNullableTToT(lowerEndpoint), uncheckedCastNullableTToT(lowerEndpoint));
127 }
128 if (hasUpperBound) {
129 comparator.compare(
130 uncheckedCastNullableTToT(upperEndpoint), uncheckedCastNullableTToT(upperEndpoint));
131 }
132
133 if (hasLowerBound && hasUpperBound) {
134 int cmp =
135 comparator.compare(
136 uncheckedCastNullableTToT(lowerEndpoint), uncheckedCastNullableTToT(upperEndpoint));
137 // be consistent with Range
138 checkArgument(
139 cmp <= 0, "lowerEndpoint (%s) > upperEndpoint (%s)", lowerEndpoint, upperEndpoint);
140 if (cmp == 0) {
141 checkArgument(lowerBoundType != OPEN | upperBoundType != OPEN);
142 }
143 }
144 }
145
146 Comparator<? super T> comparator() {
147 return comparator;
148 }
149
150 boolean hasLowerBound() {
151 return hasLowerBound;
152 }
153
154 boolean hasUpperBound() {
155 return hasUpperBound;
156 }
157
158 boolean isEmpty() {
159 // The casts are safe because of the has*Bound() checks.
160 return (hasUpperBound() && tooLow(uncheckedCastNullableTToT(getUpperEndpoint())))
161 || (hasLowerBound() && tooHigh(uncheckedCastNullableTToT(getLowerEndpoint())));
162 }
163
164 boolean tooLow(@ParametricNullness T t) {
165 if (!hasLowerBound()) {
166 return false;
167 }
168 // The cast is safe because of the hasLowerBound() check.
169 T lbound = uncheckedCastNullableTToT(getLowerEndpoint());
170 int cmp = comparator.compare(t, lbound);
171 return cmp < 0 | (cmp == 0 & getLowerBoundType() == OPEN);
172 }
173
174 boolean tooHigh(@ParametricNullness T t) {
175 if (!hasUpperBound()) {
176 return false;
177 }
178 // The cast is safe because of the hasUpperBound() check.
179 T ubound = uncheckedCastNullableTToT(getUpperEndpoint());
180 int cmp = comparator.compare(t, ubound);
181 return cmp > 0 | (cmp == 0 & getUpperBoundType() == OPEN);
182 }
183
184 boolean contains(@ParametricNullness T t) {
185 return !tooLow(t) && !tooHigh(t);
186 }
187
188 /**
189 * Returns the intersection of the two ranges, or an empty range if their intersection is empty.
190 */
191 @SuppressWarnings("nullness") // TODO(cpovirk): Add casts as needed. Will be noisy and annoying...
192 GeneralRange<T> intersect(GeneralRange<T> other) {
193 checkNotNull(other);
194 checkArgument(comparator.equals(other.comparator));
195
196 boolean hasLowBound = this.hasLowerBound;
197 T lowEnd = getLowerEndpoint();
198 BoundType lowType = getLowerBoundType();
199 if (!hasLowerBound()) {
200 hasLowBound = other.hasLowerBound;
201 lowEnd = other.getLowerEndpoint();
202 lowType = other.getLowerBoundType();
203 } else if (other.hasLowerBound()) {
204 int cmp = comparator.compare(getLowerEndpoint(), other.getLowerEndpoint());
205 if (cmp < 0 || (cmp == 0 && other.getLowerBoundType() == OPEN)) {
206 lowEnd = other.getLowerEndpoint();
207 lowType = other.getLowerBoundType();
208 }
209 }
210
211 boolean hasUpBound = this.hasUpperBound;
212 T upEnd = getUpperEndpoint();
213 BoundType upType = getUpperBoundType();
214 if (!hasUpperBound()) {
215 hasUpBound = other.hasUpperBound;
216 upEnd = other.getUpperEndpoint();
217 upType = other.getUpperBoundType();
218 } else if (other.hasUpperBound()) {
219 int cmp = comparator.compare(getUpperEndpoint(), other.getUpperEndpoint());
220 if (cmp > 0 || (cmp == 0 && other.getUpperBoundType() == OPEN)) {
221 upEnd = other.getUpperEndpoint();
222 upType = other.getUpperBoundType();
223 }
224 }
225
226 if (hasLowBound && hasUpBound) {
227 int cmp = comparator.compare(lowEnd, upEnd);
228 if (cmp > 0 || (cmp == 0 && lowType == OPEN && upType == OPEN)) {
229 // force allowed empty range
230 lowEnd = upEnd;
231 lowType = OPEN;
232 upType = CLOSED;
233 }
234 }
235
236 return new GeneralRange<T>(comparator, hasLowBound, lowEnd, lowType, hasUpBound, upEnd, upType);
237 }
238
239 @Override
240 public boolean equals(@CheckForNull Object obj) {
241 if (obj instanceof GeneralRange) {
242 GeneralRange<?> r = (GeneralRange<?>) obj;
243 return comparator.equals(r.comparator)
244 && hasLowerBound == r.hasLowerBound
245 && hasUpperBound == r.hasUpperBound
246 && getLowerBoundType().equals(r.getLowerBoundType())
247 && getUpperBoundType().equals(r.getUpperBoundType())
248 && Objects.equal(getLowerEndpoint(), r.getLowerEndpoint())
249 && Objects.equal(getUpperEndpoint(), r.getUpperEndpoint());
250 }
251 return false;
252 }
253
254 @Override
255 public int hashCode() {
256 return Objects.hashCode(
257 comparator,
258 getLowerEndpoint(),
259 getLowerBoundType(),
260 getUpperEndpoint(),
261 getUpperBoundType());
262 }
263
264 @CheckForNull private transient GeneralRange<T> reverse;
265
266 /** Returns the same range relative to the reversed comparator. */
267 GeneralRange<T> reverse() {
268 GeneralRange<T> result = reverse;
269 if (result == null) {
270 result =
271 new GeneralRange<T>(
272 Ordering.from(comparator).reverse(),
273 hasUpperBound,
274 getUpperEndpoint(),
275 getUpperBoundType(),
276 hasLowerBound,
277 getLowerEndpoint(),
278 getLowerBoundType());
279 result.reverse = this;
280 return this.reverse = result;
281 }
282 return result;
283 }
284
285 @Override
286 public String toString() {
287 return comparator
288 + ":"
289 + (lowerBoundType == CLOSED ? '[' : '(')
290 + (hasLowerBound ? lowerEndpoint : "-\u221e")
291 + ','
292 + (hasUpperBound ? upperEndpoint : "\u221e")
293 + (upperBoundType == CLOSED ? ']' : ')');
294 }
295
296 @CheckForNull
297 T getLowerEndpoint() {
298 return lowerEndpoint;
299 }
300
301 BoundType getLowerBoundType() {
302 return lowerBoundType;
303 }
304
305 @CheckForNull
306 T getUpperEndpoint() {
307 return upperEndpoint;
308 }
309
310 BoundType getUpperBoundType() {
311 return upperBoundType;
312 }
313 }