-
-
Save ttsuki/95ceef4cacdc9c5e0294 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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