#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cmath>
using namespace std;

//Global variables
vector<float> yActual;
vector<float> x;
int size;
//Prototypes

float RandomFloat(float a, float b) {
    float random = ((float) rand()) / (float) RAND_MAX;
    float diff = b - a;
    float r = random * diff;
    return a + r;
}
class Chromosome
{

public:
    vector<float> bits; //co-efficients
    vector<float> yPredicted;
    float MSE;
    float getMSE(){return MSE;}
    Chromosome()
    {
        for(int i = 0 ; i < x.size(); i++)
            yPredicted.push_back(0);
        for(int i = 0 ; i < size; i++)
            bits.push_back(0);

        randomFill();
        //calculateYPredicted();
        //calculateMSE();
    }
    void setBits(vector<int> v)
    {
        for(int i = 0 ; i < size; i++)
            bits[i] = v[i];
    }
    vector<float> getBits(){return bits;}
    void fill()
    {
        //bits.clear();
        cout << "Enter Bits Of  Chromosome" << endl;
        for(int i = 0; i < size; i++)
        {
            float num;
            cin >> num;
            bits[i] = num;
        }

        calculateYPredicted();
        calculateMSE();
    }
    void randomFill()
    {
        for(int i = 0; i < size; i++)
        {
            float num = RandomFloat(-10.0,10.0);
            /*float num = rand()%10;
            if(rand()%2 == 1)
                num -= 2 * num;
                */
            bits[i] = num;
        }

        calculateYPredicted();
        calculateMSE();
    }
    void reRandomFill()
    {
        for(int i = 0; i < size; i++)
        {
            float num = RandomFloat(-10.0,10.0);
            bits[i] = num;
        }
        calculateYPredicted();
        calculateMSE();
    }
    //Fill vector of y predicted using the equation below
    void calculateYPredicted()
    {
        //F(X) = y = a0 + a1 x^1 + a2 x^2 + a3 x^3
        for(int k = 0 ; k < yPredicted.size(); k++)
        {
            float y =0;
            for(int i = 0 ; i < bits.size() ; i++)
            {
                float degreedX = x[k];
                degreedX = pow(degreedX,i);
                ////   x^1   x^2   x^3
                y += ( bits[i] * degreedX );
            }
            yPredicted[k] = y;
        }
    }
    //Calculating Mean Square Error using mse equation
    void calculateMSE()
    {
        float error = 0;
        for(int i = 0 ; i < yPredicted.size(); i++)
            error += pow( (yPredicted[i] - yActual[i]) ,2);
        error = error/yPredicted.size();
        MSE = error;
    }
    void printBits()
    {
        for(int i = 0; i < bits.size(); i++)
            cout << bits[i] << " " ;
    }
    void printFullChromosome()
    {
        for(int i = 0; i < bits.size(); i++)
            cout << bits[i] << " ";
        cout << endl << "Mean Square Error : " << MSE << endl;

    }

    Chromosome setChromosome(Chromosome c)
    {
        for(int i = 0 ; i < bits.size(); i++)
            (*this).bits[i] = c.bits[i];
        for(int i = 0 ; i < bits.size(); i++)
            (*this).yPredicted[i] = c.yPredicted[i];

        (*this).MSE = c.MSE;
    }
    /*
    Try filling chromosome yourself
    void trying()
    {
        fill();
        printBits();
        cout << endl << "y predicted " << endl;
        for(int i = 0 ; i < yPredicted.size();i++ )
            cout << yPredicted[i] << " ";
        cout << endl;
        cout << endl << "y actual " << endl;
        for(int i = 0 ; i < yActual.size(); i++)
            cout << yActual[i] << " " ;
        cout << endl;
    }
    */
};

vector<float> createCumulativeTable( vector<Chromosome> population)
{
    vector<float> CumMSE;
    float temp;

    CumMSE.push_back(population[0].MSE);

    temp = CumMSE[0];

    for(int i=1; i < population.size(); i++)
    {
        CumMSE.push_back(population[i].MSE + temp);

        temp = CumMSE[i];

    }
    return CumMSE;
}
Chromosome mutation(Chromosome ch);
Chromosome crossOver(Chromosome ch1,Chromosome ch2)
{
    Chromosome child1,child2;
    //vector<int> ChoosenVector;

    int splitSize = rand()%ch1.bits.size();


    while(splitSize == 0 || splitSize == ch1.bits.size() - 1)
        splitSize = rand()%ch1.bits.size();

    /*for(int i = 0; i < Choosen.size(); i++)
    {
        ChoosenVector.push_back(Choosen[i]);
    }*/

    cout << "splitSize : " << splitSize << endl << endl;

        //cout << "LOL" << endl;


        for(int k = 0; k < splitSize; k++)
        {
            child1.bits.push_back(ch1.bits[k]) ;
            child2.bits.push_back(ch2.bits[k]) ;
        }

        for(int k = splitSize; k <size; k++)
        {
            child1.bits.push_back(ch2.bits[k]);
            child2.bits.push_back(ch1.bits[k]);
        }
//        cout << "-------------------------" << endl;
//        cout << "r : " << r <<endl;
//        cout << "r2 : " << r2 << endl;


//        cout << "~~~~~~~~~~~~~~~~~" << endl;
//        cout << "Child 1 : ";
//        for(int q = 0; q < ch1.size; q++)
//        {
//            cout << ch1.bits[q] << ",";
//        }
//        cout << endl;
//
//        cout << "Child 2 : ";
//        for(int q = 0; q < ch2.size; q++)
//        {
//            cout << ch2.bits[q] << ",";
//        }
//        cout << endl;
//        cout << "~~~~~~~~~~~~~~~~~" << endl;
//        cout << endl;

        child1 = mutation(child1);
        child2 = mutation(child2);

        child1.calculateYPredicted();
        child1.calculateMSE();

        child2.calculateYPredicted();
        child2.calculateMSE();
//
        if(child1.MSE > child2.MSE)
        {
        return child1;
        }
        else
        {
            return child2;

        }





//        cout << "~~~~~~~~~~~~~~~~~" << endl;
//        cout << "Child 1 after mutation : ";
//        for(int q = 0; q < ch1.size; q++)
//        {
//            cout << ch1.bits[q] << ",";
//        }
//        cout << endl;
//
//        cout << "Child 2 after mutation : ";
//        for(int q = 0; q < ch2.size; q++)
//        {
//            cout << ch2.bits[q] << ",";
//        }
//        cout << endl;
//        cout << "~~~~~~~~~~~~~~~~~" << endl;
//        cout << endl;


}
//---------------------------------------------------------//
Chromosome mutation(Chromosome ch)
{

    int r_int;
    float r_float,UB = 10.0,LB = -10.0,DU,DL;

    r_float = (rand()%10 + 1.0)/10.0;
    r_int = rand()%size;

    cout << "r_float : " << r_float << endl;
    cout << "r_int : " << r_int << endl;
    cout << "--------------" << endl << endl;;

    DU = UB - ch.bits[r_int];
    DL = ch.bits[r_int] - LB;

    cout << "DU : " << DU << endl;
    cout << "DL : " << DL << endl;

    if(r_float <= 0.5)
    {
        double r_int1,r_int2;
        r_int1 = RandomFloat(0.0,DU);

        cout << "r_int1 : " << r_int1 << endl << endl;;

        cout << "Bit : " << ch.bits[r_int] << endl;
        ch.bits[r_int] += r_int1;

        cout << "Bit : " << ch.bits[r_int] << endl;

        cout << "---------------22222" << endl;

        return ch;

    }
    else
    {

        double r_int1,r_int2;
        r_int1 = RandomFloat(0.0,DL);

        cout << "r_int1 : " << r_int1 << endl << endl;

        cout << "Bit : " << ch.bits[r_int] << endl;
        ch.bits[r_int] -= r_int1;
        cout << "Bit : " << ch.bits[r_int] << endl;

        cout << "---------------1111111" << endl;

        return ch;
    }



}
//-------------------------------------------------------//
void printTable(vector<Chromosome> population, vector<float>cumTable)
{
    for(int i = 0; i < population.size(); i++)
    {
        cout << "[" ;
        population[i].printBits();
        cout << "]      " << population[i].MSE << "\t|" << "\t" << cumTable[i] << endl;
    }
    cout << endl;

    //cout << "Random number: " << r << "\nExist in index " << index << endl;
}
void Compute(int popSize, int numOfIterations )
{
    vector<Chromosome> population;
    Chromosome bestSoFar;
    for(int i = 0; i < popSize; i++)
    {
        Chromosome c;
        //Keep our best
        if(i == 0)
            bestSoFar=c;
        else if(bestSoFar.getMSE() < c.getMSE() )
            bestSoFar.setChromosome(c);
        population.push_back(c);
    }
    /*
    for(int i = 0 ; i < population.size(); i++)
        cout << population[i].MSE << endl;
    */
    vector<float> cumTable = createCumulativeTable(population);
    //printTable(population,cumTable);

    int counter = 0;
    while(counter < numOfIterations)
    {
        for(int i = 0 ; i < popSize; i++)
        {
            Chromosome c1,c2;
            int index1,index2;

            float r = RandomFloat(0,cumTable.back());

            for(int k = cumTable.size()-1 ; k > 0; k--)
                if( r < cumTable[k] && r >= cumTable[k-1])
                {
                    index1 = k;
                    break;
                }
            c1.setChromosome(population[index1]);

            float r2 = RandomFloat(0,cumTable.back());
            for(int k = cumTable.size()-1 ; k > 0; k--)
                if( r2 < cumTable[k] && r2 >= cumTable[k-1])
                {
                    index2 = k;
                    if( index1 == index2)
                    {
                        r2 = RandomFloat(0,cumTable.back());
                        k = cumTable.size()-1;
                    }
                    else
                        break;
                }
            c2.setChromosome(population[index2]);
            Chromosome newChild;

            if(size >2)
                newChild = crossOver(c1 , c2);

            //Send c1, c2, newChild to cross over which will make 2 children. Choose best of them and return it to mutation then replace it with it's index
            //in population vector.
/*
            sort( indices.begin(), indices.end() );
            indices.erase( unique( indices.begin(), indices.end() ), indices.end() );

            double r = (rand()%10 + 1.0)/10.0;

            if(r >= 0.4 && r <= 0.7)
                crossOver(population,indices,maxWeight,bestSoFar,weights,benefits);


*/
            if(bestSoFar.MSE > newChild.MSE)
                bestSoFar.setChromosome(newChild);
            population[i].setChromosome(newChild);
        }
        counter++;
    }
    cout << endl << "And best solution the algorithm reached : ";
    bestSoFar.printFullChromosome();
    cout << endl;
}

int main()
{
    srand(time(0));
    cout << "Enter Number of points" << endl;
    int numOfPoints;
    cin >> numOfPoints;

    cout << "Enter Requested degree" << endl;
    int requestedDegree;
    cin >> requestedDegree;
    size = requestedDegree+1;

    for(int i = 0 ; i < numOfPoints; i++)
    {
        float tempX,tempY;
        cout << "Enter (X" << i << ",Y" << i << ")" << endl;
        cin >> tempX >> tempY;
        x.push_back(tempX);
        yActual.push_back(tempY);
    }

    cout << "Enter population size " ;
    int popSize;
    cin >> popSize;

    cout << "Enter number of iterations " ;
    int numOfIterations;
    cin >> numOfIterations;

    Compute(popSize,numOfIterations);
    /*
    Chromosome c;
    c.printFullChromosome();
    */
    return 0;
}