Skip to content

Instantly share code, notes, and snippets.

@Wizmann
Created September 15, 2015 16:49
Show Gist options
  • Save Wizmann/b304ba5349fe0f8eb2d3 to your computer and use it in GitHub Desktop.
Save Wizmann/b304ba5349fe0f8eb2d3 to your computer and use it in GitHub Desktop.
#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;
}
#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;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment