tree.cpp

// 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;
}