Add traversing

1 files changed, 33 insertions, 0 deletions

diff --git a/grammer.cpp b/grammer.cpp
index 07e527f..f7a370f 100644
--- a/grammer.cpp
+++ b/grammer.cpp
@@ -256,11 +256,41 @@ void Compiler::TrackBack()
  ChangeNodeType();
 }
 
+// return shortest path with variants
+// via first-entry-in-bnf-rule
+// excluding lower (already exists)
+// including upper (already determined to be included)
+
+// breadth-first search
+std::map<std::string, std::string> Compiler::traverse(lower, upper)
+{
+ std::map<std::string, std::string> visited; // node, child
+ std::deque<std::pair<std::string, std::string>> todo{{lower, ""}}; // node, child
+ 
+ while (!todo.empty()) {
+  current = todo.front();
+  todo.pop_front();
+
+  if (!visited[current.first]) {
+   parents = reverseBNF[current.first];
+   
+   visited[current.first] = current.second;
+   
+   std::for_each(parents.begin(), parents.end(), [&](const auto&x) {todo.emplace_back(x, current.first);});
+  }
+ }
+ 
+ return visited;
+}
+
 // returns list from lower (including) to upper (excluding)
 // returns empty list on fail
 std::vector<std::string> Compiler::GetPath(std::string upper, std::string lower) {
  std::vector<std::string> result;
 
+ // traverse bnf from lower to upper
+ std::map<std::string, std::string> visited {traverse(lower, upper)};
+ 
  while (lower != upper) {
   auto parents {ReverseBNF.find(lower)};
   if (parents == ReverseBNF.end())
@@ -280,6 +310,9 @@ std::vector<std::string> Compiler::GetPath(std::string upper, std::string lower)
     }
    }
   }
+
+  if (!hit)
+   throw std::runtime_error("GetPath error!"); // ICE
   lower = new_lower;
  }
  return result;