#include "bnf.h"

std::map<std::string, std::set<std::string>> Reverse(BNF bnf)
{
 std::map<std::string, std::set<std::string>> result;

 for (const auto& [from, to] : bnf) {
  for (const auto& list : to) {
   for (const auto& element : list) {
    auto i{result.find(element)};
    if (i != result.end()) // already present
     i->second.insert(from);
    else // new element
     result.emplace(element, std::set{from});
   }
  }
 }

 return result;
}

BNF SubBNF(const BNF& bnf, const std::string& top)
{
 BNF result;

 std::vector<std::string> todo{top};

 while (!todo.empty()) {
  std::string current{todo.back()};
  todo.pop_back();

  auto it = bnf.find(current);
  if (it != bnf.end()) {
   // add current value
   result[it->first] = it->second;

   // add sub-tree values if not present yet, but available in original bnf
   for (auto& variant: it->second) {
    for (auto& child: variant) {
     if (result.find(child) == result.end() && bnf.find(child) != bnf.end()) {
      todo.push_back(child);
     }
    }
   }
  }
 }

 return result;
}