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