#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <random>
#include <algorithm>

struct Customer{
    double x;
    double y;
    double size;
};

struct Shop{
    double x;
    double y;
    double cost;
    double capacity;

};


static double distance(const std::pair<double, double> &from, const std::pair<double, double> &to){
    return std::sqrt((from.first - to.first) * (from.first - to.first) + (from.second - to.second) * (from.second - to.second));
}

class Population{
public:

    Population(size_t population_sz, const std::vector<Customer> &custom, const std::vector<Shop> &sh, const std::vector<std::vector<double>> &d): population_size(population_sz), customer_size(custom.size()), shop_size(sh.size()), shops(sh), customers(custom), dist_matrix(d){
        population.resize(population_sz, std::vector<int>(customer_size));
        std::random_device rnd_device;
        std::mt19937 mersenne_engine {rnd_device()};
        int sz = static_cast<int>(shop_size - 1);
        std::uniform_int_distribution<int> dist {0, sz};
        for (int i = 0; i < population_sz; ++i){
            auto gen = [&dist, &mersenne_engine](){
                return dist(mersenne_engine);
            };
            std::vector<int> vec(customer_size);
            std::generate(std::begin(vec), std::end(vec), gen);
            population[i] = vec;
        }
        population_candidates = population;
    }
    double count_one_fitness(size_t index){
        double fitness = 0.0;
        std::vector<double> open(shop_size, 0.0);
        for (size_t i = 0; i < customer_size; ++i){
            int shop = population[index][i];
            if (open[shop] < 0.0000001){
                fitness += shops[shop].cost;

            }
            fitness += dist_matrix[shop][i];
            open[shop] += customers[i].size;
        }
        for (size_t i = 0; i < shop_size; ++i){
            double delta = shops[i].capacity - open[i];
            if (delta < 0){
                fitness += delta * fitness * 0.3;
            }

        }
        return fitness;
    }

    double one_fitness(std::vector<int>& sol){
        double fitness = 0.0;
        std::vector<double> open(shop_size, 0.0);
        for (size_t i = 0; i < customer_size; ++i){
            int shop = sol[i];
            if (open[shop] < 0.0000001){
                fitness += shops[shop].cost;

            }
            fitness += dist_matrix[shop][i];
            open[shop] += customers[i].size;
        }
        for (size_t i = 0; i < shop_size; ++i){
            double delta = shops[i].capacity - open[i];
            if (delta < 0){
                fitness += delta * fitness * 0.3;
            }

        }
        return fitness;
    }

    std::vector<int> breeding_one_iteration(size_t parent1, size_t parent2, const std::vector<size_t> &indexes){
        std::vector<int> children1 = population[parent1];
        std::vector<int> children2 = population[parent2];
        for (unsigned long index : indexes){
            children1[index] = population[parent2][index];
            children2[index] = population[parent1][index];
        }
        double f1 = one_fitness(children1);
        double f2 = one_fitness(children2);
        if (f1 < f2){
            return children1;
        }
        return children2;

    }

    std::vector<int> mutation_one_iteration(size_t parent, const std::vector<size_t> &indexes, const std::vector<int> &new_meaning) {
        std::vector<int> children = population[parent];
        for (int i = 0; i < indexes.size(); ++i) {
            children[indexes[i]] = new_meaning[i];
        }

        return children;
    }

    std::vector<std::vector<int>> breeding(size_t number_candidates){
        std::vector<size_t> ind(customer_size);
        for (int i = 0; i < customer_size; ++i){
            ind[i] = i;
        }

        std::vector<std::vector<int>> new_population(number_candidates);
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<size_t> distrib(0, population_size - 1);
        for (int i = 0; i < number_candidates; ++i){
            size_t p1 = distrib(gen);
            size_t p2 = distrib(gen);
            std::shuffle(ind.begin(), ind.end(), gen);
            new_population[i] = breeding_one_iteration(p1, p2,  std::vector<size_t> { ind.begin(), ind.begin() + customer_size / 2 + 1 });
        }
        return new_population;
    }

    std::vector<std::vector<int>> mutations(size_t number_candidates) {
        std::vector<std::vector<int>> new_population(number_candidates);
        std::random_device rd;
        std::mt19937 gen(rd());
        std::vector<size_t> ind(customer_size);
        for (int i = 0; i < customer_size; ++i){
            ind[i] = i;
        }
        std::mt19937 mersenne_engine {rd()};
        int sz = static_cast<int>(shop_size - 1);
        std::uniform_int_distribution<int> dist {0, sz};
        std::uniform_int_distribution<size_t> distrib(0, population_size - 1);
        for (int i = 0; i < number_candidates; ++i) {
            size_t p = distrib(gen);
            auto gen = [&dist, &mersenne_engine](){
                return dist(mersenne_engine);
            };
            std::vector<int> vec(customer_size / 4 + 1);
            std::generate(std::begin(vec), std::end(vec), gen);
            new_population[i] = mutation_one_iteration(p, std::vector<size_t> { ind.begin(), ind.begin() + customer_size / 4 + 1}, vec);
        }
        return new_population;
    }


    void one_iteration_genetic_algorithm(){
//        хочется в каждой итерации генерить разное количество новых кандидатов с помощью селекции/мутации
        

    }


private:
    size_t customer_size;
    size_t shop_size;
    size_t population_size;
    std::vector<std::vector<int>> population;
    std::vector<Shop> shops;
    std::vector<Customer> customers;
    std::vector<std::vector<int>> population_candidates;
    std::vector<std::vector<double>> dist_matrix;
};

int main() {
    std::ifstream in;
    int n;
    int m;
    in.open("/home/katfresal/CLionProjects/Facility location/data/");
    in >> n >> m;
    std::vector<Shop> shops(n);
    std::vector<Customer> customers(m);

    for (int i = 0; i < n; ++i){
        in >> shops[i].cost >>shops[i].capacity >> shops[i].x >> shops[i].y;
    }

    for (int i = 0; i < m; ++i){
        in >> customers[i].size >> customers[i].x >> customers[i].y;
    }

    in.close();
    std::vector<std::vector<double>> dist_matrix(n, std::vector<double>(m));
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            dist_matrix[i][j] = distance({shops[i].x, shops[i].y}, {customers[j].x, customers[j].y});
        }
    }


}