/*
 * File: algorithm-data_dependency
 * Date: Dec 23, 2016
 * Author: pgess <v.melnychenko@xreate.org>
 */

#include <unordered_set>
#include <unordered_map>
#include <string>
#include <map>
#include "gtest/gtest.h"
#include <initializer_list>
#include <cstdio>


const int V_NOVERSION = -2;
const int V_ENDOFLIFE = -1;

struct Symbol {
    std::string name;
    int version;

    Symbol getNextVersion() const{
        return Symbol{name, version+1};
    }
};

namespace std
{
    template<>
    struct hash<Symbol>
    {
        typedef Symbol argument_type;
        typedef std::size_t result_type;
        result_type operator()(argument_type const& s) const
        {
            result_type const h1 ( std::hash<std::string>()(s.name) );
            return h1 ^ (s.version << 1); // or use boost::hash_combine
        }
    };

    template<>
    struct equal_to<Symbol>
    {
      typedef Symbol argument_type;

      bool operator()(const argument_type& __x, const argument_type& __y) const
      { return __x.name == __y.name && __x.version == __y.version; }
    };
}

//Ограничения:
// - точно знаем следующую версию на этапе декл. (C.NV.1)

class DDSolver{
public:

    void l1_applyLowerBound(const Symbol& left, const std::initializer_list<Symbol>& dependencies){
        for (Symbol right: dependencies){
                //lower bound:
            __infs.emplace(left, right);
            __sups.emplace(right, left);
        }
    }

    void l1_applyOwnUpperBound(const Symbol& left){
                //own upper bound:
                //C.NV.1
        __infs.emplace(left.getNextVersion(), left);
        __sups.emplace(left, left.getNextVersion());
    }

    void l1_applyDependentUpperBound(const Symbol& left, const std::initializer_list<Symbol>& dependencies){
            // additionally apply dependent upper bound
        for (Symbol right: dependencies){
            auto right2 = right.getNextVersion();

            __infs.emplace(right2, left);
            __sups.emplace(left, right2);
        }
    }

    void addVariable(const Symbol& left, const std::initializer_list<Symbol>& dependencies){
        l1_applyLowerBound(left, dependencies);
        l1_applyOwnUpperBound(left);

        //initialization upper bound
        l1_applyDependentUpperBound(left, dependencies);

    }

    //TODO assert: only aliases allowed
    void addAlias(const Symbol& left, const std::initializer_list<Symbol>& dependencies){
        l1_applyLowerBound(left, dependencies);
        l1_applyOwnUpperBound(left);

        //lifetime upper bound
        l1_applyDependentUpperBound(left.getNextVersion(), dependencies);
    }


    bool checkCyclicComponent(const Symbol& s, std::unordered_set<Symbol>& symbolsVisited, std::unordered_set<Symbol>& symbolsSups){
        if (symbolsVisited.count(s)) return false;

        symbolsVisited.insert(s);
        symbolsSups.insert(s);

        auto rangeInf = __infs.equal_range(s);
        if (__infs.count(s))
        for (auto sInf = rangeInf.first; sInf != rangeInf.second; ++sInf){
            if (symbolsSups.count(sInf->second)) {
                __flagCycle = std::make_pair(sInf->second, s);
                return true;
            }
            if(checkCyclicComponent(sInf->second, symbolsVisited, symbolsSups)) return true;
        }

        symbolsSups.erase(s);
        return false;
    }

    bool checkCyclicFull(){
        std::unordered_set<Symbol> symbolsVisited, symbolsSups;

        std::unordered_multimap<Symbol, Symbol>::iterator s;
        for (s = __infs.begin(); s != __infs.end(); ++s){
            if(checkCyclicComponent(s->first, symbolsVisited, symbolsSups)) return true;
        }

        return false;
    }

    bool validate(){
        return !checkCyclicFull();
    }

    void solve(){
        std::unordered_set<Symbol> binEnabled, binFrontier;

        //seed
        for (auto edge: __sups){
            if (! __infs.count(edge.first)){
                binEnabled.insert(edge.first);
                binFrontier.insert(edge.first);
            }
        }

        while (binFrontier.size()){
            const Symbol& node= *binFrontier.begin();

            //print node:
            std:: printf("put (%s, %d)\n",  node.name.c_str(), node.version);

            auto rangeSups = __sups.equal_range(node);
            for(auto sup=rangeSups.first; sup != rangeSups.second; ++sup){
                bool flagEnabled = true;

                auto rangeInfs = __infs.equal_range(sup->second);
                for (auto inf=rangeInfs.first; inf != rangeInfs.second; ++inf){
                    if (!binEnabled.count(inf->second)){
                        flagEnabled = false;
                        break;
                    }
                }

                if (flagEnabled){
                    binEnabled.insert(sup->second);
                    binFrontier.insert(sup->second);
                }
            }

            binFrontier.erase(node);
        }
    }

    void solve2(Symbol nodeEntry, std::unordered_set<Symbol>& binPreviousNodes, std::unordered_set<Symbol>& binEnabledNodes){
        binPreviousNodes.insert(nodeEntry);

        auto rangeChilds = __infs.equal_range(nodeEntry);
        for(auto node=rangeChilds.first; node != rangeChilds.second; ++node){
            if (binEnabledNodes.count(node->second)) continue;

            auto nodeError =  binPreviousNodes.find(node->second);
            if (nodeError != binPreviousNodes.end()){
                std:: printf("(%s, %d) - (%s, %d)",
                    nodeError->name.c_str(), nodeError->version,
                    node->second.name.c_str(), node->second.version);
                assert(true);
            }

            solve2(node->second, binPreviousNodes, binEnabledNodes);
        }

        std:: printf("put (%s, %d)\n",  nodeEntry.name.c_str(), nodeEntry.version);
        binEnabledNodes.insert(nodeEntry);
        binPreviousNodes.erase(nodeEntry);

//        auto rangeParents = __sups.equal_range(nodeEntry);
//        for(auto node=rangeParents.first; node != rangeParents.second; ++node){
//            std::unordered_set<Symbol> binEmpty;
//            solve2(node->second, binEmpty, binEnabledNodes);
//        }
    }

    void __debug_printGraph(){
        for (auto edge: __infs){
             std:: printf("(%s, %d) <- (%s, %d) \n",
                edge.second.name.c_str(), edge.second.version,
                edge.first.name.c_str(), edge.first.version);
        }
    }

private:
    std::unordered_multimap<Symbol, Symbol> __sups;
    std::unordered_multimap<Symbol, Symbol> __infs;

public:
    std::pair<Symbol, Symbol> __flagCycle;
};

//TEST(Datadependency, test1){
//    DDSolver solver;
//
//    solver.addAlias(Symbol{"c", V_NOVERSION}, {Symbol{"a", 0}});
//    solver.addVariable(Symbol{"a", 1}, {Symbol{"b", 0}});
//    solver.addVariable(Symbol{"b", 1}, {Symbol{"c", V_NOVERSION}});
//
//    solver.__debug_printGraph();
//
//    ASSERT_FALSE(solver.validate());
//
//    std:: printf("(%s, %d) - (%s, %d)",
//        solver.__flagCycle.first.name.c_str(), solver.__flagCycle.first.version,
//        solver.__flagCycle.second.name.c_str(), solver.__flagCycle.second.version);
//}

//TEST(Datadependency, test2){
//    DDSolver solver;
//
//    solver.addVariable(Symbol{"c", V_NOVERSION}, {Symbol{"a", 0}});
//    solver.addVariable(Symbol{"a", 1}, {Symbol{"b", 0}});
//    solver.addVariable(Symbol{"b", 1}, {Symbol{"c", V_NOVERSION}});
//
//    ASSERT_TRUE(solver.validate());
//
//    solver.solve();
//}

TEST(Datadependency, test3){
    DDSolver solver;

    solver.addVariable(Symbol{"c", V_NOVERSION}, {Symbol{"a", 0}});
    solver.addVariable(Symbol{"a", 1}, {Symbol{"b", 0}});
    solver.addVariable(Symbol{"b", 1}, {Symbol{"c", V_NOVERSION}});

    std::unordered_set<Symbol> binPreviousNodes, binEnabledNodes;
    solver.solve2(Symbol{"b", 1}, binPreviousNodes, binEnabledNodes);
    ASSERT_TRUE(true);
}