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

struct Console
{
    static void Pause()
    {
        string str;
        getline(cin,str);
    }

    static void GetInt(int & n)
    {
        string str;

        while (true)
        {
            getline(cin,str);
            stringstream buffer(str);
            buffer >> n;

            if (buffer && buffer.eof()) break;
            else cout << "please, enter a number: ";
        }
    }
};

struct Solution
{
    vector<int> genes;
    double fitness;

    void Print() const
    {
        cout << "genes: ";

        for (int i=0; i<genes.size(); i++)
            cout << genes[i] << " ";

        cout << "fitness: " << fitness;
    }

    friend ostream & operator<<(ostream & os, const Solution & s) { s.Print(); }

    bool operator<(const Solution & s) const { return fitness>s.fitness; }
    bool operator==(const Solution & s) const { return genes==s.genes; }
};

struct Mutator
{
    virtual void Mutate(Solution & s, Solution & new_s, struct GeneticAlgorithm & ga)=0;
    virtual Mutator * Clone()=0;
    virtual ~Mutator() {}
};

struct Crossbreeder
{
    virtual void Crossbreed(Solution & s1, Solution & s2, Solution & new_s, struct GeneticAlgorithm & ga)=0;
    virtual Crossbreeder * Clone()=0;
    virtual ~Crossbreeder() {}
};

struct FitnessCalculator
{
    virtual void CalculateFitness(Solution & s, struct GeneticAlgorithm & ga)=0;
    virtual FitnessCalculator * Clone()=0;
    virtual ~FitnessCalculator() {}
};

struct GeneticAlgorithm
{
    int N;
    int max_weight;
    int pool_size;
    vector<int> value;
    vector<int> weight;
    vector<Solution> pool;

    Mutator * mutator;
    Crossbreeder * crossbreeder;
    FitnessCalculator * fitness_calculator;

    GeneticAlgorithm()
    {
        mutator=0;
        crossbreeder=0;
        fitness_calculator=0;
    }

    ~GeneticAlgorithm()
    {
        if (mutator) delete mutator;
        if (crossbreeder) delete crossbreeder;
        if (fitness_calculator) delete fitness_calculator;
    }

    void SetMutator(Mutator * new_m)
    {
        if (mutator) delete mutator;
        mutator=new_m;
    }

    void SetCrossbreeder(Crossbreeder * new_c)
    {
        if (crossbreeder) delete crossbreeder;
        crossbreeder=new_c;
    }

    void SetFitnessCalculator(FitnessCalculator * new_fc)
    {
        if (fitness_calculator) delete fitness_calculator;
        fitness_calculator=new_fc;
    }

    void Init()
    {
        cout << "enter N: ";
        Console::GetInt(N);

        value.resize(N);
        weight.resize(N);

        for (int i=0; i<N; i++)
        {
            cout << "enter value for object " << i+1 << ": ";
            Console::GetInt(value[i]);

            cout << "enter weight for object " << i+1 << ": ";
            Console::GetInt(weight[i]);
        }

        cout << "enter max weight: ";
        Console::GetInt(max_weight);

        cout << "enter pool size: ";
        Console::GetInt(pool_size);

        Spawn(pool_size);
        sort(pool.begin(),pool.end());
    }

    void Spawn(int n)
    {
        for(int i=0; i<n; i++)
        {
            Solution new_s;
            new_s.genes.resize(N);

            for (int j=0; j<N; j++) { new_s.genes[j]=rand()%2; }

            CalcFitness(new_s);
            pool.push_back(new_s);
        }
    }

    void CalcFitness(Solution & s)
    {
        fitness_calculator->CalculateFitness(s, *this);
    }

    void Mutate()
    {
        Solution new_s;

        for (int i=0; i<pool_size; i++)
        {
            mutator->Mutate(pool[i], new_s, *this);

            CalcFitness(new_s);
            pool.push_back(new_s);
        }
    }

    void Crossbreed()
    {
        for (int i=0; i<pool_size-1; i++)
        {
            Solution new_s;

            crossbreeder->Crossbreed(pool[i], pool[i+1], new_s, *this);

            CalcFitness(new_s);
            pool.push_back(new_s);
        }
    }

    void NextGeneration()
    {
        Crossbreed();
        Mutate();
        Spawn(pool_size);

        sort(pool.begin(),pool.end());
        unique(pool.begin(),pool.end());
        pool.resize(pool_size);
        sort(pool.begin(),pool.end());
    }
};

struct Mutator1 : public Mutator
{
    void Mutate(Solution & s, Solution & new_s, GeneticAlgorithm & ga)
    {
        new_s=s;

        int j=rand()%ga.N;
        int xj=new_s.genes[j];

        if (xj==0) xj=1;
        else xj=0;

        new_s.genes[j]=xj;
    }

    Mutator * Clone() { return new Mutator1; }
};

struct Mutator2 : public Mutator
{
    void Mutate(Solution & s, Solution & new_s, GeneticAlgorithm & ga)
    {
        new_s=s;

        for (int i=0; i<ga.N; i++)
        {
            if (rand()%100<20)
            {
                new_s.genes[i]++;
                new_s.genes[i]%=2;
            }
        }
    }

    Mutator * Clone() { return new Mutator2; }
};

struct Crossbreeder1 : public Crossbreeder
{
    void Crossbreed(Solution & s1, Solution & s2, Solution & new_s, GeneticAlgorithm & ga)
    {
        new_s.genes.resize(ga.N);

        int xj1;
        int xj2;
        int new_xj;

        for (int j=0; j<ga.N; j++)
        {
            xj1=s1.genes[j];
            xj2=s2.genes[j];

            if (xj1==xj2) new_xj=xj1;
            else new_xj=rand()%2;

            new_s.genes[j]=new_xj;
        }
    }

    Crossbreeder * Clone() { return new Crossbreeder1; }
};

struct Crossbreeder2 : public Crossbreeder
{
    void Crossbreed(Solution & s1, Solution & s2, Solution & new_s, GeneticAlgorithm & ga)
    {
        new_s.genes.resize(ga.N);

        int split_point;
        split_point=rand()%(ga.N-2)+1;

        copy(s1.genes.begin(),s1.genes.begin()+split_point,new_s.genes.begin());
        copy(s2.genes.begin()+split_point,s2.genes.end(),new_s.genes.begin()+split_point);
    }

    Crossbreeder * Clone() { return new Crossbreeder2; }
};

struct FitnessCalculator1 : public FitnessCalculator
{
    virtual void CalculateFitness(Solution & s, GeneticAlgorithm & ga)
    {
        s.fitness=0;

        double total_val=0, max_val=0, total_weight=0;

        for (int i=0; i<ga.N; i++)
        {
            total_val+=ga.value[i]*s.genes[i];
            max_val+=ga.value[i];
            total_weight+=ga.weight[i]*s.genes[i];
        }

        s.fitness=total_val*1000/max_val;
        if (total_weight>ga.max_weight) s.fitness/=2*ga.N;
    }

    FitnessCalculator * Clone() { return new FitnessCalculator1; }
};

struct FitnessCalculator2 : public FitnessCalculator
{
    virtual void CalculateFitness(Solution & s, GeneticAlgorithm & ga)
    {
        s.fitness=0;

        double total_val=0, total_weight=0;

        for (int i=0; i<ga.N; i++)
        {
            total_val+=ga.value[i]*s.genes[i];
            total_weight+=ga.weight[i]*s.genes[i];
        }

        s.fitness=total_val;
        if (total_weight>ga.max_weight) s.fitness=sqrt(s.fitness);
    }

    FitnessCalculator * Clone() { return new FitnessCalculator2; }
};

template <class T>
void cleanup(vector<T*> & v)
{
    typename vector<T*>::iterator it;

    it=v.begin();

    while (it!=v.end())
    {
        delete *it;
        it++;
    }
}

int main()
{
    srand(time(0));

    GeneticAlgorithm ga;

    vector<Mutator*> mutators;
    mutators.push_back(new Mutator1);
    mutators.push_back(new Mutator2);

    vector<Crossbreeder*> crossbreeders;
    crossbreeders.push_back(new Crossbreeder1);
    crossbreeders.push_back(new Crossbreeder2);

    vector<FitnessCalculator*> fitness_calculators;
    fitness_calculators.push_back(new FitnessCalculator1);
    fitness_calculators.push_back(new FitnessCalculator2);

    int mutator;
    int crossbreeder;
    int fitness_calculator;

    while (true)
    {
        cout << "choose mutator (1-" << mutators.size() << ") ";
        Console::GetInt(mutator);
        if (mutator>0 && mutator<=mutators.size()) break;
    }

    while (true)
    {
        cout << "choose crossbreeder (1-" << crossbreeders.size() << ") ";
        Console::GetInt(crossbreeder);
        if (crossbreeder>0 && crossbreeder<=crossbreeders.size()) break;
    }

    while (true)
    {
        cout << "choose fitness_calculator (1-" << fitness_calculators.size() << ") ";
        Console::GetInt(fitness_calculator);
        if (fitness_calculator>0 && fitness_calculator<=fitness_calculators.size()) break;
    }

    ga.SetMutator(mutators[mutator-1]->Clone());
    ga.SetCrossbreeder(crossbreeders[crossbreeder-1]->Clone());
    ga.SetFitnessCalculator(fitness_calculators[fitness_calculator-1]->Clone());

    cleanup(mutators);
    cleanup(crossbreeders);
    cleanup(fitness_calculators);

    int choice;
    bool quit=false;

    ga.Init();

    while (true)
    {
        ga.NextGeneration();
        copy(ga.pool.begin(),ga.pool.end(),ostream_iterator<Solution>(cout,"\n"));

        while (true)
        {
            cout << "continue? (1->yes 2->no) ";
            Console::GetInt(choice);

            if (choice==1) break;
            if (choice==2) {quit=true; break;}
        }

        if (quit) break;
    }

    cout << "(hit enter to quit...)";
    Console::Pause();

    return 0;
}