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

// ******************************************************************************
// Function Name : main
// 
// Brief :
//         主函数框架.
//         请在YourMethod处提供算法以返回向量X.
//         可选用F00~F09测试映射,亦可自定义其他映射.
//
// Function :
//         CheckSpec:检查X是否符合题目要求.
//         LinearInterpolation:线性内插值函数.
//         SplineInterpolation:二次B样条插值函数(*随后更新*).
//         PrintResult:打印结果与RMSE信息.
// 
// Author :
//         GalaxyCore Inc.
// ******************************************************************************

#define			_TEST_FUNCTION_			(F08)

int F00(int x)
{
	return (x);
}

int F01(int x)
{
	return (x * x);
}

int F02(int x)
{
	return (int)(sqrt((double)(x)));
}

int F03(int x)
{
	return (int)(pow((double)(x),2.2));
}

int F04(int x)
{
	return (int)(pow((double)(x),0.4545));
}

int F05(int x)
{
	return (int)(x & 0x04);
}

int F06(int x)
{
	return (int)(x & 0x03);
}

int F07(int x)
{
	return (int)(128+128*sin((double)(x)));
}

int F08(int x)
{
	return (int)(128+128*cos((double)(x)));
}

int F09(int x)
{
	return (int)(256*log(1+(double)(x)));
}

void PrintResult(int *X_FULL, int *Y_FULL, int *Y_INTP, int *X, int RANGE_FULL)
{
	double S = 0;
	int i = 0,j = 0;
	printf("X_FULL\t\tY_FULL\t\tY_INTP\n");
	for(i = 0; i < RANGE_FULL; i++)
	{
		if(i == X[j])
		{
			printf("%6d\t\t",X[j]);
			j = j + 1;
		}
		else if(i > X[j])
		{
			printf("%6d\t\t",X[j]);
			j = j + 1;
		}
		else //(i < X[j])
		{
			printf("      \t\t");
		}
		printf("%6d\t\t",Y_FULL[i]);
		printf("%6d\n",Y_INTP[i]);
		S = S + (Y_FULL[i] - Y_INTP[i]) * (Y_FULL[i] - Y_INTP[i]);
	}
	S = sqrt(S / RANGE_FULL);
	printf("RMSE = %lf\n",S);
}

int CheckSpec(int *X, int L, int RANGE_FULL)
{
	int i,j;
	int isBothEnds = 1;
	int isIncrease = 1;
	int isPowerTwo = 1;
	if((X[0] != 0) || (X[L-1] != RANGE_FULL - 1))
	{
		printf("BothEnds Fail\n");
		isBothEnds = 0;
	}
	for(i = 0; i < L - 1; i++)
	{
		if(X[i] >= X[i+1])
		{
			printf("Increase Fail\n");
			isIncrease = 0;
		}
		j = X[i+1] - X[i];
		if(j & (j - 1) != 0)
		{
			printf("PowerTwo Fail\n");
			isPowerTwo = 0;
		}
	}
	if(isBothEnds & isIncrease & isPowerTwo == 1)
	{
		printf("CheckSpec Pass\n");
		return 0;
	}
	else
	{
		printf("CheckSpec Fail\n");
		return 1;
	}

	return 0;
}

void LinearInterpolation(int *Y_INTP, int *X, int *Y, int *X_FULL, int L, int RANGE_FULL)
{
	// Y_INTP[RANGE_FULL] = interpolation(X[L],Y[L],X_FULL[RANGE_FULL]);
	int i,j;
	int left = 0;
	int right = 1;
	for(i = 0; i < RANGE_FULL; i++)
	{
		if(i > X[right])
		{
			left = left + 1;
			right = right + 1;
		}
		if(X[right] - X[left] == 0)
		{
			Y_INTP[i] = Y[right];
		}
		else
		{
			Y_INTP[i] = (Y[right] * (i - X[left]) + Y[left] * (X[right] - i)) / (X[right] - X[left]);
		}
	}

	return;
}

void main()
{
	int i,j;
	int CheckResult;
	int L = 16;
	int BIT_FULL = 4;
	int RANGE_FULL = (1 << BIT_FULL);
	int *X_FULL = (int *)malloc(sizeof(int) * RANGE_FULL);
	int *Y_FULL = (int *)malloc(sizeof(int) * RANGE_FULL);
	int *X      = (int *)malloc(sizeof(int) * L);
	int *Y      = (int *)malloc(sizeof(int) * L);
	int *Y_INTP = (int *)malloc(sizeof(int) * RANGE_FULL);

	/* ****** Curve Set ****** */
	for(i = 0; i < RANGE_FULL; i++)
	{
		X_FULL[i] = i;
		Y_FULL[i] = _TEST_FUNCTION_(X_FULL[i]);
	}
	
	/* ****** Your Method Here ****** */
	// YourMethod(X, Y_FULL, L, RANGE_FULL);
	X[0] = 0;
	X[1] = 1;
	X[2] = 2;
	X[3] = 3;
	X[4] = 4;
	X[5] = 5;
	X[6] = 6;
	X[7] = 7;
	X[8] = 8;
	X[9] = 9;
	X[10] = 10;
	X[11] = 11;
	X[12] = 12;
	X[13] = 13;
	X[14] = 14;
	X[15] = 15;

	/* ****** Interpolation ****** */
	CheckResult = CheckSpec(X, L, RANGE_FULL);
	for(i = 0; i < L; i++)
	{
		Y[i] = _TEST_FUNCTION_(X[i]);
	}
	LinearInterpolation(Y_INTP, X, Y, X_FULL, L, RANGE_FULL);
//	SplineInterpolation(Y_INTP, X, Y, X_FULL, L, RANGE_FULL);

	/* ****** Information Output ****** */
	PrintResult(X_FULL, Y_FULL, Y_INTP, X, RANGE_FULL);

	getchar();
	return;
}