Interval.java

/*
 * 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
 *
 *      http://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.geometry.euclidean.oned;

import java.text.MessageFormat;

import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.numbers.core.Precision;

/** Class representing an interval in one dimension. The interval is defined
 * by minimum and maximum values. One or both of these values may be infinite
 * although not with the same sign.
 *
 * <p>Instances of this class are guaranteed to be immutable.</p>
 */
public final class Interval implements HyperplaneBoundedRegion<Vector1D> {
    /** Interval instance representing the entire real number line. */
    private static final Interval FULL = new Interval(null, null);

    /** {@link OrientedPoint} instance representing the min boundary of the interval,
     * or null if no min boundary exists. If present, this instance will be negative-facing.
     * Infinite values are allowed but not NaN.
     */
    private final OrientedPoint minBoundary;

    /** {@link OrientedPoint} instance representing the max boundary of the interval,
     * or null if no max boundary exists. If present, this instance will be negative-facing.
     * Infinite values are allowed but not NaN.
     */
    private final OrientedPoint maxBoundary;

    /** Create an instance from min and max bounding hyperplanes. No validation is performed.
     * Callers are responsible for ensuring that the given hyperplanes represent a valid
     * interval.
     * @param minBoundary the min (negative-facing) hyperplane
     * @param maxBoundary the max (positive-facing) hyperplane
     */
    private Interval(final OrientedPoint minBoundary, final OrientedPoint maxBoundary) {
        this.minBoundary = minBoundary;
        this.maxBoundary = maxBoundary;
    }

    /** Get the minimum value for the interval or {@link Double#NEGATIVE_INFINITY}
     * if no minimum value exists.
     * @return the minimum value for the interval or {@link Double#NEGATIVE_INFINITY}
     *      if no minimum value exists.
     */
    public double getMin() {
        return (minBoundary != null) ? minBoundary.getLocation() : Double.NEGATIVE_INFINITY;
    }

    /** Get the maximum value for the interval or {@link Double#POSITIVE_INFINITY}
     * if no maximum value exists.
     * @return the maximum value for the interval or {@link Double#POSITIVE_INFINITY}
     *      if no maximum value exists.
     */
    public double getMax() {
        return (maxBoundary != null) ? maxBoundary.getLocation() : Double.POSITIVE_INFINITY;
    }

    /**
     * Get the {@link OrientedPoint} forming the minimum bounding hyperplane
     * of the interval, or null if none exists. If present, This hyperplane
     * is oriented to point in the negative direction.
     * @return the hyperplane forming the minimum boundary of the interval or
     *      null if no minimum boundary exists
     */
    public OrientedPoint getMinBoundary() {
        return minBoundary;
    }

    /**
     * Get the {@link OrientedPoint} forming the maximum bounding hyperplane
     * of the interval, or null if none exists. If present, this hyperplane
     * is oriented to point in the positive direction.
     * @return the hyperplane forming the maximum boundary of the interval or
     *      null if no maximum boundary exists
     */
    public OrientedPoint getMaxBoundary() {
        return maxBoundary;
    }

    /** Return true if the interval has a minimum (lower) boundary.
     * @return true if the interval has minimum (lower) boundary
     */
    public boolean hasMinBoundary() {
        return minBoundary != null;
    }

    /** Return true if the interval has a maximum (upper) boundary.
     * @return true if the interval has maximum (upper) boundary
     */
    public boolean hasMaxBoundary() {
        return maxBoundary != null;
    }

    /** True if the region is infinite, meaning that at least one of the boundaries
     * does not exist.
     * @return true if the region is infinite
     */
    @Override
    public boolean isInfinite() {
        return minBoundary == null || maxBoundary == null;
    }

    /** True if the region is finite, meaning that both the minimum and maximum
     * boundaries exist and the region size is finite.
     * @return true if the region is finite
     */
    @Override
    public boolean isFinite() {
        return !isInfinite();
    }

    /** {@inheritDoc} */
    @Override
    public RegionLocation classify(final Vector1D pt) {
        return classify(pt.getX());
    }

    /** Classify a point with respect to the interval.
     * @param location the location to classify
     * @return the classification of the point with respect to the interval
     * @see #classify(Vector1D)
     */
    public RegionLocation classify(final double location) {
        final RegionLocation minLoc = classifyWithBoundary(location, minBoundary);
        final RegionLocation maxLoc = classifyWithBoundary(location, maxBoundary);

        if (minLoc == RegionLocation.BOUNDARY || maxLoc == RegionLocation.BOUNDARY) {
            return RegionLocation.BOUNDARY;
        } else if (minLoc == RegionLocation.INSIDE && maxLoc == RegionLocation.INSIDE) {
            return RegionLocation.INSIDE;
        }
        return RegionLocation.OUTSIDE;
    }

    /** Classify the location using the given interval boundary, which may be null.
     * @param location the location to classify
     * @param boundary interval boundary to classify against
     * @return the location of the point relative to the boundary
     */
    private RegionLocation classifyWithBoundary(final double location, final OrientedPoint boundary) {
        if (Double.isNaN(location)) {
            return RegionLocation.OUTSIDE;
        } else if (boundary == null) {
            return RegionLocation.INSIDE;
        } else {
            final HyperplaneLocation hyperLoc = boundary.classify(location);

            if (hyperLoc == HyperplaneLocation.ON) {
                return RegionLocation.BOUNDARY;
            } else if (hyperLoc == HyperplaneLocation.PLUS) {
                return RegionLocation.OUTSIDE;
            }
            return RegionLocation.INSIDE;
        }
    }

    /** Return true if the given point location is on the inside or boundary
     * of the region.
     * @param x the location to test
     * @return true if the location is on the inside or boundary of the region
     * @see #contains(org.apache.commons.geometry.core.Point)
     */
    public boolean contains(final double x) {
        return classify(x) != RegionLocation.OUTSIDE;
    }

    /** {@inheritDoc}
     *
     * <p>The point is projected onto the nearest interval boundary. When a point
     * is on the inside of the interval and is equidistant from both boundaries,
     * then the minimum boundary is selected. when a point is on the outside of the
     * interval and is equidistant from both boundaries (as is the case for intervals
     * representing a single point), then the boundary facing the point is returned,
     * ensuring that the returned offset is positive.
     * </p>
     */
    @Override
    public Vector1D project(final Vector1D pt) {

        OrientedPoint boundary = null;

        if (minBoundary != null && maxBoundary != null) {
            // both boundaries are present; use the closest
            final double minOffset = minBoundary.offset(pt.getX());
            final double maxOffset = maxBoundary.offset(pt.getX());

            final double minDist = Math.abs(minOffset);
            final double maxDist = Math.abs(maxOffset);

            // Project onto the max boundary if it's the closest or the point is on its plus side.
            // Otherwise, project onto the min boundary.
            if (maxDist < minDist || maxOffset > 0) {
                boundary = maxBoundary;
            } else {
                boundary = minBoundary;
            }
        } else if (minBoundary != null) {
            // only the min boundary is present
            boundary = minBoundary;
        } else if (maxBoundary != null) {
            // only the max boundary is present
            boundary = maxBoundary;
        }

        return (boundary != null) ? boundary.project(pt) : null;
    }

    /** Return a new instance transformed by the argument.
     * @param transform transform to apply
     * @return a new instance transformed by the argument
     */
    public Interval transform(final Transform<Vector1D> transform) {
        final OrientedPoint transformedMin = (minBoundary != null) ?
                minBoundary.transform(transform) :
                null;
        final OrientedPoint transformedMax = (maxBoundary != null) ?
                maxBoundary.transform(transform) :
                null;

        return of(transformedMin, transformedMax);
    }

    /** {@inheritDoc}
     *
     *  <p>This method always returns false since there is always at least
     *  one point that can be classified as not being on the outside of
     *  the region.</p>
     */
    @Override
    public boolean isEmpty() {
        return false;
    }

    /** {@inheritDoc} */
    @Override
    public boolean isFull() {
        return minBoundary == null && maxBoundary == null;
    }

    /** {@inheritDoc} */
    @Override
    public double getSize() {
        if (isInfinite()) {
            return Double.POSITIVE_INFINITY;
        }

        return getMax() - getMin();
    }

    /** {@inheritDoc}
     *
     *  <p>This method simply returns 0 because boundaries in one dimension do not
     *  have any size.</p>
     */
    @Override
    public double getBoundarySize() {
        return 0;
    }

    /** {@inheritDoc} */
    @Override
    public Vector1D getCentroid() {
        if (isInfinite()) {
            return null;
        }

        final double min = getMin();
        final double max = getMax();

        return Vector1D.of((0.5 * (max - min)) + min);
    }

    /** {@inheritDoc} */
    @Override
    public Split<Interval> split(final Hyperplane<Vector1D> splitter) {
        final OrientedPoint splitOrientedPoint = (OrientedPoint) splitter;
        final Vector1D splitPoint = splitOrientedPoint.getPoint();

        final HyperplaneLocation splitterMinLoc = (minBoundary != null) ? minBoundary.classify(splitPoint) : null;
        final HyperplaneLocation splitterMaxLoc = (maxBoundary != null) ? maxBoundary.classify(splitPoint) : null;

        Interval low = null;
        Interval high = null;

        if (splitterMinLoc != HyperplaneLocation.ON || splitterMaxLoc != HyperplaneLocation.ON) {

            if (splitterMinLoc != null && splitterMinLoc != HyperplaneLocation.MINUS) {
                // splitter is on or below min boundary
                high = this;
            } else if (splitterMaxLoc != null && splitterMaxLoc != HyperplaneLocation.MINUS) {
                // splitter is on or above max boundary
                low = this;
            } else {
                // the interval is split in two
                low = new Interval(minBoundary, OrientedPoints.createPositiveFacing(
                        splitPoint, splitOrientedPoint.getPrecision()));
                high = new Interval(OrientedPoints.createNegativeFacing(
                        splitPoint, splitOrientedPoint.getPrecision()), maxBoundary);
            }
        }

        // assign minus/plus based on the orientation of the splitter
        final boolean lowIsMinus = splitOrientedPoint.isPositiveFacing();
        final Interval minus = lowIsMinus ? low : high;
        final Interval plus = lowIsMinus ? high : low;

        return new Split<>(minus, plus);
    }

    /** Return a {@link RegionBSPTree1D} representing the same region as this instance.
     * @return a BSP tree representing the same region
     * @see RegionBSPTree1D#from(Interval, Interval...)
     */
    public RegionBSPTree1D toTree() {
        return RegionBSPTree1D.from(this);
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        sb.append(this.getClass().getSimpleName())
            .append("[min= ")
            .append(getMin())
            .append(", max= ")
            .append(getMax())
            .append(']');

        return sb.toString();
    }

    /** Create a new interval from the given point locations. The returned interval represents
     * the region between the points, regardless of the order they are given as arguments.
     * @param a first point location
     * @param b second point location
     * @param precision precision context used to compare floating point numbers
     * @return a new interval representing the region between the given point locations
     * @throws IllegalArgumentException if either number is {@link Double#NaN NaN} or the numbers
     *      are both infinite and have the same sign
     */
    public static Interval of(final double a, final double b, final Precision.DoubleEquivalence precision) {
        validateIntervalValues(a, b);

        final double min = Math.min(a, b);
        final double max = Math.max(a, b);

        final OrientedPoint minBoundary = Double.isFinite(min) ?
                OrientedPoints.fromLocationAndDirection(min, false, precision) :
                null;

        final OrientedPoint maxBoundary = Double.isFinite(max) ?
                OrientedPoints.fromLocationAndDirection(max, true, precision) :
                null;

        if (minBoundary == null && maxBoundary == null) {
            return FULL;
        }

        return new Interval(minBoundary, maxBoundary);
    }

    /** Create a new interval from the given points. The returned interval represents
     * the region between the points, regardless of the order they are given as arguments.
     * @param a first point
     * @param b second point
     * @param precision precision context used to compare floating point numbers
     * @return a new interval representing the region between the given points
     * @throws IllegalArgumentException if either point is {@link Vector1D#isNaN() NaN} or the points
     *      are both {@link Vector1D#isInfinite() infinite} and have the same sign
     */
    public static Interval of(final Vector1D a, final Vector1D b, final Precision.DoubleEquivalence precision) {
        return of(a.getX(), b.getX(), precision);
    }

    /** Create a new interval from the given hyperplanes. The hyperplanes may be given in
     * any order but one must be positive-facing and the other negative-facing, with the positive-facing
     * hyperplane located above the negative-facing hyperplane. Either or both argument may be null,
     * in which case the returned interval will extend to infinity in the appropriate direction. If both
     * arguments are null, an interval representing the full space is returned.
     * @param a first hyperplane; may be null
     * @param b second hyperplane; may be null
     * @return a new interval representing the region between the given hyperplanes
     * @throws IllegalArgumentException if the hyperplanes have the same orientation or
     *      do not form an interval (for example, if the positive-facing hyperplane is below
     *      the negative-facing hyperplane)
     */
    public static Interval of(final OrientedPoint a, final OrientedPoint b) {

        validateBoundaryRelationship(a, b);

        final boolean hasA = a != null;
        final boolean hasB = b != null;

        if (!hasA && !hasB) {
            // both boundaries null; return the full space
            return FULL;
        }

        // determine the ordering of the hyperplanes; we know that at least one is non-null
        final OrientedPoint minBoundary = ((hasA && !a.isPositiveFacing()) || (hasB && b.isPositiveFacing())) ? a : b;
        final OrientedPoint maxBoundary = ((hasA && a.isPositiveFacing()) || (hasB && !b.isPositiveFacing())) ? a : b;

        // validate the boundary locations; this will ensure that we don't have NaN values
        final double minLoc = (minBoundary != null) ? minBoundary.getLocation() : Double.NEGATIVE_INFINITY;
        final double maxLoc = (maxBoundary != null) ? maxBoundary.getLocation() : Double.POSITIVE_INFINITY;

        validateIntervalValues(minLoc, maxLoc);

        // create the interval, replacing infinites with nulls
        return new Interval(
                Double.isFinite(minLoc) ? minBoundary : null,
                Double.isFinite(maxLoc) ? maxBoundary : null);
    }

    /** Return an interval with the given min value and no max.
     * @param min min value for the interval
     * @param precision precision context used to compare floating point numbers
     * @return an interval with the given min value and no max.
     */
    public static Interval min(final double min, final Precision.DoubleEquivalence precision) {
        return of(min, Double.POSITIVE_INFINITY, precision);
    }

    /** Return an interval with the given max value and no min.
     * @param max max value for the interval
     * @param precision precision context used to compare floating point numbers
     * @return an interval with the given max value and no min.
     */
    public static Interval max(final double max, final Precision.DoubleEquivalence precision) {
        return of(Double.NEGATIVE_INFINITY, max, precision);
    }

    /** Return an interval representing a single point at the given location.
     * @param location the location of the interval
     * @param precision precision context used to compare floating point numbers
     * @return an interval representing a single point
     */
    public static Interval point(final double location, final Precision.DoubleEquivalence precision) {
        return of(location, location, precision);
    }

    /** Return an interval representing the entire real number line. The {@link #isFull()}
     * method of the instance will return true.
     * @return an interval representing the entire real number line
     * @see #isFull()
     */
    public static Interval full() {
        return FULL;
    }

    /** Validate that the orientations and positions of the arguments may be used to create an interval.
     * The arguments may be given in any order. Does nothing if one or both arguments are null.
     * @param a first boundary; may be null
     * @param b second boundary may be null
     * @throws IllegalArgumentException is {@code a} and {@code b} have the same orientation or one does
     *      not lie on the plus side of the other.
     */
    private static void validateBoundaryRelationship(final OrientedPoint a, final OrientedPoint b) {
        if (a != null && b != null) {
            if (a.isPositiveFacing() == b.isPositiveFacing()) {
                throw new IllegalArgumentException(
                        MessageFormat.format("Invalid interval: hyperplanes have same orientation: {0}, {1}", a, b));
            }

            if (a.classify(b.getPoint()) == HyperplaneLocation.PLUS ||
                    b.classify(a.getPoint()) == HyperplaneLocation.PLUS) {
                throw new IllegalArgumentException(
                        MessageFormat.format("Invalid interval: hyperplanes do not form interval: {0}, {1}", a, b));
            }
        }
    }

    /** Validate that the given value can be used to construct an interval. The values
     * must not be NaN and if infinite, must have opposite signs.
     * @param a first value
     * @param b second value
     * @throws IllegalArgumentException if either value is NaN or if both values are infinite
     *      and have the same sign
     */
    private static void validateIntervalValues(final double a, final double b) {
        if (Double.isNaN(a) || Double.isNaN(b) ||
                (Double.isInfinite(a) && Double.compare(a, b) == 0)) {

            throw new IllegalArgumentException(
                    MessageFormat.format("Invalid interval values: [{0}, {1}]", a, b));
        }
    }
}