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