#include <boost/variant.hpp>
#include <functional>
#include <iostream>
#include <vector>

typedef boost::make_recursive_variant<std::string,
    // put anything else you want here (e.g. double, int, some custom type)
    std::vector<boost::recursive_variant_>>::type semantic_value_t;

struct success_t {
    semantic_value_t val;
    std::string      rest;
};

struct failure_t {
    std::string msg;
    std::string rest;
};

typedef std::string                                          parser_arg_t;
typedef boost::variant<success_t, failure_t>                 parser_result_t;
typedef std::function<parser_result_t(parser_arg_t)>         parser_t;

typedef semantic_value_t                                     generator_arg_t;
typedef parser_t                                             generator_result_t;
typedef std::function<generator_result_t(generator_arg_t)>   generator_t;

typedef std::vector<parser_t>                                combinator_arg_t;
typedef parser_t                                             combinator_result_t;
typedef std::function<combinator_result_t(combinator_arg_t)> combinator_t;

auto lit = [](generator_arg_t match_v) -> parser_t {

    return [=](std::string input) -> parser_result_t {

        auto match = boost::get<std::string>(match_v);

        auto inLen = input.length();
        auto  mLen = match.length();

        auto len  = mLen < inLen ? mLen : inLen;

        auto head = input.substr(0, len);
        auto tail = input.substr(len, inLen - 1);

        if (head == match) return success_t{match,   tail };
        else               return failure_t{"error", input};
    };
};

auto succeed = [](generator_arg_t val) -> parser_t {

    return [=](std::string input) -> parser_result_t {

        return success_t{val, input};
    };
};

auto alt = [](combinator_arg_t parsers) -> parser_t {

    return [=](std::string input) -> parser_result_t {

        for (auto parser : parsers) {
            parser_result_t result = parser(input);

            if (success_t * pret = boost::get<success_t>(&result))
                return *pret;
        }

        return failure_t{"error", input};
    };
};

auto seq = [](combinator_arg_t parsers) -> parser_t {

    return [=](std::string input) -> parser_result_t {

        semantic_value_t val{std::vector<semantic_value_t>{}};
        std::string rest = input;

        for (auto parser : parsers) {

            auto r = parser(rest);

            if (failure_t * pr = boost::get<failure_t>(&r))
                return failure_t{"error", input};

            success_t * pr = boost::get<success_t>(&r);

            boost::get<std::vector<semantic_value_t>>(&val)->push_back(pr->val);

            rest = pr->rest;
        }

        return success_t{val, rest};
    };
};

struct semantic_value_printer : boost::static_visitor<> {

    template <class T>
    void operator()(const T & val) const { std::cout << val; }

    void operator()(const std::string & val) const { std::cout << '"' << val << '"'; }

    void operator()(const std::vector<semantic_value_t> & vec) const {
        std::cout << "[ ";

        for (auto val : vec) {
            boost::apply_visitor(semantic_value_printer(), val);
            std::cout << ' ';
        }

        std::cout << ']';
    }
};

struct result_printer : boost::static_visitor<> {

    void operator()(const success_t & s) const {
        std::cout << "success("; boost::apply_visitor(semantic_value_printer(), s.val);
        std::cout << ", \"" << s.rest << "\")" << std::endl;
    }

    void operator()(const failure_t & f) const {
        std::cout << "failure(" << '"' << f.msg << "\", \"" << f.rest << "\")" << std::endl;
    }
};

int main()
{
    parser_t number = alt({lit("0"), lit("1"), lit("2"), lit("3"), lit("4"),
                           lit("5"), lit("6"), lit("7"), lit("8"), lit("9")});

    parser_t term;
    term = [&](std::string input) { return
        alt({
             seq({number, lit("*"), term}),
             number,
           })(input);
    };

    parser_t expr;
    expr = [&](std::string input) { return
        alt({
             seq({term, lit("+"), expr}),
             term,
           })(input);
    };

    auto results = {
        lit("Hello")("HelloWorld!"),
        seq({lit("asdf"), lit("qwerty")})("asdfqwerty"),
        alt({lit("qwerty"), lit("asdf")})("asdfqwerty"),
        expr("1+2*3+4*5+6")
    };

    for (auto result : results)
        boost::apply_visitor(result_printer(), result);
}