/** * AlgorithmLP.java v6.0 Last Edited by: Ryan Irwin 05/23/2005 * Nishant Aggarwal, Jun-Won Suh Created: 12/15/04 * * Description: Linear Prediction algorithm. Determines the estimate of  * the data points based on the points given by the user.  * The appraoch is data interpolation [ based on cubic interpolation ], * Autocorrelation coefficients and Linear Predictor Coefficients [based * on Levinson Durbin Algorithm] *///----------------------// import java packages//----------------------import java.util.*;import java.awt.*; import java.awt.Graphics;import javax.swing.JApplet; // import class Algorithmpublic class AlgorithmLP extends Algorithm{    //-----------------------------------------------------------------    //    // static data members    //    //-----------------------------------------------------------------    int lporder;    int iporder;    int scale;    //-----------------------------------------------------------------    //    // primitive data members    //    //-----------------------------------------------------------------    int output_canvas_d[][];       //-----------------------------------------------------------------    //    // instance data members    //    //-----------------------------------------------------------------    String algo_id = "AlgorithmLP";     Vector<MyPoint> support_vectors_d;    Vector<MyPoint> decision_regions_d;    // for original data    //    Vector<MyPoint> set1_d = new Vector<MyPoint>(40, 20);    Vector<MyPoint> set2_d = new Vector<MyPoint>(40, 20);    Vector<MyPoint> set3_d = new Vector<MyPoint>(40, 20);    Vector<MyPoint> set4_d = new Vector<MyPoint>(40, 20);    // for interpolation function    //    Vector<MyPoint> iset1 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> iset2 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> iset3 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> iset4 = new Vector<MyPoint>(40, 20);     // vector for mean-subtracted [zero-mean] data    //    Vector<MyPoint> mset1 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> mset2 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> mset3 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> mset4 = new Vector<MyPoint>(40, 20);     // for display purpose    //    Vector<MyPoint> display_set1 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> display_set2 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> display_set3 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> display_set4 = new Vector<MyPoint>(40, 20);     // to store autoCorrelation coefficient   //    double auto_co_1[];    double auto_co_2[];    double auto_co_3[];    double auto_co_4[];    // to store the average values for each class    //    double average1;    double average2;    double average3;    double average4;    // to store LP coefficient    //    double final_lpc_1[];     double final_lpc_2[];    double final_lpc_3[];    double final_lpc_4[];    // to store residual energy     //    double estimate_err_1 = 0;	    double estimate_err_2 = 0;	    double estimate_err_3 = 0;    double estimate_err_4 = 0;     // to store actual error energy    //    double actual_err_1 = 0;    double actual_err_2 = 0;    double actual_err_3 = 0;    double actual_err_4 = 0;    // to store the reflection coefficients    //    double ref_coeff_1[];    double ref_coeff_2[];    double ref_coeff_3[];     double ref_coeff_4[];    // to store the final results    //    Vector<MyPoint> y_estimate1 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> y_estimate2 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> y_estimate3 = new Vector<MyPoint>(40, 20);     Vector<MyPoint> y_estimate4 = new Vector<MyPoint>(40, 20);     //---------------------------------------------------------------    //    // class methods    //    //---------------------------------------------------------------    /**     *      * Implements the initialize() method in the base class. Initializes     * member data and prepares for execution of first step. This method     * "resets" the algorithm.     *     * @return   returns true if sets of data are valid     *     */    public boolean initialize()    {	DisplayArea disp_area_d = new DisplayArea();	point_means_d           = new Vector<MyPoint>();	decision_regions_d      = new Vector<MyPoint>();	support_vectors_d       = new Vector<MyPoint>();	description_d           = new Vector<String>();	step_count  = 3;	lporder    = Classify.main_menu_d.lporder;	iporder    = Classify.main_menu_d.iporder;	scale      = lporder * iporder;	// Add the process description for the LP algorithm	//	if (description_d.size() == 0)	{	    String str = new String("   0.  Checking for the Data Validity.");	    description_d.addElement(str);	    	    str = new String("   1.  Displaying the Input Data Points.");	    description_d.addElement(str);	    	    str = new String("   2.  Computing LP Parameters.");	    description_d.addElement(str);	    	    str = new String("   3.  Displaying the Linear Predicted Signal");	    description_d.addElement(str);	}	// set the data points for this algorithm	//	//	set1_d = (Vector)data_points_d.dset1.clone();	//	set2_d = (Vector)data_points_d.dset2.clone();	//	set3_d = (Vector)data_points_d.dset3.clone();	//	set4_d = (Vector)data_points_d.dset4.clone();	//	set1_d = data_points_d.dset1;	set2_d = data_points_d.dset2;	set3_d = data_points_d.dset3;	set4_d = data_points_d.dset4;		int max1 = set2_d.size();	if (set1_d.size() > set2_d.size())	    max1 = set1_d.size();	int max2 = set4_d.size();	if (set3_d.size() > set4_d.size())	    max2 = set3_d.size();	else	    max2 = set4_d.size();	if (max2 > max1)	    max1 = max2;	if (max1 > scale)	    scale = max1;	step_index_d = 0;	if((checkdata_LP(set1_d) == true) && (checkdata_LP(set2_d) == true) 	   && (checkdata_LP(set3_d) == true) && (checkdata_LP(set4_d) == true))	{	    pro_box_d.appendMessage((String)description_d.get(step_index_d));	    pro_box_d.appendMessage("         Data points valid");	    return true;		}	else        {	    pro_box_d.appendMessage("\n" + "Invalid data");	    pro_box_d.appendMessage("Clear and enter valid data" + "\n");	    return false;	}    }    /**    *     * Validates the class entered by user for Linear Prediction      *    * @param    lp    * @return   true if data is Vector lp is valid. It is invalid    *           if the size of lp is 1 or any element is larger than the    *           the previous element    *     */    public boolean checkdata_LP(Vector lp)    {	if ( lp.size() == 1) 	    return false;	else	   for(int i = 0; i <= lp.size() - 1 ; i++ )	       for(int j = i + 1; j <= lp.size() - 1 ; j++ )		   // amplitudes should be in time progression		   //		   if ( (((MyPoint)lp.elementAt(i)).x == 			 ((MyPoint)lp.elementAt(j)).x) || 			(((MyPoint)lp.elementAt(i)).x > 			 ((MyPoint)lp.elementAt(j)).x) )		       return false;	return true;    }    /**     *     * Implementation of the run function from the Runnable interface.     * Determines what the current step is and calls the appropriate method.     *     */    public void run()    {	if (step_index_d == 1)	{	    disableControl();	    step1();	    enableControl();	}	if (step_index_d == 2)	{	    disableControl();	    step2();	    enableControl(); 	}	if (step_index_d == 3)	{	    disableControl();	    step3(); 	    enableControl();        }		// exit gracefully	//	return;    }        /**     *     * Displays data sets from input box in output box, clears the data     * points from the Vector fro input data, zero-mean data,     * does interpolation, and then finds mean of the interpolated data     * interpolates the zero-mean data, displays the result     *     * @return   True     *     */    boolean step1()    {	// set up progress bar	//	pro_box_d.setProgressMin(0);	pro_box_d.setProgressMax(1);	pro_box_d.setProgressCurr(0);	output_panel_d.disp_area_d.output_points_d.removeAllElements();	output_panel_d.disp_area_d.type_d.removeAllElements();	output_panel_d.disp_area_d.color_d.removeAllElements();	      	// Display original data	// size of the point made four times bigger	//        if(set1_d.size() > 0 )       {	   display_set1.removeAllElements();	   iset1.removeAllElements();	   mset1.removeAllElements();	   interpol(set1_d, display_set1);	   average1 = mean(display_set1, mset1);	   interpol(mset1, iset1);	   output_panel_d.addOutput(set1_d, (Classify.PTYPE_INPUT * 4), 				    data_points_d.color_dset1);       }       if(set2_d.size() > 0 )       {	   display_set2.removeAllElements();	   iset2.removeAllElements();  	   mset2.removeAllElements();	   interpol(set2_d, display_set2);	   average2 = mean(display_set2, mset2);	   interpol(mset2, iset2);   	  	   output_panel_d.addOutput(set2_d, (Classify.PTYPE_INPUT * 4), 				    data_points_d.color_dset2);       }              if(set3_d.size() > 0 )       {	   display_set3.removeAllElements();	   iset3.removeAllElements();	   mset3.removeAllElements();	   interpol(set3_d, display_set3);	   average3 = mean(display_set3, mset3);	   interpol(mset3, iset3);	   output_panel_d.addOutput(set3_d, (Classify.PTYPE_INPUT * 4), 				    data_points_d.color_dset3);       }              if(set4_d.size() > 0 )       {		   display_set4.removeAllElements();	   iset4.removeAllElements();	   mset4.removeAllElements();	   interpol(set4_d, display_set4);	   average4 = mean(display_set4, mset4);	   interpol(mset4, iset4);   	   output_panel_d.addOutput(set4_d, (Classify.PTYPE_INPUT * 4), 				    data_points_d.color_dset4);       }	pro_box_d.setProgressCurr(1);	output_panel_d.repaint();	return true;    }     /**     *     * Calculates the interpolated points for the data inputs        *     * @param  v  input data points     * @param  iset  interpolated data points     *     */    public void interpol(Vector<MyPoint> v , Vector<MyPoint> iset)    {		double sample;	double d ;	MyPoint r = new MyPoint();			double[] y2 = new double[v.size()];  	double[] y  = new double[v.size()];	double[] x  = new double[v.size()];              for (int k = 0; k < v.size(); k++)       {	   x[k] = ((MyPoint)v.elementAt(k)).x;	   y[k] = ((MyPoint)v.elementAt(k)).y;       }       // Reference:       // "Numerical Recipe in C", Cambridge University Press, pp 113-116              // total time interval of the data points calculated       //       d = ((MyPoint)v.lastElement()).x - ((MyPoint)v.firstElement()).x ;               // time step calculation       //       sample = d / scale;       spline(x, y, y2, v.size());              // iset holds new data points - interpolated values       // First value added        //       iset.addElement(new MyPoint((MyPoint)v.firstElement()));              // Increment to next Time value       //      	r.x = sample + ((MyPoint)v.firstElement()).x;	while (r.x <=  ((MyPoint)v.lastElement()).x)	{	    for(int j = 1; j < v.size(); j++)	    {		// the New Interpolated amplitude will be calculated		// for the two points within which the time intervals 		// lies, Hence, the condition check		//		if((r.x <= ((MyPoint)v.elementAt(j)).x ) && 		   (r.x >=  ((MyPoint)v.elementAt(j - 1)).x)) 		{		    r.y = 0 ;		    splint ((MyPoint)v.elementAt(j - 1), 			    (MyPoint)v.elementAt(j), r, y2, (j - 1));		    // New value appended to the array		    //		    iset.addElement(new MyPoint(r));		    break; 		}	    }	       	    r.x = r.x + sample;	}	// sometimes the last element of the user entered 	// values is missed out hence the condition to 	// cross-check and put it in	//	if (((MyPoint)iset.lastElement()).x != ((MyPoint)v.lastElement()).x )	    iset.addElement( new MyPoint((MyPoint)v.lastElement()));    }    /**     *     * Actually interpolates the points     *     * @param x    array containing the x coordinates of datapoints     * @param y    array containing the y coordinates of datapoints     * @param y2   array containing the interpolated y coordinates     * @param size the size of the array to be interpolated     *      */    public void spline (double[] x, double[] y, double[] y2, int size )    { 	double[] u = new double[size];	double p; 	double sig; 		y2[0] = 0;	u[0] = 0;	 	for( int i = 1; i < size - 1; i++ )	{ 	    sig = ( x[i] - x[i - 1] ) / ( x[i + 1] - x[i - 1] ) ;	    p = sig * y2[i - 1] + 2 ;	    y2[i] = ( sig - 1) / p ;	    u[i] = ( y[i + 1] - y[i] ) / ( x[i + 1] - x[i] ) ;	    u[i] = ( 6 * u[i] / ( x[i + 1] - x[i - 1] ) 		     - sig * u[i - 1] ) / p ;	}	y2[size - 1] = 0 ;		// This is the back substitution loop of the tridiagonal algorithm	//	for(int i = size - 2; i >= 0; i-- )     	    y2[i] = y2[i] * y2[i + 1] + u[i] ;    }    /**     * Interpolates for a point between the two known points     * using Cubic Interpolation     *     * @param   u1 start point for the interpolation     * @param   u2 end point for the interpolation     * @param   r  returning point, basically the interpolated point     * @param   y2 array used for reassigning of r     * @param   i  the sample number     *     */    public void splint ( MyPoint u1, MyPoint u2, MyPoint r, 			 double[] y2, int i )    {	double h;	double a;	double b; 	h = u2.x - u1.x ;	a = ( u2.x - r.x ) / h ;	b = ( r.x - u1.x ) / h ;	r.y = a * u1.y + b * u2.y + ((a * a * a - a) * y2[i] 	                             + ( b * b * b - b ) * y2[i + 1] ) 	                                                 * ( h * h ) / 6 ;     }    /**     *     * Calculates the mean and the zero-mean data points       *     * @param    v orginal datapoints     * @param    mv zero mean datapoints      *     * @return   The average in a double     *      */    public double mean(Vector<MyPoint> v, Vector<MyPoint> mv)    {        double average = 0;	MyPoint p      = new MyPoint();       for(int i = 0; i < v.size(); i++ )	   average = average + ((MyPoint)v.elementAt(i)).y;       average = average / v.size();              for(int i = 0; i < v.size(); i++ )       {	   p.y = ((MyPoint)v.elementAt(i)).y - average;