001/* 002 * Copyright (C) 2008 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021 022import com.google.common.annotations.GwtCompatible; 023import com.google.common.base.Equivalence; 024import com.google.common.base.Predicate; 025import com.google.errorprone.annotations.Immutable; 026import com.google.errorprone.annotations.InlineMe; 027import java.io.Serializable; 028import java.util.Comparator; 029import java.util.Iterator; 030import java.util.NoSuchElementException; 031import java.util.SortedSet; 032import org.jspecify.annotations.Nullable; 033 034/** 035 * A range (or "interval") defines the <i>boundaries</i> around a contiguous span of values of some 036 * {@code Comparable} type; for example, "integers from 1 to 100 inclusive." Note that it is not 037 * possible to <i>iterate</i> over these contained values. To do so, pass this range instance and an 038 * appropriate {@link DiscreteDomain} to {@link ContiguousSet#create}. 039 * 040 * <h3>Types of ranges</h3> 041 * 042 * <p>Each end of the range may be bounded or unbounded. If bounded, there is an associated 043 * <i>endpoint</i> value, and the range is considered to be either <i>open</i> (does not include the 044 * endpoint) or <i>closed</i> (includes the endpoint) on that side. With three possibilities on each 045 * side, this yields nine basic types of ranges, enumerated below. (Notation: a square bracket 046 * ({@code [ ]}) indicates that the range is closed on that side; a parenthesis ({@code ( )}) means 047 * it is either open or unbounded. The construct {@code {x | statement}} is read "the set of all 048 * <i>x</i> such that <i>statement</i>.") 049 * 050 * <blockquote> 051 * 052 * <table> 053 * <caption>Range Types</caption> 054 * <tr><th>Notation <th>Definition <th>Factory method 055 * <tr><td>{@code (a..b)} <td>{@code {x | a < x < b}} <td>{@link Range#open open} 056 * <tr><td>{@code [a..b]} <td>{@code {x | a <= x <= b}}<td>{@link Range#closed closed} 057 * <tr><td>{@code (a..b]} <td>{@code {x | a < x <= b}} <td>{@link Range#openClosed openClosed} 058 * <tr><td>{@code [a..b)} <td>{@code {x | a <= x < b}} <td>{@link Range#closedOpen closedOpen} 059 * <tr><td>{@code (a..+∞)} <td>{@code {x | x > a}} <td>{@link Range#greaterThan greaterThan} 060 * <tr><td>{@code [a..+∞)} <td>{@code {x | x >= a}} <td>{@link Range#atLeast atLeast} 061 * <tr><td>{@code (-∞..b)} <td>{@code {x | x < b}} <td>{@link Range#lessThan lessThan} 062 * <tr><td>{@code (-∞..b]} <td>{@code {x | x <= b}} <td>{@link Range#atMost atMost} 063 * <tr><td>{@code (-∞..+∞)}<td>{@code {x}} <td>{@link Range#all all} 064 * </table> 065 * 066 * </blockquote> 067 * 068 * <p>When both endpoints exist, the upper endpoint may not be less than the lower. The endpoints 069 * may be equal only if at least one of the bounds is closed: 070 * 071 * <ul> 072 * <li>{@code [a..a]} : a singleton range 073 * <li>{@code [a..a); (a..a]} : {@linkplain #isEmpty empty} ranges; also valid 074 * <li>{@code (a..a)} : <b>invalid</b>; an exception will be thrown 075 * </ul> 076 * 077 * <h3>Warnings</h3> 078 * 079 * <ul> 080 * <li>Use immutable value types only, if at all possible. If you must use a mutable type, <b>do 081 * not</b> allow the endpoint instances to mutate after the range is created! 082 * <li>Your value type's comparison method should be {@linkplain Comparable consistent with 083 * equals} if at all possible. Otherwise, be aware that concepts used throughout this 084 * documentation such as "equal", "same", "unique" and so on actually refer to whether {@link 085 * Comparable#compareTo compareTo} returns zero, not whether {@link Object#equals equals} 086 * returns {@code true}. 087 * <li>A class which implements {@code Comparable<UnrelatedType>} is very broken, and will cause 088 * undefined horrible things to happen in {@code Range}. For now, the Range API does not 089 * prevent its use, because this would also rule out all ungenerified (pre-JDK1.5) data types. 090 * <b>This may change in the future.</b> 091 * </ul> 092 * 093 * <h3>Other notes</h3> 094 * 095 * <ul> 096 * <li>All ranges are shallow-immutable. 097 * <li>Instances of this type are obtained using the static factory methods in this class. 098 * <li>Ranges are <i>convex</i>: whenever two values are contained, all values in between them 099 * must also be contained. More formally, for any {@code c1 <= c2 <= c3} of type {@code C}, 100 * {@code r.contains(c1) && r.contains(c3)} implies {@code r.contains(c2)}). This means that a 101 * {@code Range<Integer>} can never be used to represent, say, "all <i>prime</i> numbers from 102 * 1 to 100." 103 * <li>When evaluated as a {@link Predicate}, a range yields the same result as invoking {@link 104 * #contains}. 105 * <li>Terminology note: a range {@code a} is said to be the <i>maximal</i> range having property 106 * <i>P</i> if, for all ranges {@code b} also having property <i>P</i>, {@code a.encloses(b)}. 107 * Likewise, {@code a} is <i>minimal</i> when {@code b.encloses(a)} for all {@code b} having 108 * property <i>P</i>. See, for example, the definition of {@link #intersection intersection}. 109 * <li>A {@code Range} is serializable if it has no bounds, or if each bound is serializable. 110 * </ul> 111 * 112 * <h3>Further reading</h3> 113 * 114 * <p>See the Guava User Guide article on <a 115 * href="https://github.com/google/guava/wiki/RangesExplained">{@code Range}</a>. 116 * 117 * @author Kevin Bourrillion 118 * @author Gregory Kick 119 * @since 10.0 120 */ 121@GwtCompatible 122@SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989 123@Immutable(containerOf = "C") 124public final class Range<C extends Comparable> extends RangeGwtSerializationDependencies 125 implements Predicate<C>, Serializable { 126 @SuppressWarnings("unchecked") 127 static <C extends Comparable<?>> Ordering<Range<C>> rangeLexOrdering() { 128 return (Ordering<Range<C>>) RangeLexOrdering.INSTANCE; 129 } 130 131 static <C extends Comparable<?>> Range<C> create(Cut<C> lowerBound, Cut<C> upperBound) { 132 return new Range<>(lowerBound, upperBound); 133 } 134 135 /** 136 * Returns a range that contains all values strictly greater than {@code lower} and strictly less 137 * than {@code upper}. 138 * 139 * @throws IllegalArgumentException if {@code lower} is greater than <i>or equal to</i> {@code 140 * upper} 141 * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable 142 * @since 14.0 143 */ 144 public static <C extends Comparable<?>> Range<C> open(C lower, C upper) { 145 return create(Cut.aboveValue(lower), Cut.belowValue(upper)); 146 } 147 148 /** 149 * Returns a range that contains all values greater than or equal to {@code lower} and less than 150 * or equal to {@code upper}. 151 * 152 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 153 * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable 154 * @since 14.0 155 */ 156 public static <C extends Comparable<?>> Range<C> closed(C lower, C upper) { 157 return create(Cut.belowValue(lower), Cut.aboveValue(upper)); 158 } 159 160 /** 161 * Returns a range that contains all values greater than or equal to {@code lower} and strictly 162 * less than {@code upper}. 163 * 164 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 165 * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable 166 * @since 14.0 167 */ 168 public static <C extends Comparable<?>> Range<C> closedOpen(C lower, C upper) { 169 return create(Cut.belowValue(lower), Cut.belowValue(upper)); 170 } 171 172 /** 173 * Returns a range that contains all values strictly greater than {@code lower} and less than or 174 * equal to {@code upper}. 175 * 176 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 177 * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable 178 * @since 14.0 179 */ 180 public static <C extends Comparable<?>> Range<C> openClosed(C lower, C upper) { 181 return create(Cut.aboveValue(lower), Cut.aboveValue(upper)); 182 } 183 184 /** 185 * Returns a range that contains any value from {@code lower} to {@code upper}, where each 186 * endpoint may be either inclusive (closed) or exclusive (open). 187 * 188 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 189 * @throws ClassCastException if {@code lower} and {@code upper} are not mutually comparable 190 * @since 14.0 191 */ 192 public static <C extends Comparable<?>> Range<C> range( 193 C lower, BoundType lowerType, C upper, BoundType upperType) { 194 checkNotNull(lowerType); 195 checkNotNull(upperType); 196 197 Cut<C> lowerBound = 198 (lowerType == BoundType.OPEN) ? Cut.aboveValue(lower) : Cut.belowValue(lower); 199 Cut<C> upperBound = 200 (upperType == BoundType.OPEN) ? Cut.belowValue(upper) : Cut.aboveValue(upper); 201 return create(lowerBound, upperBound); 202 } 203 204 /** 205 * Returns a range that contains all values strictly less than {@code endpoint}. 206 * 207 * @since 14.0 208 */ 209 public static <C extends Comparable<?>> Range<C> lessThan(C endpoint) { 210 return create(Cut.<C>belowAll(), Cut.belowValue(endpoint)); 211 } 212 213 /** 214 * Returns a range that contains all values less than or equal to {@code endpoint}. 215 * 216 * @since 14.0 217 */ 218 public static <C extends Comparable<?>> Range<C> atMost(C endpoint) { 219 return create(Cut.<C>belowAll(), Cut.aboveValue(endpoint)); 220 } 221 222 /** 223 * Returns a range with no lower bound up to the given endpoint, which may be either inclusive 224 * (closed) or exclusive (open). 225 * 226 * @since 14.0 227 */ 228 public static <C extends Comparable<?>> Range<C> upTo(C endpoint, BoundType boundType) { 229 switch (boundType) { 230 case OPEN: 231 return lessThan(endpoint); 232 case CLOSED: 233 return atMost(endpoint); 234 } 235 throw new AssertionError(); 236 } 237 238 /** 239 * Returns a range that contains all values strictly greater than {@code endpoint}. 240 * 241 * @since 14.0 242 */ 243 public static <C extends Comparable<?>> Range<C> greaterThan(C endpoint) { 244 return create(Cut.aboveValue(endpoint), Cut.<C>aboveAll()); 245 } 246 247 /** 248 * Returns a range that contains all values greater than or equal to {@code endpoint}. 249 * 250 * @since 14.0 251 */ 252 public static <C extends Comparable<?>> Range<C> atLeast(C endpoint) { 253 return create(Cut.belowValue(endpoint), Cut.<C>aboveAll()); 254 } 255 256 /** 257 * Returns a range from the given endpoint, which may be either inclusive (closed) or exclusive 258 * (open), with no upper bound. 259 * 260 * @since 14.0 261 */ 262 public static <C extends Comparable<?>> Range<C> downTo(C endpoint, BoundType boundType) { 263 switch (boundType) { 264 case OPEN: 265 return greaterThan(endpoint); 266 case CLOSED: 267 return atLeast(endpoint); 268 } 269 throw new AssertionError(); 270 } 271 272 private static final Range<Comparable> ALL = new Range<>(Cut.belowAll(), Cut.aboveAll()); 273 274 /** 275 * Returns a range that contains every value of type {@code C}. 276 * 277 * @since 14.0 278 */ 279 @SuppressWarnings("unchecked") 280 public static <C extends Comparable<?>> Range<C> all() { 281 return (Range) ALL; 282 } 283 284 /** 285 * Returns a range that {@linkplain Range#contains(Comparable) contains} only the given value. The 286 * returned range is {@linkplain BoundType#CLOSED closed} on both ends. 287 * 288 * @since 14.0 289 */ 290 public static <C extends Comparable<?>> Range<C> singleton(C value) { 291 return closed(value, value); 292 } 293 294 /** 295 * Returns the minimal range that {@linkplain Range#contains(Comparable) contains} all of the 296 * given values. The returned range is {@linkplain BoundType#CLOSED closed} on both ends. 297 * 298 * @throws ClassCastException if the values are not mutually comparable 299 * @throws NoSuchElementException if {@code values} is empty 300 * @throws NullPointerException if any of {@code values} is null 301 * @since 14.0 302 */ 303 public static <C extends Comparable<?>> Range<C> encloseAll(Iterable<C> values) { 304 checkNotNull(values); 305 if (values instanceof SortedSet) { 306 SortedSet<C> set = (SortedSet<C>) values; 307 Comparator<?> comparator = set.comparator(); 308 if (Ordering.<C>natural().equals(comparator) || comparator == null) { 309 return closed(set.first(), set.last()); 310 } 311 } 312 Iterator<C> valueIterator = values.iterator(); 313 C min = checkNotNull(valueIterator.next()); 314 C max = min; 315 while (valueIterator.hasNext()) { 316 C value = checkNotNull(valueIterator.next()); 317 min = Ordering.<C>natural().min(min, value); 318 max = Ordering.<C>natural().max(max, value); 319 } 320 return closed(min, max); 321 } 322 323 final Cut<C> lowerBound; 324 final Cut<C> upperBound; 325 326 private Range(Cut<C> lowerBound, Cut<C> upperBound) { 327 this.lowerBound = checkNotNull(lowerBound); 328 this.upperBound = checkNotNull(upperBound); 329 if (lowerBound.compareTo(upperBound) > 0 330 || lowerBound == Cut.<C>aboveAll() 331 || upperBound == Cut.<C>belowAll()) { 332 throw new IllegalArgumentException("Invalid range: " + toString(lowerBound, upperBound)); 333 } 334 } 335 336 /** Returns {@code true} if this range has a lower endpoint. */ 337 public boolean hasLowerBound() { 338 return lowerBound != Cut.belowAll(); 339 } 340 341 /** 342 * Returns the lower endpoint of this range. 343 * 344 * @throws IllegalStateException if this range is unbounded below (that is, {@link 345 * #hasLowerBound()} returns {@code false}) 346 */ 347 public C lowerEndpoint() { 348 return lowerBound.endpoint(); 349 } 350 351 /** 352 * Returns the type of this range's lower bound: {@link BoundType#CLOSED} if the range includes 353 * its lower endpoint, {@link BoundType#OPEN} if it does not. 354 * 355 * @throws IllegalStateException if this range is unbounded below (that is, {@link 356 * #hasLowerBound()} returns {@code false}) 357 */ 358 public BoundType lowerBoundType() { 359 return lowerBound.typeAsLowerBound(); 360 } 361 362 /** Returns {@code true} if this range has an upper endpoint. */ 363 public boolean hasUpperBound() { 364 return upperBound != Cut.aboveAll(); 365 } 366 367 /** 368 * Returns the upper endpoint of this range. 369 * 370 * @throws IllegalStateException if this range is unbounded above (that is, {@link 371 * #hasUpperBound()} returns {@code false}) 372 */ 373 public C upperEndpoint() { 374 return upperBound.endpoint(); 375 } 376 377 /** 378 * Returns the type of this range's upper bound: {@link BoundType#CLOSED} if the range includes 379 * its upper endpoint, {@link BoundType#OPEN} if it does not. 380 * 381 * @throws IllegalStateException if this range is unbounded above (that is, {@link 382 * #hasUpperBound()} returns {@code false}) 383 */ 384 public BoundType upperBoundType() { 385 return upperBound.typeAsUpperBound(); 386 } 387 388 /** 389 * Returns {@code true} if this range is of the form {@code [v..v)} or {@code (v..v]}. (This does 390 * not encompass ranges of the form {@code (v..v)}, because such ranges are <i>invalid</i> and 391 * can't be constructed at all.) 392 * 393 * <p>Note that certain discrete ranges such as the integer range {@code (3..4)} are <b>not</b> 394 * considered empty, even though they contain no actual values. In these cases, it may be helpful 395 * to preprocess ranges with {@link #canonical(DiscreteDomain)}. 396 */ 397 public boolean isEmpty() { 398 return lowerBound.equals(upperBound); 399 } 400 401 /** 402 * Returns {@code true} if {@code value} is within the bounds of this range. For example, on the 403 * range {@code [0..2)}, {@code contains(1)} returns {@code true}, while {@code contains(2)} 404 * returns {@code false}. 405 */ 406 public boolean contains(C value) { 407 checkNotNull(value); 408 // let this throw CCE if there is some trickery going on 409 return lowerBound.isLessThan(value) && !upperBound.isLessThan(value); 410 } 411 412 /** 413 * @deprecated Provided only to satisfy the {@link Predicate} interface; use {@link #contains} 414 * instead. 415 */ 416 @InlineMe(replacement = "this.contains(input)") 417 @Deprecated 418 @Override 419 public boolean apply(C input) { 420 return contains(input); 421 } 422 423 /** 424 * Returns {@code true} if every element in {@code values} is {@linkplain #contains contained} in 425 * this range. 426 */ 427 public boolean containsAll(Iterable<? extends C> values) { 428 if (Iterables.isEmpty(values)) { 429 return true; 430 } 431 432 // this optimizes testing equality of two range-backed sets 433 if (values instanceof SortedSet) { 434 SortedSet<? extends C> set = (SortedSet<? extends C>) values; 435 Comparator<?> comparator = set.comparator(); 436 if (Ordering.natural().equals(comparator) || comparator == null) { 437 return contains(set.first()) && contains(set.last()); 438 } 439 } 440 441 for (C value : values) { 442 if (!contains(value)) { 443 return false; 444 } 445 } 446 return true; 447 } 448 449 /** 450 * Returns {@code true} if the bounds of {@code other} do not extend outside the bounds of this 451 * range. Examples: 452 * 453 * <ul> 454 * <li>{@code [3..6]} encloses {@code [4..5]} 455 * <li>{@code (3..6)} encloses {@code (3..6)} 456 * <li>{@code [3..6]} encloses {@code [4..4)} (even though the latter is empty) 457 * <li>{@code (3..6]} does not enclose {@code [3..6]} 458 * <li>{@code [4..5]} does not enclose {@code (3..6)} (even though it contains every value 459 * contained by the latter range) 460 * <li>{@code [3..6]} does not enclose {@code (1..1]} (even though it contains every value 461 * contained by the latter range) 462 * </ul> 463 * 464 * <p>Note that if {@code a.encloses(b)}, then {@code b.contains(v)} implies {@code 465 * a.contains(v)}, but as the last two examples illustrate, the converse is not always true. 466 * 467 * <p>Being reflexive, antisymmetric and transitive, the {@code encloses} relation defines a 468 * <i>partial order</i> over ranges. There exists a unique {@linkplain Range#all maximal} range 469 * according to this relation, and also numerous {@linkplain #isEmpty minimal} ranges. Enclosure 470 * also implies {@linkplain #isConnected connectedness}. 471 */ 472 public boolean encloses(Range<C> other) { 473 return lowerBound.compareTo(other.lowerBound) <= 0 474 && upperBound.compareTo(other.upperBound) >= 0; 475 } 476 477 /** 478 * Returns {@code true} if there exists a (possibly empty) range which is {@linkplain #encloses 479 * enclosed} by both this range and {@code other}. 480 * 481 * <p>For example, 482 * 483 * <ul> 484 * <li>{@code [2, 4)} and {@code [5, 7)} are not connected 485 * <li>{@code [2, 4)} and {@code [3, 5)} are connected, because both enclose {@code [3, 4)} 486 * <li>{@code [2, 4)} and {@code [4, 6)} are connected, because both enclose the empty range 487 * {@code [4, 4)} 488 * </ul> 489 * 490 * <p>Note that this range and {@code other} have a well-defined {@linkplain #span union} and 491 * {@linkplain #intersection intersection} (as a single, possibly-empty range) if and only if this 492 * method returns {@code true}. 493 * 494 * <p>The connectedness relation is both reflexive and symmetric, but does not form an {@linkplain 495 * Equivalence equivalence relation} as it is not transitive. 496 * 497 * <p>Note that certain discrete ranges are not considered connected, even though there are no 498 * elements "between them." For example, {@code [3, 5]} is not considered connected to {@code [6, 499 * 10]}. In these cases, it may be desirable for both input ranges to be preprocessed with {@link 500 * #canonical(DiscreteDomain)} before testing for connectedness. 501 */ 502 public boolean isConnected(Range<C> other) { 503 return lowerBound.compareTo(other.upperBound) <= 0 504 && other.lowerBound.compareTo(upperBound) <= 0; 505 } 506 507 /** 508 * Returns the maximal range {@linkplain #encloses enclosed} by both this range and {@code 509 * connectedRange}, if such a range exists. 510 * 511 * <p>For example, the intersection of {@code [1..5]} and {@code (3..7)} is {@code (3..5]}. The 512 * resulting range may be empty; for example, {@code [1..5)} intersected with {@code [5..7)} 513 * yields the empty range {@code [5..5)}. 514 * 515 * <p>The intersection exists if and only if the two ranges are {@linkplain #isConnected 516 * connected}. 517 * 518 * <p>The intersection operation is commutative, associative and idempotent, and its identity 519 * element is {@link Range#all}). 520 * 521 * @throws IllegalArgumentException if {@code isConnected(connectedRange)} is {@code false} 522 */ 523 public Range<C> intersection(Range<C> connectedRange) { 524 int lowerCmp = lowerBound.compareTo(connectedRange.lowerBound); 525 int upperCmp = upperBound.compareTo(connectedRange.upperBound); 526 if (lowerCmp >= 0 && upperCmp <= 0) { 527 return this; 528 } else if (lowerCmp <= 0 && upperCmp >= 0) { 529 return connectedRange; 530 } else { 531 Cut<C> newLower = (lowerCmp >= 0) ? lowerBound : connectedRange.lowerBound; 532 Cut<C> newUpper = (upperCmp <= 0) ? upperBound : connectedRange.upperBound; 533 534 // create() would catch this, but give a confusing error message 535 checkArgument( 536 newLower.compareTo(newUpper) <= 0, 537 "intersection is undefined for disconnected ranges %s and %s", 538 this, 539 connectedRange); 540 541 // TODO(kevinb): all the precondition checks in the constructor are redundant... 542 return create(newLower, newUpper); 543 } 544 } 545 546 /** 547 * Returns the maximal range lying between this range and {@code otherRange}, if such a range 548 * exists. The resulting range may be empty if the two ranges are adjacent but non-overlapping. 549 * 550 * <p>For example, the gap of {@code [1..5]} and {@code (7..10)} is {@code (5..7]}. The resulting 551 * range may be empty; for example, the gap between {@code [1..5)} {@code [5..7)} yields the empty 552 * range {@code [5..5)}. 553 * 554 * <p>The gap exists if and only if the two ranges are either disconnected or immediately adjacent 555 * (any intersection must be an empty range). 556 * 557 * <p>The gap operation is commutative. 558 * 559 * @throws IllegalArgumentException if this range and {@code otherRange} have a nonempty 560 * intersection 561 * @since 27.0 562 */ 563 public Range<C> gap(Range<C> otherRange) { 564 /* 565 * For an explanation of the basic principle behind this check, see 566 * https://stackoverflow.com/a/35754308/28465 567 * 568 * In that explanation's notation, our `overlap` check would be `x1 < y2 && y1 < x2`. We've 569 * flipped one part of the check so that we're using "less than" in both cases (rather than a 570 * mix of "less than" and "greater than"). We've also switched to "strictly less than" rather 571 * than "less than or equal to" because of *handwave* the difference between "endpoints of 572 * inclusive ranges" and "Cuts." 573 */ 574 if (lowerBound.compareTo(otherRange.upperBound) < 0 575 && otherRange.lowerBound.compareTo(upperBound) < 0) { 576 throw new IllegalArgumentException( 577 "Ranges have a nonempty intersection: " + this + ", " + otherRange); 578 } 579 580 boolean isThisFirst = this.lowerBound.compareTo(otherRange.lowerBound) < 0; 581 Range<C> firstRange = isThisFirst ? this : otherRange; 582 Range<C> secondRange = isThisFirst ? otherRange : this; 583 return create(firstRange.upperBound, secondRange.lowerBound); 584 } 585 586 /** 587 * Returns the minimal range that {@linkplain #encloses encloses} both this range and {@code 588 * other}. For example, the span of {@code [1..3]} and {@code (5..7)} is {@code [1..7)}. 589 * 590 * <p><i>If</i> the input ranges are {@linkplain #isConnected connected}, the returned range can 591 * also be called their <i>union</i>. If they are not, note that the span might contain values 592 * that are not contained in either input range. 593 * 594 * <p>Like {@link #intersection(Range) intersection}, this operation is commutative, associative 595 * and idempotent. Unlike it, it is always well-defined for any two input ranges. 596 */ 597 public Range<C> span(Range<C> other) { 598 int lowerCmp = lowerBound.compareTo(other.lowerBound); 599 int upperCmp = upperBound.compareTo(other.upperBound); 600 if (lowerCmp <= 0 && upperCmp >= 0) { 601 return this; 602 } else if (lowerCmp >= 0 && upperCmp <= 0) { 603 return other; 604 } else { 605 Cut<C> newLower = (lowerCmp <= 0) ? lowerBound : other.lowerBound; 606 Cut<C> newUpper = (upperCmp >= 0) ? upperBound : other.upperBound; 607 return create(newLower, newUpper); 608 } 609 } 610 611 /** 612 * Returns the canonical form of this range in the given domain. The canonical form has the 613 * following properties: 614 * 615 * <ul> 616 * <li>equivalence: {@code a.canonical().contains(v) == a.contains(v)} for all {@code v} (in 617 * other words, {@code ContiguousSet.create(a.canonical(domain), domain).equals( 618 * ContiguousSet.create(a, domain))} 619 * <li>uniqueness: unless {@code a.isEmpty()}, {@code ContiguousSet.create(a, 620 * domain).equals(ContiguousSet.create(b, domain))} implies {@code 621 * a.canonical(domain).equals(b.canonical(domain))} 622 * <li>idempotence: {@code a.canonical(domain).canonical(domain).equals(a.canonical(domain))} 623 * </ul> 624 * 625 * <p>Furthermore, this method guarantees that the range returned will be one of the following 626 * canonical forms: 627 * 628 * <ul> 629 * <li>[start..end) 630 * <li>[start..+∞) 631 * <li>(-∞..end) (only if type {@code C} is unbounded below) 632 * <li>(-∞..+∞) (only if type {@code C} is unbounded below) 633 * </ul> 634 */ 635 public Range<C> canonical(DiscreteDomain<C> domain) { 636 checkNotNull(domain); 637 Cut<C> lower = lowerBound.canonical(domain); 638 Cut<C> upper = upperBound.canonical(domain); 639 return (lower == lowerBound && upper == upperBound) ? this : create(lower, upper); 640 } 641 642 /** 643 * Returns {@code true} if {@code object} is a range having the same endpoints and bound types as 644 * this range. Note that discrete ranges such as {@code (1..4)} and {@code [2..3]} are <b>not</b> 645 * equal to one another, despite the fact that they each contain precisely the same set of values. 646 * Similarly, empty ranges are not equal unless they have exactly the same representation, so 647 * {@code [3..3)}, {@code (3..3]}, {@code (4..4]} are all unequal. 648 */ 649 @Override 650 public boolean equals(@Nullable Object object) { 651 if (object instanceof Range) { 652 Range<?> other = (Range<?>) object; 653 return lowerBound.equals(other.lowerBound) && upperBound.equals(other.upperBound); 654 } 655 return false; 656 } 657 658 /** Returns a hash code for this range. */ 659 @Override 660 public int hashCode() { 661 return lowerBound.hashCode() * 31 + upperBound.hashCode(); 662 } 663 664 /** 665 * Returns a string representation of this range, such as {@code "[3..5)"} (other examples are 666 * listed in the class documentation). 667 */ 668 @Override 669 public String toString() { 670 return toString(lowerBound, upperBound); 671 } 672 673 private static String toString(Cut<?> lowerBound, Cut<?> upperBound) { 674 StringBuilder sb = new StringBuilder(16); 675 lowerBound.describeAsLowerBound(sb); 676 sb.append(".."); 677 upperBound.describeAsUpperBound(sb); 678 return sb.toString(); 679 } 680 681 // We declare accessors so that we can use method references like `Range::lowerBound`. 682 683 Cut<C> lowerBound() { 684 return lowerBound; 685 } 686 687 Cut<C> upperBound() { 688 return upperBound; 689 } 690 691 Object readResolve() { 692 if (this.equals(ALL)) { 693 return all(); 694 } else { 695 return this; 696 } 697 } 698 699 @SuppressWarnings("unchecked") // this method may throw CCE 700 static int compareOrThrow(Comparable left, Comparable right) { 701 return left.compareTo(right); 702 } 703 704 /** Needed to serialize sorted collections of Ranges. */ 705 private static class RangeLexOrdering extends Ordering<Range<?>> implements Serializable { 706 static final Ordering<?> INSTANCE = new RangeLexOrdering(); 707 708 @Override 709 public int compare(Range<?> left, Range<?> right) { 710 return ComparisonChain.start() 711 .compare(left.lowerBound, right.lowerBound) 712 .compare(left.upperBound, right.upperBound) 713 .result(); 714 } 715 716 private static final long serialVersionUID = 0; 717 } 718 719 private static final long serialVersionUID = 0; 720}