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