#include <iostream>
#include <utility>
#include <functional>
#include <vector>
#include <cmath>
#include <stdexcept>
#include <algorithm>
#define EPSILON 0,00001

double Koeficijenti (int i, int vel, int red, std::vector<std::pair<double, double>>cvorovi);

std::function <double(double)> BaricentricnaInterpolacija(std::vector<std::pair<double, double>>cvorovi, int red){

        if (red < 0 || red > cvorovi.size()) throw std::domain_error ("Nedozvoljen red");

        for (int i = 0; i < cvorovi.size(); i++){
            for (int j = 0; j < cvorovi.size(); j++){

                if (j == i) continue;
                else if (fabs(cvorovi[i].first - cvorovi[j].first) < EPSILON) throw std::domain_error ("Neispravni cvorovi");
        }
    }

    return [cvorovi, red] (double x){

        int vel = cvorovi.size();
        double brojnici(0), nazivnici(0);
        double xi(0), yi(0), w(0);

        for (int i = 0; i < vel; i++){

            xi = cvorovi[i].first;
            yi = cvorovi[i].second;

            if (fabs(xi - x) < EPSILON) return yi;

            // dio sa tezinskim
            w = Koeficijenti(i, vel, red, cvorovi);

            brojnici += ( w / (x - xi)) * yi;
            nazivnici += w / (x - xi);
        }

        return brojnici / nazivnici;
    };
}

double Koeficijenti (int i, int vel, int red, std::vector<std::pair<double, double>>cvorovi){

    int gore = std::min(i+1, vel - red);
    int donja = std::max(1, i+1 - red);
    double p(1), suma(0);
    double xi = cvorovi.at(i).first, xj;
        for (int k = donja; k < gore; k++ ){
         p = 1;
         for (int j = k; j < k + red; j++){
             if (j != i){
                 xj = cvorovi.at(j).first;
                 p *= 1 / (xi - xj);
             }

         }
        double koef = std::pow (-1, k - 1);
        suma += koef * p;
    }
return suma;
}


std::function <double(double)> BaricentricnaInterpolacija (std::function<double(double)> fja, double xminimum, double xmaximum, double deltax, double red){

    std::vector <std::pair <double, double>> povratni;

    if (xminimum > xmaximum || deltax <= 0) throw std::domain_error ("Nekorektni parametri");

    for(int i = xminimum; i <= xmaximum;  i+=deltax){
        povratni.push_back(std::make_pair(i, fja(i)));
    }

    return BaricentricnaInterpolacija(povratni, red);
}

int main ()
{
    try{
        std::cout << "Odaberite opciju (1 - unos cvorova, 2 - aproksimacija): ";
        int izabir;
        std::cin >> izabir;

        std::cout << "Unesite broj cvorova: ";
        int broj_cvorova;
        std::cin >> broj_cvorova;

        std::vector<std::pair<double, double>> vektor(broj_cvorova);
        double x,y;
        for (int i = 0 ; i <broj_cvorova; i++){
            std::cin >> x >> y;
            vektor[i] = std::make_pair (x,y);
        }

         if (izabir == 1){

        std::cout << "Unesite red interpolacije: ";
        int red_interpolacije;
        std::cin >> red_interpolacije;

        auto f (BaricentricnaInterpolacija(vektor, red_interpolacije));

        while(true){
            std::cout << "Unesite argument (ili ""kraj"" za kraj): ";
             double argument;
            std::cin >> argument;
            if (!std::cin) break;
            std::cout << "f (" << argument << ") = " << f(argument) ;
        }
    }

    if (izabir == 2){

        std::cout << "Unesite krajeve intervala i korak: ";
        double pocetak_intervala, kraj_intervala, korak;
        std::cin >> pocetak_intervala >> kraj_intervala >> korak;

        std::cout << "Unesite red interpolacije: ";
        int red_interpolacije;
        std::cin >> red_interpolacije;
        auto f(BaricentricnaInterpolacija(vektor, red_interpolacije));
        auto f1 (BaricentricnaInterpolacija(f,pocetak_intervala, kraj_intervala,korak, red_interpolacije));
        while(true){
            std::cout << "Unesite argument (ili ""kraj"" za kraj): ";
            double argument;
            std::cin >> argument;
            if (!std::cin) break;
            std::cout << "f (" << argument << ") = " << f(argument) << " fapprox (" << argument << ") = " << f1(argument);
        }

    }
}

catch(std::domain_error izuzetak){
    std::cout << izuzetak.what();
}
    return 0;
}