Участник:AdamantBot/Исходники/adabot.h

Документация
#include "json.hpp"
#include "httplib.h"
#include "mysql++/mysql++.h"
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cctype>
#include <vector>
#include <string>
#include <list>

namespace adabot {
    namespace utils {
        void map(auto begin, auto end, auto fn) {
            transform(begin, end, begin, fn);
        }

        auto map(auto container, auto fn) {
            std::vector<typename std::result_of<decltype(fn)(
                typename decltype(container)::value_type
            )>::type> result;
            transform(begin(container),
                      end(container),
                      std::back_inserter(result), fn);
            return result;
        }

        template<typename T>
        std::vector<std::vector<T>> slice(std::vector<T> container,
                                          int block_size) {
            std::vector<std::vector<T>> res;
            for(size_t i = 0; i < container.size(); i += block_size) {
                size_t last = std::min(i + block_size, container.size());
                res.emplace_back(begin(container) + i, begin(container) + last);
            }
            return res;
        }
    };

    namespace str {
        std::string join(const auto begin, const auto end, std::string separator) {
            std::string res;
            for(auto it = begin; it != end; ++it) {
                res += (res.empty() ? std::string() : separator) + *it;
            }
            return res;
        }

        std::string join(const auto &container, std::string separator) {
            return join(begin(container), end(container), separator);
        }

        std::string rtrim(const std::string &s) {
            return std::string(begin(s), find_if(s.rbegin(), s.rend(), [](char c){
                return !std::isspace(c);
            }).base());
        }

        std::string ltrim(const std::string &s) {
            return std::string(find_if(begin(s), end(s), [](char c){
                return !std::isspace(c);
            }), end(s));
        }
        
        std::string trim(const std::string &s) {
            return ltrim(rtrim(s));
        }

        std::vector<std::string> split(std::string s, char d) {
            s += d;
            size_t start = 0;
            std::vector<std::string> result;
            for(size_t i = 0; i < s.size(); i++) {
                if(s[i] == d) {
                    result.emplace_back(begin(s) + start, begin(s) + i);
                    start = i + 1;
                }
            }
            return result;
        }
            
        std::string replace(std::string a, std::string b, std::string c) {
            size_t idx = a.find(b);
            while(idx != std::string::npos) {
                a.replace(idx, b.size(), c);
                idx = a.find(b);
            }
            return a;
        }
        std::string replace(const std::string &s, char r, const std::string &x) {
            std::string res;
            for(char c: s) {
                if(c == r) {
                    res += x;
                } else {
                    res += c;
                }
            }
            return res;
        }
        auto replacer(char r, const std::string &x) {
            return [r, &x](const std::string &s) {
                return replace(s, r, x);
            };
        }
    };

    class w_token {
    public:
        enum term {
            w_text,
            w_raw,
            w_template,
            w_table,
            w_args,
            w_arg,
            w_value,
            w_iraw,
            w_link,
            w_uninit
        };

        static std::string to_string(term type) {
            switch(type) {
                case w_text     : return "text";
                case w_raw      : return "raw";
                case w_template : return "template";
                case w_table    : return "table";
                case w_arg      : return "arg";
                case w_value    : return "value";
                case w_iraw     : return "iraw";
                case w_link     : return "link";
                case w_uninit   : return "uninitialised";
                default         : return "???";
            };
        }
    private:
        std::list<w_token> tokens;
        std::string value;
        term type;
    public:
        w_token(): type(w_uninit){}
        w_token(term type): type(type){}
        w_token& operator=(const w_token &t) {
            w_token tmp(t);
            tokens = tmp.tokens;
            value = tmp.value;
            type = tmp.type;
            return *this;
        }

        std::string get_name() const {
            assert(special() && type != w_table);
            return tokens.front().get_value();
        }

        std::unordered_map<std::string, w_token> get_args() const {
            assert(special());
            int idx = 1;
            std::unordered_map<std::string, w_token> result;
            for(auto it = type == w_table
                        ? begin(tokens)
                        : next(begin(tokens));
                it != end(tokens); ++it, ++idx) {
                std::string name;
                if(it->size() == 2) {
                    name = it->get_tokens().front().get_value();
                } else {
                    assert(it->size() == 1);
                    name = std::to_string(idx);
                }
                result[name] = it->get_tokens().back();
            }
            return result;
        }

        term get_type() const {
            return type;
        }

        const std::string& get_value() const {
            assert(literal());
            return value;
        }

        const std::list<w_token>& get_tokens() const {
            assert(!literal());
            return tokens;
        }

        bool literal() const {
            return type == w_iraw || type == w_raw;
        }

        bool special() const {
            return type == w_template || type == w_link || type == w_table;
        }

        bool empty() const {
            return tokens.empty() && value.empty();
        }

        size_t size() const {
            if(literal()) {
                return value.size();
            } else {
                return tokens.size();
            }
        }

        void append(const w_token &token) {
            assert(!literal());
            tokens.emplace_back(token);
        }
        void append(auto c) {
            assert(literal());
            value += c;
        }

        w_token& ltrim() {
            if(literal()) {
                value = adabot::str::ltrim(value);
            } else if(!tokens.empty()) {
                tokens.front().ltrim();
            }
            return *this;
        }
        w_token& rtrim() {
            if(literal()) {
                value = adabot::str::rtrim(value);
            } else if(!tokens.empty()) {
                tokens.back().rtrim();
            }
            return *this;
        }
        w_token& trim() {
            ltrim();
            rtrim();
            return *this;
        }

        w_token& finalize() {
            if(type == w_arg) {
                assert(!tokens.empty());
                if(tokens.size() == 1) {
                    trim();
                } else { // a = b = c = ... = x
                    assert(tokens.front().size() == 1);
                    w_token compressed = *next(begin(tokens));
                    for(auto it = next(next(begin(tokens)));
                        it != end(tokens);
                        ++it) {
                        if(compressed.tokens.back().type != w_iraw) {
                            compressed.append(w_token(w_iraw));
                        }
                        compressed.tokens.back().append('=');
                        for(auto jt: it->tokens) {
                            if(compressed.tokens.back().type == w_iraw &&
                               jt.type == w_iraw) {
                                compressed.tokens.back().append(jt.value);
                            } else {
                                compressed.append(jt);
                            }
                        }
                    }
                    tokens = {tokens.front().tokens.front().trim(),
                              compressed.trim()};
                }
            } else if(type == w_text) {
                trim();
            } else if(special() && type != w_table) {
                assert(!tokens.empty());
                assert(tokens.front().size() == 1);
                assert(tokens.front().tokens.front().size() == 1);
                tokens.front() = tokens.front().tokens.front().tokens.front();
            }
            return *this;
        }

        std::string dump(int tab = 4, int h = 0) const {
            std::string result(h, ' ');
            result += to_string(type) + ": " + value + "\n";
            for(auto it: tokens) {
                result += it.dump(tab, h + tab);
            }
            return result;
        }

        std::string to_wikitext() {
            if(literal()) {
                return value;
            } else if(special()) {
                std::string res;
                res = tokens.front().to_wikitext();
                for(auto it = next(begin(tokens)); it != end(tokens); ++it) {
                    res += "|";
                    res += it->to_wikitext();
                }
                if(type == w_template) {
                    res = "{{" + res + "}}";
                } else if(type == w_link) {
                    res = "[[" + res + "]]";
                } else {
                    res = "{|" + res + "|}";
                }
                return res;
            } else if(type == w_arg) {
                if(tokens.size() == 1) {
                    return tokens.front().to_wikitext();
                } else {
                    assert(tokens.size() == 2);
                    return tokens.front().to_wikitext() + "=" +
                           tokens.back().to_wikitext();
                }
            } else {
                std::string res;
                for(auto it: tokens) {
                    res += it.to_wikitext();
                }
                return res;
            }
        }
    }; // w_token

    void to_json(nlohmann::json &j, const w_token &t) {
        if(t.literal()) {
            j = t.get_value();
        } else if(t.special()) {
            j["token_type"] = w_token::to_string(t.get_type());
            if(t.get_type() != w_token::w_table) {
                j["token_name"] = t.get_name();
            }
            j["token_args"] = t.get_args();
        } else {
            j = t.get_tokens();
        }
    }

    /* Production rules:
     * w_text       -> (w_raw | w_special)*
     * w_special    -> w_link | w_template | w_table (implicit term)
     * w_link       -> "[[" arg "|" arg "|" arg ... "|" arg "]]"
     * w_template   -> "{{" arg "|" arg "|" arg ... "|" arg "}}"
     * w_table      -> "{|" arg "|" arg "|" arg ... "|" arg "|}" // very dirty,
     *                                                           but need to do
     *                                                           something with
     *                                                           tables
     * w_arg        -> w_value "=" w_value ... "=" w_value
     * w_value      -> (w_iraw | w_special)*
     * w_raw        -> std::string
     * w_iraw       -> std::string
     *
     * w_arg finalizes to be w_value or w_iraw "=" w_value
     * w_raw can't contain "{{", "[[" and "{|"
     * w_iraw can't contain "{{", "}}", "[[", "]]", "=" and "|"
     * "|" as well might be used in some tags, but let's skip it for now
     */
    class w_parser {
        static bool good_start(const std::string &stream, std::string pat) {
            return stream.size() >= pat.size() &&
                   stream.substr(stream.size() - pat.size()) == pat;
        }
        static bool good_template(const std::string &stream) {
            return good_start(stream, "{{");
        }
        static bool good_link(const std::string &stream) {
            return good_start(stream, "[[");
        }
        static bool good_table(const std::string &stream) {
            return good_start(stream, "|{");
        }
        static bool good_template_cl(const std::string &stream) {
            return good_start(stream, "}}");
        }
        static bool good_link_cl(const std::string &stream) {
            return good_start(stream, "]]");
        }
        static bool good_table_cl(const std::string &stream) {
            return good_start(stream, "}|");
        }
        static bool good_special(const std::string &stream) {
            return good_template(stream) ||
                   good_link(stream) ||
                   good_table(stream);
        }
        static bool good_special_cl(const std::string &stream) {
            return good_template_cl(stream) ||
                   good_link_cl(stream) ||
                   good_table_cl(stream);
        }
        static bool good_raw(const std::string &stream) {
            return !stream.empty() && !good_special(stream);
        }
        static bool good_iraw(const std::string &stream) {
            return good_raw(stream) &&
                   !good_special_cl(stream) &&
                   !good_start(stream, "|") &&
                   !good_start(stream, "=");
        }

        // parse simple word with constraints
        static w_token parse_string(std::string &stream,
                             w_token::term type,
                             auto check) {
            w_token result(type);
            while(check(stream)) {
                result.append(stream.back());
                stream.pop_back();
            }
            return result.finalize();
        }
        static w_token parse_raw(std::string &stream) {
            return parse_string(stream, w_token::w_raw, good_raw);
        }
        static w_token parse_iraw(std::string &stream) {
            return parse_string(stream, w_token::w_iraw, good_iraw);
        }

        // parse (A|B)*, no two A in a row, always parse B if possible
        static w_token parse_seq(std::string &stream,
                                 w_token::term type,
                                 auto parse_r) {
            w_token result(type);
            if(!good_special(stream)) {
                result.append(parse_r(stream));
            }
            while(good_special(stream)) {
                result.append(parse_special(stream));
                if(!good_special(stream)) {
                    result.append(parse_r(stream));
                }
            }
            return result.finalize();
        }

        static w_token parse_split(std::string &stream,
                                   w_token::term type,
                                   auto parse,
                                   char delim) {
            w_token result(type);
            result.append(parse(stream));
            while(!stream.empty() &&
                  !good_special_cl(stream) &&
                  stream.back() == delim) {
                stream.pop_back();
                result.append(parse(stream));
            }
            return result.finalize();
        }

        static w_token parse_value(std::string &stream) {
            return parse_seq(stream, w_token::w_value, parse_iraw);
        }
        static w_token parse_arg(std::string &stream) {
            return parse_split(stream, w_token::w_arg, parse_value, '=');
        }

        static w_token parse_arged(std::string &stream, w_token::term type) {
            assert(good_special(stream));
            stream.pop_back();
            stream.pop_back();
            auto result = parse_split(stream, type, parse_arg, '|');
            assert(good_special_cl(stream));
            stream.pop_back();
            stream.pop_back();
            return result;
        }

        static w_token parse_template(std::string &stream) {
            return parse_arged(stream, w_token::w_template);
        }
        static w_token parse_link(std::string &stream) {
            return parse_arged(stream, w_token::w_link);
        }
        static w_token parse_table(std::string &stream) {
            return parse_arged(stream, w_token::w_table);
        }

        static w_token parse_special(std::string &stream) {
            if(good_template(stream)) {
                return parse_template(stream);
            } else if(good_link(stream)) {
                return parse_link(stream);
            } else {
                return parse_table(stream);
            }
        }

        static w_token parse_text(std::string &stream) {
            return parse_seq(stream, w_token::w_text, parse_raw);
        }
    public:
        static w_token parse(std::string text) {
            std::reverse(begin(text), end(text));
            return parse_text(text);
        }
    }; // w_parser

    class w_client {
        httplib::SSLClient cli;
        bool verbose;
        static int max_block;
        char api[11] = "/w/api.php";
        httplib::Headers headers;
        std::unordered_map<std::string, std::string> tokens;

        static void print_headers(const httplib::Headers &headers) {
            for(auto it: headers) {
                std::cerr << it.first << " : " << it.second << std::endl;
            }
            std::cerr << std::endl;
        }

        void set_cookies(const httplib::Headers &response_headers) {
            // Ok, I have no idea why does it have to be this way...
            if(verbose) {
                std::cerr << "Headers:" << std::endl;
                for(auto it: response_headers) {
                    std::cerr << it.first << " : " << it.second << std::endl;
                }
                std::cerr << std::endl;
            }
            for(auto it: response_headers) {
                if(it.first == "Set-Cookie" &&
                   it.second.find("ession") != std::string::npos) {
                    headers.erase("Cookie");
                    headers.emplace("Cookie", it.second);
                }
            }
        }

        auto send_params(httplib::Params params) {
            auto response = cli.Post(api, headers, params);
            set_cookies(response->headers);
            return nlohmann::json::parse(response->body);
        }

        std::string get_token(std::string type) {
            if(!tokens.count(type)) {
                auto resp = send_params({
                    {"action", "query"},
                    {"format", "json"},
                    {"meta", "tokens"},
                    {"type", type}
                });
                auto token = resp["query"]["tokens"][std::string(type) + "token"];
                std::cerr << "Retrieved " << type << " token: "
                          << token << std::endl;
                tokens[type] = token;
            }
            return tokens[type];
        }

        std::unordered_map<std::string, int> ns_ids;
        std::unordered_map<int, std::string> ns_names;

        void prepare_namespaces() {
            auto resp = send_params({
                {"action", "query"},
                {"format", "json"},
                {"meta", "siteinfo"},
                {"siprop", "namespaces"}
            });
            for(auto it: resp["query"]["namespaces"]) {
                ns_ids[it["*"]] = it["id"];
                ns_names[it["id"]] = it["*"];
            }
        }
    public:
        static void set_max_block(int new_block) {
            max_block = new_block;
        }
        w_client(std::string domain, bool verb = false): cli(domain),
                                                         verbose(verb) {
            std::cerr << "Connected to " << domain << std::endl;
            prepare_namespaces();
            std::cerr << "Site has " << ns_ids.size()
                      << " namespaces" << std::endl;
        }

        std::unordered_map<std::string, int> get_namespaces() {
            return ns_ids;
        }

        std::string login(std::string login,
                          std::string botname,
                          std::string password) {
            auto token = get_token("login");
            auto response = send_params({
                {"action", "login"},
                {"format", "json"},
                {"lgname", login + "@" + botname},
                {"lgpassword", password},
                {"lgtoken", token}
            });
            auto result = response["login"]["result"];
            std::cerr << "Login as " << login
                      << ", status: " << result << std::endl;
            if(result != "Success" || verbose) {
                std::cerr << response << std::endl;
            }
            return result;
        }

        auto userinfo() {
            httplib::Params params ;
            auto response = send_params({
                {"action", "query"},
                {"format", "json"},
                {"meta", "userinfo"},
                {"uiprop", "groups|rights|ratelimits"}
            });
            return response;
        }

        auto transcludedin(std::vector<std::string> all_titles,
                           unsigned block_size = max_block) {
            std::cerr << "Extracting transcludedin of "
                      << all_titles.size() << " page(s)..." << std::endl;
            int queries = 0;
            std::unordered_map<std::string, std::vector<std::string>> result;
            for(auto titles: utils::slice(all_titles, block_size)) {
                httplib::Params params {
                    {"action", "query"},
                    {"format", "json"},
                    {"titles", str::join(titles, "|")},
                    {"prop", "transcludedin"},
                    {"tilimit", "max"}
                };
                do {
                    queries++;
                    auto obj = send_params(params);
                    params.erase("ticontinue");
                    if(!obj["continue"].empty()) {
                        params.emplace("ticontinue", obj["continue"]
                                                        ["ticontinue"]);
                    }
                    for(auto it: obj["query"]["pages"]) {
                        std::string title = it["title"];
                        for(auto jt: it["transcludedin"]) {
                            result[title].push_back(jt["title"]);
                        }
                    }
                } while(params.count("ticontinue"));
            }
            std::cerr << "Extracted in " << queries << " queries" << std::endl;
            return result;
        }

        auto transcludedin(std::string title) {
            return begin(transcludedin(std::vector<std::string>{title}))
                    ->second;
        }

        auto wikitext(std::vector<std::string> all_titles,
                      unsigned block_size = max_block) {
            std::unordered_map<std::string, std::string> result;
            std::cerr << "Extracting wikitext of "
                      << all_titles.size() << " page(s)..." << std::endl;
            int queries = 0;
            for(auto titles: utils::slice(all_titles, block_size)) {
                httplib::Params params {
                    {"action", "query"},
                    {"format", "json"},
                    {"titles", str::join(titles, "|")},
                    {"prop", "revisions"},
                    {"rvslots", "*"},
                    {"rvprop", "content"}
                };
                do {
                    queries++;
                    auto obj = send_params(params);
                    params.erase("rvcontinue");
                    if(!obj["continue"].empty()) {
                        params.emplace("rvcontinue", obj["continue"]
                                                        ["rvcontinue"]);
                    }
                    for(auto it: obj["query"]["pages"]) {
                        result[it["title"]] = it["revisions"][0]
                                                ["slots"]["main"]["*"];
                    }
                } while(params.count("rvcontinue"));
            }
            std::cerr << "Extracted in " << queries << " queries" << std::endl;
            return result;
        }

        auto wikitext(std::string title) {
            return begin(wikitext(std::vector<std::string>{title}))->second;
        }

        void edit(std::string title,
                  std::string text,
                  std::string summary = "automated edit via AdaBot",
                  bool minor = true,
                  bool bot = true) {
            auto token = get_token("csrf");
            auto params = httplib::Params{
                {"action", "edit"},
                {"format", "json"},
                {"title", title},
                {"text", text},
                {"summary", summary},
                {"token", token},
                {"assert", "bot"}
            };
            if(minor) {
                params.emplace("minor", "");
            }
            if(bot) {
                params.emplace("bot", "");
            }
            auto response = send_params(params);
            auto result = response["edit"]["result"];
            std::cerr << "Edit on page " << title
                      << ", status: " << result << std::endl;
            if(result != "Success" || verbose) {
                std::cerr << response << std::endl;
            }
        }
    }; // w_client
    int w_client::max_block = 50;

    class r_client {
        mysqlpp::Connection con;

        static std::string normalize(std::string s) {
            return "\"" + str::replace(s, '\"', "\\\"") + "\"";
        }
    public:
        r_client(std::string db,
                 std::string server,
                 std::string login,
                 std::string password,
                 unsigned port): con(db.c_str(),
                                     server.c_str(),
                                     login.c_str(),
                                     password.c_str(),
                                     port) {}

        std::unordered_set<std::string>
            get_subcats(std::string root,
                        std::vector<std::string> forbidd = {},
                        int max_depth = -1) {
            forbidd.push_back(root);
            std::vector<std::string> newcats = {root};
            std::unordered_set<std::string> subcats = {root};
            int depth = 1;
            while(newcats.size() && max_depth--) {
                auto query = con.query("select page_title from categorylinks "
                                       "inner join page on cl_from = page_id "
                                       "where cl_type = \"subcat\" and "
                                       "cl_to in (" +
                                       str::join(utils::map(newcats,
                                                            normalize), ",") +
                                       ") and page_title not in (" +
                                       str::join(utils::map(forbidd,
                                                            normalize), ",") +
                                       ");").use();
                newcats.clear();
                while(auto row = query.fetch_row()) {
                    std::string title = row["page_title"].data();
                    if(!subcats.count(title)) {
                        newcats.push_back(title);
                        subcats.insert(title);
                    }
                }
                std::cerr << "New categories on depth " << depth++ << ": "
                          << newcats.size() << ",\ttotal: "
                          << subcats.size() << std::endl;
            }
            return subcats;
        }

        std::vector<std::pair<int,          // id
                              std::string>  // title
                              > dump_categories() {
            std::cerr << "Collecting category names..." << std::endl;
            auto query = con.query("select page_id, page_title "
                                   "from page where page_namespace=14;").use();
            std::vector<std::pair<int, std::string>> result;
            while(auto row = query.fetch_row()) {
                result.emplace_back(row["page_id"], row["page_title"]);
            }
            std::cerr << "Categories collected, " << result.size()
                      << " categories" << std::endl;
            return result;
        }

        std::vector<std::pair<int,  // cl_from
                              int>  // cl_to
                              > dump_catlinks() {
            std::cerr << "Collecting category links..." << std::endl;
            auto query = con.query("select cl_from, page_id as cl_to "
                                   "from categorylinks inner join page "
                                   "on page_title = cl_to "
                                   "where cl_type=\"subcat\";").use();
            std::vector<std::pair<int, int>> result;
            while(auto row = query.fetch_row()) {
                result.emplace_back(row["cl_from"], row["cl_to"]);
            }
            std::cerr << "Catlinks collected, " << result.size()
                      << " catlinks" << std::endl;
            return result;
        }

        std::vector<std::tuple<int,         // id
                               int,         // namespace
                               std::string, // name
                               std::string, // timestamp
                               std::string> // actor
                               > dump_recentchanges() { // pages from 2019 on
            std::cerr << "Collecting recent changes..." << std::endl;
            auto query = con.query("select log_page,log_timestamp,"
                                   "actor_name,page_title,page_namespace "
                                   "from logging "
                                   "inner join actor on log_actor = actor_id "
                                   "inner join page on log_page = page_id "
                                   "where log_type = \"create\" "
                                   "order by log_timestamp;").use();
            std::vector<std::tuple<int,
                                   int,
                                   std::string,
                                   std::string,
                                   std::string>> result;
            while(auto row = query.fetch_row()) {
                result.emplace_back(row["log_page"],
                                    row["page_namespace"],
                                    row["page_title"],
                                    row["log_timestamp"],
                                    row["actor_name"]);
            }
            std::cerr << "Recent pages collected, " << result.size()
                      << " pages" << std::endl;
            return result;
        }

        std::unordered_map<int,                     // id
                           std::vector<std::string> // cl_to
                           > catlinks(auto ids) {
            std::cerr << "Collecting categories of " << ids.size()
                      << " pages..." << std::endl;
            auto query = con.query("select cl_from, cl_to from categorylinks "
                                   "where cl_from in(" +
                                   str::join(utils::map(ids, [](int x){
                                       return std::to_string(x);
                                   }), ",") +
                                   ");").use();
            int counter = 0;
            std::unordered_map<int, std::vector<std::string>> result;
            while(auto row = query.fetch_row()) {
                result[row["cl_from"]].push_back(std::string(row["cl_to"]));
                counter++;
            }
            std::cerr << "Categories collected, " << counter
                      << " categoies" << std::endl;
            return result;
        }

    }; // r_client

    class r_pages {
        std::unordered_map<int, int> ns;
        std::unordered_map<int, std::string> name;
        std::unordered_map<int, std::string> actor;
        std::unordered_map<int, std::string> timestamp;
        std::unordered_map<int, std::vector<std::string>> categories;
        std::vector<int> id_list;
        
        std::string full_name(int ns, std::string title) {
            return std::to_string(ns) + ":" + title;
        }
    public:
        r_pages(r_client rcl) {            
            auto recents = rcl.dump_recentchanges();
            for(auto it: recents) {
                int id = std::get<0>(it);
                tie(id, ns[id], name[id],
                    timestamp[id], actor[id]) = it;
                id_list.push_back(id);
            }
            categories = rcl.catlinks(id_list);
        }

        std::vector<std::tuple<std::string, // timestamp
                               std::string, // title
                               std::string  // actor
                               >> pages(std::unordered_set<std::string> cats,
                                        int space) {
            std::vector<std::tuple<std::string,
                                   std::string,
                                   std::string>> result;
            for(auto id: id_list) {
                if(ns[id] == space) {
                    for(auto cat: categories[id]) {
                        if(cats.count(cat)) {
                            result.emplace_back(timestamp[id],
                                                name[id],
                                                actor[id]);
                            break;
                        }
                    }
                }
            }
            reverse(begin(result), end(result));
            return result;
        }
    };

    class cl_graph {
        std::unordered_map<int, std::string> cl_names;
        std::unordered_map<std::string, int> cl_ids;
        std::unordered_map<int, std::vector<int>> g;

        void add_cat(int id, std::string name) {
            cl_names[id] = name;
            cl_ids[name] = id;
        }

        void add_edge(int from, int to) {
            g[from].push_back(to);
        }
    public:
        cl_graph(std::vector<std::pair<int, std::string>> cats,
                 std::vector<std::pair<int, int>> catlinks) {
            for(auto it: cats) {
                add_cat(it.first, it.second);
            }
            for(auto it: catlinks) {
                add_edge(it.second, it.first);
            }
        }
        cl_graph(r_client rcl) {
            *this = cl_graph(rcl.dump_categories(),
                             rcl.dump_catlinks());
        }

        std::unordered_set<std::string>
                                    get_subcats(std::vector<std::string> root,
                                                std::vector<std::string> forb,
                                                int depth) {
            std::unordered_set<std::string> subcats(begin(root), end(root)),
                                            forbidd(begin(forb), end(forb));
            std::vector<std::string> layer = root;
            while(!layer.empty() && depth--) {
                std::vector<std::string> new_layer;
                for(auto it: layer) {
                    for(auto jt: g[cl_ids[it]]) {
                        auto title = cl_names[jt];
                        if(!subcats.count(title) &&
                           !forbidd.count(title)) {
                            subcats.insert(title);
                            new_layer.push_back(title);
                        }
                    }
                }
                layer = new_layer;
            }
            return subcats;
        }
    }; // cl_graph
}

 

Prefix: a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9

Portal di Ensiklopedia Dunia