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