Skip to content

Instantly share code, notes, and snippets.

@ttsuki ttsuki/tree.cpp Secret
Last active Dec 31, 2015

Embed
What would you like to do?
// treecontainer.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//
#include "stdafx.h"
#include <cassert>
#include <algorithm>
#include <functional>
template <class T> class Tree;
template <class T>
class TreeNode
{
public:
typedef TreeNode Node;
//const static int nullptr = 0;
void ASSERT(bool exp) { assert(exp); }
public:
Node *Parent() const { return _parent; }
Node *Next() const { return _next; }
Node *Prev() const { return _prev; }
Node *FirstChild() const { return _firstChild; }
T & Value() { return _value; }
const T& Value() const { return _value; }
/// construct
TreeNode(const T &value)
: _parent(nullptr)
, _prev(nullptr), _next(nullptr)
, _firstChild(nullptr), _lastChild(nullptr)
, _value(value)
{
}
/// 親子の縁組み。親側で呼ぶ。
void AddChild(Node *pNewChild)
{
ASSERT(pNewChild != nullptr);
ASSERT(pNewChild->_parent == nullptr);
if (!pNewChild || pNewChild->Parent()) return;
if (_lastChild != nullptr)
{
_lastChild->_next = pNewChild;
pNewChild->_prev = _lastChild;
_lastChild = pNewChild;
}
else
{
_firstChild = _lastChild = pNewChild;
}
pNewChild->_parent = this;
}
/// 親子の縁を切る。親側で呼ぶ
void UnlinkChild(Node *pChild)
{
ASSERT(pChild != nullptr);
ASSERT(pChild->Parent() == this);
if (!pChild || pChild->Parent() != this) return;
if (pChild->_next) pChild->_next->_prev = pChild->_prev;
if (pChild->_prev) pChild->_prev->_next = pChild->_next;
if (_firstChild == pChild) _firstChild = pChild->_next;
if (_lastChild == pChild) _lastChild = pChild->_prev;
pChild->_parent = nullptr;
pChild->_prev = nullptr;
pChild->_next = nullptr;
// pChildの子には関与しない。
}
/// 自身と全ての子ノードにfuncを適用。親が先。
template <class TFunc>
void ApplyFunc(TFunc &func, bool children = true, bool recursive = true)
{
func(this);
if (children && _firstChild != nullptr)
{
for (Node *p = _firstChild, *n; p; p = n)
{
n = p->_next;
p->ApplyFunc(func, recursive, true);
}
}
}
/// 自身と全ての子ノードにfuncを適用。子供が先。
template <class TFunc>
void ApplyFuncChildrenFirst(TFunc &func, bool children = true, bool recursive = true)
{
if (children && _firstChild != nullptr)
{
for (Node *p = _firstChild, *n; p; p = n)
{
n = p->_next;
p->ApplyFuncChildrenFirst(func, recursive, true);
}
}
func(this);
}
/// 根から自分までのパスに対してfuncを適用。根が先。
template <class TFunc>
void ApplyFuncToPath(TFunc &func)
{
if (_parent != nullptr)
_parent->ApplyFuncToPath(func);
func(this);
}
/// 根から自分までのパスに対してfuncを適用。根が先。
template <class TFunc>
void ApplyFuncToPath(TFunc &func) const
{
if (_parent != nullptr)
const_cast<const Node *>(_parent)->ApplyFuncToPath(func);
func(this);
}
/// ルートからの距離を取得する。 O(depth(this))
int GetDepth() const
{
int depth;
GetRoot(&depth);
return depth;
};
/// 根を探す。*pDepth にnullptr以外を渡すと深さも返る。 O(depth(this))
Node *GetRoot(/* out */ int *pDepth) const
{
struct
{
int counter;
const Node *pRoot;
void operator () (const Node *pNode)
{
counter++;
if (pRoot == nullptr) pRoot = pNode;
}
} func = { 0, nullptr };
ApplyFuncToPath(func);
if (pDepth != nullptr) *pDepth = func.counter;
return const_cast<Node *>(func.pRoot);
}
// pTargetNodeと共通の最も近い親を探す。 O(max(depth(this),depth(other))
Node *GetNearestCommonAncestor(const Node *pOther) const
{
// 深さを浅い方に揃えてから、根に向かって一致点を調べる。
const Node *pa = this, *pb = pOther;
int da, db;
if (pa->GetRoot(&da) != pb->GetRoot(&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<Node *>(pa);
}
private:
Node *_parent, *_prev, *_next, *_firstChild, *_lastChild;
T _value;
};
/// destruct and deallocate tree or sub-tree recursively with deleter
template <class T, class TDeleter>
inline void DeleteTree(TreeNode<T> *pRoot, TDeleter &deleter)
{
struct
{
TDeleter &deleter;
void operator () (TreeNode<T> *pNode)
{
if (pNode->Parent() != nullptr)
{
pNode->Parent()->UnlinkChild(pNode);
}
deleter(pNode);
}
} delFunctor = { deleter };
pRoot->ApplyFuncChildrenFirst(delFunctor);
}
/// allocate and construct new node
// Nodeオブジェクトをメモリプールしたいなど、独自管理したいときは、
// この関数に似たようなアロケータを書いて使えばよい。
template <class T>
inline TreeNode<T> * NewTreeNode(const T &value)
{
return new TreeNode<T>(value);
}
// destruct and deallocate tree or sub-tree
template <class T>
inline void DeleteTree(TreeNode<T> *pRoot)
{
DestructTree(pRoot, operator delete);
}
//以下テスト用コード。
typedef TreeNode<int> Node;
void DisplayNodeValue(const Node *pNode)
{
printf("/%d", pNode->Value());
}
void DisplayNodeFullPath(const Node *pNode)
{
pNode->ApplyFuncToPath(DisplayNodeValue);
printf(" depth = %d\n", pNode->GetDepth());
}
void DestructTreeWithTrace(Node *pRoot)
{
struct Tracer
{
static void DeleteNode(Node *pNode)
{
printf("deleting %d\n", pNode->Value());
delete pNode;
}
};
DeleteTree(pRoot, Tracer::DeleteNode);
}
Node * CreateTestTree()
{
int i = 0;
Node *tmp, *tmp2, *tmp3;
Node *root = NewTreeNode(i++);
root->AddChild(tmp = NewTreeNode(i++));
tmp->AddChild(tmp2 = NewTreeNode(i++));
tmp->AddChild(NewTreeNode(i++));
tmp2->AddChild(NewTreeNode(i++));
root->AddChild(tmp = NewTreeNode(i++));
tmp->AddChild(tmp2 = NewTreeNode(i++));
tmp->AddChild(NewTreeNode(i++));
tmp->AddChild(tmp3 = NewTreeNode(i++));
tmp3->AddChild(tmp = NewTreeNode(i++));
tmp2->AddChild(tmp = NewTreeNode(i++));
tmp->AddChild(NewTreeNode(i++));
root->AddChild(tmp = NewTreeNode(i++));
root->AddChild(NewTreeNode(i++));
tmp->Value() = 100;
return root;
}
int _tmain(int argc, _TCHAR* argv[])
{
Node *pRoot = CreateTestTree();
pRoot->ApplyFunc(DisplayNodeFullPath); // dump current tree
DestructTreeWithTrace(pRoot->FirstChild()); // destruct first child
pRoot->ApplyFunc(DisplayNodeFullPath); // dump current tree
printf(" common ancestor: ");
DisplayNodeFullPath(
pRoot->FirstChild()->FirstChild()->Next()->Next()->FirstChild()->GetNearestCommonAncestor(
pRoot->FirstChild()->FirstChild()->FirstChild()->FirstChild()));
DestructTreeWithTrace(pRoot->FirstChild()->FirstChild()->FirstChild());
pRoot->FirstChild()->FirstChild()->AddChild(NewTreeNode(123));
pRoot->FirstChild()->FirstChild()->AddChild(NewTreeNode(456));
pRoot->FirstChild()->FirstChild()->AddChild(NewTreeNode(789));
DestructTreeWithTrace(pRoot->FirstChild()->FirstChild()->FirstChild());
DestructTreeWithTrace(pRoot->FirstChild()->FirstChild()->FirstChild()->Next());
DestructTreeWithTrace(pRoot->FirstChild()->FirstChild()->FirstChild());
pRoot->ApplyFunc(DisplayNodeFullPath);
DestructTreeWithTrace(pRoot);
return 0;
}
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.