#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include "Hash.hpp"
constexpr std::size_t hashdim = 32;
struct Item;
using ItemPtr = std::shared_ptr<Item>;
using Dependencies = Hash<std::string, ItemPtr>;
struct Item {
Item(std::string name) :
name(std::move(name)), dependencies(hashdim), reversed(hashdim) {
}
std::string name;
Dependencies dependencies;
Dependencies reversed;
};
int main() {
Hash<std::string, ItemPtr> items(hashdim);
auto lookup = [&items](const std::string& name) -> ItemPtr {
auto it = items.find(name);
if (it == items.end()) {
auto item = std::make_shared<Item>(name);
std::tie(it, std::ignore) = items.insert(std::make_pair(name, item));
}
return it->second;
};
std::string line;
while (std::getline(std::cin, line)) {
std::istringstream in(line);
std::string name;
if (!(in >> name)) continue;
auto item = lookup(name);
std::string depname;
while (in >> depname) {
auto dep = lookup(depname);
item->dependencies.insert(std::make_pair(depname, dep));
dep->reversed.insert(std::make_pair(name, item));
}
}
while (items.size() > 0) {
std::size_t removed = 0;
auto it = items.begin();
while (it != items.end()) {
auto next = it; ++next;
auto item = it->second;
if (item->dependencies.size() == 0) {
std::cout << item->name << std::endl;
for (auto& revdepobj: item->reversed) {
auto revdep = revdepobj.second;
auto it = revdep->dependencies.find(item->name);
revdep->dependencies.erase(it);
}
items.erase(it);
++removed;
}
it = next;
}
if (removed == 0) {
std::cerr << "reference cycle!" << std::endl; break;
}
}
for (auto& object: items) {
auto item = object.second;
std::cout << item->name << ":";
for (auto& depobj: item->dependencies) {
auto dep = depobj.second;
std::cout << " " << dep->name;
}
std::cout << std::endl;
}
}