/*
								+---------------------------------+
								|                                 |
								| ***  Generic tree template  *** |
								|                                 |
								|  Copyright  © -tHE SWINe- 2006  |
								|                                 |
								|             Tree.h              |
								|                                 |
								+---------------------------------+
*/

#pragma once
#ifndef __TREE_TEMPLATE_INCLUDED
#define __TREE_TEMPLATE_INCLUDED

/**
 *	@file Tree.h
 *	@date 2006
 *	@author -tHE SWINe-
 *	@brief Generic tree template
 *
 *	@date 2012-06-19
 *
 *	Moved multiple inclusion guard before file documentation comment.
 *
 *	Unified linux / windows line ends.
 *
 */

/*struct CCaller {
	inline bool operator ()(CNode *p_node) { return p_node->DoSomething(); }
};

struct CProgressCaller { // with measurement of progress
	inline bool operator ()(CNode *p_node, float f_progress)
	{ UpdateProgressMeter(f_progress); return p_node->DoSomething(); }
};*/

/*
 *	template <const int n_subnode_num, class CNodeClass>
 *	class CNode
 *		- generic node class (not container class!)
 *		- n_subnode_num means maximal number of subnodes, node can have
 *		  (2 is binary tree, 8 is octree, ...)
 *      - CNodeClass is name of node class (this template is meant to be
 *        inherited from by node class, whose name needs to be passed here)
 *		- nodes have links between them so you can write very non-recursive
 *		  pre-order traversal function (pre-order means visit node, then it's children)
 */
template <const int n_subnode_num, class CNodeClass>
class CNode {
protected:
	CNodeClass *m_subnode_list[n_subnode_num];
	int m_n_prev_delta, m_n_next_delta;
	CNodeClass *m_p_parent_node, *m_p_prev_node, *m_p_next_node;

public:
	/*
	 *	CNode(CNodeClass *p_parent_node)
	 *		- default constructor
	 *		- p_parent_node points to parent node, when it's 0, node considers itself root
	 *		- clears children list
	 */
	CNode(CNodeClass *p_parent_node)
		:m_p_parent_node(p_parent_node), m_p_prev_node(0), m_p_next_node(0),
		m_n_prev_delta(0), m_n_next_delta(0)
	{
		for(CNodeClass **p_sub_node = m_subnode_list, **p_end = m_subnode_list + n_subnode_num;
		   p_sub_node < p_end;)
			*p_sub_node ++ = 0;
	}

	/*
	 *	~CNode()
	 *		- destructor
	 *		- delete subnodes as well
	 *		- in case node isn't root, it clears pointer pointing to it
	 *		- updates fast recurse pointers
	 */
	~CNode()
	{
		for(CNodeClass **p_sub_node = m_subnode_list, **p_end = m_subnode_list + n_subnode_num;
		   p_sub_node < p_end; p_sub_node ++) {
			if(*p_sub_node)
				delete *p_sub_node;
		}
		// delete child nodes

		if(m_p_parent_node) {
			for(CNodeClass **p_sibling_node = m_p_parent_node->m_subnode_list,
			   **p_end = m_p_parent_node->m_subnode_list + n_subnode_num;
			   p_sibling_node < p_end; p_sibling_node ++) {
				if(*p_sibling_node == this) {
					*p_sibling_node = 0;
					break;
				}
			}
		}
		// remove from parent subnode list

		if(m_p_prev_node) {
			m_p_prev_node->m_p_next_node = m_p_next_node;
			m_p_prev_node->m_n_next_delta += m_n_next_delta;
		}
		if(m_p_next_node) {
			m_p_next_node->m_p_prev_node = m_p_prev_node;
			m_p_next_node->m_n_prev_delta += m_n_prev_delta;
		}
		// keep fast-traversal list chained
	}

	/*
	 *	inline CNodeClass *p_Parent()
	 *		- returns pointer to parent node or 0 in case node is root
	 */
	inline CNodeClass *p_Parent()
	{
		return m_p_parent_node;
	}

	/*
	 *	inline const CNodeClass *p_Parent() const
	 *		- returns pointer to parent node or 0 in case node is root
	 */
	inline const CNodeClass *p_Parent() const
	{
		return m_p_parent_node;
	}

	/*
	 *	inline bool b_IsRoot() const
	 *		- returns true in case node is root. otherwise false
	 */
	inline bool b_IsRoot() const
	{
		return m_p_parent_node == 0;
	}

	/*
	 *	bool b_IsLeaf() const
	 *		- returns true in case node is leaf (has no children) otherwise false
	 */
	bool b_IsLeaf() const
	{
		for(const CNodeClass **p_sub_node = p_Front_SubNode(), **p_end = p_End_SubNode();
		   p_sub_node < p_end; p_sub_node ++) {
			if(*p_sub_node)
				return false;
		}
		return true;
	}

	/*
	 *	inline CNodeClass **p_Front_SubNode()
	 *		- returns iterator, pointing to first subnode
	 */
	inline CNodeClass **p_Front_SubNode()
	{
		return m_subnode_list;
	}

	/*
	 *	inline CNodeClass **p_Back_SubNode()
	 *		- returns iterator, pointing to last subnode
	 */
	inline CNodeClass **p_Back_SubNode()
	{
		return m_subnode_list + n_subnode_num - 1;
	}

	/*
	 *	inline CNodeClass **p_End_SubNode()
	 *		- returns iterator, pointing behind last subnode
	 */
	inline CNodeClass **p_End_SubNode()
	{
		return m_subnode_list + n_subnode_num;
	}

	/*
	 *	inline CNodeClass **p_Front_SubNode()
	 *		- returns iterator, pointing to first subnode
	 */
	inline const CNodeClass **p_Front_SubNode() const
	{
		return (const CNodeClass **)m_subnode_list;
	}

	/*
	 *	inline const CNodeClass **p_Back_SubNode() const
	 *		- returns iterator, pointing to last subnode
	 */
	inline const CNodeClass **p_Back_SubNode() const
	{
		return (const CNodeClass **)m_subnode_list + n_subnode_num - 1;
	}

	/*
	 *	inline const CNodeClass **p_End_SubNode() const
	 *		- returns iterator, pointing behind last subnode
	 */
	inline const CNodeClass **p_End_SubNode() const
	{
		return (const CNodeClass **)m_subnode_list + n_subnode_num;
	}

	/*
	 *	inline CNodeClass *p_Prev_Node()
	 *		- returns pointer to previous node or 0 in case node is root
	 *		- previous means previous node in traversal
	 */
	inline CNodeClass *p_Prev_Node()
	{
		return m_p_prev_node;
	}

	/*
	 *	inline CNodeClass *p_Next_Node()
	 *		- returns pointer to next node or 0 in case node is rightmost child of root
	 *		- next means next node in traversal
	 */
	inline CNodeClass *p_Next_Node()
	{
		return m_p_next_node;
	}

	/*
	 *	inline const CNodeClass *p_Prev_Node() const
	 *		- returns pointer to previous node or 0 in case node is root
	 *		- previous means previous node in traversal
	 */
	inline const CNodeClass *p_Prev_Node() const
	{
		return m_p_prev_node;
	}

	/*
	 *	inline const CNodeClass *p_Next_Node() const
	 *		- returns pointer to next node or 0 in case node is rightmost child of root
	 *		- next means next node in traversal
	 */
	inline const CNodeClass *p_Next_Node() const
	{
		return m_p_next_node;
	}

	/*
	 *	inline int n_Prev_DeltaLevel() const
	 *		- returns number of tree levels to prev node
	 *		  (negative number means descent to root, positive means ascend towards leafs)
	 */
	inline int n_Prev_DeltaLevel() const
	{
		return m_n_prev_delta;
	}

	/*
	 *	inline int n_Next_DeltaLevel() const
	 *		- returns number of tree levels to next node
	 *		  (negative number means descent to root, positive means ascend towards leafs)
	 */
	inline int n_Next_DeltaLevel() const
	{
		return m_n_next_delta;
	}

protected:
	/*
	 *	template <class CCaller>
	 *	bool TraverseFunc_UpdateTree_Progress(CCaller t_caller)
	 *		- simple traversal, called function must not create any new nodes
	 *		  (it can delete them, destructor will do the updates)
	 *		- CCaller must have public member function:
	 *		  bool operator ()(CNodeClass *p_node)
	 *		- p_node must not be deleted in that function
	 */
	template <class CCaller>
	bool TraverseFunc(CCaller t_caller)
	{
		int n_level = 0;
		CNodeClass *p_cur_node = (CNodeClass*)this;
		do {
			if(!t_caller(p_cur_node))
				return false;
			n_level += p_cur_node->m_n_next_delta;
			p_cur_node = p_cur_node->m_p_next_node;
		} while(n_level > 0 && p_cur_node);

		return true;
	}

	/*
	 *	template <class CCaller>
	 *	bool TraverseFunc_UpdateTree(CCaller t_caller)
	 *		- traversal with possibility of tree modification (fast traverse pointers
	 *		  gets updated)
	 *		- CCaller must have public member function:
	 *		  bool operator ()(CNodeClass *p_node)
	 *		- p_node must not be deleted in that function
	 */
	template <class CCaller>
	bool TraverseFunc_UpdateTree(CCaller t_caller)
	{
		int n_level = 0;
		CNodeClass *p_cur_node = (CNodeClass*)this;

		do {
			if(!t_caller(p_cur_node))
				return false;

			p_cur_node->m_p_next_node = 0;
			for(CNodeClass **p_sub_node = p_cur_node->m_subnode_list,
			   **p_end = p_cur_node->m_subnode_list + n_subnode_num;
			   p_sub_node < p_end; p_sub_node ++) {
				if(*p_sub_node) {
					n_level ++;
					p_cur_node->m_n_next_delta = 1;
					p_cur_node->m_p_next_node = *p_sub_node;
					break;
				}
			}
			// try to recurse up

			bool b_break = false;
			if(!p_cur_node->m_p_next_node) {
				p_cur_node->m_n_next_delta = 0;
				if(p_cur_node->m_p_parent_node) {
					CNodeClass *p_parent = p_cur_node;
					do {
						CNodeClass *p_search_node = p_parent; 
						p_parent = p_parent->m_p_parent_node;
						p_cur_node->m_n_next_delta --;
						if(-- n_level < 0) {
							b_break = true; // need to link to next node!
							if(!p_parent)
								break;
						}
						// (could end here for root, but when calling this for non-root node,
						// we need to assure it's linkage to the rest of the tree)

						{bool b_found_self = false;
						for(CNodeClass **p_sub_node = p_parent->m_subnode_list,
						   **p_end = p_parent->m_subnode_list + n_subnode_num;
						   p_sub_node < p_end; p_sub_node ++) {
							if(b_found_self && *p_sub_node) {
								n_level ++;
								p_cur_node->m_n_next_delta ++;
								p_cur_node->m_p_next_node = *p_sub_node;
								break;
							} else if(*p_sub_node == p_search_node)
								b_found_self = true;
						}}
						// try to recurse sideways
					} while(!p_cur_node->m_p_next_node);
				}
			}
			// determine node next to current

			if(p_cur_node->m_p_next_node) {
				p_cur_node->m_p_next_node->m_p_prev_node = p_cur_node;
				p_cur_node->m_p_next_node->m_n_prev_delta = -p_cur_node->m_n_next_delta;
			}
			// link prev node

			if(b_break)
				break;
		} while((p_cur_node = p_cur_node->m_p_next_node) && n_level > 0);

		return true;
	}
	// the same, but algorithm may delete / add some nodes, this refreshes fast recurse tree

	/*
	 *	template <class CProgressCaller>
	 *	bool TraverseFunc_UpdateTree_Progress(CProgressCaller t_caller)
	 *		- simple traversal, called function must not create any new nodes
	 *		  (it can delete them, destructor will do the updates)
	 *		- caller struct gets float value in range <0, 1) for some progress-meter
	 *		  (the progress is calculated as before calling the function so it can never be 1)
	 *		- CProgressCaller must have public member function:
	 *		  bool operator ()(CNodeClass *p_node, float f_progress)
	 *		- p_node must not be deleted in that function
	 */
	template <class CProgressCaller>
	bool TraverseFunc_Progress(CProgressCaller t_caller)
	{
		float f_progress = .0f;
		int n_level = 0;
		CNodeClass *p_cur_node = (CNodeClass*)this;
		do {
			if(!t_caller(p_cur_node, f_progress))
				return false;

			if(p_cur_node->b_IsLeaf())
				f_progress += (float)pow(n_subnode_num, -n_level);
			// calc progress

			n_level += p_cur_node->m_n_next_delta;
			p_cur_node = p_cur_node->m_p_next_node;
		} while(n_level > 0 && p_cur_node);

		return true;
	}

	/*
	 *	template <class CProgressCaller>
	 *	bool TraverseFunc_UpdateTree_Progress(CProgressCaller t_caller)
	 *		- traversal with possibility of tree modification (fast traverse pointers
	 *		  gets updated)
	 *		- caller struct gets float value in range <0, 1) for some progress-meter
	 *		  (the progress is calculated as before calling the function so it can never be 1)
	 *		- CProgressCaller must have public member function:
	 *		  bool operator ()(CNodeClass *p_node, float f_progress)
	 *		- p_node must not be deleted in that function
	 */
	template <class CProgressCaller>
	bool TraverseFunc_UpdateTree_Progress(CProgressCaller t_caller)
	{
		float f_progress = .0f;
		int n_level = 0;
		CNodeClass *p_cur_node = (CNodeClass*)this;

		do {
			if(!t_caller(p_cur_node, f_progress))
				return false;

			if(p_cur_node->b_IsLeaf())
				f_progress += (float)pow(n_subnode_num, -n_level);
			// calc progress

			p_cur_node->m_p_next_node = 0;
			for(CNodeClass **p_sub_node = p_cur_node->m_subnode_list,
			   **p_end = p_cur_node->m_subnode_list + n_subnode_num;
			   p_sub_node < p_end; p_sub_node ++) {
				if(*p_sub_node) {
					n_level ++;
					p_cur_node->m_n_next_delta = 1;
					p_cur_node->m_p_next_node = *p_sub_node;
					break;
				}
			}
			// try to recurse up

			bool b_break = false;
			if(!p_cur_node->m_p_next_node) {
				p_cur_node->m_n_next_delta = 0;
				if(p_cur_node->m_p_parent_node) {
					CNodeClass *p_parent = p_cur_node;
					do {
						CNodeClass *p_search_node = p_parent; 
						p_parent = p_parent->m_p_parent_node;
						p_cur_node->m_n_next_delta --;
						if(-- n_level < 0) {
							b_break = true; // need to link to next node!
							if(!p_parent)
								break;
						}
						// (could end here for root, but when calling this for non-root node,
						// we need to assure it's linkage to the rest of the tree)

						{bool b_found_self = false;
						for(CNodeClass **p_sub_node = p_parent->m_subnode_list,
						   **p_end = p_parent->m_subnode_list + n_subnode_num;
						   p_sub_node < p_end; p_sub_node ++) {
							if(b_found_self && *p_sub_node) {
								n_level ++;
								p_cur_node->m_n_next_delta ++;
								p_cur_node->m_p_next_node = *p_sub_node;
								break;
							} else if(*p_sub_node == p_search_node)
								b_found_self = true;
						}}
						// try to recurse sideways
					} while(!p_cur_node->m_p_next_node);
				}
			}
			// determine node next to current

			if(p_cur_node->m_p_next_node) {
				p_cur_node->m_p_next_node->m_p_prev_node = p_cur_node;
				p_cur_node->m_p_next_node->m_n_prev_delta = -p_cur_node->m_n_next_delta;
			}
			// link prev node

			if(b_break)
				break;
		} while((p_cur_node = p_cur_node->m_p_next_node) && n_level > 0);

		return true;
	}

	/*
	 *	template <class CCaller>
	 *	bool TraverseFunc_UpdateTree_Progress(CCaller t_caller)
	 *		- simple traversal, called function must not create any new nodes
	 *		  (it can delete them, destructor will do the updates)
	 *		- CCaller must have public member function:
	 *		  bool operator ()(CNodeClass *p_node)
	 *		- p_node must not be deleted in that function
	 */
	template <class CCaller>
	bool TraverseFunc(CCaller t_caller) const
	{
		int n_level = 0;
		const CNodeClass *p_cur_node = (CNodeClass*)this;
		do {
			if(!t_caller(p_cur_node))
				return false;
			n_level += p_cur_node->m_n_next_delta;
			p_cur_node = p_cur_node->m_p_next_node;
		} while(n_level > 0 && p_cur_node);

		return true;
	}

	/*
	 *	template <class CProgressCaller>
	 *	bool TraverseFunc_UpdateTree_Progress(CProgressCaller t_caller)
	 *		- simple traversal, called function must not create any new nodes
	 *		  (it can delete them, destructor will do the updates)
	 *		- caller struct gets float value in range <0, 1) for some progress-meter
	 *		  (the progress is calculated as before calling the function so it can never be 1)
	 *		- CProgressCaller must have public member function:
	 *		  bool operator ()(CNodeClass *p_node, float f_progress)
	 *		- p_node must not be deleted in that function
	 */
	template <class CProgressCaller>
	bool TraverseFunc_Progress(CProgressCaller t_caller) const
	{
		float f_progress = .0f;
		int n_level = 0;
		const CNodeClass *p_cur_node = (CNodeClass*)this;
		do {
			if(!t_caller(p_cur_node, f_progress))
				return false;

			if(p_cur_node->b_IsLeaf())
				f_progress += (float)pow(n_subnode_num, -n_level);
			// calc progress

			n_level += p_cur_node->m_n_next_delta;
			p_cur_node = p_cur_node->m_p_next_node;
		} while(n_level > 0 && p_cur_node);

		return true;
	}
};

#endif // !__TREE_TEMPLATE_INCLUDED
