Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
CC0 1.0 Universal
// intrusive_tree_base.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#include <tchar.h>
#include <cassert>
#include "intrusive_tree_base.hpp"
//以下テスト用コード。木構造にしたいノード。
struct IntTreeNode : public intrusive_tree_base<IntTreeNode>
{
int value;
int Value() const { return value; }
int & Value() { return value; }
IntTreeNode(int i) : value(i) { }
};
void DisplayNodeValue(const IntTreeNode* pNode)
{
printf("/%d", pNode->Value());
}
void DisplayNodeFullPath(const IntTreeNode* pNode)
{
pNode->apply_from_root_path(DisplayNodeValue);
printf(" depth = %d\n", pNode->find_depth());
}
void DestructTreeWithTrace(IntTreeNode* pRoot)
{
struct Tracer
{
static void DeleteNode(IntTreeNode* pNode)
{
printf("deleting %d\n", pNode->Value());
delete pNode;
}
};
destruct_tree(pRoot, Tracer::DeleteNode);
}
IntTreeNode* CreateTestTree()
{
int i = 0;
IntTreeNode* tmp, *tmp2, *tmp3;
IntTreeNode* root = new IntTreeNode(i++);
root->add_child(tmp = new IntTreeNode(i++));
tmp->add_child(tmp2 = new IntTreeNode(i++));
tmp->add_child(new IntTreeNode(i++));
tmp2->add_child(new IntTreeNode(i++));
root->add_child(tmp = new IntTreeNode(i++));
tmp->add_child(tmp2 = new IntTreeNode(i++));
tmp->add_child(new IntTreeNode(i++));
tmp->add_child(tmp3 = new IntTreeNode(i++));
tmp3->add_child(tmp = new IntTreeNode(i++));
tmp2->add_child(tmp = new IntTreeNode(i++));
tmp->add_child(new IntTreeNode(i++));
root->add_child(tmp = new IntTreeNode(i++));
root->add_child(new IntTreeNode(i++));
tmp->Value() = 100;
return root;
}
int main(int argc, char* argv [])
{
IntTreeNode* pRoot = CreateTestTree();
pRoot->apply(DisplayNodeFullPath); // dump current tree
DestructTreeWithTrace(pRoot->first_child()); // destruct first child
pRoot->apply(DisplayNodeFullPath); // dump current tree
printf(" common ancestor: ");
DisplayNodeFullPath(
pRoot->first_child()->first_child()->next()->next()->first_child()->find_nearest_common_ancestor(
pRoot->first_child()->first_child()->first_child()->first_child()));
DestructTreeWithTrace(pRoot->first_child()->first_child()->first_child());
pRoot->first_child()->first_child()->add_child(new IntTreeNode(123));
pRoot->first_child()->first_child()->add_child(new IntTreeNode(456));
pRoot->first_child()->first_child()->add_child(new IntTreeNode(789));
DestructTreeWithTrace(pRoot->first_child()->first_child()->first_child());
DestructTreeWithTrace(pRoot->first_child()->first_child()->first_child()->next());
DestructTreeWithTrace(pRoot->first_child()->first_child()->first_child());
pRoot->apply(DisplayNodeFullPath);
DestructTreeWithTrace(pRoot);
return 0;
}
//
// Intrusive Tree node base class
//
#ifndef INTRUSIVE_TREE_BASE_HPP_INCLUDED
#define INTRUSIVE_TREE_BASE_HPP_INCLUDED
template <class T>
class intrusive_tree_base
{
public:
typedef T *pointer;
typedef const T *const_pointer;
void ASSERT(bool exp) { assert(exp); }
public:
pointer parent() const { return _parent; }
pointer next() const { return _next; }
pointer prev() const { return _prev; }
pointer first_child() const { return _first_child; }
/// construct
intrusive_tree_base()
: _parent(nullptr)
, _prev(nullptr), _next(nullptr)
, _first_child(nullptr), _last_child(nullptr)
{
}
intrusive_tree_base(const intrusive_tree_base &rhs)
: _parent(nullptr)
, _prev(nullptr), _next(nullptr)
, _first_child(nullptr), _last_child(nullptr)
{
// リンクは空で
}
/// 親子の縁組み。親側で呼ぶ。
void add_child(pointer new_child)
{
ASSERT(new_child != nullptr);
ASSERT(new_child->_parent == nullptr);
if (!new_child || new_child->parent()) return;
if (_last_child != nullptr)
{
_last_child->_next = new_child;
new_child->_prev = _last_child;
_last_child = new_child;
}
else
{
_first_child = _last_child = new_child;
}
new_child->_parent = this_as_pointer();
}
/// 親子の縁を切る。親側で呼ぶ
void remove_child(pointer child)
{
ASSERT(child != nullptr);
ASSERT(child->parent() == this_as_pointer());
if (!child || child->parent() != this_as_pointer()) return;
if (child->_next) child->_next->_prev = child->_prev;
if (child->_prev) child->_prev->_next = child->_next;
if (_first_child == child) _first_child = child->_next;
if (_last_child == child) _last_child = child->_prev;
child->_parent = nullptr;
child->_prev = nullptr;
child->_next = nullptr;
// childの子には関与しない。
}
/// 自身と全ての子ノードにfuncを適用。親が先。
template <class TFunc>
void apply(TFunc &func, bool children = true, bool recursive = true)
{
func(this_as_pointer());
if (children && _first_child != nullptr)
{
for (pointer p = _first_child, n; p; p = n)
{
n = p->_next;
p->apply(func, recursive, true);
}
}
}
/// 自身と全ての子ノードにfuncを適用。子供が先。
template <class TFunc>
void apply_from_leaf(TFunc &func, bool children = true, bool recursive = true)
{
if (children && _first_child != nullptr)
{
for (pointer p = _first_child, n; p; p = n)
{
n = p->_next;
p->apply_from_leaf(func, recursive, true);
}
}
func(this_as_pointer());
}
/// 根から自分までのパスに対してfuncを適用。根が先。
template <class TFunc>
void apply_from_root_path(TFunc &func)
{
if (_parent != nullptr)
_parent->apply_from_root_path(func);
func(this_as_pointer());
}
/// 根から自分までのパスに対してfuncを適用。根が先。
template <class TFunc>
void apply_from_root_path(TFunc &func) const
{
if (_parent != nullptr)
const_cast<const_pointer>(_parent)->apply_from_root_path(func);
func(this_as_const_pointer());
}
/// ルートからの距離を取得する。 O(depth(this))
int find_depth() const
{
int depth;
find_root(&depth);
return depth;
};
/// 根を探す。*depth にnullptr以外を渡すと深さも返る。 O(depth(this))
pointer find_root(/* out */ int *depth = nullptr) const
{
// 根を探すためのファンクタ
struct
{
int counter;
const_pointer root;
void operator () (const_pointer cur)
{
counter++;
if (root == nullptr) root = cur;
}
} func = { 0, nullptr };
apply_from_root_path(func);
if (depth != nullptr) { *depth = func.counter; }
return const_cast<pointer >(func.root);
}
/// otherと共通の最も近い親を探す。 O(max(depth(this),depth(other))
/// otherが共通の木に属さないとき nullptr。
pointer find_nearest_common_ancestor(const pointer other) const
{
const_pointer pa = this_as_const_pointer(), pb = other;
// 根と深さを調べる
int da, db;
if (pa->find_root(&da) != pb->find_root(&db)) { return nullptr; } // 共通の親でない
// 浅い方に深さをそろえる
int dMin = da < db ? da : db;
for (; da > dMin; da--) { pa = pa->parent(); }
for (; db > dMin; db--) { pb = pb->parent(); }
// 一致するまでさかのぼる
while (pa != pb) { pa = pa->parent(); pb = pb->parent(); }
return const_cast<pointer>(pa);
}
private:
pointer _parent, _prev, _next, _first_child, _last_child;
pointer this_as_pointer() const { return const_cast<pointer>(this_as_const_pointer()); }
const_pointer this_as_const_pointer() const { return static_cast<const_pointer>(this); }
};
/// destruct and deallocate tree or sub-tree recursively with deleter
template <class T, class TDeleter>
inline void destruct_tree(T *tree_root, TDeleter &deleter = T::operator delete)
{
struct
{
TDeleter &deleter;
void operator () (T *node)
{
if (node->parent() != nullptr)
{
node->parent()->remove_child(node);
}
deleter(node);
}
} func = { deleter };
tree_root->apply_from_leaf(func);
}
#endif // #ifndef INTRUSIVE_TREE_BASE_HPP_INCLUDED
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.