// File: practice.cxx
// Written by Michael and Allison
// Demonstrates the bisection method to find a root to an equation.

//----------------------------------------------------------------------------
#include <cstdlib>
#include <iostream>
#include <cassert>
using namespace std;
const double MYSTERY = 92.337;
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// Prototypes:

// This function finds a value that is within EPSILON for a root of F.
// Preconditoin: F(low_x) <= 0 and F(high_x) >= 0.
const double EPSILON = 1e-10;
#define F(x) (3*x*x - 2*x - 9)
double f(double x);

double bisection(double low_x, double high_x);

double bisection(
    double func(double x), // func is a function that we want to find a root for 
    double low_x,          // func(low_x) <= 0 
    double high_x          // func (high_x) >= 0
    );
    
double bisection_search(double low_x, double high_x);
bool mystery_number(double a);
double linear_search();

double integral(
    double func(double x), // func is a function that we want to integrate 
    double a,              // lower bound
    double b,              // higher bound
    int rand_count         // how many random x's we look at
    );
//----------------------------------------------------------------------------


//----------------------------------------------------------------------------
int main()
{
    //cout << "One root of F is " << bisection(0.0, 1000.0) << endl;
    //cout << "One root of sin is " << bisection(sin, 4.0, 2.0) << endl;

    cout << "Integral of function f is " << integral(f, 0.0, 1.0, 1000) << endl;

    //cout << "bisection_search result is: " << bisection_search(0.0, 100.0) << endl;
    //cout << "linear_search result is: " << linear_search() << endl;

    return EXIT_SUCCESS;
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
double bisection(double low_x, double high_x)
{
    double mid_x;

    assert(F(low_x) <= 0);
    assert(F(high_x) >= 0);
    
    while (abs(high_x - low_x) > EPSILON)
    {
	mid_x = (high_x + low_x)/2;
	if (F(mid_x) < 0)
	{
	    low_x = mid_x;
	}
	else
	{
	    high_x = mid_x;
	}
    }
    return (high_x + low_x)/2;
}
//----------------------------------------------------------------------------

double bisection(
    double func(double x), // func is a function that we want to find a root for 
    double low_x,          // func(low_x) <= 0 
    double high_x          // func (high_x) >= 0
    )
{
    double mid_x;

    assert(func(low_x) <= 0);
    assert(func(high_x) >= 0);
    
    while (abs(high_x - low_x) > EPSILON)
    {
	mid_x = (high_x + low_x)/2;
	if (func(mid_x) < 0)
	{
	    low_x = mid_x;
	}
	else
	{
	    high_x = mid_x;
	}
    }
    return (high_x + low_x)/2;
}



//----------------------------------------------------------------------------
double bisection_search(double low_x, double high_x)
{
    double mid_x;
    int count = 0;
    assert(!mystery_number(low_x));
    assert(mystery_number(high_x));
    
    while (abs(high_x - low_x) > EPSILON)
    {
	cout << count << " " << low_x << " " << high_x
	     << " " << abs(high_x - low_x) << endl;
	mid_x = (high_x + low_x)/2;
	if (mystery_number(mid_x))
	{
	    high_x = mid_x;
	}
	else
	{
	    low_x = mid_x;
	}
	++ count;
    }
    cout << "This is how many times: " << count << endl;    
    return (high_x + low_x)/2;
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
double linear_search()
{
    double ans;
    int count = 0;
    for (ans = 0; !mystery_number(ans); ans += 0.1)
    {
	++count;
    }
    cout << "This is how many times: " << count << endl;
    return ans;
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
bool mystery_number(double x)
{
    return (x > MYSTERY); // MYSTERY is a global named constant between
                          // 0.0 and 100.0!
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
double integral(
    double func(double x), // func is a function that we want to integrate 
    double a,              // lower bound
    double b,              // higher bound
    int rand_count         // how many random x's we look at
    )
{
    double sum = 0;
    double ans;
    double x, y;
    int i;
    for (i = 0; i < rand_count; ++i)
    {
	x = a + (double(rand())/RAND_MAX)*(b-a);
	y = func(x);
	sum += y;
    }
    ans = (sum/rand_count)*(b-a);
    return ans;
}
//----------------------------------------------------------------------------

double f(double x)
{
    return x;
}