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 1565243 2014-02-06 13:37:12Z sebb $
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 comp  the comparator to be used, null for natural ordering
144     */
145    @SuppressWarnings("unchecked")
146    private Range(final T element1, final T element2, final Comparator<T> comp) {
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 (comp == null) {
152            this.comparator = ComparableComparator.INSTANCE;
153        } else {
154            this.comparator = comp;            
155        }
156        if (this.comparator.compare(element1, element2) < 1) {
157            this.minimum = element1;
158            this.maximum = element2;
159        } else {
160            this.minimum = element2;
161            this.maximum = element1;
162        }
163    }
164
165    // Accessors
166    //--------------------------------------------------------------------
167
168    /**
169     * <p>Gets the minimum value in this range.</p>
170     *
171     * @return the minimum value in this range, not null
172     */
173    public T getMinimum() {
174        return minimum;
175    }
176
177    /**
178     * <p>Gets the maximum value in this range.</p>
179     *
180     * @return the maximum value in this range, not null
181     */
182    public T getMaximum() {
183        return maximum;
184    }
185
186    /**
187     * <p>Gets the comparator being used to determine if objects are within the range.</p>
188     * 
189     * <p>Natural ordering uses an internal comparator implementation, thus this
190     * method never returns null. See {@link #isNaturalOrdering()}.</p>
191     *
192     * @return the comparator being used, not null
193     */
194    public Comparator<T> getComparator() {
195        return comparator;
196    }
197
198    /**
199     * <p>Whether or not the Range is using the natural ordering of the elements.</p>
200     * 
201     * <p>Natural ordering uses an internal comparator implementation, thus this
202     * method is the only way to check if a null comparator was specified.</p>
203     *
204     * @return true if using natural ordering
205     */
206    public boolean isNaturalOrdering() {
207        return comparator == ComparableComparator.INSTANCE;
208    }
209
210    // Element tests
211    //--------------------------------------------------------------------
212
213    /**
214     * <p>Checks whether the specified element occurs within this range.</p>
215     *
216     * @param element  the element to check for, null returns false
217     * @return true if the specified element occurs within this range
218     */
219    public boolean contains(final T element) {
220        if (element == null) {
221            return false;
222        }
223        return comparator.compare(element, minimum) > -1 && comparator.compare(element, maximum) < 1;
224    }
225
226    /**
227     * <p>Checks whether this range is after the specified element.</p>
228     *
229     * @param element  the element to check for, null returns false
230     * @return true if this range is entirely after the specified element
231     */
232    public boolean isAfter(final T element) {
233        if (element == null) {
234            return false;
235        }
236        return comparator.compare(element, minimum) < 0;
237    }
238
239    /**
240     * <p>Checks whether this range starts with the specified element.</p>
241     *
242     * @param element  the element to check for, null returns false
243     * @return true if the specified element occurs within this range
244     */
245    public boolean isStartedBy(final T element) {
246        if (element == null) {
247            return false;
248        }
249        return comparator.compare(element, minimum) == 0;
250    }
251
252    /**
253     * <p>Checks whether this range starts with the specified element.</p>
254     *
255     * @param element  the element to check for, null returns false
256     * @return true if the specified element occurs within this range
257     */
258    public boolean isEndedBy(final T element) {
259        if (element == null) {
260            return false;
261        }
262        return comparator.compare(element, maximum) == 0;
263    }
264
265    /**
266     * <p>Checks whether this range is before the specified element.</p>
267     *
268     * @param element  the element to check for, null returns false
269     * @return true if this range is entirely before the specified element
270     */
271    public boolean isBefore(final T element) {
272        if (element == null) {
273            return false;
274        }
275        return comparator.compare(element, maximum) > 0;
276    }
277
278    /**
279     * <p>Checks where the specified element occurs relative to this range.</p>
280     * 
281     * <p>The API is reminiscent of the Comparable interface returning {@code -1} if
282     * the element is before the range, {@code 0} if contained within the range and
283     * {@code 1} if the element is after the range. </p>
284     *
285     * @param element  the element to check for, not null
286     * @return -1, 0 or +1 depending on the element's location relative to the range
287     */
288    public int elementCompareTo(final T element) {
289        if (element == null) {
290            // Comparable API says throw NPE on null
291            throw new NullPointerException("Element is null");
292        }
293        if (isAfter(element)) {
294            return -1;
295        } else if (isBefore(element)) {
296            return 1;
297        } else {
298            return 0;
299        }
300    }
301
302    // Range tests
303    //--------------------------------------------------------------------
304
305    /**
306     * <p>Checks whether this range contains all the elements of the specified range.</p>
307     *
308     * <p>This method may fail if the ranges have two different comparators or element types.</p>
309     *
310     * @param otherRange  the range to check, null returns false
311     * @return true if this range contains the specified range
312     * @throws RuntimeException if ranges cannot be compared
313     */
314    public boolean containsRange(final Range<T> otherRange) {
315        if (otherRange == null) {
316            return false;
317        }
318        return contains(otherRange.minimum)
319            && contains(otherRange.maximum);
320    }
321
322    /**
323     * <p>Checks whether this range is completely after the specified range.</p>
324     *
325     * <p>This method may fail if the ranges have two different comparators or element types.</p>
326     *
327     * @param otherRange  the range to check, null returns false
328     * @return true if this range is completely after the specified range
329     * @throws RuntimeException if ranges cannot be compared
330     */
331    public boolean isAfterRange(final Range<T> otherRange) {
332        if (otherRange == null) {
333            return false;
334        }
335        return isAfter(otherRange.maximum);
336    }
337
338    /**
339     * <p>Checks whether this range is overlapped by the specified range.</p>
340     * 
341     * <p>Two ranges overlap if there is at least one element in common.</p>
342     *
343     * <p>This method may fail if the ranges have two different comparators or element types.</p>
344     *
345     * @param otherRange  the range to test, null returns false
346     * @return true if the specified range overlaps with this
347     *  range; otherwise, {@code false}
348     * @throws RuntimeException if ranges cannot be compared
349     */
350    public boolean isOverlappedBy(final Range<T> otherRange) {
351        if (otherRange == null) {
352            return false;
353        }
354        return otherRange.contains(minimum)
355            || otherRange.contains(maximum)
356            || contains(otherRange.minimum);
357    }
358
359    /**
360     * <p>Checks whether this range is completely before the specified range.</p>
361     *
362     * <p>This method may fail if the ranges have two different comparators or element types.</p>
363     *
364     * @param otherRange  the range to check, null returns false
365     * @return true if this range is completely before the specified range
366     * @throws RuntimeException if ranges cannot be compared
367     */
368    public boolean isBeforeRange(final Range<T> otherRange) {
369        if (otherRange == null) {
370            return false;
371        }
372        return isBefore(otherRange.minimum);
373    }
374
375    /**
376     * Calculate the intersection of {@code this} and an overlapping Range.
377     * @param other overlapping Range
378     * @return range representing the intersection of {@code this} and {@code other} ({@code this} if equal)
379     * @throws IllegalArgumentException if {@code other} does not overlap {@code this}
380     * @since 3.0.1
381     */
382    public Range<T> intersectionWith(final Range<T> other) {
383        if (!this.isOverlappedBy(other)) {
384            throw new IllegalArgumentException(String.format(
385                "Cannot calculate intersection with non-overlapping range %s", other));
386        }
387        if (this.equals(other)) {
388            return this;
389        }
390        final T min = getComparator().compare(minimum, other.minimum) < 0 ? other.minimum : minimum;
391        final T max = getComparator().compare(maximum, other.maximum) < 0 ? maximum : other.maximum;
392        return between(min, max, getComparator());
393    }
394
395    // Basics
396    //--------------------------------------------------------------------
397
398    /**
399     * <p>Compares this range to another object to test if they are equal.</p>.
400     *
401     * <p>To be equal, the minimum and maximum values must be equal, which
402     * ignores any differences in the comparator.</p>
403     *
404     * @param obj the reference object with which to compare
405     * @return true if this object is equal
406     */
407    @Override
408    public boolean equals(final Object obj) {
409        if (obj == this) {
410            return true;
411        } else if (obj == null || obj.getClass() != getClass()) {
412            return false;
413        } else {
414            @SuppressWarnings("unchecked") // OK because we checked the class above
415            final
416            Range<T> range = (Range<T>) obj;
417            return minimum.equals(range.minimum) &&
418                   maximum.equals(range.maximum);
419        }
420    }
421
422    /**
423     * <p>Gets a suitable hash code for the range.</p>
424     *
425     * @return a hash code value for this object
426     */
427    @Override
428    public int hashCode() {
429        int result = hashCode;
430        if (hashCode == 0) {
431            result = 17;
432            result = 37 * result + getClass().hashCode();
433            result = 37 * result + minimum.hashCode();
434            result = 37 * result + maximum.hashCode();
435            hashCode = result;
436        }
437        return result;
438    }
439
440    /**
441     * <p>Gets the range as a {@code String}.</p>
442     *
443     * <p>The format of the String is '[<i>min</i>..<i>max</i>]'.</p>
444     *
445     * @return the {@code String} representation of this range
446     */
447    @Override
448    public String toString() {
449        String result = toString;
450        if (result == null) {
451            final StringBuilder buf = new StringBuilder(32);
452            buf.append('[');
453            buf.append(minimum);
454            buf.append("..");
455            buf.append(maximum);
456            buf.append(']');
457            result = buf.toString();
458            toString = result;
459        }
460        return result;
461    }
462
463    /**
464     * <p>Formats the receiver using the given format.</p>
465     * 
466     * <p>This uses {@link java.util.Formattable} to perform the formatting. Three variables may
467     * be used to embed the minimum, maximum and comparator.
468     * Use {@code %1$s} for the minimum element, {@code %2$s} for the maximum element
469     * and {@code %3$s} for the comparator.
470     * The default format used by {@code toString()} is {@code [%1$s..%2$s]}.</p>
471     * 
472     * @param format  the format string, optionally containing {@code %1$s}, {@code %2$s} and  {@code %3$s}, not null
473     * @return the formatted string, not null
474     */
475    public String toString(final String format) {
476        return String.format(format, minimum, maximum, comparator);
477    }
478
479    //-----------------------------------------------------------------------
480    @SuppressWarnings({"rawtypes", "unchecked"})
481    private enum ComparableComparator implements Comparator {
482        INSTANCE;
483        /**
484         * Comparable based compare implementation. 
485         *
486         * @param obj1 left hand side of comparison
487         * @param obj2 right hand side of comparison
488         * @return negative, 0, positive comparison value
489         */
490        @Override
491        public int compare(final Object obj1, final Object obj2) {
492            return ((Comparable) obj1).compareTo(obj2);
493        }
494    }
495
496}