/*****************************************************************//**
 * \file   ChainsInitializer.h
 * \brief  Initializes the restricted master porblem with all the cycle exchanges.
 *
 * \author Matteo Petris
 * \date   February 2023
 *********************************************************************/
#ifndef CHAINSINITIALIZER_H
#define CHAINSINITIALIZER_H

#include "RestrictedMasterProblemInitializerAbstract.h"
#include "RestrictedMasterProblem.h"
#include "Label.h"

 /**
  * \class ChainsInitializer
  * \brief  Initializes the restricted master problem with all the chains exchanges.
  */
class ChainsInitializer : public RestrictedMasterProblemInitializerAbstract<Instance, vector<Exchange>> {

protected:
  
    const vector<Vertex>& vertices;
    const vector<int>& incompatiblePairs;
    int altruisticNumber;
    int chainLength;
    int wordsNumber;
    vector<Exchange> solution;

public:
    /**
     * \brief Constructor.
     *
     */
    ChainsInitializer(Instance& instance) : RestrictedMasterProblemInitializerAbstract(instance), vertices(instance.getVertices()), incompatiblePairs(instance.getIncompatiblePairs()) {
        this->chainLength = min(instance.getChainsLength(), ::CHAINSINITIALISATIONLENGTH) + 1;
        this->wordsNumber = instance.getWordsNumber();
        this->altruisticNumber = instance.getAltruisticDonors().size();
        this->exchangesPerVertex = instance.getExchangesPerVertexInitialisation();
    }


    /**
     * \brief Evaluates if the handler (the algorithm) can handle (initlize) the restricted master problem based on the code of request.
     *
     * \param request : string
     * \return True if the concrete algorithm can solve the pricing sub-problem, false otherwise.
     */
    bool can_initialize(const string& request) const {
        return request == "CHAINSINITIALIZER" || "WHATEVER";
    }

    /**
     * Initializes the restrcted master problem.
     * \details This method has to be implemented in the inherent classes.
     * \param request : string
     */
    vector<Exchange> initialize(const string& request) override {
        if (can_initialize(request) && this->chainLength > 0 && this->altruisticNumber > 0) {
            
            int source = this->vertices.at(0).getId();
            vector<vector<Label>> labels = dynamicProgram(source, this->chainLength);

            //build exchange objects
            for (int l = 0; l < labels.size(); l++) {
                for (int h = 0; h < labels.at(l).size(); h++) {
                    const Label* label = &labels.at(l).at(h);
                    if (label->getSequence().size() > 2) {
                        Exchange exchange("chain", static_cast<int>(label->getWeight()), label->getLength(), label->getSequence(), this->instance.getVertexNumber());
                        this->solution.push_back(exchange);
                    }
                }
            }
           
            //displayChains();
            assert(check_solution());
            return this->solution;
        }
        else
            return RestrictedMasterProblemInitializerAbstract::initialize(request);
    }

    vector<vector<Label>> dynamicProgram(const int& source, const int& maxLength) {

        //INITIALIZATION
        Label sourceLabel(source, 0, 0, 0.0);
        sourceLabel.buildSequence({});
        vector<int> ngMemory(this->wordsNumber, 0);
        sourceLabel.buildNgSetFullMemory(ngMemory, this->vertices.at(source).getWord(), this->vertices.at(source).getBitKey());
        //cout << "INITI\n" << sourceLabel.toString() << endl;

        size_t vSize = this->vertices.size();
        vector<vector<Label>> labels(vSize);
        labels.at(source).push_back(sourceLabel);

        //ITERATIONS
        bool termination = false;
        int counter = 0;
        int maxExchangeNumber = this->altruisticNumber * this->exchangesPerVertex;

        while (termination != true) {

            termination = true;

            for (int i = 0; i < vSize; i++) {

                const Vertex* v = &this->vertices.at(i);
                //cout << "VERTEX\n" << v->toString(false) << endl;

                for (int h = 0; h < labels.at(i).size(); h++) {

                    const Label* l = &labels.at(i).at(h);
                    //cout << "LABEL\n" << l->toString() << endl;

                    if (!l->getIsExtended() && l->getLength() < maxLength) {

                        /*const Vertex* v = &this->vertices.at(this->incompatiblePairs.at(i));
                        cout << "VERTEX\n" << v->toString(false) << endl;*/
                        

                        for (unordered_map<int, int>::const_iterator it = v->getOutGoingArcs().begin(); it != v->getOutGoingArcs().end(); it++) {

                            const Vertex* w = &this->vertices.at(it->first);
                            /*cout << "TO REACH\n" << w->toString(false) << endl;
                            cout << "IS VISITED? " << l->isVisited(w->getWord(), w->getBitKey()) << endl;*/

                            if (!l->isVisited(w->getWord(), w->getBitKey())) {

                                Label extension(w->getId(), l->getLength() + 1, l->getWeight() + it->second, 0.0);
                                extension.buildSequence(l->getSequence());
                                extension.buildNgSetFullMemory(l->getNgMemory(), w->getWord(), w->getBitKey());
                                labels.at(w->getId()).push_back(extension);
                                //cout << "EXT\n" << extension.toString() << endl;
                                counter++;
                                if (counter > maxExchangeNumber) {
                                    return labels;
                                }


                                termination = false;

                            }

                        }

                    }

                    labels.at(i).at(h).setIsExtended(true);

                }

            }

        }

        return labels;

    }

    /**
     * Displays the cycles.
     */
    void displayChains() {
        cout << "----Chain initialisation :" << endl;
        for (int i = 0; i < this->solution.size(); i++)
            cout << this->solution.at(i).toString() << endl;
    }

    bool check_solution() {
        map<int, int> occurences;

        for (const Exchange& exchange : this->solution) {
            if (exchange.getLength() > this->chainLength) {
                cout << "ERROR LENGTH\n" << exchange.toString() << "\n";
                return false;
            }
        }
        
        for (const Exchange& exchange : this->solution) {
            if (exchange.getSequence().front() != this->vertices.front().getId()) {
                cout << "ERROR NOT A CHAIN\n" << exchange.toString() << "\n";
                return false;
            }
        }

        for (const Exchange& exchange : this->solution) {
            for (int i = 0; i < exchange.getSequence().size(); i++) {
                if (exchange.getVisit(exchange.getSequence().at(i)) > 1) {
                    cout << "ERROR SAME PAIR MORE THAN ONCE\n" << exchange.toString() << "\n";
                    return false;
                }
            }
        }

        for (const Exchange& exchange : this->solution) {
            int weight = 0;
            for (int i = 0; i < exchange.getSequence().size() - 1; i++) {
                const Vertex* v = &this->vertices.at(exchange.getSequence().at(i));
                unordered_map<int, int>::const_iterator finder = v->getOutGoingArcs().find(exchange.getSequence().at(i + 1));
                if (finder == v->getOutGoingArcs().end()) {
                    cout << "ERROR VERTICES NOT COMPATIBLE\n" << exchange.toString() << "\n";
                    return false;
                }
                else if (v->getType() != 'D') {
                    weight += finder->second;
                }
            }
            if (weight != exchange.getWeight()) {
                cout << "ERROR WRONG WEIGHT\t" << weight << "\n" << exchange.toString() << "\n";
                return false;
            }
        }

        return true;
    }
};


#endif //CHAINSINITIALIZER_H
