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