#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<std::string> Lex(std::string s)
{
 return split(s);
}

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

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
}

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 Top{"program"};
 BNF bnf{
  {"program", {{"statement-list"}}},
  {"statement-list", {{"statement", "statement-list"}}},
  {"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);
 auto Program = Compile(tokens, Top, bnf, Terminals);
}

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