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 java.io.Serializable; 23 import java.util.Comparator; 24 25 import javax.annotation.Nullable; 26 27 import com.google.common.annotations.GwtCompatible; 28 import 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) 40 final class GeneralRange<T> implements Serializable { 41 /** 42 * Converts a Range to a GeneralRange. 43 */ from(Range<T> range)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 */ all(Comparator<? super T> comparator)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 */ downTo(Comparator<? super T> comparator, @Nullable T endpoint, BoundType boundType)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 */ upTo(Comparator<? super T> comparator, @Nullable T endpoint, BoundType boundType)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 */ range(Comparator<? super T> comparator, @Nullable T lower, BoundType lowerType, @Nullable T upper, BoundType upperType)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 GeneralRange(Comparator<? super T> comparator, boolean hasLowerBound, @Nullable T lowerEndpoint, BoundType lowerBoundType, boolean hasUpperBound, @Nullable T upperEndpoint, BoundType upperBoundType)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 comparator()128 Comparator<? super T> comparator() { 129 return comparator; 130 } 131 hasLowerBound()132 boolean hasLowerBound() { 133 return hasLowerBound; 134 } 135 hasUpperBound()136 boolean hasUpperBound() { 137 return hasUpperBound; 138 } 139 isEmpty()140 boolean isEmpty() { 141 return (hasUpperBound() && tooLow(upperEndpoint)) 142 || (hasLowerBound() && tooHigh(lowerEndpoint)); 143 } 144 tooLow(@ullable T t)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 tooHigh(@ullable T t)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 contains(@ullable T t)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 */ intersect(GeneralRange<T> other)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 equals(@ullable Object obj)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 hashCode()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 */ reverse()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 toString()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