001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.lang3;
018
019import java.io.Serializable;
020import java.util.Comparator;
021
022/**
023 * <p>An immutable range of objects from a minimum to maximum point inclusive.</p>
024 *
025 * <p>The objects need to either be implementations of {@code Comparable}
026 * or you need to supply a {@code Comparator}. </p>
027 *
028 * <p>#ThreadSafe# if the objects and comparator are thread-safe</p>
029 *
030 * @param <T> The type of range values.
031 * @since 3.0
032 */
033public final class Range<T> implements Serializable {
034
035    //-----------------------------------------------------------------------
036    @SuppressWarnings({"rawtypes", "unchecked"})
037    private enum ComparableComparator implements Comparator {
038        INSTANCE;
039        /**
040         * Comparable based compare implementation.
041         *
042         * @param obj1 left hand side of comparison
043         * @param obj2 right hand side of comparison
044         * @return negative, 0, positive comparison value
045         */
046        @Override
047        public int compare(final Object obj1, final Object obj2) {
048            return ((Comparable) obj1).compareTo(obj2);
049        }
050    }
051
052    /**
053     * Serialization version.
054     * @see java.io.Serializable
055     */
056    private static final long serialVersionUID = 1L;
057    /**
058     * <p>Obtains a range with the specified minimum and maximum values (both inclusive).</p>
059     *
060     * <p>The range uses the natural ordering of the elements to determine where
061     * values lie in the range.</p>
062     *
063     * <p>The arguments may be passed in the order (min,max) or (max,min).
064     * The getMinimum and getMaximum methods will return the correct values.</p>
065     *
066     * @param <T> the type of the elements in this range
067     * @param fromInclusive  the first value that defines the edge of the range, inclusive
068     * @param toInclusive  the second value that defines the edge of the range, inclusive
069     * @return the range object, not null
070     * @throws IllegalArgumentException if either element is null
071     * @throws ClassCastException if the elements are not {@code Comparable}
072     */
073    public static <T extends Comparable<T>> Range<T> between(final T fromInclusive, final T toInclusive) {
074        return between(fromInclusive, toInclusive, null);
075    }
076
077    /**
078     * <p>Obtains a range with the specified minimum and maximum values (both inclusive).</p>
079     *
080     * <p>The range uses the specified {@code Comparator} to determine where
081     * values lie in the range.</p>
082     *
083     * <p>The arguments may be passed in the order (min,max) or (max,min).
084     * The getMinimum and getMaximum methods will return the correct values.</p>
085     *
086     * @param <T> the type of the elements in this range
087     * @param fromInclusive  the first value that defines the edge of the range, inclusive
088     * @param toInclusive  the second value that defines the edge of the range, inclusive
089     * @param comparator  the comparator to be used, null for natural ordering
090     * @return the range object, not null
091     * @throws IllegalArgumentException if either element is null
092     * @throws ClassCastException if using natural ordering and the elements are not {@code Comparable}
093     */
094    public static <T> Range<T> between(final T fromInclusive, final T toInclusive, final Comparator<T> comparator) {
095        return new Range<>(fromInclusive, toInclusive, comparator);
096    }
097
098    /**
099     * <p>Obtains a range using the specified element as both the minimum
100     * and maximum in this range.</p>
101     *
102     * <p>The range uses the natural ordering of the elements to determine where
103     * values lie in the range.</p>
104     *
105     * @param <T> the type of the elements in this range
106     * @param element  the value to use for this range, not null
107     * @return the range object, not null
108     * @throws IllegalArgumentException if the element is null
109     * @throws ClassCastException if the element is not {@code Comparable}
110     */
111    public static <T extends Comparable<T>> Range<T> is(final T element) {
112        return between(element, element, null);
113    }
114
115    /**
116     * <p>Obtains a range using the specified element as both the minimum
117     * and maximum in this range.</p>
118     *
119     * <p>The range uses the specified {@code Comparator} to determine where
120     * values lie in the range.</p>
121     *
122     * @param <T> the type of the elements in this range
123     * @param element  the value to use for this range, must not be {@code null}
124     * @param comparator  the comparator to be used, null for natural ordering
125     * @return the range object, not null
126     * @throws IllegalArgumentException if the element is null
127     * @throws ClassCastException if using natural ordering and the elements are not {@code Comparable}
128     */
129    public static <T> Range<T> is(final T element, final Comparator<T> comparator) {
130        return between(element, element, comparator);
131    }
132
133    /**
134     * The ordering scheme used in this range.
135     */
136    private final Comparator<T> comparator;
137
138    /**
139     * Cached output hashCode (class is immutable).
140     */
141    private transient int hashCode;
142
143    /**
144     * The maximum value in this range (inclusive).
145     */
146    private final T maximum;
147
148    /**
149     * The minimum value in this range (inclusive).
150     */
151    private final T minimum;
152
153    /**
154     * Cached output toString (class is immutable).
155     */
156    private transient String toString;
157
158    // Accessors
159    //--------------------------------------------------------------------
160
161    /**
162     * Creates an instance.
163     *
164     * @param element1  the first element, not null
165     * @param element2  the second element, not null
166     * @param comp  the comparator to be used, null for natural ordering
167     */
168    @SuppressWarnings("unchecked")
169    private Range(final T element1, final T element2, final Comparator<T> comp) {
170        if (element1 == null || element2 == null) {
171            throw new IllegalArgumentException("Elements in a range must not be null: element1=" +
172                                               element1 + ", element2=" + element2);
173        }
174        if (comp == null) {
175            this.comparator = ComparableComparator.INSTANCE;
176        } else {
177            this.comparator = comp;
178        }
179        if (this.comparator.compare(element1, element2) < 1) {
180            this.minimum = element1;
181            this.maximum = element2;
182        } else {
183            this.minimum = element2;
184            this.maximum = element1;
185        }
186    }
187
188    /**
189     * <p>Checks whether the specified element occurs within this range.</p>
190     *
191     * @param element  the element to check for, null returns false
192     * @return true if the specified element occurs within this range
193     */
194    public boolean contains(final T element) {
195        if (element == null) {
196            return false;
197        }
198        return comparator.compare(element, minimum) > -1 && comparator.compare(element, maximum) < 1;
199    }
200
201    /**
202     * <p>Checks whether this range contains all the elements of the specified range.</p>
203     *
204     * <p>This method may fail if the ranges have two different comparators or element types.</p>
205     *
206     * @param otherRange  the range to check, null returns false
207     * @return true if this range contains the specified range
208     * @throws RuntimeException if ranges cannot be compared
209     */
210    public boolean containsRange(final Range<T> otherRange) {
211        if (otherRange == null) {
212            return false;
213        }
214        return contains(otherRange.minimum)
215            && contains(otherRange.maximum);
216    }
217
218    /**
219     * <p>Checks where the specified element occurs relative to this range.</p>
220     *
221     * <p>The API is reminiscent of the Comparable interface returning {@code -1} if
222     * the element is before the range, {@code 0} if contained within the range and
223     * {@code 1} if the element is after the range. </p>
224     *
225     * @param element  the element to check for, not null
226     * @return -1, 0 or +1 depending on the element's location relative to the range
227     */
228    public int elementCompareTo(final T element) {
229        // Comparable API says throw NPE on null
230        Validate.notNull(element, "Element is null");
231        if (isAfter(element)) {
232            return -1;
233        } else if (isBefore(element)) {
234            return 1;
235        } else {
236            return 0;
237        }
238    }
239
240    // Element tests
241    //--------------------------------------------------------------------
242
243    /**
244     * <p>Compares this range to another object to test if they are equal.</p>.
245     *
246     * <p>To be equal, the minimum and maximum values must be equal, which
247     * ignores any differences in the comparator.</p>
248     *
249     * @param obj the reference object with which to compare
250     * @return true if this object is equal
251     */
252    @Override
253    public boolean equals(final Object obj) {
254        if (obj == this) {
255            return true;
256        } else if (obj == null || obj.getClass() != getClass()) {
257            return false;
258        } else {
259            @SuppressWarnings("unchecked") // OK because we checked the class above
260            final
261            Range<T> range = (Range<T>) obj;
262            return minimum.equals(range.minimum) &&
263                   maximum.equals(range.maximum);
264        }
265    }
266
267    /**
268     * <p>Gets the comparator being used to determine if objects are within the range.</p>
269     *
270     * <p>Natural ordering uses an internal comparator implementation, thus this
271     * method never returns null. See {@link #isNaturalOrdering()}.</p>
272     *
273     * @return the comparator being used, not null
274     */
275    public Comparator<T> getComparator() {
276        return comparator;
277    }
278
279    /**
280     * <p>Gets the maximum value in this range.</p>
281     *
282     * @return the maximum value in this range, not null
283     */
284    public T getMaximum() {
285        return maximum;
286    }
287
288    /**
289     * <p>Gets the minimum value in this range.</p>
290     *
291     * @return the minimum value in this range, not null
292     */
293    public T getMinimum() {
294        return minimum;
295    }
296
297    /**
298     * <p>Gets a suitable hash code for the range.</p>
299     *
300     * @return a hash code value for this object
301     */
302    @Override
303    public int hashCode() {
304        int result = hashCode;
305        if (hashCode == 0) {
306            result = 17;
307            result = 37 * result + getClass().hashCode();
308            result = 37 * result + minimum.hashCode();
309            result = 37 * result + maximum.hashCode();
310            hashCode = result;
311        }
312        return result;
313    }
314
315    /**
316     * Calculate the intersection of {@code this} and an overlapping Range.
317     * @param other overlapping Range
318     * @return range representing the intersection of {@code this} and {@code other} ({@code this} if equal)
319     * @throws IllegalArgumentException if {@code other} does not overlap {@code this}
320     * @since 3.0.1
321     */
322    public Range<T> intersectionWith(final Range<T> other) {
323        if (!this.isOverlappedBy(other)) {
324            throw new IllegalArgumentException(String.format(
325                "Cannot calculate intersection with non-overlapping range %s", other));
326        }
327        if (this.equals(other)) {
328            return this;
329        }
330        final T min = getComparator().compare(minimum, other.minimum) < 0 ? other.minimum : minimum;
331        final T max = getComparator().compare(maximum, other.maximum) < 0 ? maximum : other.maximum;
332        return between(min, max, getComparator());
333    }
334
335    // Range tests
336    //--------------------------------------------------------------------
337
338    /**
339     * <p>Checks whether this range is after the specified element.</p>
340     *
341     * @param element  the element to check for, null returns false
342     * @return true if this range is entirely after the specified element
343     */
344    public boolean isAfter(final T element) {
345        if (element == null) {
346            return false;
347        }
348        return comparator.compare(element, minimum) < 0;
349    }
350
351    /**
352     * <p>Checks whether this range is completely after the specified range.</p>
353     *
354     * <p>This method may fail if the ranges have two different comparators or element types.</p>
355     *
356     * @param otherRange  the range to check, null returns false
357     * @return true if this range is completely after the specified range
358     * @throws RuntimeException if ranges cannot be compared
359     */
360    public boolean isAfterRange(final Range<T> otherRange) {
361        if (otherRange == null) {
362            return false;
363        }
364        return isAfter(otherRange.maximum);
365    }
366
367    /**
368     * <p>Checks whether this range is before the specified element.</p>
369     *
370     * @param element  the element to check for, null returns false
371     * @return true if this range is entirely before the specified element
372     */
373    public boolean isBefore(final T element) {
374        if (element == null) {
375            return false;
376        }
377        return comparator.compare(element, maximum) > 0;
378    }
379
380    /**
381     * <p>Checks whether this range is completely before the specified range.</p>
382     *
383     * <p>This method may fail if the ranges have two different comparators or element types.</p>
384     *
385     * @param otherRange  the range to check, null returns false
386     * @return true if this range is completely before the specified range
387     * @throws RuntimeException if ranges cannot be compared
388     */
389    public boolean isBeforeRange(final Range<T> otherRange) {
390        if (otherRange == null) {
391            return false;
392        }
393        return isBefore(otherRange.minimum);
394    }
395
396    /**
397     * <p>Checks whether this range ends with the specified element.</p>
398     *
399     * @param element  the element to check for, null returns false
400     * @return true if the specified element occurs within this range
401     */
402    public boolean isEndedBy(final T element) {
403        if (element == null) {
404            return false;
405        }
406        return comparator.compare(element, maximum) == 0;
407    }
408
409    // Basics
410    //--------------------------------------------------------------------
411
412    /**
413     * <p>Whether or not the Range is using the natural ordering of the elements.</p>
414     *
415     * <p>Natural ordering uses an internal comparator implementation, thus this
416     * method is the only way to check if a null comparator was specified.</p>
417     *
418     * @return true if using natural ordering
419     */
420    public boolean isNaturalOrdering() {
421        return comparator == ComparableComparator.INSTANCE;
422    }
423
424    /**
425     * <p>Checks whether this range is overlapped by the specified range.</p>
426     *
427     * <p>Two ranges overlap if there is at least one element in common.</p>
428     *
429     * <p>This method may fail if the ranges have two different comparators or element types.</p>
430     *
431     * @param otherRange  the range to test, null returns false
432     * @return true if the specified range overlaps with this
433     *  range; otherwise, {@code false}
434     * @throws RuntimeException if ranges cannot be compared
435     */
436    public boolean isOverlappedBy(final Range<T> otherRange) {
437        if (otherRange == null) {
438            return false;
439        }
440        return otherRange.contains(minimum)
441            || otherRange.contains(maximum)
442            || contains(otherRange.minimum);
443    }
444
445    /**
446     * <p>Checks whether this range starts with the specified element.</p>
447     *
448     * @param element  the element to check for, null returns false
449     * @return true if the specified element occurs within this range
450     */
451    public boolean isStartedBy(final T element) {
452        if (element == null) {
453            return false;
454        }
455        return comparator.compare(element, minimum) == 0;
456    }
457
458    /**
459     * <p>
460     * Fits the given element into this range by returning the given element or, if out of bounds, the range minimum if
461     * below, or the range maximum if above.
462     * </p>
463     * <pre>
464     * Range&lt;Integer&gt; range = Range.between(16, 64);
465     * range.fit(-9) --&gt;  16
466     * range.fit(0)  --&gt;  16
467     * range.fit(15) --&gt;  16
468     * range.fit(16) --&gt;  16
469     * range.fit(17) --&gt;  17
470     * ...
471     * range.fit(63) --&gt;  63
472     * range.fit(64) --&gt;  64
473     * range.fit(99) --&gt;  64
474     * </pre>
475     * @param element the element to check for, not null
476     * @return the minimum, the element, or the maximum depending on the element's location relative to the range
477     * @since 3.10
478     */
479    public T fit(final T element) {
480        // Comparable API says throw NPE on null
481        Validate.notNull(element, "element");
482        if (isAfter(element)) {
483            return minimum;
484        } else if (isBefore(element)) {
485            return maximum;
486        } else {
487            return element;
488        }
489    }
490
491    /**
492     * <p>Gets the range as a {@code String}.</p>
493     *
494     * <p>The format of the String is '[<i>min</i>..<i>max</i>]'.</p>
495     *
496     * @return the {@code String} representation of this range
497     */
498    @Override
499    public String toString() {
500        if (toString == null) {
501            toString = "[" + minimum + ".." + maximum + "]";
502        }
503        return toString;
504    }
505
506    /**
507     * <p>Formats the receiver using the given format.</p>
508     *
509     * <p>This uses {@link java.util.Formattable} to perform the formatting. Three variables may
510     * be used to embed the minimum, maximum and comparator.
511     * Use {@code %1$s} for the minimum element, {@code %2$s} for the maximum element
512     * and {@code %3$s} for the comparator.
513     * The default format used by {@code toString()} is {@code [%1$s..%2$s]}.</p>
514     *
515     * @param format  the format string, optionally containing {@code %1$s}, {@code %2$s} and  {@code %3$s}, not null
516     * @return the formatted string, not null
517     */
518    public String toString(final String format) {
519        return String.format(format, minimum, maximum, comparator);
520    }
521
522}