#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<math.h>
#include <vector>
#include <Windows.h>
#include <stdlib.h>

using namespace std;

const double PI = 3.1415926535897932384626433832795;

typedef double (*functiontype)(double x);

typedef struct Node
{
    double x,y;
}Node;

typedef struct Interval
{
    double InitialNode,EndNode;
}Interval;

int Factorial(int n)
{ // Факториал
    int x = 1;
    for (int i = 1; i <= n; i++)
    {
        x *= i;
    }
    return x;
}

double sinus(double x)
{ // Синус
    return sin(x);
}

double xv10(double x)
{ // x^10
    return double(powl(x,10));
}

double exponenta(double x)
{ // Экспонента
    return exp(x);
}

void ValueUniformTable(functiontype *f, Node *Array, double Initial, double End, int Count)
{ // Создание равномерной таблицы значений
    double step = abs(Initial - End) / (Count - 1);
    Array[0].x = Initial;
    Array[0].y = (*f)(Array[0].x);
    for (int i = 1; i < Count; i++)
    {
        Array[i].x = Array[i-1].x + step;
        Array[i].y = (*f)(Array[i].x);
    }
}

void ValueChebyshevTable(functiontype *f, Node *Array, double Initial, double End, int Count)
{ // Создание таблицы Чебышевских значений
    for (int i = 0; i < Count; i++)
    {
        Array[i].x = ((End + Initial) / 2) + ((End - Initial) / 2) * cos(((2 * i + 1) * PI) / (2 * (Count + 1)));
        Array[i].y = (*f)(Array[i].x);
    }
}

double PolynomLG(double x, Node *Array, int Count)
{ // Полином Лагранжа
    double Polynom = 0;
    for (int i = 0; i < Count; i++)
    { // Счетчик по функциям l_i
        double Li = 1;
        for (int j = 0; j < Count; j++)
        { // Счетчик по x_j
            if (i != j) Li *= (x - Array[j].x) / (Array[i].x - Array[j].x);
        }
        Polynom += Array[i].y * Li;
    }
    return Polynom;
}

double PolynomN(double x, Node *Array, int Count)
{
    double Result = Array[0].y;
    for (int i = 1; i < Count; i++)
    {
        double Polynom = 0;
        for (int j = 0; j <= i; j++)
        { // Следующее слагаемое полинома
            double Composition = 1;
            for (int k = 0; k <= i; k++)
            { // Считаем знаменатель разделенной разности
                if (k != j) Composition *= (Array[j].x - Array[k].x);
            }
            Polynom += Array[j].y / Composition; // Считаем разделенную разность
        }
        for (int k = 0; k < i; k++) Polynom *= (x - Array[k].x); // Домножаем разделенную разность на скобки (x-x[0])...(x-x[i-1])
        Result += Polynom; // Полином
    }
    return Result;
}

void CoordinateSystemAndFunction(functiontype *f, double Initial, double End)
{ // Центр 100,200
    HDC hDC = GetDC( GetConsoleWindow( ) ); // Получаем контекст устройства по полученному дескриптору
    HPEN PenWhite = CreatePen( PS_SOLID, 2, RGB(255, 255, 255)); // Задается перо (стиль,ширина,цвет)
    HPEN PenGreen = CreatePen( PS_SOLID, 2, RGB(0, 128, 0));
    SelectObject( hDC, PenWhite ); // Выбираем элемент рисования

    // Рисуем оси координат
    MoveToEx( hDC, 0, 200, NULL ); // Ставим точку горизонталь
    LineTo( hDC, 200, 200 ); // Соеденяем
    MoveToEx( hDC, 100, 100, NULL ); // Ставим точку вертикаль
    LineTo( hDC, 100, 300 ); // Соеденяем

    // График интерполируемой функции
    SelectObject( hDC, PenGreen );
    for (double x = Initial; x <= End; x += 0.01)
    {
        MoveToEx( hDC, 30 * x + 100, -30 * (*f)(x) + 200, NULL ); // 20 - Масштаб
        LineTo( hDC, 30 * x + 100, -30 * (*f)(x) + 200 );
    }
}

void AbsoluteError(functiontype *Function, double Initial, double End, Node *Array, int Count)
{ // Абсолютная погрешность
    HDC hDC = GetDC( GetConsoleWindow( ) ); // Получаем контекст устройства по полученному дескриптору
    HPEN PenBlue = CreatePen( PS_SOLID, 2, RGB(0, 0, 255));
    SelectObject( hDC, PenBlue );
    for (double x = Initial; x <= End; x += 0.01f)
    {
        MoveToEx( hDC, 30 * x + 100, -30 * abs((*Function)(x) - PolynomLG(x,Array,Count)) + 200, NULL ); // 20 - Масштаб
        LineTo( hDC, 30 * x + 100, -30 * abs((*Function)(x) - PolynomLG(x,Array,Count)) + 200 );
    }
}

double DFunc(functiontype *func, double x, int n)
{ // Производная функции
    double h = 0.0001;
    if (n == 1)
    {
        return ((*func)(x + h) - (*func)(x)) / h;
    }
    else
    {
        return (DFunc(func, x + h, n - 1) - DFunc(func, x, n - 1)) / h;
    }
}

double test(functiontype *func, double x, int n, long double h)
{ // Производная функции
    h = 0.0001;
    while (n > 1)
    {
        return (test(func, x + h, n - 1, h / pow(10,-2)) - test(func,x - h,n - 1,h / pow(10,-2))) / 2 * h;
    }
    if (n == 1)
    {
        return ((*func)(x + h) - (*func)(x - h)) / 2 * h;
    }
}

double DividedDifference(int i, Node *Array)
{ // Разделенная разность
    double DD = 0;
    for (int j = 0; j <= i; j++)
    {
        double tmp = 1;
        for (int k = 0; k <= i; k++)
        {
            if (k != j)
                tmp *= Array[j].x - Array[k].x;
        }
        DD += Array[j].y / tmp;
    }
    return DD;
}

double W(double x, int n, Node *Array)
{ // Полином вида: (x - x1) * (x - x2) * ... * (x - xn)
    double w = 1;
    for (int i = 1; i <= n; i++)
    {
        w *= x - Array[i].x;
    }
    return w;
}

void ApproximateError(functiontype *Function, double Initial, double End, Node *Array, int Count)
{ // Приближенная погрешность
    HDC hDC = GetDC( GetConsoleWindow( ) ); // Получаем контекст устройства по полученному дескриптору
    HPEN PenYellow = CreatePen( PS_SOLID, 2, RGB(255, 255, 0));
    SelectObject( hDC, PenYellow );
    for (double x = Initial; x <= End; x += 0.01f)
    {
        MoveToEx( hDC, 30 * x + 100, -30 * abs(exp(End) * W(x,Count,Array) / Factorial(Count + 1)) + 200, NULL ); // 20 - Масштаб
        LineTo( hDC, 30 * x + 100, -30 * abs(exp(End) * W(x,Count,Array) / Factorial(Count + 1)) + 200 );
    }
}

int main()
{
    Interval Interval;
    int CountNodes;
    functiontype Func = &exponenta;

    cout << "Enter the interval: " << endl;
    cin >> Interval.InitialNode >> Interval.EndNode;
    cout << "Enter the number of nodes: " << endl;
    cin >> CountNodes;

    Node *ArrayUniformNodes = new Node[CountNodes]; // Массив с равномерными узлами
    Node *ArrayChebyshevNodes = new Node[CountNodes]; // Массив с Чебышевскими узлами
    ValueUniformTable(&Func,ArrayUniformNodes,Interval.InitialNode,Interval.EndNode,CountNodes); // Заполнение таблицы равномерных значений
    ValueChebyshevTable(&Func,ArrayChebyshevNodes,Interval.InitialNode,Interval.EndNode,CountNodes); // Заполнение таблицы Чебышевских значений

    //cout << "PolynomLG_Uni: " << PolynomLG(1,ArrayUniformNodes,CountNodes) << endl;
    //cout << "PolynomN_Uni: " << PolynomN(1,ArrayUniformNodes,CountNodes) << endl;

    //cout << "PolynomLG_Chb: " << PolynomLG(1,ArrayChebyshevNodes,CountNodes) << endl;
    //cout << "PolynomN_Chb: " << PolynomN(1,ArrayChebyshevNodes,CountNodes) << endl;

    CoordinateSystemAndFunction(&Func,Interval.InitialNode,Interval.EndNode);

    HDC hDC = GetDC( GetConsoleWindow( ) ); // Получаем контекст устройства по полученному дескриптору

    // График Полинома Лагранжа
    /*HPEN PenRed = CreatePen( PS_SOLID, 2, RGB(255, 0, 0));
    SelectObject( hDC, PenRed );
    for (double x = Interval.InitialNode; x <= Interval.EndNode; x += 0.01 )
    {
        MoveToEx( hDC, 30 * x + 100, -30 * PolynomLG(x,ArrayUniformNodes,CountNodes) + 200, NULL ); // 20 - Масштаб
        LineTo( hDC, 30 * x + 100, -30 * PolynomLG(x,ArrayUniformNodes,CountNodes) + 200 );
    }*/

    // График Полинома Ньютона
    HPEN Pentest = CreatePen( PS_SOLID, 2, RGB(255, 0, 255));
    SelectObject( hDC, Pentest );
    for (double x = Interval.InitialNode; x <= Interval.EndNode; x += 0.01 )
    {
        MoveToEx( hDC, 20 * x + 100, -20 * PolynomN(x,ArrayChebyshevNodes,CountNodes) + 200, NULL ); // 20 - Масштаб
        LineTo( hDC, 20 * x + 100, -20 * PolynomN(x,ArrayChebyshevNodes,CountNodes) + 200 );
    }

    // Абсолютная погрешность
    AbsoluteError(&Func,Interval.InitialNode,Interval.EndNode,ArrayUniformNodes,CountNodes);
    // Приближенная погрешность
    ApproximateError(&Func,Interval.InitialNode,Interval.EndNode,ArrayUniformNodes,CountNodes);

    system("pause");
    return 0;
}