KVTree.cc

#include "KVTree.hpp"

void TreeIterator::next() {
    return;
}

bool TreeIterator::has_next() {
    while (!_stack.empty() || _cur) {
        if (_cur == nullptr) {
            _cur = _stack.top();
            _visited[_cur]++;
            if (_visited[_cur] == _cur->children().end()) {
                _cur = nullptr;
                _stack.pop();
                _path.pop_back();
            } else {
                _cur = _visited[_cur]->second;
            }
        } else if (_cur->is_leaf()) {
            return true;
        } else {
            auto iter = _visited.find(_cur);
            if (iter == _visited.end()) {
                _visited[_cur] = _cur->children().begin();
                _stack.push(_cur);
                _path.push_back(_cur->key());
                _cur = _visited[_cur]->second;
            } else {
                _cur = nullptr;
            }
        }
    }
            
    return false;
}

pair<string, string> TreeIterator::get_value() {
    string res = _cur->value();
    
    string path = full_path() + "/" + _cur->key();
    _cur = nullptr;
    return {path, res};
}

int main() {
    Handle handle;

    handle.add_mapping("/foo/bar/x", "XController");
    handle.add_mapping("/foo/bar/z", "ZController");
    handle.add_mapping("/foo/baz", "BazController");
    
    {
        auto res = handle.get_mapping("/");
        for (auto p: res) {
            auto path = p.first;
            auto value = p.second;

            Printer::get_instance().print(path + " -> " + value);
        }
        Printer::get_instance().print("---");
    }

    {
        auto res = handle.get_mapping("/foo/bar/x");
        for (auto p: res) {
            auto path = p.first;
            auto value = p.second;

            Printer::get_instance().print(path + " -> " + value);
        }
        Printer::get_instance().print("---");
    }
    
    {
        auto res = handle.get_mapping("/foo/bar");
        for (auto p: res) {
            auto path = p.first;
            auto value = p.second;

            Printer::get_instance().print(path + " -> " + value);
        }
        Printer::get_instance().print("---");
    }

    return 0;
}

KVTree.hpp

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <stack>
#include <vector>
#include <unordered_map>

using namespace std;

class Printer {
public:
    static Printer& get_instance() {
        static Printer printer;
        return printer;
    }

    template <typename T>
    void print(const T& item) {
        cout << item << endl;
    }

    template <typename T>
    void error(const T& item) {
        cerr << item << endl;
    }
private:
    Printer() {}
    Printer(const Printer& printer);
    Printer& operator= (const Printer& printer);
};

class TreeNode;

class TreeIterator {
public:
    TreeIterator(TreeNode* cur): _cur(cur) {}
    bool has_next();

    void next();
    pair<string, string> get_value();
private:
    string full_path() {
        string res;
        for (auto path: _path) {
            if (!res.empty() && *res.rbegin() != '/') {
                res += "/";
            }
            res += path;
        }
        return res;
    }
private:
    TreeNode* _cur;
    vector<string> _path;
    stack<TreeNode*> _stack;
    unordered_map<TreeNode*, map<string, TreeNode*>::iterator > _visited;
};

class TreeNode {
public:
    TreeNode(const string& key): _key(key), _value("") {}
    TreeNode(const string& key, const string& value): _key(key), _value(value) {}

    bool is_leaf() {
        return !_value.empty();
    }
    
    const string& key() {
        return _key;
    }

    const string& value() {
        return _value;
    }

    TreeIterator list(const vector<string>& path) {
        return list(path.begin(), path.end());
    }

    map<string, TreeNode*>& children() {
        return _children;
    }

    TreeIterator list(vector<string>::const_iterator begin, vector<string>::const_iterator end) {
        if (begin == end) {
            return TreeIterator(this);
        }

        auto iter = _children.find(*begin);

        if (iter == _children.end()) {
            return TreeIterator(nullptr);
        }

        return iter->second->list(++begin, end);
    }

    int add_child(const vector<string>& path, const string& value) {
        if (path.size() < 2) {
            Printer::get_instance().error("Encounter an empty path when adding child");
            return -1;
        }
        return add_child(path.begin(), path.end(), value);
    }
private:
    int add_child(vector<string>::const_iterator begin, vector<string>::const_iterator end, const string& value) {
        if (begin == end) {
            _value = value;
            return 0;
        } else {
            auto iter = _children.find(*begin);
            if (iter == _children.end()) {
                TreeNode* tree_node = new TreeNode(*begin);
                _children[*begin] = tree_node;
            }
            return _children[*begin]->add_child(++begin, end, value);
        }
    }

private:
    string _key;
    string _value;
    map<string, TreeNode*> _children;
};


class Handle {
public:
    Handle(): _root(new TreeNode("/")) {}

    vector<pair<string, string> > get_mapping(const string& pathstr) {
        vector<string> path = get_path(pathstr);
        auto iter = _root->list(path);
        vector<pair<string, string> > res;
        
        while (iter.has_next()) {
            iter.next();
            res.push_back(iter.get_value());
        }
        return res;
    }
    
    void add_mapping(const string& pathstr, const string& value) {
        vector<string> path = get_path(pathstr);
        _root->add_child(path, value);
    }
    
private:
    vector<string> get_path(const string& pathstr) {
        vector<string> res;

        string tmp;
        for (auto c: pathstr) {
            if (c == '/' && !tmp.empty()) {
                res.push_back(tmp);
                tmp = "";
            } else if (c != '/') {
                tmp.push_back(c);
            }
        }
        if (!tmp.empty()) {
            res.push_back(tmp);
        }
        return res;
    }
private:
    TreeNode* _root;
};