Skip to content

Instantly share code, notes, and snippets.

@oconnore oconnore/Tree.h
Last active Jun 7, 2016

Embed
What would you like to do?
Hierarchical Tree in C++14
#pragma once
#include <algorithm>
#include <exception>
#include <map>
#include <memory>
#include <stack>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
#include <cstddef>
using namespace std;
template <typename T>
class HTree : public std::enable_shared_from_this<HTree<T>> {
private:
bool hasValue = false;
T value = T();
map<string, shared_ptr<HTree<T>>, StrICmp> children;
protected:
void setValue(T& val) {
value = val;
}
T& getValue() {
return value;
}
shared_ptr< HTree<T> > traverse(const vector<string>& path, bool create) {
auto c = this->shared_from_this();
int depth = path.size();
for (auto i : path) {
auto it = c->children.find(i);
if (it != c->children.end()) {
if (depth > 1 && c->hasValue) {
// Only leaves store values
c->hasValue = false;
c->value = T();
}
c = it->second;
} else {
//
if (create) {
// Create a child node
auto nest = make_shared< HTree<T> >();
c->children[i] = nest;
if (depth > 1 && c->hasValue) {
// Only leaves store values
c->hasValue = false;
c->value = T();
}
c = nest;
} else {
// Null and break
c = nullptr;
break;
}
}
depth--;
}
return c;
}
public:
size_t getSize() {
size_t s;
for_each([&s](auto i, auto j) {
s++;
});
return s;
}
void insert(const vector<string>& path, const T& val) {
auto p = traverse(path, true);
if (p) {
p->value = val;
p->hasValue = true;
p->children.clear();
} else {
throw domain_error("Insert failed: No node could be inserted.");
}
}
void update(const vector<string>& path, const T& val) {
auto p = traverse(path, false);
if (p) {
p->value = val;
p->hasValue = true;
p->children.clear();
} else {
throw domain_error("Update failed: No node found.");
}
}
T& lookup(const vector<string>& path) {
auto p = traverse(path, false);
if (p != nullptr && p->hasValue) {
return p->value;
} else {
T* res = nullptr;
int count = 0;
if (p != nullptr) {
try {
p->for_each([&res, &count](auto i, auto j) {
count++;
res = &i;
if (count > 1)
throw -1;
});
} catch (const int& e) {
count = -1;
}
}
if (count == 1 && res != nullptr) {
return *res;
} else {
throw domain_error("Lookup failed: No node found.");
}
}
}
T& lookup(const vector<string>& path, T& def) {
try {
return lookup(path);
} catch (exception& e) {
return def;
}
}
unique_ptr< vector<string> > list(const vector<string>& path) {
auto p = traverse(path, false);
if (p && p->children.size() > 0) {
auto vec = make_unique< vector<string> >(p->children.size());
transform(p->children.begin(), p->children.end(),
vec->begin(), [](auto pair) { return pair.first; });
return vec;
}
return make_unique< vector<string> >();
}
bool erase(const vector<string>& path) {
auto term = path.cend();
if (path.size() >= 1) {
term--;
auto butLast = vector<string>(path.cbegin(), term);
auto p = traverse(butLast, false);
if (p) {
auto el = p->children.find(path.back());
if (el != p->children.end()) {
p->children.erase(el);
return true;
}
}
}
return false;
}
void clear() {
hasValue = false;
value = T();
children.clear();
}
template <class Function>
void for_each(Function f) {
stack< tuple<shared_ptr<HTree<T>>, string, size_t> > s;
vector<string> p;
s.push(make_tuple(this->shared_from_this(), "", 0));
while (!s.empty()) {
auto k = s.top();
s.pop();
auto ptr = get<0>(k); auto name = get<1>(k); auto depth = get<2>(k);
while (depth > 0 && depth < p.size() + 1) {
p.pop_back();
}
if (depth > 0) p.push_back(name);
if (ptr->hasValue) {
f(ptr->value, p);
}
std::for_each(ptr->children.crbegin(), ptr->children.crend(),
[&s, &depth](auto p) {
s.push(make_tuple(p.second, p.first, depth + 1));
});
}
}
template <class Function>
void for_subtree(const vector<string>& path, Function f) {
auto s = traverse(path, false);
if (s) {
vector<string> pp(path);
size_t len = path.size();
auto lf = [&pp, len, f](auto i, auto p) {
pp.resize(len, "__null__");
pp.insert(pp.end(), p.cbegin(), p.cend());
f(i, pp);
};
s->for_each(lf);
}
}
};
// EOF
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.