// name: Devin Scott N23 CS407
// Assignment A02

#include <math.h>
#include <stdio.h>


int signof(double x)  //return 1 if the sign is positive , 0 if it is negative
{
if (x >= 0)
return 1;

else 
return 0;

}


double interpolate(int numberofpairs, double xvalues[], double yvalues[], double bigx, int k)
{
double result = 40.2;
int i =0;
int j =0;
int nexthigher=0;
int kbegin=0;
int kend=0;
int aflag =0;
double product;
double summation;
int r=0;
double temproduct=0;
double temproduct2=0;
double temproduct3=0;
double temproduct4=0;



j=numberofpairs;



	for (i = 1; i <= j; i++)
	{
		printf("\n x%d : %lf , y%d : %lf \n", i,xvalues[i],i,yvalues[i]);	
	}


	if (bigx >xvalues[1] && bigx < xvalues[j]) //normal middle case
	{  //interpolation points will be half k points after and the remainder points before the point that is found just higher than bigx. 
	
	
		if (bigx > xvalues[j-1]) //if target bigx is greater than the second to last point
		{ 			//interpolation points will be j, j-1, j-2 .. j-k
	
			printf("target is close to the last point\n");
			aflag=1;
		}

		if (bigx < xvalues[2]) //if target bigx is smaller than the second point.
		{ 			//interpolation points will be 1, 2, 3 .. k

			printf("target is close to the first point\n");	
			aflag=1;
		}

		
		
		for (i=1; i <= j; i++) //find xi that is just higher than bigx
		{
			if (xvalues[i] > bigx)
			{
			nexthigher = i;
			printf("the point that is just bigger than bigx %lf is %lf \n",bigx, xvalues[nexthigher]);
			break;
			}	

		}
		
		
		if (aflag == 0)
		{
			//identify the range of k as nexthigher + (k/2 -1) points ahead and - k/2 points behind
			kbegin = nexthigher - ( k - (k/2) );
			kend =  nexthigher + (k/2) -1;

			if (kbegin < 1)  //adjustment needs to be made if overflow occurs
			{
				kend = kend + abs(kbegin) + 1;  //move nodes from beginning range of k to end range
				kbegin = kbegin + abs(kbegin) +1;
			}
			if (kend > j) //k was too big!
			{
				kend = kend - (k-j);  //move nodes from end range of k to begin range
				kbegin = kbegin - (k-j);
				
			}

			
			if (kbegin < 1  || kend > j)
			{
				printf("unhandled overflow occured k was too big\n");			
			}

			
			printf("the range of k has been identified as: %d to %d \n",kbegin,kend);
		}


	}
product = 1;
summation =0;

for (i =1; i<k; i++)
{



	for (r = 1; r<k; r++)
	{
		if (r != k)
		{
			
/*
			printf ("\n product is growing. it is now equal to %lf \n",product);
			temproduct = (bigx - xvalues[r]);
			printf("\n temproduct is now equal to %lf \n",temproduct); 
			temproduct2 = xvalues[i] -xvalues[j];
			printf("\n temproduct2 is now equal to %lf \n",temproduct2);
			temproduct3 = temproduct/temproduct2;
			printf("\n temproduct3 is now equal to %lf \n",temproduct3);
			temproduct4 = product * temproduct3;
			product = temproduct4;
*/
			
			

			product = product * ( (bigx - xvalues[r])/( xvalues[i] -xvalues[j] ) );
			
			printf ("\n product is growing. it is now equal to %lf \n",product);
			
		}

	}


	summation = summation + (yvalues[i] * product);
	printf ("\n summation is growing. it is now equal to %lf \n",summation);

}
result = summation;

return result;
}

int main ()
{

	int num_table_pairs =0;
	double x =0;
	double y =0;
	int k =0;
	int j=0;
	int i=0;
	double xvalues[30];
	double yvalues[30];
	double bigx=0.0;
	double bigy=0.0;
	double resulty =0.0;
	printf ("\n Devin Scott NN: 23 Numerical Analysis. assignment 3: interpolation\n");  //header
	
														//collect input from user
														//input is "lower limit","upper limit"
														//"number of subintervals","relative error thresh",
															//"maximum number of iterations"

	printf ("\n please enter the number of table pairs\n");
	scanf("%d",&num_table_pairs); 
	printf ("please enter values for %d table pairs\n", num_table_pairs);
	
	j=num_table_pairs;

		
   
/*

	for (i = 1; i<=j; i++)
	{
		printf ("please enter value for x%d \n",i);
		scanf ("%lf", &x);	
		printf ("please enter value for y%d \n",i);
		scanf ("%lf", &y);		
		xvalues[i] = x;
		yvalues[i] = y;

	}
     */
	xvalues[1] =1.0;
	xvalues[2] =1.5;
	xvalues[3] = 2.0;
	xvalues[4] =2.5;
	xvalues[5] = 3.0;
	xvalues[6] =3.5;
	xvalues[7] =4.0;

	yvalues[1] = 0.000;
	yvalues[2] =0.405;
	yvalues[3] = 0.693;
	yvalues[4] = 0.916;
	yvalues[5] = 1.098;
	yvalues[6] = 1.252;
	yvalues[7] = 1.386;



	for (i = 1; i <= j; i++)
	{
		printf("\n x%d : %lf , y%d : %lf \n", i,xvalues[i],i,yvalues[i]);	
	}

	printf ("please enter value of K nodes to consider for interpolation\n");
	scanf ("%d",&k);
	

	for (i=0; i<20; i++)
	{
	printf ("please enter value of X (unknown in the table) to interpolate value for");
	scanf ("%lf",&bigx);




	printf ("interpolating value of BigY for BigX: %lf using %d nodes \n", bigx, k);

	
	resulty = interpolate(j, xvalues, yvalues, bigx, k);			

	printf("the result of interpolation of %lf is %lf \n",bigx, resulty);
	}
	return 0;
}