CC0 1.0 Universal

intrusive_tree_base.cpp

// 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_base.hpp

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