generator: generate item sets recursively

1 files changed, 49 insertions, 3 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");
+	}
 }
 
 }