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