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 25 import java.io.Serializable; 26 import java.util.Comparator; 27 28 import 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) 40 final 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