/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.lang3;

import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.Serializable;
import java.util.Comparator;
import java.util.Objects;

/**
 * An immutable range of objects from a minimum to maximum point inclusive.
 *
 * <p>
 * The objects need to either be implementations of {@link Comparable}
 * or you need to supply a {@link Comparator}.
 * </p>
 *
 * <p>
 * #ThreadSafe# if the objects and comparator are thread-safe.
 * </p>
 *
 * @param <T> The type of range values.
 * @since 3.0
 */
public class Range<T> implements Serializable {

    @SuppressWarnings({"rawtypes", "unchecked"})
    private enum ComparableComparator implements Comparator {
        INSTANCE;

        /**
         * Comparable based compare implementation.
         *
         * @param obj1 left-hand side of comparison.
         * @param obj2 right-hand side of comparison.
         * @return negative, 0, positive comparison value.
         */
        @Override
        public int compare(final Object obj1, final Object obj2) {
            return ((Comparable) obj1).compareTo(obj2);
        }
    }

    /**
     * Serialization version.
     *
     * @see java.io.Serializable
     */
    private static final long serialVersionUID = 1L;

    /**
     * Creates a range with the specified minimum and maximum values (both inclusive).
     *
     * <p>
     * The range uses the natural ordering of the elements to determine where
     * values lie in the range.
     * </p>
     *
     * <p>
     * The arguments may be passed in the order (min, max) or (max, min).
     * The getMinimum and getMaximum methods will return the correct values.
     * </p>
     *
     * @param <T> The type of the elements in this range.
     * @param fromInclusive  The first value that defines the edge of the range, inclusive.
     * @param toInclusive  The second value that defines the edge of the range, inclusive.
     * @return The range object, not null.
     * @throws NullPointerException Thrown when fromInclusive is null.
     * @throws NullPointerException Thrown when toInclusive is null.
     * @throws ClassCastException Thrown if the elements are not {@link Comparable}.
     * @throws IllegalArgumentException Thrown if either element is a floating-point NaN.
     * @deprecated Use {@link #of(Comparable, Comparable)}.
     */
    @Deprecated
    public static <T extends Comparable<? super T>> Range<T> between(final T fromInclusive, final T toInclusive) {
        return of(fromInclusive, toInclusive, null);
    }

    /**
     * Creates a range with the specified minimum and maximum values (both inclusive).
     *
     * <p>
     * The range uses the specified {@link Comparator} to determine where
     * values lie in the range.
     * </p>
     *
     * <p>
     * The arguments may be passed in the order (min, max) or (max, min).
     * The getMinimum and getMaximum methods will return the correct values.
     * </p>
     *
     * @param <T> The type of the elements in this range.
     * @param fromInclusive  The first value that defines the edge of the range, inclusive.
     * @param toInclusive  The second value that defines the edge of the range, inclusive.
     * @param comparator  The comparator to be used, null for natural ordering.
     * @return The range object, not null.
     * @throws NullPointerException Thrown when fromInclusive is null.
     * @throws NullPointerException Thrown when toInclusive is null.
     * @throws ClassCastException Thrown if using natural ordering and the elements are not {@link Comparable}.
     * @throws IllegalArgumentException Thrown if either element is a floating-point NaN.
     * @deprecated Use {@link #of(Object, Object, Comparator)}.
     */
    @Deprecated
    public static <T> Range<T> between(final T fromInclusive, final T toInclusive, final Comparator<T> comparator) {
        return new Range<>(fromInclusive, toInclusive, comparator);
    }

    private static int hash(final Object value1, final Object value2) {
        return Objects.hash(value1, value2);
    }

    /**
     * Creates a range using the specified element as both the minimum
     * and maximum in this range.
     *
     * <p>
     * The range uses the natural ordering of the elements to determine where
     * values lie in the range.
     * </p>
     *
     * @param <T> The type of the elements in this range.
     * @param element  The value to use for this range, not null.
     * @return The range object, not null.
     * @throws NullPointerException Thrown if the element is null.
     * @throws ClassCastException Thrown if the element is not {@link Comparable}.
     * @throws IllegalArgumentException Thrown if the element is a floating-point NaN.
     */
    public static <T extends Comparable<? super T>> Range<T> is(final T element) {
        return of(element, element, null);
    }

    /**
     * Creates a range using the specified element as both the minimum
     * and maximum in this range.
     *
     * <p>
     * The range uses the specified {@link Comparator} to determine where
     * values lie in the range.
     * </p>
     *
     * @param <T> The type of the elements in this range.
     * @param element  The value to use for this range, must not be {@code null}.
     * @param comparator  The comparator to be used, null for natural ordering.
     * @return The range object, not null.
     * @throws NullPointerException Thrown if the element is null.
     * @throws ClassCastException Thrown if using natural ordering and the elements are not {@link Comparable}.
     * @throws IllegalArgumentException Thrown if the element is a floating-point NaN.
     */
    public static <T> Range<T> is(final T element, final Comparator<T> comparator) {
        return of(element, element, comparator);
    }

    /**
     * Tests whether the element is a floating-point NaN. A NaN endpoint sorts above every value under the natural
     * total order ({@link Double#compareTo(Double)} / {@link Float#compareTo(Float)}), silently producing a
     * half-unbounded range whose {@code contains}/{@code fit} accept every value above the minimum.
     *
     * @param element The element to test, may be null.
     * @return Whether the element is a floating-point NaN.
     */
    private static boolean isNaN(final Object element) {
        return element instanceof Double && ((Double) element).isNaN()
                || element instanceof Float && ((Float) element).isNaN();
    }

    /**
     * Creates a range with the specified minimum and maximum values (both inclusive).
     *
     * <p>
     * The range uses the natural ordering of the elements to determine where
     * values lie in the range.
     * </p>
     *
     * <p>
     * The arguments may be passed in the order (min, max) or (max, min).
     * The getMinimum and getMaximum methods will return the correct values.
     * </p>
     *
     * @param <T> The type of the elements in this range.
     * @param fromInclusive  The first value that defines the edge of the range, inclusive.
     * @param toInclusive  The second value that defines the edge of the range, inclusive.
     * @return The range object, not null.
     * @throws NullPointerException Thrown if either element is null.
     * @throws ClassCastException Thrown if the elements are not {@link Comparable}.
     * @throws IllegalArgumentException Thrown if either element is a floating-point NaN.
     * @since 3.13.0
     */
    public static <T extends Comparable<? super T>> Range<T> of(final T fromInclusive, final T toInclusive) {
        return of(fromInclusive, toInclusive, null);
    }

    /**
     * Creates a range with the specified minimum and maximum values (both inclusive).
     *
     * <p>
     * The range uses the specified {@link Comparator} to determine where
     * values lie in the range.
     * </p>
     *
     * <p>
     * The arguments may be passed in the order (min, max) or (max, min).
     * The getMinimum and getMaximum methods will return the correct values.
     * </p>
     *
     * @param <T> The type of the elements in this range.
     * @param fromInclusive  The first value that defines the edge of the range, inclusive.
     * @param toInclusive  The second value that defines the edge of the range, inclusive.
     * @param comparator  The comparator to be used, null for natural ordering.
     * @return The range object, not null.
     * @throws NullPointerException Thrown when fromInclusive is null.
     * @throws NullPointerException Thrown when toInclusive is null.
     * @throws ClassCastException Thrown if using natural ordering and the elements are not {@link Comparable}.
     * @throws IllegalArgumentException Thrown if either element is a floating-point NaN.
     * @since 3.13.0
     */
    public static <T> Range<T> of(final T fromInclusive, final T toInclusive, final Comparator<T> comparator) {
        return new Range<>(fromInclusive, toInclusive, comparator);
    }

    /**
     * Validates that a floating-point endpoint is not NaN, mirroring the fail-closed posture of
     * {@link Validate#notNaN(double, String, Object...)}.
     *
     * @param element The endpoint to validate.
     * @param name The parameter name for the exception message.
     * @throws IllegalArgumentException Thrown if the endpoint is a floating-point NaN.
     */
    private static void requireNotNaN(final Object element, final String name) {
        if (isNaN(element)) {
            throw new IllegalArgumentException(name + " must not be NaN");
        }
    }

    /**
     * The ordering scheme used in this range.
     */
    private final Comparator<T> comparator;

    /**
     * Cached output hashCode (class is immutable).
     */
    private transient int hashCode;

    /**
     * The maximum value in this range (inclusive).
     */
    private final T maximum;

    /**
     * The minimum value in this range (inclusive).
     */
    private final T minimum;

    /**
     * Cached output toString (class is immutable).
     */
    private transient String toString;

    /**
     * Creates an instance.
     *
     * @param element1  The first element, not null.
     * @param element2  The second element, not null
     * @param comp  The comparator to be used, null for natural ordering.
     * @throws NullPointerException Thrown when element1 is null.
     * @throws NullPointerException Thrown when element2 is null.
     * @throws IllegalArgumentException Thrown when element1 or element2 is a floating-point NaN.
     */
    @SuppressWarnings("unchecked")
    Range(final T element1, final T element2, final Comparator<T> comp) {
        Objects.requireNonNull(element1, "element1");
        Objects.requireNonNull(element2, "element2");
        requireNotNaN(element1, "element1");
        requireNotNaN(element2, "element2");
        if (comp == null) {
            this.comparator = ComparableComparator.INSTANCE;
        } else {
            this.comparator = comp;
        }
        if (this.comparator.compare(element1, element2) < 1) {
            this.minimum = element1;
            this.maximum = element2;
        } else {
            this.minimum = element2;
            this.maximum = element1;
        }
        this.hashCode = hash(minimum, maximum);
    }

    /**
     * Checks whether the specified element occurs within this range.
     *
     * @param element  The element to check for, null returns false.
     * @return true if the specified element occurs within this range.
     */
    public boolean contains(final T element) {
        if (element == null) {
            return false;
        }
        return comparator.compare(element, minimum) > -1 && comparator.compare(element, maximum) < 1;
    }

    /**
     * Checks whether this range contains all the elements of the specified range.
     *
     * <p>
     * This method may fail if the ranges have two different comparators or element types.
     * </p>
     *
     * @param otherRange  The range to check, null returns false.
     * @return true if this range contains the specified range.
     * @throws RuntimeException Thrown if ranges cannot be compared.
     */
    public boolean containsRange(final Range<T> otherRange) {
        if (otherRange == null) {
            return false;
        }
        return contains(otherRange.minimum)
            && contains(otherRange.maximum);
    }

    /**
     * Checks where the specified element occurs relative to this range.
     *
     * <p>
     * The API is reminiscent of the Comparable interface returning {@code -1} if
     * the element is before the range, {@code 0} if contained within the range and
     * {@code 1} if the element is after the range.
     * </p>
     *
     * @param element  The element to check for, not null.
     * @return -1, 0 or +1 depending on the element's location relative to the range.
     * @throws NullPointerException Thrown if {@code element} is {@code null}.
     */
    public int elementCompareTo(final T element) {
        // Comparable API says throw NPE on null
        Objects.requireNonNull(element, "element");
        if (isAfter(element)) {
            return -1;
        }
        if (isBefore(element)) {
            return 1;
        }
        return 0;
    }

    /**
     * Compares this range to another object to test if they are equal.
     *
     * <p>
     * To be equal, the minimum and maximum values must be equal, which
     * ignores any differences in the comparator.
     * </p>
     *
     * @param obj The reference object with which to compare.
     * @return true if this object is equal.
     */
    @Override
    public boolean equals(final Object obj) {
        if (obj == this) {
            return true;
        }
        if (obj == null || obj.getClass() != getClass()) {
            return false;
        }
        @SuppressWarnings("unchecked") // OK because we checked the class above
        final
        Range<T> range = (Range<T>) obj;
        return minimum.equals(range.minimum) &&
               maximum.equals(range.maximum);
    }

    /**
     * Fits the given element into this range by returning the given element or, if out of bounds, the range minimum if
     * below, or the range maximum if above.
     *
     * <pre>{@code
     * Range<Integer> range = Range.between(16, 64);
     * range.fit(-9) -->  16
     * range.fit(0)  -->  16
     * range.fit(15) -->  16
     * range.fit(16) -->  16
     * range.fit(17) -->  17
     * ...
     * range.fit(63) -->  63
     * range.fit(64) -->  64
     * range.fit(99) -->  64
     * }</pre>
     *
     * @param element The element to check for, not null.
     * @return The minimum, the element, or the maximum depending on the element's location relative to the range.
     * @throws NullPointerException Thrown if {@code element} is {@code null}.
     * @since 3.10
     */
    public T fit(final T element) {
        // Comparable API says throw NPE on null
        Objects.requireNonNull(element, "element");
        if (isAfter(element)) {
            return minimum;
        }
        if (isBefore(element)) {
            return maximum;
        }
        return element;
    }

    /**
     * Gets the comparator being used to determine if objects are within the range.
     *
     * <p>
     * Natural ordering uses an internal comparator implementation, thus this
     * method never returns null. See {@link #isNaturalOrdering()}.
     * </p>
     *
     * @return The comparator being used, not null.
     */
    public Comparator<T> getComparator() {
        return comparator;
    }

    /**
     * Gets the maximum value in this range.
     *
     * @return The maximum value in this range, not null.
     */
    public T getMaximum() {
        return maximum;
    }

    /**
     * Gets the minimum value in this range.
     *
     * @return The minimum value in this range, not null.
     */
    public T getMinimum() {
        return minimum;
    }

    /**
     * Gets a suitable hash code for the range.
     *
     * @return A hash code value for this object.
     */
    @Override
    public int hashCode() {
        return hashCode;
    }

    /**
     * Calculate the intersection of {@code this} and an overlapping Range.
     *
     * @param other overlapping Range.
     * @return range representing the intersection of {@code this} and {@code other} ({@code this} if equal).
     * @throws IllegalArgumentException Thrown if {@code other} does not overlap {@code this}.
     * @since 3.0.1
     */
    public Range<T> intersectionWith(final Range<T> other) {
        if (!this.isOverlappedBy(other)) {
            throw new IllegalArgumentException(String.format(
                "Cannot calculate intersection with non-overlapping range %s", other));
        }
        if (this.equals(other)) {
            return this;
        }
        final T min = getComparator().compare(minimum, other.minimum) < 0 ? other.minimum : minimum;
        final T max = getComparator().compare(maximum, other.maximum) < 0 ? maximum : other.maximum;
        return of(min, max, getComparator());
    }

    /**
     * Tests whether this range is after the specified element.
     *
     * @param element  The element to check for, null returns false.
     * @return true if this range is entirely after the specified element.
     */
    public boolean isAfter(final T element) {
        if (element == null) {
            return false;
        }
        return comparator.compare(element, minimum) < 0;
    }

    /**
     * Tests whether this range is completely after the specified range.
     *
     * <p>
     * This method may fail if the ranges have two different comparators or element types.
     * </p>
     *
     * @param otherRange  The range to check, null returns false.
     * @return true if this range is completely after the specified range.
     * @throws RuntimeException Thrown if ranges cannot be compared.
     */
    public boolean isAfterRange(final Range<T> otherRange) {
        if (otherRange == null) {
            return false;
        }
        return isAfter(otherRange.maximum);
    }

    /**
     * Tests whether this range is before the specified element.
     *
     * @param element  The element to check for, null returns false.
     * @return true if this range is entirely before the specified element.
     */
    public boolean isBefore(final T element) {
        if (element == null) {
            return false;
        }
        return comparator.compare(element, maximum) > 0;
    }

    /**
     * Tests whether this range is completely before the specified range.
     *
     * <p>
     * This method may fail if the ranges have two different comparators or element types.
     * </p>
     *
     * @param otherRange  The range to check, null returns false.
     * @return true if this range is completely before the specified range.
     * @throws RuntimeException Thrown if ranges cannot be compared.
     */
    public boolean isBeforeRange(final Range<T> otherRange) {
        if (otherRange == null) {
            return false;
        }
        return isBefore(otherRange.minimum);
    }

    /**
     * Tests whether this range ends with the specified element.
     *
     * @param element  The element to check for, null returns false.
     * @return true if the specified element occurs within this range.
     */
    public boolean isEndedBy(final T element) {
        if (element == null) {
            return false;
        }
        return comparator.compare(element, maximum) == 0;
    }

    /**
     * Tests whether or not the Range is using the natural ordering of the elements.
     *
     * <p>
     * Natural ordering uses an internal comparator implementation, thus this
     * method is the only way to check if a null comparator was specified.
     * </p>
     *
     * @return true if using natural ordering.
     */
    public boolean isNaturalOrdering() {
        return comparator == ComparableComparator.INSTANCE;
    }

    /**
     * Tests whether this range is overlapped by the specified range.
     *
     * <p>
     * Two ranges overlap if there is at least one element in common.
     * </p>
     *
     * <p>
     * This method may fail if the ranges have two different comparators or element types.
     * </p>
     *
     * @param otherRange  The range to test, null returns false.
     * @return true if the specified range overlaps with this
     *  range; otherwise, {@code false}.
     * @throws RuntimeException Thrown if ranges cannot be compared.
     */
    public boolean isOverlappedBy(final Range<T> otherRange) {
        if (otherRange == null) {
            return false;
        }
        return otherRange.contains(minimum)
            || otherRange.contains(maximum)
            || contains(otherRange.minimum);
    }

    /**
     * Tests whether this range starts with the specified element.
     *
     * @param element  The element to check for, null returns false.
     * @return true if the specified element occurs within this range.
     */
    public boolean isStartedBy(final T element) {
        if (element == null) {
            return false;
        }
        return comparator.compare(element, minimum) == 0;
    }

    /**
     * Validates the endpoints and comparator and recomputes the cached hash code after deserialization.
     *
     * @param in See {@link Serializable}.
     * @throws IOException Thrown as described in {@link Serializable}.
     * @throws ClassNotFoundException Thrown as described in {@link Serializable}.
     * @throws InvalidObjectException Thrown if the endpoints or comparator violate the range invariants.
     */
    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        SerializationUtils.requireNonNull(maximum, "maximum null");
        SerializationUtils.requireNonNull(minimum, "minimum null");
        SerializationUtils.requireNonNull(comparator, "comparator null");
        // Mirror the constructor's NaN endpoint rejection: a crafted stream cannot smuggle in the degenerate
        // half-unbounded range that construction refuses.
        if (isNaN(minimum) || isNaN(maximum)) {
            throw new InvalidObjectException("Range minimum/maximum must not be NaN.");
        }
        if (comparator.compare(minimum, maximum) > 0) {
            throw new InvalidObjectException("Range minimum is greater than maximum under the comparator.");
        }
        hashCode = hash(minimum, maximum);
    }

    /**
     * Gets the range as a {@link String}.
     *
     * <p>
     * The format of the String is '[<em>min</em>..<em>max</em>]'.
     * </p>
     *
     * @return The {@link String} representation of this range.
     */
    @Override
    public String toString() {
        if (toString == null) {
            toString = "[" + minimum + ".." + maximum + "]";
        }
        return toString;
    }

    /**
     * Formats the receiver using the given format.
     *
     * <p>
     * This uses {@link java.util.Formattable} to perform the formatting. Three variables may
     * be used to embed the minimum, maximum and comparator.
     * Use {@code %1$s} for the minimum element, {@code %2$s} for the maximum element
     * and {@code %3$s} for the comparator.
     * The default format used by {@code toString()} is {@code [%1$s..%2$s]}.
     * </p>
     *
     * @param format  The format string, optionally containing {@code %1$s}, {@code %2$s} and  {@code %3$s}, not null.
     * @return The formatted string, not null.
     */
    public String toString(final String format) {
        return String.format(format, minimum, maximum, comparator);
    }

}