#include <cassert>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <vector>

#include "VertexSet.h"
#include "graph.hh"
#include "ExecutionPlan.hh"
#include "cmap.h"

static std::vector<vidType>
update_and_prune(cmap8_t &cmap, const VertexSet &vertices, const EncodedRuleInst &rule)
{
    const auto &policy = rule.policy;
    std::vector<vidType> frontier;

    for (vidType v : vertices) {

        bool within_range = (v >= rule.lower && v < rule.upper);

        if (policy.range == ALL || within_range) {
            uint8_t value = cmap.get(v);
            bool cmap_match = policy.update_cond(value);

            if (policy.update_cmap && cmap_match) {
                cmap.set(v, policy.update_op(value));
            }

            if (within_range && cmap_match) {
                frontier.push_back(v);
            }
        }
    }

    return frontier;
}

static void
restore(cmap8_t &cmap, const VertexSet &vertices, const EncodedRuleInst &rule)
{
    const auto &policy = rule.policy;

    for (vidType v : vertices) {

        bool within_range = (v >= rule.lower && v < rule.upper);

        if (policy.range == ALL || within_range) {
            uint8_t value = cmap.get(v);
            if ( policy.update_cmap && policy.restore_cond(value) ) {
                cmap.set(v, policy.restore_op(value));
            }
        }
    }
}

static void
cleanup(cmap8_t &cmap)
{}

uint64_t
SolveSinglePattern(Graph &g, const ExecutionPlan &plan)
{
    uint64_t counter = 0;
    size_t level = 0;

    size_t k = plan.pattern_size();
    if (k > 8) {
        std::stringstream sstream;
        sstream << "The solver can't handle patterns with size > 8 (current size = "
                << k << ")";
        throw runtime_error{sstream.str()};
    }

    std::vector<vidType> history;
    std::vector<std::vector<vidType>> frontiers; 
    std::vector<size_t> pointer_stack;

    history.reserve(k - 1);
    frontiers.reserve(k - 1);
    pointer_stack.reserve(k - 1);

    cmap8_t cmap;

    for (vidType v0 = 0; v0 < g.V(); v0 ++) {

        frontiers.push_back({v0});
        pointer_stack.push_back(0);
        level++;

        while (true) {
            size_t &pointer = pointer_stack.back();

            if (pointer == frontiers.back().size()) {
                if (level == 1) break;

                level--;
                const EncodedRuleInst &rule = plan.rule_at(level).inst_with(history);

                restore(cmap, g.N(rule.src_id), rule);

                pointer_stack.pop_back();
                frontiers.pop_back();
                history.pop_back();
                continue;

            }

            vidType root = frontiers.back()[pointer++];
            history.push_back(root);

            const EncodedRuleInst &rule = plan.rule_at(level).inst_with(history);
            std::vector<vidType> new_frontier = update_and_prune(cmap, g.N(rule.src_id), rule);

            if (level == k - 1) {

                counter += static_cast<uint64_t> (new_frontier.size());
                history.pop_back();
            } else {
                frontiers.push_back(new_frontier);
                pointer_stack.push_back(0);
                level++;
            }
        }

        level--;
        pointer_stack.pop_back();
        frontiers.pop_back();

        assert(pointer_stack.size() == 0);
        assert(frontiers.size() == 0);
        assert(history.size() == 0);
        cleanup(cmap);
    }

    return count;
}

int main(int argc, char *argv[]) {
{
    using namespace std;

    if (argc < 2) {
        printf("Usage: %s <graph>\n", argv[0]);
        exit(1);
    }
    Graph g(argv[1]); 

    vector<EmbExtension> ext_triangles = {
        make_pair(1, {make_pair(uidType::MIN, 0), {0}, {}}),
        make_pair(2, {make_pair(uidType::MIN, 1), {0, 1}, {}})
    };

    vector<EmbExtension> ext_4clique(ext_triangles);
    ext_4clique.push_back( make_pair(3, {make_pair(uidType::MIN, 2), {0, 1, 2}, {}}) );

    vector<EmbExtension> ext_diamond = {
        make_pair(1, {make_pair(uidType::MIN, 0), {0}, {}}),
        make_pair(2, {make_pair(uidType::MIN, uidType::MAX), {0, 1}, {}}),
        make_pair(3, {make_pair(uidType::MIN, 2), {0, 1}, {}})
    };

    SolveSinglePattern(g, ExecutionPlan(ext_triangles));

    return 0;
}
#include <cassert>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <vector>

#include "VertexSet.h"
#include "graph.hh"
#include "ExecutionPlan.hh"
#include "cmap.h"

// class SinglePatternSolver;

static std::vector<vidType>
update_and_prune(cmap8_t &cmap, const VertexSet &vertices, const EncodedRuleInst &rule)
{
    const auto &policy = rule.policy;
    std::vector<vidType> frontier;

    for (vidType v : vertices) {
        // if (policy.range == FILTERED && v >= rule.upper) break;
        bool within_range = (v >= rule.lower && v < rule.upper);

        if (policy.range == ALL || within_range) {
            uint8_t value = cmap.get(v);
            bool cmap_match = policy.update_cond(value);

            if (policy.update_cmap && cmap_match) {
                cmap.set(v, policy.update_op(value));
            }

            if (within_range && cmap_match) {
                frontier.push_back(v);
            }
        }
    }

    return frontier;
}

static void
restore(cmap8_t &cmap, const VertexSet &vertices, const EncodedRuleInst &rule)
{
    const auto &policy = rule.policy;

    for (vidType v : vertices) {
        // if (policy.range == FILTERED && v >= rule.upper) break;
        bool within_range = (v >= rule.lower && v < rule.upper);

        if (policy.range == ALL || within_range) {
            uint8_t value = cmap.get(v);
            if ( policy.update_cmap && policy.restore_cond(value) ) {
                cmap.set(v, policy.restore_op(value));
            }
        }
    }
}

static void
cleanup(cmap8_t &cmap)
{}

// a solver to count #ocurrences of a single pattern in the graph dataset
// @param   g       the graph dataset
// @param   plan    the execution plan generated by analyzing the input pattern
// @return  the number of occurrences of the input pattern
uint64_t
SolveSinglePattern(Graph &g, const ExecutionPlan &plan)
{
    uint64_t counter = 0;
    size_t level = 0;

    size_t k = plan.pattern_size();
    if (k > 8) {
        std::stringstream sstream;
        sstream << "The solver can't handle patterns with size > 8 (current size = "
                << k << ")";
        throw runtime_error{sstream.str()};
    }

    std::vector<vidType> history;
    std::vector<std::vector<vidType>> frontiers; // TODO: to be replaced by emb_list
    std::vector<size_t> pointer_stack;

    history.reserve(k - 1);
    frontiers.reserve(k - 1);
    pointer_stack.reserve(k - 1);

    cmap8_t cmap;

    for (vidType v0 = 0; v0 < g.V(); v0 ++) {

        frontiers.push_back({v0});
        pointer_stack.push_back(0);
        level++;

        // before each loop begins:
        // frontiers.back().at(pointer_stack.back()) is the root vertex of the subtree to search
        // level is the next level
        // history stack doesn't contain the root vertex yet
        while (true) {
            size_t &pointer = pointer_stack.back();

            if (pointer == frontiers.back().size()) {
                if (level == 1) break;
                // current-level frontier is completed
                // clear cmap and backtrack
                level--;
                const EncodedRuleInst &rule = plan.rule_at(level).inst_with(history);
                // TODO: vertex set could come from existing frontiers
                restore(cmap, g.N(rule.src_id), rule);

                pointer_stack.pop_back();
                frontiers.pop_back();
                history.pop_back();
                continue;

            }

            vidType root = frontiers.back()[pointer++];
            history.push_back(root);

            // generate next-level frontier
            const EncodedRuleInst &rule = plan.rule_at(level).inst_with(history);
            std::vector<vidType> new_frontier = update_and_prune(cmap, g.N(rule.src_id), rule);

            if (level == k - 1) {
                // `new_frontier` is a last-level frontier
                counter += static_cast<uint64_t> (new_frontier.size());
                history.pop_back();
            } else {
                frontiers.push_back(new_frontier);
                pointer_stack.push_back(0);
                level++;
            }
        }

        // exploration rooted at v0 completed
        level--;
        pointer_stack.pop_back();
        frontiers.pop_back();

        assert(pointer_stack.size() == 0);
        assert(frontiers.size() == 0);
        assert(history.size() == 0);
        cleanup(cmap);
    }

    return count;
}

int main(int argc, char *argv[]) {
{
    using namespace std;

    if (argc < 2) {
        printf("Usage: %s <graph>\n", argv[0]);
        exit(1);
    }
    Graph g(argv[1]); // no DAG

    // edge-centric embeddings
    // extension plan for triangles
    vector<EmbExtension> ext_triangles = {
        make_pair(1, {make_pair(uidType::MIN, 0), {0}, {}}),
        make_pair(2, {make_pair(uidType::MIN, 1), {0, 1}, {}})
    };

    // extension plan for 4-clique
    vector<EmbExtension> ext_4clique(ext_triangles);
    ext_4clique.push_back( make_pair(3, {make_pair(uidType::MIN, 2), {0, 1, 2}, {}}) );

    // extension plan for diamond
    vector<EmbExtension> ext_diamond = {
        make_pair(1, {make_pair(uidType::MIN, 0), {0}, {}}),
        make_pair(2, {make_pair(uidType::MIN, uidType::MAX), {0, 1}, {}}),
        make_pair(3, {make_pair(uidType::MIN, 2), {0, 1}, {}})
    };

    SolveSinglePattern(g, ExecutionPlan(ext_triangles));

    return 0;
}

