/*
 * @(#)Tangent.java    1.0  15 December 2003
 *
 * Copyright 2004
 * College of Computer and Information Science
 * Northeastern University
 * Boston, MA  02115
 *
 * The Java Power Tools software may be used for educational
 * purposes as long as this copyright notice is retained intact
 * at the top of all source files.
 *
 * To discuss possible commercial use of this software, 
 * contact Richard Rasala at Northeastern University, 
 * College of Computer and Information Science,
 * 617-373-2462 or rasala@ccs.neu.edu.
 *
 * The Java Power Tools software has been designed and built
 * in collaboration with Viera Proulx and Jeff Raab.
 *
 * Should this software be modified, the words "Modified from 
 * Original" must be included as a comment below this notice.
 *
 * All publication rights are retained.  This software or its 
 * documentation may not be published in any media either
 * in whole or in part without explicit permission.
 *
 * This software was created with support from Northeastern 
 * University and from NSF grant DUE-9950829.
 */

package edu.neu.ccs.gui;

import edu.neu.ccs.util.*;

/**
 * <P>Class <CODE>Tangent</CODE> encapsulates an interface <CODE>Strategy</CODE>
 * that defines the requirement for a strategy that can automatically use the
 * vertex array and boundary information to generate the tangent array for
 * Bezier curves.</P>
 * 
 * <P>Class <CODE>Tangent</CODE> also provides some examples of Strategy objects
 * via factory methods and also makes their methods directly available as public
 * static methods in the class to permit others to create Strategy objects.</P>
 *
 * <P>Class <CODE>Tangent</CODE> cannot be instantiated.</P>
 *
 * @author  Richard Rasala
 * @version 2.3
 * @since   2.3
 */
public class Tangent {

    /** Private constructor to prevent instantiation. */
    private Tangent() {}
    
    
    /**
     * The <CODE>Strategy</CODE> interface requires methods that
     * return the tangent array for a closed or open Bezier curve
     * from its vertex array and, if needed, its end tangent data.
     */
    public interface Strategy {
        /**
         * <P>Returns the tangent array for a closed Bezier curve
         * corresponding to the given vertex array
         * using the encapsulated vertex-to-tangent strategy.</P>
         *
         * <P>Precondition: For some integer N >= 0:</P>
         * <UL>
         *   <LI>The given vertex array is
         *          float[N][2] with non-<CODE>null</CODE> entries</LI>
         * </UL>
         * 
         * <P>Postcondition: For the same integer N:</P>
         * <UL>
         *   <LI>The tangent array returned is
         *          float[N][2] with non-<CODE>null</CODE> entries</LI>
         * </UL>
         *
         * <P>If the vertex array fails its precondition then the method should
         * return float[0][2].</P>
         *
         * @param  vertex the vertex array of a closed curve
         * @return the associated tangent array constructed using the strategy
         */
        public float[][] makeTangents(float[][] vertex);
        
        
        /**
         * <P>Returns the tangent array for an open Bezier curve
         * corresponding to the given vertex array
         * and the given endTangent data
         * using the encapsulated vertex-to-tangent strategy.</P>
         *
         * <P>Precondition 1. For some integer N >= 0:</P>
         * <UL>
         *   <LI>The given vertex array is
         *          float[N][2] with non-<CODE>null</CODE> entries</LI>
         * </UL>
         * 
         * <P>Precondition 2.</P>
         * <UL>
         *   <LI>The given endTangent array is
         *          either <CODE>null</CODE> or
         *          float[2][2] with non-<CODE>null</CODE> entries</LI>
         * </UL>
         * 
         * <P>Postcondition 1. For the same integer N:</P>
         * <UL>
         *   <LI>The tangent array returned is
         *          float[N][2] with non-<CODE>null</CODE> entries</LI>
         * </UL>
         *
         * <P>Postcondition 2: If the endTangent array is <CODE>null</CODE>,
         * then the function should return <CODE>makeTangents(vertex)</CODE>.</P>
         *
         * <P>Postcondition 3: If the endTangent array is non-<CODE>null</CODE>:</P>
         * <UL>
         *   <LI>If N > 0, for i = 0, 1:
         *          <CODE>tangent[0][i] == endTangent[0][i]</CODE></LI>
         *   <LI>If N > 1, for i = 0, 1:
         *          <CODE>tangent[N-1][i] == endTangent[1][i]</CODE></LI>
         * </UL>
         *
         * <P>If the vertex array fails its precondition then the method should
         * return float[0][2].</P>
         *
         * <P>If the endTangent array fails its precondition then it should be
         * treated as if it were <CODE>null</CODE>.</P>
         *
         * @param  vertex     the vertex array of an open curve
         * @param  endTangent the tangent data for the ends of the open curve
         * @return the associated tangent array constructed using the strategy
         */
        public float[][] makeTangents(float[][] vertex, float[][] endTangent);
    }
    
    
    ////////////////////////////
    // Smooth Bezier Strategy //
    ////////////////////////////
    
    /** The minimum number of terms for which the bezierStrategy will be used. */
    private static final int minTerms = 1;
    
    /**
     * The maximum number of terms for which the bezierStrategy will be cached
     * and the maximum number of terms needed to achieve practical smoothness.
     */
    private static final int maxTerms = 7;
    
    /** The bezierStrategy cache. */
    private static final Strategy standardBezierStrategy =
        bezierStrategy(maxTerms);
    
    
    /**
     * <P>Returns the strategy that encapsulates the bezierTangents method using
     * sufficient terms to guarantee second derviative smoothness in practical
     * situations.</P>
     *
     * <P>In this implementation, the maximum number of terms used is 7.</P>
     *
     * <P>See, Richard Rasala, Explicit Cubic Spline Interpolation Formulas, in
     * Andrew S. Glassner, Graphics Gems, Academic Press, 1990, 579-584.</P>
     *
     * @return the strategy that encapsulates the bezierTangents method
     * @see #bezierStrategy(int)
     * @see #bezierTangents(float[][], int)
     */
    public static Tangent.Strategy bezierStrategy() {
        return standardBezierStrategy;
    }
    
    
    /**
     * <P>Returns the strategy that encapsulates the bezierTangents method using
     * the given number of terms.</P>
     *
     * <P>If terms < 1, then terms is set to 1.</P>
     *
     * <P>See, Richard Rasala, Explicit Cubic Spline Interpolation Formulas, in
     * Andrew S. Glassner, Graphics Gems, Academic Press, 1990, 579-584.</P>
     *
     * @param  terms the maximum number of terms to use in computing each tangent
     * @return the strategy that encapsulates the bezierTangents method
     * @see #bezierStrategy()
     * @see #bezierTangents(float[][], int)
     */
    public static Tangent.Strategy bezierStrategy(int terms) {
        final int t = (terms < minTerms) ? minTerms : terms;
        
        return new Tangent.Strategy() {
            public float[][] makeTangents(float[][] vertex) {
                return bezierTangents(vertex, t);
            }
            
            public float[][] makeTangents(float[][] vertex, float[][] endTangent) {
                return bezierTangents(vertex, endTangent, t);
            }
        };
    }
    
    
    /**
     * <P>Returns the unique Bezier tangents to make a smooth closed cubic spline
     * curve through the given vertex data.</P>
     *
     * <P>In this context smooth means that the first derivative is continuous at
     * each vertex and the degree of continuity of the second derivative at each
     * vertex is controlled by the number of terms used to compute the tangent.</P>
     *
     * <P>If terms >= 7, then in practical situations, the second derivative will
     * be continuous.  Using a smaller value of terms will mean that fewer points
     * affect the computation of the tangent at each vertex at the cost of some
     * loss of continuity of the second derivative at each vertex.</P>
     *
     * <P>Precondition: For some integer N >= 0:</P>
     * <UL>
     *   <LI>The given vertex array is
     *          float[N][2] with non-<CODE>null</CODE> entries</LI>
     * </UL>
     * 
     * <P>Postcondition: For the same integer N:</P>
     * <UL>
     *   <LI>The tangent array returned is
     *          float[N][2] with non-<CODE>null</CODE> entries</LI>
     * </UL>
     *
     * <P>If the vertex array fails its precondition then float[0][2] is returned.</P>
     *
     * <P>If terms < 1, then terms is set to 1.</P>
     *
     * <P>See, Richard Rasala, Explicit Cubic Spline Interpolation Formulas, in
     * Andrew S. Glassner, Graphics Gems, Academic Press, 1990, 579-584.</P>
     * 
     * @param  vertex the vertex data
     * @param  terms  the maximum number of terms to use in computing each tangent 
     * @return the associated smooth Bezier tangent data
     * @see #bezierStrategy()
     * @see #bezierStrategy(int)
     * @see #bezierCoefficients(int, int)
     */
    public static float[][] bezierTangents
        (float[][] vertex, int terms)
    {
        if (! FloatArray.checkArray(vertex, 2))
            return new float[0][2];
        
        int N = vertex.length;
        
        float[][] tangent = new float[N][2];
        
        if (N <= 2)
            return tangent;
        
        float[] a = bezierCoefficients(N, terms);
        int m = a.length - 1;
        
        for (int i = 0; i < N; i++) {
            for (int k = 1; k <= m; k++) {
                int r = i + k;
                int s = i - k;
                
                if (r >= N) r -= N;
                if (s <  0) s += N;
                
                tangent[i][0] += (a[k] * (vertex[r][0] - vertex[s][0]));
                tangent[i][1] += (a[k] * (vertex[r][1] - vertex[s][1]));
            }
        }
        
        return tangent;
    }
    
    
    /**
     * <P>Returns the unique Bezier tangents to make a smooth open cubic spline
     * curve through the given vertex data and with the given endTangent data.</P>
     *
     * <P>In this context smooth means that the first derivative is continuous at
     * each vertex and the degree of continuity of the second derivative at each
     * vertex is controlled by the number of terms used to compute the tangent.</P>
     *
     * <P>If terms >= 7, then in practical situations, the second derivative will
     * be continuous.  Using a smaller value of terms will mean that fewer points
     * affect the computation of the tangent at each vertex at the cost of some
     * loss of continuity of the second derivative at each vertex.</P>
     *
     * <P>Precondition 1. For some integer N >= 0:</P>
     * <UL>
     *   <LI>The given vertex array is
     *          float[N][2] with non-<CODE>null</CODE> entries</LI>
     * </UL>
     * 
     * <P>Precondition 2.</P>
     * <UL>
     *   <LI>The given endTangent array is
     *          either <CODE>null</CODE> or
     *          float[2][2] with non-<CODE>null</CODE> entries</LI>
     * </UL>
     * 
     * <P>Postcondition 1. For the same integer N:</P>
     * <UL>
     *   <LI>The tangent array returned is
     *          float[N][2] with non-<CODE>null</CODE> entries</LI>
     * </UL>
     *
     * <P>Postcondition 2: If the endTangent array is <CODE>null</CODE>,
     * then the function returns <CODE>bezierTangents(vertex, terms)</CODE>.
     * In other words, the fact that the curve is open is ignored.</P>
     *
     * <P>Postcondition 3: If the endTangent array is non-<CODE>null</CODE>:</P>
     * <UL>
     *   <LI>If N > 0, for i = 0, 1:
     *          <CODE>tangent[0][i] == endTangent[0][i]</CODE></LI>
     *   <LI>If N > 1, for i = 0, 1:
     *          <CODE>tangent[N-1][i] == endTangent[1][i]</CODE></LI>
     * </UL>
     *
     * <P>If the vertex array fails its precondition then float[0][2] is returned.</P>
     *
     * <P>If the endTangent array fails its precondition then it is treated as if
     * it were <CODE>null</CODE>.</P>
     *
     * <P>If terms < 1, then terms is set to 1.</P>
     *
     * <P>See, Richard Rasala, Explicit Cubic Spline Interpolation Formulas, in
     * Andrew S. Glassner, Graphics Gems, Academic Press, 1990, 579-584.</P>
     * 
     * @param  vertex     the vertex data
     * @param  endTangent the tangent data for the ends of the open curve
     * @param  terms      the maximum number of terms to use in computing each tangent 
     * @return the associated smooth Bezier tangent data
     * @see #bezierStrategy()
     * @see #bezierStrategy(int)
     * @see #bezierCoefficients(int, int)
     */
    public static float[][] bezierTangents
        (float[][] vertex, float[][] endTangent, int terms)
    {
        if (! (FloatArray.checkArray(endTangent, 2) && (endTangent.length == 2)))
            return bezierTangents(vertex, terms);
        
        if (! FloatArray.checkArray(vertex, 2))
            return new float[0][2];
        
        int N = vertex.length;
        int M = N - 1;
        
        float[][] tangent = new float[N][2];
        
        if (N > 0) {
            tangent[0][0] = endTangent[0][0];
            tangent[0][1] = endTangent[0][1];
        }
        
        if (N > 1) {
            tangent[M][0] = endTangent[1][0];
            tangent[M][1] = endTangent[1][1];
        }
        
        if (N <= 2)
            return tangent;
        
        float[][] v = FloatArray.deepclone(vertex);
        
        v[0][0] = vertex[0][0] + tangent[0][0];
        v[0][1] = vertex[0][1] + tangent[0][1];
        
        v[M][0] = vertex[M][0] - tangent[M][0];
        v[M][1] = vertex[M][1] - tangent[M][1];
        
        int Z = 2 * M;
        float[] a = bezierCoefficients(Z, terms);
        int m = a.length - 1;
        
        for (int i = 1; i < M; i++) {
            for (int k = 1; k <= m; k++) {
                int r = i + k;
                int s = i - k;
                
                if (r >= N) r = Z - r;
                if (s <  0) s = -s;
                
                tangent[i][0] += (a[k] * (v[r][0] - v[s][0]));
                tangent[i][1] += (a[k] * (v[r][1] - v[s][1]));
            }
        }
        
        return tangent;
    }
    
    
    /**
     * <P>Returns the coefficients needed to compute the Bezier tangents
     * corresponding to the length of the vertex data.</P>
     * 
     * <P>Note that: If length <= 2, returns the empty array: float[0].  For
     * such a length, the coefficients are not in fact used in the algorithm.</P>
     *
     * <P>If terms < 1, then terms is set to 1.</P>
     *
     * <P>See, Richard Rasala, Explicit Cubic Spline Interpolation Formulas, in
     * Andrew S. Glassner, Graphics Gems, Academic Press, 1990, 579-584.</P>
     *
     * @param  N the length of the vertex data array
     * @param  terms the maximum number of terms to use in computing each tangent
     * @return the coefficients needed to compute the Bezier tangents
     * @see #bezierTangents(float[][], int)
     */
    public static float[] bezierCoefficients(int N, int terms) {
        if (N <= 2)
            return new float[0];
        
        // find the maxindex of the coefficients array in the general case
        int m = (N - 1) / 2;
        
        if (terms < minTerms)
            terms = minTerms;
        
        if (m > terms)
            m = terms;
        
        // define the coefficients array a to include the index m
        float[] a = new float[m + 1];
        
        // define the helper array h needed to compute the array a
        float[] h = new float[m + 1];
        
        h[0] = 1;
        h[1] = ((N % 2) == 1) ? -3 : -4;
        
        for (int i = 2; i <= m; i++)
            h[i] = (-4) * h[i-1] - h[i-2];
        
        // now compute and return the array a
        for (int k = 1; k <= m; k++)
            a[k] = - h[m-k] / h[m];
        
        return a;
    }
    
    
    ////////////////////
    // Chord Strategy //
    ////////////////////
    
    
    /**
     * Returns the strategy that encapsulates the chordTangents method.
     *
     * @param  factor the fraction of the chord to use as the tangent
     * @return the strategy that encapsulates the chordTangents method
     * @see #chordTangents(float[][], float)
     */
    public static Tangent.Strategy chordStrategy(final float factor) {
        return new Tangent.Strategy() {
            public float[][] makeTangents(float[][] vertex) {
                return chordTangents(vertex, factor);
            }
            
            public float[][] makeTangents(float[][] vertex, float[][] endTangent) {
                return chordTangents(vertex, endTangent, factor);
            }
        };
    }
    
    
    /**
     * <P>Returns a tangent array for a closed cubic spline curve that is
     * computed from the given vertex array by a chord-based strategy.</P>
     *
     * <P>Specifically, the rule for tangent computation is:</P>
     *
     * <UL>
     *   <LI><CODE>tangent[i] = factor * (vertex[i+1] - vertex[i-1])</CODE>.</LI>
     * </UL
     * 
     * <P>In this formula, we assume that indices wrap around at the ends of
     * the vertex array.</P>
     *
     * <P>This technique for computing the tangent array ensures that each
     * tangent is influenced only by the two neighboring vertex points.</P>
     * 
     * <P>Precondition: For some integer N >= 0:</P>
     * <UL>
     *   <LI>The given vertex array is
     *          float[N][2] with non-<CODE>null</CODE> entries</LI>
     * </UL>
     * 
     * <P>Postcondition: For the same integer N:</P>
     * <UL>
     *   <LI>The tangent array returned is
     *          float[N][2] with non-<CODE>null</CODE> entries</LI>
     * </UL>
     *
     * <P>If the vertex array fails its precondition then float[0][2] is returned.</P>
     *
     * @param  vertex the vertex data
     * @param  factor the fraction of the chord to use as the tangent
     * @return the associated tangent data
     * @see #chordStrategy(float)
     */
    public static float[][] chordTangents
        (float[][] vertex, float factor)
    {
        if (! FloatArray.checkArray(vertex, 2))
            return new float[0][2];
        
        int N = vertex.length;
        
        float[][] tangent = new float[N][2];
        
        if (N <= 2)
            return tangent;
        
        for (int i = 0; i < N; i++) {
            int r = i + 1;
            int s = i - 1;
            
            if (r >= N) r -= N;
            if (s <  0) s += N;
            
            tangent[i][0] = factor * (vertex[r][0] - vertex[s][0]);
            tangent[i][1] = factor * (vertex[r][1] - vertex[s][1]);
        }
        
        return tangent;
    }
    
    
    /**
     * <P>Returns a tangent array for an open cubic spline curve that is
     * computed from the given vertex array and the given endTangent data
     * by a chord-based strategy.</P>
     *
     * <P>Specifically, the rules for tangent computation are:</P>
     *
     * <UL>
     *   <LI>End tangents are obtained from the given endTangent data.
     *   <LI>Interior tangents are computed by the following formula:
     *       <CODE>tangent[i] = factor * (vertex[i+1] - vertex[i-1])</CODE>.</LI>
     * </UL
     * 
     * <P>This technique for computing the tangent array ensures that each
     * tangent is influenced only by the two neighboring vertex points.</P>
     * 
     * <P>Precondition 1. For some integer N >= 0:</P>
     * <UL>
     *   <LI>The given vertex array is
     *          float[N][2] with non-<CODE>null</CODE> entries</LI>
     * </UL>
     * 
     * <P>Precondition 2.</P>
     * <UL>
     *   <LI>The given endTangent array is
     *          either <CODE>null</CODE> or
     *          float[2][2] with non-<CODE>null</CODE> entries</LI>
     * </UL>
     * 
     * <P>Postcondition 1. For the same integer N:</P>
     * <UL>
     *   <LI>The tangent array returned is
     *          float[N][2] with non-<CODE>null</CODE> entries</LI>
     * </UL>
     *
     * <P>Postcondition 2: If the endTangent array is <CODE>null</CODE>,
     * then the function returns <CODE>chordTangents(vertex, factor)</CODE>.
     * In other words, the fact that the curve is open is ignored.</P>
     *
     * <P>Postcondition 3: If the endTangent array is non-<CODE>null</CODE>:</P>
     * <UL>
     *   <LI>If N > 0, for i = 0, 1:
     *          <CODE>tangent[0][i] == endTangent[0][i]</CODE></LI>
     *   <LI>If N > 1, for i = 0, 1:
     *          <CODE>tangent[N-1][i] == endTangent[1][i]</CODE></LI>
     * </UL>
     *
     * <P>If the vertex array fails its precondition then float[0][2] is returned.</P>
     *
     * <P>If the endTangent array fails its precondition then it is treated as if
     * it were <CODE>null</CODE>.</P>
     *
     * @param  vertex the vertex data
     * @param  factor the fraction of the chord to use as the tangent
     * @return the associated tangent data
     * @see #chordStrategy(float)
     */
    public static float[][] chordTangents
        (float[][] vertex, float[][] endTangent, float factor)
    {
        if (! (FloatArray.checkArray(endTangent, 2) && (endTangent.length == 2)))
            return chordTangents(vertex, factor);
        
        if (! FloatArray.checkArray(vertex, 2))
            return new float[0][2];
        
        int N = vertex.length;
        int M = N - 1;
        
        float[][] tangent = new float[N][2];
        
        if (N > 0) {
            tangent[0][0] = endTangent[0][0];
            tangent[0][1] = endTangent[0][1];
        }
        
        if (N > 1) {
            tangent[M][0] = endTangent[1][0];
            tangent[M][1] = endTangent[1][1];
        }
        
        if (N <= 2)
            return tangent;
        
        for (int i = 1; i < M; i++) {
            int r = i + 1;
            int s = i - 1;
            
            tangent[i][0] = factor * (vertex[r][0] - vertex[s][0]);
            tangent[i][1] = factor * (vertex[r][1] - vertex[s][1]);
        }
        
        return tangent;
    }
    
}