#include <boost/algorithm/string.hpp>

#include "gmock/gmock.h"
#include "gtest/gtest.h"

#include <deque>
#include <map>
#include <string>
#include <utility>
#include <vector>

using namespace std::string_literals;

using BNF = std::map<std::string, std::vector<std::vector<std::string>>>;
using Terminals = std::set<std::string>;
using ProgramNode = std::deque<std::string>;
using PathElement = std::pair<std::string, size_t>; // Name, Index

std::vector<std::string> split(std::string s)
{
 std::vector<std::string> result;
 boost::algorithm::split(result, s, boost::algorithm::is_any_of(s), boost::algorithm::token_compress_on);
 while (result.size() > 0 && result.back() == ""s)
   result.pop_back();
 return result;
}

std::vector<PathElement> GetPath(std::string Token, BNF ReverseBNF, std::string Top, Terminals terminals = {}, std::vector<PathElement> PreviousPath = {})
{
 throw std::runtime_error("Compile error");
 return {}; // TODO
}

BNF Reverse(BNF bnf){
 return {}; // TODO
}

std::vector<std::string> Lex(std::string s, std::string Top, BNF bnf)
{
 std::vector<std::string> result;
 std::string token;

 BNF ReverseBNF{ Reverse(bnf)};

 std::string Whitespace{"\t \n\r"};

 for (size_t pos{0}; pos < s.size(); pos++) {
  char c{s[pos]};
  if (token.empty() and Whitespace.find(c) != std::string::npos)
   continue; // skip whitespace between tokens

  auto Path = GetPath(std::string{1, c}, ReverseBNF, Top);
 }

 return result;
}

ProgramNode Compile(std::vector<std::string> Tokens, std::string Top, BNF bnf, Terminals terminals)
{
 BNF ReverseBNF{ Reverse(bnf)};

 if (Tokens.size()){
  std::string Token = Tokens[0];
  auto Path = GetPath(Token, ReverseBNF, Top, terminals);
  if (Path.size()) {
   size_t Index{1};
   while (Index < Tokens.size()) {
    Path = GetPath(Token, ReverseBNF, Top, terminals, Path);
    Index++;
   }
  } else
   throw std::runtime_error("Invalid token: "s + Token);
 } else
  throw std::runtime_error("No tokens!");

 return {};
}

class Test: public ::testing::Test {
protected:
 Test(){}
 ~Test() override {}
};

TEST_F(Test, BNF) {
 std::string LexTop{"preprocessing-token"};
 BNF LexBNF{
  {"preprocessing-token", {{"identifier"},
                           {"preprocessing-op-or-punc"},
                           {"pp-number"}}},

  {"identifier", {{"identifier-nondigit"},
                  {"identifier", "identifier-nondigit"},
                  {"identifier", "digit"}}},
  {"digit", {{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9" }}},
  {"identifier-nondigit", {{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",
                            "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "_"}}},
  {"preprocessing-op-or-punc", {{";"}}},
  {"pp-number", {{"digit"},
                 {"pp-number", "digit"}}}
 };

 std::string Top{"program"};
 BNF bnf{
  {"program", {{"statement-list"}}},
  {"statement-list", {{"statement", "statement-list"},
                      {}, }},
  {"statement", {{"assigmnent", ";"}}},
  {"assignment", {{"identifier", "=", "identifier"}}}
 };

 std::set<std::string> Terminals{"identifier", "=", ";"};

 std::string Code{"a = b ; c = d ; e = f ;"};

 auto tokens = Lex(Code, LexTop, LexBNF);
 auto Program = Compile(tokens, Top, bnf, Terminals);
}

int main(int argc, char* argv[]) {
 ::testing::InitGoogleMock(&argc, argv);
 return RUN_ALL_TESTS();
}