// Time-stamp: <01/05/09 11:24:16 5duvigne>

package CH.ifa.draw.util;

import java.awt.Point;
import java.util.Vector;


/**
 * Calculates B-Splines and caches the computed results.
 * <p>
 * This class consists of two major parts:
 * <UL>
 * <LI>The static method {@link #calculateSpline} computes a
 *     B-Spline for a given vector of control points with
 *     specifiable degree and number of curve segments.
 *     </LI>
 * <LI>An instance of this class can be used to cache the
 *     computation results and automatically recompute them
 *     if changes are made to the vector of control points,
 *     degree or segment number.
 *     </LI>
 * </UL>
 * All calculations are carried out in double precision,
 * resulting in a vector of <code>DoublePoints</code>.
 * But the caching <code>BSpline</code> instance can also
 * be queried for a vector of integer <code>Points</code>.
 * <p>
 * BSpline.java
 * Created: Wed Nov  1  2000
 *
 * @author Friedrich Delgado Friedrichs, Lutz Kirsten, Klaus Mitreiter
 * {@link DoublePoint}
 * {@link Point}
 **/
public class BSpline {
    /**
     * Logger for the class BSpline.
     * Only a single logger instance exists at any given time. If a logger for BSpline
     * already exists it is returned or else a new instance is created.
     */
    public static final org.apache.log4j.Logger LOGGER =
        org.apache.log4j.Logger.getLogger(BSpline.class);

    /**
     * Default value to use for the number of segments.
     * Currently, 15.
     **/
    public final static int DEFSEGMENTS = 15;

    /**
     * Default value to use for the spline's degree.
     * Currently, 2.
     **/
    public final static int DEFDEGREE = 2;

    // -------------- instantiable part for result caching ----------------


    /**
     * Caches the last result of the point computation
     * as <code>DoublePoint</code> objects
     * (e.g. <code>double</code> values).
     **/
    private Vector<DoublePoint> _curvepoints = null;

    /**
     * Caches the last result of the point computation
     * as <code>Point</code> objects
     * (e.g. <code>int</code> values).
     **/
    private Vector<Point> _curvepointsInt = null;

    /**
     * Indicates whether the cached points in <code>curvepoints</code>
     * and <code>curvepointsInt</code> are still valid.
     **/
    private boolean _curvepointsValid = false;

    /**
     * The current list of control points as
     * <code>Point</code> objects.
     **/
    private Vector<Point> _controlpoints = null;

    /**
     * The number of subdivisions between two control points.
     **/
    private int _segments;

    /**
     * The degree of the B-Spline.
     **/
    private int _degree;

    /**
     * No-Arg-Constructor, not useful???
     **/
    public BSpline() {}

    /**
     * New B-Spline with 15 segments and degree of 2
     * @param points <code>Vector</code> of <code>Point</code>s
     */
    public BSpline(Vector<Point> points) {
        initBSpline(points, DEFSEGMENTS, DEFDEGREE);
    }

    /**
     * Constructs a new B-Spline with a default degree and a custom amount of segments.
     *
     * @param points <code>Vector</code> of <code>Points</code>
     * @param segments amount of segments for the new B-Spline
     */
    public BSpline(Vector<Point> points, int segments) {
        initBSpline(points, segments, DEFDEGREE);
    }

    /**
     * Constructs a new B-Spline with a custom degree, control points and segments.
     *
     * @param points <code>Vector</code> of <code>Points</code>
     * @param psegments amount of segments for the new B-Spline
     * @param pdegree degree of the new B-Spline
     */
    public BSpline(Vector<Point> points, int psegments, int pdegree) {
        initBSpline(points, psegments, pdegree);
    }

    private void initBSpline(Vector<Point> points, int psegments, int pdegree) {
        _segments = psegments;
        _degree = pdegree;
        setVector(points);
        invalidatePointCache();
    }

    /**
     * Sets the number of segments and invalidates the point cache if
     * the amount of segments changed.
     *
     * @param psegments the <code>int</code> representing the amount of segments
     */
    public void setSegments(int psegments) {
        if (_segments != psegments) {
            _segments = psegments;
            invalidatePointCache();
        }
    }

    /**
     * Sets the degree of the B-Spline and invalidates the point cache if the degree changed.
     *
     * @param pdegree the <code>int</code> representing the degree of the B-Spline
     */
    public void setDegree(int pdegree) {
        if (_degree != pdegree) {
            _degree = pdegree;
            invalidatePointCache();
        }
    }

    /**
     * Set the control points of the b-spline.
     *
     * @param points Vector of <code>Point</code> objects.
     * {@link Point}
     **/
    public void setPoints(Vector<Point> points) {
        // The following distinction addresses the
        // tradeoff between spline calculation and
        // vector comparison.
        // If the point cache is already invalid, we
        // can set the new control points without any
        // check (else-branch), but in the other case
        // we can save the spline calculation time if
        // the new point vector does not differ from
        // the old one. But the equality check takes
        // some time, too.
        if (isPointCacheValid()) {
            if (!theSame(points)) {
                setVector(points);
                invalidatePointCache();
            }
        } else {
            setVector(points);
        }
    }

    /**
     * Gets the amount of segments in the B-Spline.
     *
     * @return the amount of segments
     */
    public int getSegments() {
        return _segments;
    }

    /**
     * Gets the degree of the B-Spline.
     *
     * @return the degree of the B-Spline
     */
    public int getDegree() {
        return _degree;
    }

    /**
     * Calculates a b-spline and returns the curve points.
     *
     * @return Vector of <code>Point</code>
     * {@link Point}
     */
    public Vector<Point> getCurvepointsInt() {
        //NOTICERedundant
        updatePointCache();
        return _curvepointsInt;
    }

    /**
     * Calculates a b-spline and returns the curve points.
     *
     * @return Vector of <code>DoublePoint</code>
     * {@link DoublePoint}
     */
    public Vector<DoublePoint> getCurvepointsDouble() {
        //NOTICERedundant
        updatePointCache();
        return _curvepoints;
    }

    /**
     * Calculates the corresponding segment of a given index
     * by dividing the index by the total number of segments.
     *
     * @param i the point of interest (1-based)
     * @return 0-based <code>integer</code> that indicates on which segment the index falls
     */
    public int lineSegment(int i) {
        return ((i - 1) / _segments);
    }

    /**
     * Marks the point cache as invalid, so that the spline
     * has to be recomputed on the next query.
     **/
    private void invalidatePointCache() {
        _curvepointsValid = false;
    }

    /**
     * Checks if the point cache is still valid and
     * initiates recalculation of the spline, if needed.
     **/
    private void updatePointCache() {
        if (!isPointCacheValid()) {
            _curvepoints = calculateSpline(_degree, _segments, _controlpoints);
            _curvepointsInt = DoublePoint.convertDoublePointVector(_curvepoints);
            _curvepointsValid = true;
        }
    }

    /**
     * Returns whether the point cache is still valid.
     **/
    private boolean isPointCacheValid() {
        return _curvepointsValid;
    }

    private void setVector(Vector<Point> vector) {
        Vector<Point> v = new Vector<>();
        int s = vector.size();
        for (int i = 0; i < s; i++) {
            v.addElement(new Point(vector.elementAt(i)));
        }

        _controlpoints = v;
    }

    private boolean theSame(Vector<Point> vector) {
        Point p1;
        Point p2;
        if ((vector == null) || (_controlpoints == null)) {
            return false;
        }
        if (vector.size() != _controlpoints.size()) {
            return false;
        }
        for (int i = 0; i < vector.size(); i++) {
            p1 = vector.elementAt(i);
            p2 = _controlpoints.elementAt(i);
            if (!p1.equals(p2)) {
                return false;
            }
        }
        return true;
    }

    // --------------- static methods for spline calculation ------------------


    /** Calculate the pointvector for a B-Spline.
    @param mydegree is the degree p of the spline,
    @param sections controls the subdivisions between two control points
    @param points is the vector of control <code>Point</code>s
    @return Vector of <code>DoublePoints</code> that make up the spline
    */
    public static Vector<DoublePoint> calculateSpline(
        int mydegree, int sections, Vector<Point> points)
    {
        int numcontrol = points.size();
        int degree = mydegree;
        if (numcontrol < degree + 1) {
            degree = numcontrol - 1;
        }
        if (numcontrol > 2) {
            int numpoints = (numcontrol - 1) * sections;
            Vector<DoublePoint> cpoints = new Vector<>();

            int m = numcontrol + degree;

            double[] us = knotvector(m, degree);
            double ustep = 1.0 / numpoints;
            double u;

            DoublePoint tmppoint;

            for (int i = 0; i < numpoints; ++i) {
                u = i * ustep;
                tmppoint = sppoint(u, degree, points, us);


                //logger.debug("U: "+u+" point: "+tmppoint);
                cpoints.addElement(tmppoint);
            }
            cpoints.addElement(new DoublePoint(points.lastElement()));
            return cpoints;
        } else {
            return DoublePoint.convertPointVector(points);
        }
    }

    private static double[] knotvector(int m, int p) {
        //return evenly spaced vector for a clamped curve of degree p
        int mb = m + 1;
        double[] us = new double[mb];
        int bound = m - (p * 2);
        for (int i = 0; i < bound; ++i) {
            us[i + p] = (1 / (double) bound) * i;
        }

        for (int i = 0; i < p + 1; ++i) {
            us[i] = 0.0;
            us[mb - 1 - i] = 1.0;
        }
        return us;
    }

    private static double div0(double divident, double divisor) {
        if (divisor == 0.0) {
            return 0.0;
        } else {
            return divident / divisor;
        }
    }

    //http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/bspline-basis.html
    private static double[] weightDyn(int mini, int maxi, int p, double[] us, double u) {
        double[] result = new double[maxi + 1 + p];
        for (int ii = mini; ii <= maxi + p; ii++) {
            if ((us[ii] <= u) && (u < us[ii + 1])) {
                result[ii] = 1.0;
            } else {
                result[ii] = 0.0;
            }
        }

        for (int pp = 1; pp <= p; pp++) {
            for (int ii = mini; ii <= maxi + p - pp; ii++) {
                result[ii] = div0((u - us[ii]) * result[ii], (us[ii + pp] - us[ii]))
                    + div0((us[ii + pp + 1] - u) * result[ii + 1], (us[ii + pp + 1] - us[ii + 1]));
            }
        }

        return result;
    }

    /**
     * Computes a point on a curve defined by a set of control points
     * and corresponding parameter values.
     *
     * @param u the parameter value at which to evaluate the curve
     * @param p the degree of the polynomial for the interpolation
     * @param points a vector of control points that define the curve
     * @param us an array of parameter values corresponding to the control points
     * @return a DoublePoint representing the coordinates (x, y) of the point on the curve
     *         evaluated at the given parameter `u`
     */
    public static DoublePoint sppoint(double u, int p, Vector<Point> points, double[] us) {
        int n = points.size();

        double x = 0;
        double y = 0;
        double w;
        Point pt;

        int maxi = 0;
        for (int i = 1; i < n; ++i) {
            if (us[i] <= u) {
                maxi = i;
            }
        }
        int mini = maxi;
        for (int i = maxi; i >= 0; --i) {
            if (u < us[i + p + 1]) {
                mini = i;
            }
        }

        double[] weights = weightDyn(mini, maxi, p, us, u);

        for (int i = 0; i < n; ++i) {
            if (us[i] <= u && u < us[i + p + 1]) {
                w = weights[i];


                //logger.debug ("w("+i+","+p+","+u+")="+w);
                pt = points.elementAt(i);
                x += w * pt.x;
                y += w * pt.y;
            }
        }
        return new DoublePoint(x, y);
    }
} // BSpline
