#include <iostream>
#include <iomanip>
#include <fstream>
#include <math.h>

using namespace std;

// Deklarationen
bool debug = false;
bool plot = false;
float** punkte;
float** polynome;
ifstream quelldatei;
ofstream zieldatei;
int zeilen = 0;

void punkte_ausgabe();


void punkte_ausgabe()
{
	
	for(int i=0;i < zeilen;i++)
	{
		cout << "x" << i+1 << "=" << punkte[i][0] << "  y"<< i+1 << "=" << punkte[i][1] << endl;
	}
	
}

int main()
{
	float tempx = 0,tempy = 0;
	char puffer[255] = "";
	cout << "Aufgabe 16: Polynom-Interpolation\n";
	
	cout << "Sollen Polynommatrizen angezeigt werden? (j/n) [n]: ";
	cin.getline(puffer,sizeof(puffer),'\n');
	if((string)puffer == "j")
	{
		debug = true;
		cout << "Ok, Polynommatrizen werden angezeigt...\n";
	}
	
	cout << "Soll das Ergebnis am Ende graphisch angezeigt werden? (setzt die Binary 'gnuplot' voraus) (j/n) [n]: ";
	cin.getline(puffer,sizeof(puffer),'\n');
	if((string)puffer == "j")
	{
	    plot=true;
	}
	
	//oeffnen & einlesen der Datei
	quelldatei.open("a16-interpol.dat",ios::in);
	
	
	if(!quelldatei)
	{
		cerr << "Fehler: Die Quelldatei konnte nicht geoeffnet werden.\n";
		return(1);
	}
	
	// Anzahl Zeilen herausfinden
	while(quelldatei >> tempx >> tempy) zeilen++;
	// An den Dateianfang springen
	quelldatei.clear();
	quelldatei.seekg(0);
	
	// Feld initialisieren
	punkte = new float*[zeilen];
	int zeiletemp = 0;
	while((quelldatei >>  tempx >>  tempy))
	{	
		punkte[zeiletemp] = new float[2];
		punkte[zeiletemp][0] = tempx;
		punkte[zeiletemp][1] = tempy;
		zeiletemp++;
		
	}
	quelldatei.close();
	
	//punkte_ausgabe();
	
	// Zieldatei oeffnen
	zieldatei.open("a16-interpol-res.dat",ios::out);
	if(!zieldatei)
	{
		cerr << "Fehler: Die Zieldatei konnte nicht geoeffnet werden.\n";
		return(1);
	}
	
	// Initialisierung des Polynomfeldes
	polynome = new float*[zeilen];
	for(int i=0;i< zeilen;i++) polynome[i] = new float[zeilen];
	
	// Einlesen & schreiben der neuen Punkte
	cout << "Bitte Punkte zum interpolieren eingeben. Mit 0 Eingabe beenden.\n";
	float eingabe=0, ausgabe = 0;
	cin >> eingabe;
	while(eingabe !=0)
	{
		zieldatei << eingabe << " ";
		for(int i=0;i< zeilen;i++)
		{
			polynome[i][0] = punkte[i][1];
			for(int j=1;j <= i;j++)
			{
				polynome[i][j] = (((eingabe - punkte[i-j][0])* polynome[i][j-1])-((eingabe - punkte[i][0])* polynome[i-1][j-1]))/(punkte[i][0] - punkte[i-j][0]);
			}
		}
		zieldatei << polynome[zeilen -1][zeilen-1] << endl;
		
		// Ausgabe der Polynomtabelle
		if(debug)
		{
			for(int i=0;i< zeilen;i++)
			{
				for(int j=0;j< zeilen;j++)
				{
					cout << setw(8) << setprecision(5) << polynome[i][j] << " ";
				}
				cout << endl;
			}
		}
		
		// Ausgabe des Ergebnispaars:
		cout << "Ergebnis: (x, f(x)) : (" << eingabe << "," << polynome[zeilen -1][zeilen-1] << ")" << endl;
		cin >> eingabe;
	}
	zieldatei.close();

	

	if(plot) system("gnuplot -persist a16.gnu");
	return(0);
}