summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorMatthias Schiffer <mschiffer@universe-factory.net>2015-03-31 20:25:04 +0200
committerMatthias Schiffer <mschiffer@universe-factory.net>2015-03-31 20:25:04 +0200
commit03b5a87eeb87fb059c9d51696912bfa9c39c5929 (patch)
tree6ff1e85d67afc4b105a02230611da854695c9477 /src
parent129b81e09375dbee4a12c468ef75f18243e8a0a4 (diff)
downloadsolar-03b5a87eeb87fb059c9d51696912bfa9c39c5929.tar
solar-03b5a87eeb87fb059c9d51696912bfa9c39c5929.zip
generator: generate item sets recursively
Diffstat (limited to 'src')
-rw-r--r--src/generator.cpp52
-rw-r--r--src/generator.hpp12
2 files changed, 59 insertions, 5 deletions
diff --git a/src/generator.cpp b/src/generator.cpp
index f8f4f1d..7f5f5e9 100644
--- a/src/generator.cpp
+++ b/src/generator.cpp
@@ -62,6 +62,45 @@ void generator_t::close_set(std::set<item_t> *set) {
}
}
+void generator_t::generate_itemsets() {
+ std::queue<std::set<item_t>> queue;
+
+ {
+ std::set<item_t> set0 = get_set("");
+ close_set(&set0);
+
+ add_set(set0);
+ queue.push(set0);
+ }
+
+ for (; !queue.empty(); queue.pop()) {
+ const std::set<item_t> &cur = queue.front();
+
+ const std::set<item_t> empty_set;
+ std::map<symbol_t, std::set<item_t>> new_sets;
+
+ for (const item_t &item : cur) {
+ if (!item.has_next())
+ continue;
+
+ const symbol_t &sym = item.get_next_symbol();
+
+ item_t shifted = item;
+ shifted.shift();
+
+ std::set<item_t> &set = new_sets.emplace(sym, empty_set).first->second;
+ set.insert(std::move(shifted));
+ }
+
+ for (auto &entry : new_sets) {
+ close_set(&entry.second);
+
+ if (add_set(entry.second).first)
+ queue.push(entry.second);
+ }
+ }
+}
+
void generator_t::print_item(const item_t &item) {
printf("%s |=", item.get_lhs().c_str());
@@ -100,10 +139,17 @@ generator_t::generator_t(const std::set<item_t> &rules0) {
}
}
- std::set<item_t> set0 = get_set("");
- close_set(&set0);
+ generate_itemsets();
- print_set(set0);
+ const std::set<item_t> *setlist[itemsets.size()];
+ for (const auto &entry : itemsets)
+ setlist[entry.second] = &entry.first;
+
+ for (unsigned i = 0; i < itemsets.size(); i++) {
+ printf("Item %u:\n", i);
+ print_set(*setlist[i]);
+ printf("\n");
+ }
}
}
diff --git a/src/generator.hpp b/src/generator.hpp
index d9bcaf6..880323b 100644
--- a/src/generator.hpp
+++ b/src/generator.hpp
@@ -38,12 +38,20 @@ class generator_t {
private:
std::multimap<std::string, item_t> rules;
std::multimap<symbol_t, item_t> items;
+ std::map<std::set<item_t>, unsigned> itemsets;
void close_set(std::set<item_t> *set);
std::set<item_t> get_set(const std::string &nonterm);
- void print_item(const item_t &item);
- void print_set(const std::set<item_t> &set);
+ std::pair<bool, unsigned> add_set(const std::set<item_t> &set) {
+ auto ret = itemsets.emplace(set, itemsets.size());
+ return std::make_pair(ret.second, ret.first->second);
+ }
+
+ void generate_itemsets();
+
+ static void print_item(const item_t &item);
+ static void print_set(const std::set<item_t> &set);
public:
generator_t(const std::set<item_t> &rules0);