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 * @version $Id: Range.java 1436770 2013-01-22 07:09:45Z ggregory $
032 */
033public final class Range<T> implements Serializable {
034
035    /**
036     * Serialization version.
037     * @see java.io.Serializable
038     */
039    private static final long serialVersionUID = 1L;
040
041    /**
042     * The ordering scheme used in this range.
043     */
044    private final Comparator<T> comparator;
045    /**
046     * The minimum value in this range (inclusive).
047     */
048    private final T minimum;
049    /**
050     * The maximum value in this range (inclusive).
051     */
052    private final T maximum;
053    /**
054     * Cached output hashCode (class is immutable).
055     */
056    private transient int hashCode;
057    /**
058     * Cached output toString (class is immutable).
059     */
060    private transient String toString;
061
062    /**
063     * <p>Obtains a range using the specified element as both the minimum
064     * and maximum in this range.</p>
065     * 
066     * <p>The range uses the natural ordering of the elements to determine where
067     * values lie in the range.</p>
068     *
069     * @param <T> the type of the elements in this range
070     * @param element  the value to use for this range, not null
071     * @return the range object, not null
072     * @throws IllegalArgumentException if the element is null
073     * @throws ClassCastException if the element is not {@code Comparable}
074     */
075    public static <T extends Comparable<T>> Range<T> is(final T element) {
076        return between(element, element, null);
077    }
078
079    /**
080     * <p>Obtains a range using the specified element as both the minimum
081     * and maximum in this range.</p>
082     * 
083     * <p>The range uses the specified {@code Comparator} to determine where
084     * values lie in the range.</p>
085     *
086     * @param <T> the type of the elements in this range
087     * @param element  the value to use for this range, must not be {@code null}
088     * @param comparator  the comparator to be used, null for natural ordering
089     * @return the range object, not null
090     * @throws IllegalArgumentException if the element is null
091     * @throws ClassCastException if using natural ordering and the elements are not {@code Comparable}
092     */
093    public static <T> Range<T> is(final T element, final Comparator<T> comparator) {
094        return between(element, element, comparator);
095    }
096
097    /**
098     * <p>Obtains a range with the specified minimum and maximum values (both inclusive).</p>
099     * 
100     * <p>The range uses the natural ordering of the elements to determine where
101     * values lie in the range.</p>
102     *
103     * <p>The arguments may be passed in the order (min,max) or (max,min).
104     * The getMinimum and getMaximum methods will return the correct values.</p>
105     *
106     * @param <T> the type of the elements in this range
107     * @param fromInclusive  the first value that defines the edge of the range, inclusive
108     * @param toInclusive  the second value that defines the edge of the range, inclusive
109     * @return the range object, not null
110     * @throws IllegalArgumentException if either element is null
111     * @throws ClassCastException if the elements are not {@code Comparable}
112     */
113    public static <T extends Comparable<T>> Range<T> between(final T fromInclusive, final T toInclusive) {
114        return between(fromInclusive, toInclusive, null);
115    }
116
117    /**
118     * <p>Obtains a range with the specified minimum and maximum values (both inclusive).</p>
119     * 
120     * <p>The range uses the specified {@code Comparator} to determine where
121     * values lie in the range.</p>
122     *
123     * <p>The arguments may be passed in the order (min,max) or (max,min).
124     * The getMinimum and getMaximum methods will return the correct values.</p>
125     *
126     * @param <T> the type of the elements in this range
127     * @param fromInclusive  the first value that defines the edge of the range, inclusive
128     * @param toInclusive  the second value that defines the edge of the range, inclusive
129     * @param comparator  the comparator to be used, null for natural ordering
130     * @return the range object, not null
131     * @throws IllegalArgumentException if either element is null
132     * @throws ClassCastException if using natural ordering and the elements are not {@code Comparable}
133     */
134    public static <T> Range<T> between(final T fromInclusive, final T toInclusive, final Comparator<T> comparator) {
135        return new Range<T>(fromInclusive, toInclusive, comparator);
136    }
137
138    /**
139     * Creates an instance.
140     *
141     * @param element1  the first element, not null
142     * @param element2  the second element, not null
143     * @param comparator  the comparator to be used, null for natural ordering
144     */
145    @SuppressWarnings("unchecked")
146    private Range(final T element1, final T element2, Comparator<T> comparator) {
147        if (element1 == null || element2 == null) {
148            throw new IllegalArgumentException("Elements in a range must not be null: element1=" +
149                                               element1 + ", element2=" + element2);
150        }
151        if (comparator == null) {
152            comparator = ComparableComparator.INSTANCE;
153        }
154        if (comparator.compare(element1, element2) < 1) {
155            this.minimum = element1;
156            this.maximum = element2;
157        } else {
158            this.minimum = element2;
159            this.maximum = element1;
160        }
161        this.comparator = comparator;
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 starts 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        if (element == null) {
289            // Comparable API says throw NPE on null
290            throw new NullPointerException("Element is null");
291        }
292        if (isAfter(element)) {
293            return -1;
294        } else if (isBefore(element)) {
295            return 1;
296        } else {
297            return 0;
298        }
299    }
300
301    // Range tests
302    //--------------------------------------------------------------------
303
304    /**
305     * <p>Checks whether this range contains all the elements of the specified range.</p>
306     *
307     * <p>This method may fail if the ranges have two different comparators or element types.</p>
308     *
309     * @param otherRange  the range to check, null returns false
310     * @return true if this range contains the specified range
311     * @throws RuntimeException if ranges cannot be compared
312     */
313    public boolean containsRange(final Range<T> otherRange) {
314        if (otherRange == null) {
315            return false;
316        }
317        return contains(otherRange.minimum)
318            && contains(otherRange.maximum);
319    }
320
321    /**
322     * <p>Checks whether this range is completely after the specified range.</p>
323     *
324     * <p>This method may fail if the ranges have two different comparators or element types.</p>
325     *
326     * @param otherRange  the range to check, null returns false
327     * @return true if this range is completely after the specified range
328     * @throws RuntimeException if ranges cannot be compared
329     */
330    public boolean isAfterRange(final Range<T> otherRange) {
331        if (otherRange == null) {
332            return false;
333        }
334        return isAfter(otherRange.maximum);
335    }
336
337    /**
338     * <p>Checks whether this range is overlapped by the specified range.</p>
339     * 
340     * <p>Two ranges overlap if there is at least one element in common.</p>
341     *
342     * <p>This method may fail if the ranges have two different comparators or element types.</p>
343     *
344     * @param otherRange  the range to test, null returns false
345     * @return true if the specified range overlaps with this
346     *  range; otherwise, {@code false}
347     * @throws RuntimeException if ranges cannot be compared
348     */
349    public boolean isOverlappedBy(final Range<T> otherRange) {
350        if (otherRange == null) {
351            return false;
352        }
353        return otherRange.contains(minimum)
354            || otherRange.contains(maximum)
355            || contains(otherRange.minimum);
356    }
357
358    /**
359     * <p>Checks whether this range is completely before the specified range.</p>
360     *
361     * <p>This method may fail if the ranges have two different comparators or element types.</p>
362     *
363     * @param otherRange  the range to check, null returns false
364     * @return true if this range is completely before the specified range
365     * @throws RuntimeException if ranges cannot be compared
366     */
367    public boolean isBeforeRange(final Range<T> otherRange) {
368        if (otherRange == null) {
369            return false;
370        }
371        return isBefore(otherRange.minimum);
372    }
373
374    /**
375     * Calculate the intersection of {@code this} and an overlapping Range.
376     * @param other overlapping Range
377     * @return range representing the intersection of {@code this} and {@code other} ({@code this} if equal)
378     * @throws IllegalArgumentException if {@code other} does not overlap {@code this}
379     * @since 3.0.1
380     */
381    public Range<T> intersectionWith(final Range<T> other) {
382        if (!this.isOverlappedBy(other)) {
383            throw new IllegalArgumentException(String.format(
384                "Cannot calculate intersection with non-overlapping range %s", other));
385        }
386        if (this.equals(other)) {
387            return this;
388        }
389        final T min = getComparator().compare(minimum, other.minimum) < 0 ? other.minimum : minimum;
390        final T max = getComparator().compare(maximum, other.maximum) < 0 ? maximum : other.maximum;
391        return between(min, max, getComparator());
392    }
393
394    // Basics
395    //--------------------------------------------------------------------
396
397    /**
398     * <p>Compares this range to another object to test if they are equal.</p>.
399     *
400     * <p>To be equal, the minimum and maximum values must be equal, which
401     * ignores any differences in the comparator.</p>
402     *
403     * @param obj the reference object with which to compare
404     * @return true if this object is equal
405     */
406    @Override
407    public boolean equals(final Object obj) {
408        if (obj == this) {
409            return true;
410        } else if (obj == null || obj.getClass() != getClass()) {
411            return false;
412        } else {
413            @SuppressWarnings("unchecked") // OK because we checked the class above
414            final
415            Range<T> range = (Range<T>) obj;
416            return minimum.equals(range.minimum) &&
417                   maximum.equals(range.maximum);
418        }
419    }
420
421    /**
422     * <p>Gets a suitable hash code for the range.</p>
423     *
424     * @return a hash code value for this object
425     */
426    @Override
427    public int hashCode() {
428        int result = hashCode;
429        if (hashCode == 0) {
430            result = 17;
431            result = 37 * result + getClass().hashCode();
432            result = 37 * result + minimum.hashCode();
433            result = 37 * result + maximum.hashCode();
434            hashCode = result;
435        }
436        return result;
437    }
438
439    /**
440     * <p>Gets the range as a {@code String}.</p>
441     *
442     * <p>The format of the String is '[<i>min</i>..<i>max</i>]'.</p>
443     *
444     * @return the {@code String} representation of this range
445     */
446    @Override
447    public String toString() {
448        String result = toString;
449        if (result == null) {
450            final StringBuilder buf = new StringBuilder(32);
451            buf.append('[');
452            buf.append(minimum);
453            buf.append("..");
454            buf.append(maximum);
455            buf.append(']');
456            result = buf.toString();
457            toString = result;
458        }
459        return result;
460    }
461
462    /**
463     * <p>Formats the receiver using the given format.</p>
464     * 
465     * <p>This uses {@link java.util.Formattable} to perform the formatting. Three variables may
466     * be used to embed the minimum, maximum and comparator.
467     * Use {@code %1$s} for the minimum element, {@code %2$s} for the maximum element
468     * and {@code %3$s} for the comparator.
469     * The default format used by {@code toString()} is {@code [%1$s..%2$s]}.</p>
470     * 
471     * @param format  the format string, optionally containing {@code %1$s}, {@code %2$s} and  {@code %3$s}, not null
472     * @return the formatted string, not null
473     */
474    public String toString(final String format) {
475        return String.format(format, minimum, maximum, comparator);
476    }
477
478    //-----------------------------------------------------------------------
479    @SuppressWarnings({"rawtypes", "unchecked"})
480    private enum ComparableComparator implements Comparator {
481        INSTANCE;
482        /**
483         * Comparable based compare implementation. 
484         *
485         * @param obj1 left hand side of comparison
486         * @param obj2 right hand side of comparison
487         * @return negative, 0, positive comparison value
488         */
489        @Override
490        public int compare(final Object obj1, final Object obj2) {
491            return ((Comparable) obj1).compareTo(obj2);
492        }
493    }
494
495}