#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
}

using index_t = size_t;

struct TreeNode {
 index_t parent;
 std::vector<index_t> childs;
 std::string name;
};

using Tree = std::map<index_t, TreeNode>;

bool ValidTree(const Tree& tree) {
 // Start symbol?
 // All terminal symbols?
 return true; // 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"};
 std::deque<Tree> candidates;

 for (size_t pos{0}; pos < s.size(); pos++) {
  char c{s[pos]};
  if (Whitespace.find(c) != std::string::npos) { // found whitespace character
   if (candidates.empty()) { // skip
    if (!token.empty())
     throw std::runtime_error("Expected empty token, got "s + token);
   } else { // check candidates
    bool valid{false};
    for (const auto& ct : candidates) {
     if (ValidTree(ct)) {
      if (valid)
       throw std::runtime_error("Found ambigous token");
      result.push_back(token);
      token.clear();
      valid = true;
     }
    }
    if (!valid)
     throw std::runtime_error("Invalid token: "s + token);

    candidates.clear();
   }
  } else { // no whitespace: try to add to tree
   for (auto& ct : candidates) {
    EraseList;
    if (!Add(ct, c)) {
     EraseList.add(ct); // no candidate anymore
    }
   }

   if (candidates.size() - EraseList.size() > 0) { // Added to some candidates: Continue growing token
    token.push_back(c);
    candidates.erase(EraseList);
   } else { // no candidates left: new tree
    // TODO: same as above "check candidates"
   }
  }
 }

 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();
}