1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.lang3;
18
19 import java.io.IOException;
20 import java.io.InvalidObjectException;
21 import java.io.ObjectInputStream;
22 import java.io.Serializable;
23 import java.util.Comparator;
24 import java.util.Objects;
25
26 /**
27 * An immutable range of objects from a minimum to maximum point inclusive.
28 *
29 * <p>
30 * The objects need to either be implementations of {@link Comparable}
31 * or you need to supply a {@link Comparator}.
32 * </p>
33 *
34 * <p>
35 * #ThreadSafe# if the objects and comparator are thread-safe.
36 * </p>
37 *
38 * @param <T> The type of range values.
39 * @since 3.0
40 */
41 public class Range<T> implements Serializable {
42
43 @SuppressWarnings({"rawtypes", "unchecked"})
44 private enum ComparableComparator implements Comparator {
45 INSTANCE;
46
47 /**
48 * Comparable based compare implementation.
49 *
50 * @param obj1 left-hand side of comparison.
51 * @param obj2 right-hand side of comparison.
52 * @return negative, 0, positive comparison value.
53 */
54 @Override
55 public int compare(final Object obj1, final Object obj2) {
56 return ((Comparable) obj1).compareTo(obj2);
57 }
58 }
59
60 /**
61 * Serialization version.
62 *
63 * @see java.io.Serializable
64 */
65 private static final long serialVersionUID = 1L;
66
67 /**
68 * Creates a range with the specified minimum and maximum values (both inclusive).
69 *
70 * <p>
71 * The range uses the natural ordering of the elements to determine where
72 * values lie in the range.
73 * </p>
74 *
75 * <p>
76 * The arguments may be passed in the order (min, max) or (max, min).
77 * The getMinimum and getMaximum methods will return the correct values.
78 * </p>
79 *
80 * @param <T> The type of the elements in this range.
81 * @param fromInclusive The first value that defines the edge of the range, inclusive.
82 * @param toInclusive The second value that defines the edge of the range, inclusive.
83 * @return The range object, not null.
84 * @throws NullPointerException Thrown when fromInclusive is null.
85 * @throws NullPointerException Thrown when toInclusive is null.
86 * @throws ClassCastException Thrown if the elements are not {@link Comparable}.
87 * @throws IllegalArgumentException Thrown if either element is a floating-point NaN.
88 * @deprecated Use {@link #of(Comparable, Comparable)}.
89 */
90 @Deprecated
91 public static <T extends Comparable<? super T>> Range<T> between(final T fromInclusive, final T toInclusive) {
92 return of(fromInclusive, toInclusive, null);
93 }
94
95 /**
96 * Creates a range with the specified minimum and maximum values (both inclusive).
97 *
98 * <p>
99 * The range uses the specified {@link Comparator} to determine where
100 * values lie in the range.
101 * </p>
102 *
103 * <p>
104 * The arguments may be passed in the order (min, max) or (max, min).
105 * The getMinimum and getMaximum methods will return the correct values.
106 * </p>
107 *
108 * @param <T> The type of the elements in this range.
109 * @param fromInclusive The first value that defines the edge of the range, inclusive.
110 * @param toInclusive The second value that defines the edge of the range, inclusive.
111 * @param comparator The comparator to be used, null for natural ordering.
112 * @return The range object, not null.
113 * @throws NullPointerException Thrown when fromInclusive is null.
114 * @throws NullPointerException Thrown when toInclusive is null.
115 * @throws ClassCastException Thrown if using natural ordering and the elements are not {@link Comparable}.
116 * @throws IllegalArgumentException Thrown if either element is a floating-point NaN.
117 * @deprecated Use {@link #of(Object, Object, Comparator)}.
118 */
119 @Deprecated
120 public static <T> Range<T> between(final T fromInclusive, final T toInclusive, final Comparator<T> comparator) {
121 return new Range<>(fromInclusive, toInclusive, comparator);
122 }
123
124 private static int hash(final Object value1, final Object value2) {
125 return Objects.hash(value1, value2);
126 }
127
128 /**
129 * Creates a range using the specified element as both the minimum
130 * and maximum in this range.
131 *
132 * <p>
133 * The range uses the natural ordering of the elements to determine where
134 * values lie in the range.
135 * </p>
136 *
137 * @param <T> The type of the elements in this range.
138 * @param element The value to use for this range, not null.
139 * @return The range object, not null.
140 * @throws NullPointerException Thrown if the element is null.
141 * @throws ClassCastException Thrown if the element is not {@link Comparable}.
142 * @throws IllegalArgumentException Thrown if the element is a floating-point NaN.
143 */
144 public static <T extends Comparable<? super T>> Range<T> is(final T element) {
145 return of(element, element, null);
146 }
147
148 /**
149 * Creates a range using the specified element as both the minimum
150 * and maximum in this range.
151 *
152 * <p>
153 * The range uses the specified {@link Comparator} to determine where
154 * values lie in the range.
155 * </p>
156 *
157 * @param <T> The type of the elements in this range.
158 * @param element The value to use for this range, must not be {@code null}.
159 * @param comparator The comparator to be used, null for natural ordering.
160 * @return The range object, not null.
161 * @throws NullPointerException Thrown if the element is null.
162 * @throws ClassCastException Thrown if using natural ordering and the elements are not {@link Comparable}.
163 * @throws IllegalArgumentException Thrown if the element is a floating-point NaN.
164 */
165 public static <T> Range<T> is(final T element, final Comparator<T> comparator) {
166 return of(element, element, comparator);
167 }
168
169 /**
170 * Tests whether the element is a floating-point NaN. A NaN endpoint sorts above every value under the natural
171 * total order ({@link Double#compareTo(Double)} / {@link Float#compareTo(Float)}), silently producing a
172 * half-unbounded range whose {@code contains}/{@code fit} accept every value above the minimum.
173 *
174 * @param element The element to test, may be null.
175 * @return Whether the element is a floating-point NaN.
176 */
177 private static boolean isNaN(final Object element) {
178 return element instanceof Double && ((Double) element).isNaN()
179 || element instanceof Float && ((Float) element).isNaN();
180 }
181
182 /**
183 * Creates a range with the specified minimum and maximum values (both inclusive).
184 *
185 * <p>
186 * The range uses the natural ordering of the elements to determine where
187 * values lie in the range.
188 * </p>
189 *
190 * <p>
191 * The arguments may be passed in the order (min, max) or (max, min).
192 * The getMinimum and getMaximum methods will return the correct values.
193 * </p>
194 *
195 * @param <T> The type of the elements in this range.
196 * @param fromInclusive The first value that defines the edge of the range, inclusive.
197 * @param toInclusive The second value that defines the edge of the range, inclusive.
198 * @return The range object, not null.
199 * @throws NullPointerException Thrown if either element is null.
200 * @throws ClassCastException Thrown if the elements are not {@link Comparable}.
201 * @throws IllegalArgumentException Thrown if either element is a floating-point NaN.
202 * @since 3.13.0
203 */
204 public static <T extends Comparable<? super T>> Range<T> of(final T fromInclusive, final T toInclusive) {
205 return of(fromInclusive, toInclusive, null);
206 }
207
208 /**
209 * Creates a range with the specified minimum and maximum values (both inclusive).
210 *
211 * <p>
212 * The range uses the specified {@link Comparator} to determine where
213 * values lie in the range.
214 * </p>
215 *
216 * <p>
217 * The arguments may be passed in the order (min, max) or (max, min).
218 * The getMinimum and getMaximum methods will return the correct values.
219 * </p>
220 *
221 * @param <T> The type of the elements in this range.
222 * @param fromInclusive The first value that defines the edge of the range, inclusive.
223 * @param toInclusive The second value that defines the edge of the range, inclusive.
224 * @param comparator The comparator to be used, null for natural ordering.
225 * @return The range object, not null.
226 * @throws NullPointerException Thrown when fromInclusive is null.
227 * @throws NullPointerException Thrown when toInclusive is null.
228 * @throws ClassCastException Thrown if using natural ordering and the elements are not {@link Comparable}.
229 * @throws IllegalArgumentException Thrown if either element is a floating-point NaN.
230 * @since 3.13.0
231 */
232 public static <T> Range<T> of(final T fromInclusive, final T toInclusive, final Comparator<T> comparator) {
233 return new Range<>(fromInclusive, toInclusive, comparator);
234 }
235
236 /**
237 * Validates that a floating-point endpoint is not NaN, mirroring the fail-closed posture of
238 * {@link Validate#notNaN(double, String, Object...)}.
239 *
240 * @param element The endpoint to validate.
241 * @param name The parameter name for the exception message.
242 * @throws IllegalArgumentException Thrown if the endpoint is a floating-point NaN.
243 */
244 private static void requireNotNaN(final Object element, final String name) {
245 if (isNaN(element)) {
246 throw new IllegalArgumentException(name + " must not be NaN");
247 }
248 }
249
250 /**
251 * The ordering scheme used in this range.
252 */
253 private final Comparator<T> comparator;
254
255 /**
256 * Cached output hashCode (class is immutable).
257 */
258 private transient int hashCode;
259
260 /**
261 * The maximum value in this range (inclusive).
262 */
263 private final T maximum;
264
265 /**
266 * The minimum value in this range (inclusive).
267 */
268 private final T minimum;
269
270 /**
271 * Cached output toString (class is immutable).
272 */
273 private transient String toString;
274
275 /**
276 * Creates an instance.
277 *
278 * @param element1 The first element, not null.
279 * @param element2 The second element, not null
280 * @param comp The comparator to be used, null for natural ordering.
281 * @throws NullPointerException Thrown when element1 is null.
282 * @throws NullPointerException Thrown when element2 is null.
283 * @throws IllegalArgumentException Thrown when element1 or element2 is a floating-point NaN.
284 */
285 @SuppressWarnings("unchecked")
286 Range(final T element1, final T element2, final Comparator<T> comp) {
287 Objects.requireNonNull(element1, "element1");
288 Objects.requireNonNull(element2, "element2");
289 requireNotNaN(element1, "element1");
290 requireNotNaN(element2, "element2");
291 if (comp == null) {
292 this.comparator = ComparableComparator.INSTANCE;
293 } else {
294 this.comparator = comp;
295 }
296 if (this.comparator.compare(element1, element2) < 1) {
297 this.minimum = element1;
298 this.maximum = element2;
299 } else {
300 this.minimum = element2;
301 this.maximum = element1;
302 }
303 this.hashCode = hash(minimum, maximum);
304 }
305
306 /**
307 * Checks whether the specified element occurs within this range.
308 *
309 * @param element The element to check for, null returns false.
310 * @return true if the specified element occurs within this range.
311 */
312 public boolean contains(final T element) {
313 if (element == null) {
314 return false;
315 }
316 return comparator.compare(element, minimum) > -1 && comparator.compare(element, maximum) < 1;
317 }
318
319 /**
320 * Checks whether this range contains all the elements of the specified range.
321 *
322 * <p>
323 * This method may fail if the ranges have two different comparators or element types.
324 * </p>
325 *
326 * @param otherRange The range to check, null returns false.
327 * @return true if this range contains the specified range.
328 * @throws RuntimeException Thrown if ranges cannot be compared.
329 */
330 public boolean containsRange(final Range<T> otherRange) {
331 if (otherRange == null) {
332 return false;
333 }
334 return contains(otherRange.minimum)
335 && contains(otherRange.maximum);
336 }
337
338 /**
339 * Checks where the specified element occurs relative to this range.
340 *
341 * <p>
342 * The API is reminiscent of the Comparable interface returning {@code -1} if
343 * the element is before the range, {@code 0} if contained within the range and
344 * {@code 1} if the element is after the range.
345 * </p>
346 *
347 * @param element The element to check for, not null.
348 * @return -1, 0 or +1 depending on the element's location relative to the range.
349 * @throws NullPointerException Thrown if {@code element} is {@code null}.
350 */
351 public int elementCompareTo(final T element) {
352 // Comparable API says throw NPE on null
353 Objects.requireNonNull(element, "element");
354 if (isAfter(element)) {
355 return -1;
356 }
357 if (isBefore(element)) {
358 return 1;
359 }
360 return 0;
361 }
362
363 /**
364 * Compares this range to another object to test if they are equal.
365 *
366 * <p>
367 * To be equal, the minimum and maximum values must be equal, which
368 * ignores any differences in the comparator.
369 * </p>
370 *
371 * @param obj The reference object with which to compare.
372 * @return true if this object is equal.
373 */
374 @Override
375 public boolean equals(final Object obj) {
376 if (obj == this) {
377 return true;
378 }
379 if (obj == null || obj.getClass() != getClass()) {
380 return false;
381 }
382 @SuppressWarnings("unchecked") // OK because we checked the class above
383 final
384 Range<T> range = (Range<T>) obj;
385 return minimum.equals(range.minimum) &&
386 maximum.equals(range.maximum);
387 }
388
389 /**
390 * Fits the given element into this range by returning the given element or, if out of bounds, the range minimum if
391 * below, or the range maximum if above.
392 *
393 * <pre>{@code
394 * Range<Integer> range = Range.between(16, 64);
395 * range.fit(-9) --> 16
396 * range.fit(0) --> 16
397 * range.fit(15) --> 16
398 * range.fit(16) --> 16
399 * range.fit(17) --> 17
400 * ...
401 * range.fit(63) --> 63
402 * range.fit(64) --> 64
403 * range.fit(99) --> 64
404 * }</pre>
405 *
406 * @param element The element to check for, not null.
407 * @return The minimum, the element, or the maximum depending on the element's location relative to the range.
408 * @throws NullPointerException Thrown if {@code element} is {@code null}.
409 * @since 3.10
410 */
411 public T fit(final T element) {
412 // Comparable API says throw NPE on null
413 Objects.requireNonNull(element, "element");
414 if (isAfter(element)) {
415 return minimum;
416 }
417 if (isBefore(element)) {
418 return maximum;
419 }
420 return element;
421 }
422
423 /**
424 * Gets the comparator being used to determine if objects are within the range.
425 *
426 * <p>
427 * Natural ordering uses an internal comparator implementation, thus this
428 * method never returns null. See {@link #isNaturalOrdering()}.
429 * </p>
430 *
431 * @return The comparator being used, not null.
432 */
433 public Comparator<T> getComparator() {
434 return comparator;
435 }
436
437 /**
438 * Gets the maximum value in this range.
439 *
440 * @return The maximum value in this range, not null.
441 */
442 public T getMaximum() {
443 return maximum;
444 }
445
446 /**
447 * Gets the minimum value in this range.
448 *
449 * @return The minimum value in this range, not null.
450 */
451 public T getMinimum() {
452 return minimum;
453 }
454
455 /**
456 * Gets a suitable hash code for the range.
457 *
458 * @return A hash code value for this object.
459 */
460 @Override
461 public int hashCode() {
462 return hashCode;
463 }
464
465 /**
466 * Calculate the intersection of {@code this} and an overlapping Range.
467 *
468 * @param other overlapping Range.
469 * @return range representing the intersection of {@code this} and {@code other} ({@code this} if equal).
470 * @throws IllegalArgumentException Thrown if {@code other} does not overlap {@code this}.
471 * @since 3.0.1
472 */
473 public Range<T> intersectionWith(final Range<T> other) {
474 if (!this.isOverlappedBy(other)) {
475 throw new IllegalArgumentException(String.format(
476 "Cannot calculate intersection with non-overlapping range %s", other));
477 }
478 if (this.equals(other)) {
479 return this;
480 }
481 final T min = getComparator().compare(minimum, other.minimum) < 0 ? other.minimum : minimum;
482 final T max = getComparator().compare(maximum, other.maximum) < 0 ? maximum : other.maximum;
483 return of(min, max, getComparator());
484 }
485
486 /**
487 * Tests whether this range is after the specified element.
488 *
489 * @param element The element to check for, null returns false.
490 * @return true if this range is entirely after the specified element.
491 */
492 public boolean isAfter(final T element) {
493 if (element == null) {
494 return false;
495 }
496 return comparator.compare(element, minimum) < 0;
497 }
498
499 /**
500 * Tests whether this range is completely after the specified range.
501 *
502 * <p>
503 * This method may fail if the ranges have two different comparators or element types.
504 * </p>
505 *
506 * @param otherRange The range to check, null returns false.
507 * @return true if this range is completely after the specified range.
508 * @throws RuntimeException Thrown if ranges cannot be compared.
509 */
510 public boolean isAfterRange(final Range<T> otherRange) {
511 if (otherRange == null) {
512 return false;
513 }
514 return isAfter(otherRange.maximum);
515 }
516
517 /**
518 * Tests whether this range is before the specified element.
519 *
520 * @param element The element to check for, null returns false.
521 * @return true if this range is entirely before the specified element.
522 */
523 public boolean isBefore(final T element) {
524 if (element == null) {
525 return false;
526 }
527 return comparator.compare(element, maximum) > 0;
528 }
529
530 /**
531 * Tests whether this range is completely before the specified range.
532 *
533 * <p>
534 * This method may fail if the ranges have two different comparators or element types.
535 * </p>
536 *
537 * @param otherRange The range to check, null returns false.
538 * @return true if this range is completely before the specified range.
539 * @throws RuntimeException Thrown if ranges cannot be compared.
540 */
541 public boolean isBeforeRange(final Range<T> otherRange) {
542 if (otherRange == null) {
543 return false;
544 }
545 return isBefore(otherRange.minimum);
546 }
547
548 /**
549 * Tests whether this range ends with the specified element.
550 *
551 * @param element The element to check for, null returns false.
552 * @return true if the specified element occurs within this range.
553 */
554 public boolean isEndedBy(final T element) {
555 if (element == null) {
556 return false;
557 }
558 return comparator.compare(element, maximum) == 0;
559 }
560
561 /**
562 * Tests whether or not the Range is using the natural ordering of the elements.
563 *
564 * <p>
565 * Natural ordering uses an internal comparator implementation, thus this
566 * method is the only way to check if a null comparator was specified.
567 * </p>
568 *
569 * @return true if using natural ordering.
570 */
571 public boolean isNaturalOrdering() {
572 return comparator == ComparableComparator.INSTANCE;
573 }
574
575 /**
576 * Tests whether this range is overlapped by the specified range.
577 *
578 * <p>
579 * Two ranges overlap if there is at least one element in common.
580 * </p>
581 *
582 * <p>
583 * This method may fail if the ranges have two different comparators or element types.
584 * </p>
585 *
586 * @param otherRange The range to test, null returns false.
587 * @return true if the specified range overlaps with this
588 * range; otherwise, {@code false}.
589 * @throws RuntimeException Thrown if ranges cannot be compared.
590 */
591 public boolean isOverlappedBy(final Range<T> otherRange) {
592 if (otherRange == null) {
593 return false;
594 }
595 return otherRange.contains(minimum)
596 || otherRange.contains(maximum)
597 || contains(otherRange.minimum);
598 }
599
600 /**
601 * Tests whether this range starts with the specified element.
602 *
603 * @param element The element to check for, null returns false.
604 * @return true if the specified element occurs within this range.
605 */
606 public boolean isStartedBy(final T element) {
607 if (element == null) {
608 return false;
609 }
610 return comparator.compare(element, minimum) == 0;
611 }
612
613 /**
614 * Validates the endpoints and comparator and recomputes the cached hash code after deserialization.
615 *
616 * @param in See {@link Serializable}.
617 * @throws IOException Thrown as described in {@link Serializable}.
618 * @throws ClassNotFoundException Thrown as described in {@link Serializable}.
619 * @throws InvalidObjectException Thrown if the endpoints or comparator violate the range invariants.
620 */
621 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
622 in.defaultReadObject();
623 SerializationUtils.requireNonNull(maximum, "maximum null");
624 SerializationUtils.requireNonNull(minimum, "minimum null");
625 SerializationUtils.requireNonNull(comparator, "comparator null");
626 // Mirror the constructor's NaN endpoint rejection: a crafted stream cannot smuggle in the degenerate
627 // half-unbounded range that construction refuses.
628 if (isNaN(minimum) || isNaN(maximum)) {
629 throw new InvalidObjectException("Range minimum/maximum must not be NaN.");
630 }
631 if (comparator.compare(minimum, maximum) > 0) {
632 throw new InvalidObjectException("Range minimum is greater than maximum under the comparator.");
633 }
634 hashCode = hash(minimum, maximum);
635 }
636
637 /**
638 * Gets the range as a {@link String}.
639 *
640 * <p>
641 * The format of the String is '[<em>min</em>..<em>max</em>]'.
642 * </p>
643 *
644 * @return The {@link String} representation of this range.
645 */
646 @Override
647 public String toString() {
648 if (toString == null) {
649 toString = "[" + minimum + ".." + maximum + "]";
650 }
651 return toString;
652 }
653
654 /**
655 * Formats the receiver using the given format.
656 *
657 * <p>
658 * This uses {@link java.util.Formattable} to perform the formatting. Three variables may
659 * be used to embed the minimum, maximum and comparator.
660 * Use {@code %1$s} for the minimum element, {@code %2$s} for the maximum element
661 * and {@code %3$s} for the comparator.
662 * The default format used by {@code toString()} is {@code [%1$s..%2$s]}.
663 * </p>
664 *
665 * @param format The format string, optionally containing {@code %1$s}, {@code %2$s} and {@code %3$s}, not null.
666 * @return The formatted string, not null.
667 */
668 public String toString(final String format) {
669 return String.format(format, minimum, maximum, comparator);
670 }
671
672 }