#include <iostream>


//lab4 - interpolacja newtona
//Michal J. Sidor gr 3.5

using namespace std;

struct data
{
    double x,f;
};

int wprowadz(int n, data *tab);
void wyswietl(int n, data *tab);
void insertSort(int n, data *tab);
int interpolacja(int n, data *tab);


int main()
{
    int n;
    cout<<"Ile wezlow?: "; cin>>n;
    data *tab = new data[n];
    if (wprowadz(n, tab) == 1)
    {
        insertSort(n, tab);
        wyswietl(n, tab);
        interpolacja(n, tab);
    }

    return 0;
}


int wprowadz(int n, data *tab)
{
    cout<<endl<<"Podawanie danych: (wezly musza byc od siebie rozne)"<<endl;
    for (int i=0; i<n; i++)
    {
        cout<<"Podaj x"<<i<<": "; cin>>tab[i].x;
        for (int j=i; j>0; j--)
        {
            if (tab[i].x == tab[j-1].x)
            {
               cout<<"Nie spelniono warunkow przy wprowadzaniu wezlow, przerywam dzialanie programu..."<<endl;
               delete tab;
               return 0;
            }
        }
        cout<<"Podaj f"<<i<<": "; cin>>tab[i].f;
    }
    cout<<endl;
    return 1;
}

void wyswietl(int n, data *tab)
{
    for (int i=0; i<n; i++)
    {
        cout<<"x"<<i<<" = "<<tab[i].x<<"; f"<<i<<" = "<<tab[i].f<<endl;
    }
}

void insertSort(int n, data *tab)
{
    int j;
    double temp;
    for (int i=1; i<=n-1; i++)
    {
        j=i;
        while (tab[j].x<tab[j-1].x and j>0)
        {
            temp = tab[j-1].x;
            tab[j-1].x = tab[j].x;
            tab[j].x = temp;
            temp = tab[j-1].f;
            tab[j-1].f = tab[j].f;
            tab[j].f = temp;
            j--;
        }
    }
}

int interpolacja(int n, data *tab)
{
    float szukana;
    double R[n],wynik,mnoznik=1;
    cout<<endl<<"Podaj x dla ktorego szukasz wartosci (musi byc zawarty w przedziale pomiedzy maksymalnym a minimalnym wezlem): ";
    cin>>szukana;
    if (szukana >= tab[0].x and szukana <= tab[n-1].x)
    {
        for (int i=0; i<n; i++)
        {
            R[i] = tab[i].f;
        }

        for (int k=1; k<n; k++)
        {
            for (int j=n-1; j>=k; j--)
            {
                R[j] = (R[j] - R[j-1]) / (tab[j].x - tab[j-k].x);
            }
        }
    cout<<endl<<"Wartosci f[...]:"<<endl<<"**********************"<<endl;
    for (int i=0; i<n; i++)
    {
        cout<<"R["<<i<<"] = "<<R[i]<<endl;
    }

    for (int i=0; i<n; i++)
    {
         wynik+=R[i]*mnoznik;
         mnoznik=mnoznik*(szukana-tab[i].x);
    }
    cout<<"*********************************"<<endl;
    cout<<"Wg interpolacji Newtona dla funkcji o podanych wezlach f(";
    cout<<szukana;
    cout<<") = "<<wynik<<endl;

    }
    else
    {
        cout<<"Nie spelniono warunku przy podawaniu szukanego x, przerywam dzialanie programu..."<<endl;
        delete tab;
        return 0;
    }

}