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 com.google.common.annotations.GwtCompatible;
23import com.google.common.base.Objects;
24
25import java.io.Serializable;
26import java.util.Comparator;
27
28import javax.annotation.Nullable;
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(getUpperEndpoint()))
142        || (hasLowerBound() && tooHigh(getLowerEndpoint()));
143  }
144
145  boolean tooLow(@Nullable T t) {
146    if (!hasLowerBound()) {
147      return false;
148    }
149    T lbound = getLowerEndpoint();
150    int cmp = comparator.compare(t, lbound);
151    return cmp < 0 | (cmp == 0 & getLowerBoundType() == OPEN);
152  }
153
154  boolean tooHigh(@Nullable T t) {
155    if (!hasUpperBound()) {
156      return false;
157    }
158    T ubound = getUpperEndpoint();
159    int cmp = comparator.compare(t, ubound);
160    return cmp > 0 | (cmp == 0 & getUpperBoundType() == 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 = getLowerEndpoint();
177    BoundType lowType = getLowerBoundType();
178    if (!hasLowerBound()) {
179      hasLowBound = other.hasLowerBound;
180      lowEnd = other.getLowerEndpoint();
181      lowType = other.getLowerBoundType();
182    } else if (other.hasLowerBound()) {
183      int cmp = comparator.compare(getLowerEndpoint(), other.getLowerEndpoint());
184      if (cmp < 0 || (cmp == 0 && other.getLowerBoundType() == OPEN)) {
185        lowEnd = other.getLowerEndpoint();
186        lowType = other.getLowerBoundType();
187      }
188    }
189
190    boolean hasUpBound = this.hasUpperBound;
191    @Nullable
192    T upEnd = getUpperEndpoint();
193    BoundType upType = getUpperBoundType();
194    if (!hasUpperBound()) {
195      hasUpBound = other.hasUpperBound;
196      upEnd = other.getUpperEndpoint();
197      upType = other.getUpperBoundType();
198    } else if (other.hasUpperBound()) {
199      int cmp = comparator.compare(getUpperEndpoint(), other.getUpperEndpoint());
200      if (cmp > 0 || (cmp == 0 && other.getUpperBoundType() == OPEN)) {
201        upEnd = other.getUpperEndpoint();
202        upType = other.getUpperBoundType();
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 && getLowerBoundType().equals(r.getLowerBoundType())
225          && getUpperBoundType().equals(r.getUpperBoundType())
226          && Objects.equal(getLowerEndpoint(), r.getLowerEndpoint())
227          && Objects.equal(getUpperEndpoint(), r.getUpperEndpoint());
228    }
229    return false;
230  }
231
232  @Override
233  public int hashCode() {
234    return Objects.hashCode(comparator, getLowerEndpoint(), getLowerBoundType(), getUpperEndpoint(),
235        getUpperBoundType());
236  }
237
238  private transient GeneralRange<T> reverse;
239
240  /**
241   * Returns the same range relative to the reversed comparator.
242   */
243  GeneralRange<T> reverse() {
244    GeneralRange<T> result = reverse;
245    if (result == null) {
246      result = new GeneralRange<T>(
247          Ordering.from(comparator).reverse(), hasUpperBound, getUpperEndpoint(),
248          getUpperBoundType(), hasLowerBound, getLowerEndpoint(), getLowerBoundType());
249      result.reverse = this;
250      return this.reverse = result;
251    }
252    return result;
253  }
254
255  @Override
256  public String toString() {
257    return new StringBuilder()
258        .append(comparator)
259        .append(":")
260        .append(lowerBoundType == CLOSED ? '[' : '(')
261        .append(hasLowerBound ? lowerEndpoint : "-\u221e")
262        .append(',')
263        .append(hasUpperBound ? upperEndpoint : "\u221e")
264        .append(upperBoundType == CLOSED ? ']' : ')')
265        .toString();
266  }
267
268  T getLowerEndpoint() {
269    return lowerEndpoint;
270  }
271
272  BoundType getLowerBoundType() {
273    return lowerBoundType;
274  }
275
276  T getUpperEndpoint() {
277    return upperEndpoint;
278  }
279
280  BoundType getUpperBoundType() {
281    return upperBoundType;
282  }
283}
284