#include <iostream>
#include <assert.h>
#include <vector>
#include <math.h>

using namespace std;

#define eps 1e-15

#define ILOSC_PODPRZEDZIALOW_POSZUKIWAN_MZ 1e7
#define PRZEDZIAL_WASKI_PRAWOPODOBNIE_ASYMPTOTA 1e-20
#define MAX_ILOSC_ITERACJI 100000

// krance przedzialu poszukiwan mz
#define A -7
#define B 7

double FX(double x)
{
    //return log(x+2.0)-2*pow(x,2.0)+1;
    //return pow(x,3.0)-2*x+2;
    //return 1/x;
    return -5*pow(x,3.0)+8*pow(x,2.0)+3*x-1;

    //return tan(x);
}

double FXd(double x)
{
    return -15*x*x+16*x+3;
    //return 1+tan(x)*tan(x);
}


struct solution_t
{
    double solution;
    int iter;
    solution_t(double solution, int iter)
    {
        solution_t::solution = solution;
        solution_t::iter = iter;
    }
};

int bisekcja(double a, double b, double *solution, double fx(double), double fxd(double))
{
    assert( fx(a)*fx(b) < 0 );

    double x = a;
    double x1;
    for(int i=0; i<MAX_ILOSC_ITERACJI; i++)
    {
        if (abs(a-b) < PRZEDZIAL_WASKI_PRAWOPODOBNIE_ASYMPTOTA)
            return -1;

        x1 = (a+b) /2;
        if ( abs( fx(x1) ) < eps )
        {
            *solution = x1;
            return i;
        }

        // dzielenie przedzialu
        if ( fx(a)*fx(x1) < 0)
            b = x1;
        else if ( fx(x1)*fx(b) < 0)
            a = x1;
        x = x1;
    }
    //incase?
    return -1;
}

int metoda_newtona(double a, double b, double *solution, double fx(double), double fxd(double))
{
    double x = (a+b)/2;
    double x1;
    for(int i=0; i<MAX_ILOSC_ITERACJI; i++)
    {
        x1 = x - fx(x)/fxd(x);

        if (abs(x-x1) < PRZEDZIAL_WASKI_PRAWOPODOBNIE_ASYMPTOTA)
            return -1;
        if (abs( fx(x1) ) < eps)
        {
            *solution = x1;
            return i;
        }
        x = x1;
        if (x1 < a || x1 > b)
            return -1;
    }
    return -1;
}

double lokalizacja_i_znajdowanie_mz(double a, double b, vector<solution_t> &out,
                                  int metoda(double,double, double*,double fx(double), double fxd(double)),
                                  double fx(double), double fxd(double))
{
    double szerokosc = b-a;
    double krok = szerokosc/ILOSC_PODPRZEDZIALOW_POSZUKIWAN_MZ;
    double val = a;
    double rozwiazanie;
    while(val < b)
    {
        // rozne znaki
        if ( fx(val)*fx(val + krok) < 0 )
        {
            int ret = metoda(val, val + krok, &rozwiazanie, fx, fxd);
            if (ret >= 0 )
            {
                // dodawanie tylko roznych rozwiazan
                //if (out.size()>0 && abs(out[out.size()-1].solution - rozwiazanie) > eps
                //  || out.size() == 0)
                out.push_back(solution_t(rozwiazanie, ret));
            }
        }
        val = val + krok;
    }
    return krok;
}

int main()
{
    vector<solution_t> rozwiazania;
    double szerokosc_przedzialu = lokalizacja_i_znajdowanie_mz(A, B, rozwiazania, bisekcja, FX, FXd);

    cout << "przedzial (" << A << "," << B
        << ") podzielony na podprzedzialy poszukiwan o szerokosci: " << szerokosc_przedzialu << endl;
    cout << "bisekcja:\n";
    for(int i=0; i<rozwiazania.size(); i++)
        cout << "x" << i << ": " << rozwiazania[i].solution << ", iter: " << rozwiazania[i].iter << endl;

    rozwiazania.clear();
    lokalizacja_i_znajdowanie_mz(A, B, rozwiazania, metoda_newtona, FX, FXd);

    cout << "\nmetoda_newtona:\n";
    for(int i=0; i<rozwiazania.size(); i++)
        cout << "x" << i << ": " << rozwiazania[i].solution << ", iter: " << rozwiazania[i].iter << endl;

    return 0;
}