bst_generic.hpp

fflib的AI开发框架

/*  Copy Left/Right : OTHER ,Amfproject                                     *
 *                                                                          *
 *     This program is free software; you can redistribute it and/or modify *
 *  it under the terms of the GNU General Public License as published by    *
 *  the Free Software Foundation; version 2 of the License.                 *
 *                                                                          *
 *  This program is distributed in the hope that it will be useful,         *
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of          *
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           *
 *  GNU General Public License for more details.                            *
 *                                                                          *
 *  You should have received a copy of the GNU General Public License       *
 *  along with this program; if not, write to the Free Software             *
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA*
 ****************************************************************************
 * Project:    FFLib
 * Programmer: lucy
 * Created On: Dec 7, 2008
 ****************************************************************************/

#ifndef BST_GENERIC_HPP_
#define BST_GENERIC_HPP_
/*-- Compiler Controls -----------------------------------------------------*/

/*-- Includes --------------------------------------------------------------*/
#include <vector>
#include <stdexcept>
#include <iostream>
/*-- Namespace Controller --------------------------------------------------*/
namespace fate
{
namespace generic
{


/*-- Extern Types ----------------------------------------------------------*/

/*--------------------------------------------------------------------------*/

////////////////////////////////////////////////////////////
/// Generic binary search tree made by fate project \n
/// \n
/// Concept Check:\n
/// operator = \n
/// copyable for creation \n
/// ostream for display\n
////////////////////////////////////////////////////////////
template <typename Tp>
class BST
{
public:

	///////////////////////////////////////////////////////////
	/// exception for operate on empty tree\n
	/// this exception is called when the bst root was empty
	class bst_empty_root:public std::runtime_error
	{
	public:
		explicit bst_empty_root(std::string const & rfs)/// constructor
		:std::runtime_error(rfs)
		{   }

		///destructor
		virtual ~bst_empty_root() {/*do nothing in this*/ }
	};


	///cmpMethod represents the comparison between the two elements\n
	///@return typically this kind of cmp returns 1,0,-1 \n
	///		if return == 0 , represents that two elements are equal\n
	///		if return == 1 , represents that the former is larger than the latter\n
	///		if return == -1, represents that the former is lesser than the latter\n
	///must implement this if you want to use fate::generic::bst to hold elements
	typedef int(*cmpMethod)(Tp const &,Tp const &);


	///traverseMethod represents the method that is to be used for traverse in the tree\n
	/// the method is a function pointer, that may be used in traverse
	typedef void (*traverseMethod)(Tp const &);

	///init the bst tree\n
	///In this constructor, the bst will NOT allocate any thing \n
	///it will set the root NULL,this feature
	BST()
	:root(NULL)
	{  }

	///default constructor,create a unit at root
	///@param rfs
	///			the inserted root unit
	BST(Tp const & rfs)
	:root (new bstNode(rfs))
	{  }


	/// Destructor of the tree\n
	/// this will also clear the memory allocated by the tree
	virtual ~BST();

	///The insert method of the BST\n
	///@param x
	///		the unit that is to be inserted into tree
	///@param method
	///		the cmp method that is to used in the insertion
	void insert(Tp const & x,cmpMethod method)
	{
		if(root)
		{
			this->insert(x,root,method);
		}
		else
		{
			root= new bstNode(x);
		}
	}

	///used to concate target bst into the current tree
	///@param tree
	///		the target tree to be concatenated
	void concate(BST<Tp> const & tree);


	///used to erase unit equals target
	///@param x
	///		this is the target unit to be removed
	///@param method
	///		this is the cmp method
	void remove(Tp const & x,cmpMethod method)
	{
		this->remove(x,root);
	}


	///clear all the unit in the tree\n
	///this will also set the root to empty
	void clear()
	{
		this->clear(root);
	}

	///display the tree in a form of ostream \n
	///concept check:\n
	///must defined operator <<(ostream ,Tp)\n
	/// the unit will be separated by the target_sign
	///@param stream
	///		the stream that the tree unit was flowed to
	///@param sign
	///		the result will be separated by the sign
	void dispTree(std::ostream & stream,char sign)
	{
		if(root)
		{
			this->dispTree(root,stream,sign);
		}
		else
		{
			stream<<"empty"<<sign;
		}
	}

	//////////////////////////////////////
	///used to check if the tree is empty
	//////////////////////////////////////
	bool empty() const
	{
		return root==NULL;
	}

	///used to check the existence of the target in the tree
	///@param x
	///		the unit to be searched
	///@return \n
	///		true  for exist\n
	///		false for not exist
	bool exists(Tp const & x) const
	{
		return exists(x,root);
	}

	///used to traverse the unit
	///@param method
	///		the method is a void(Tp const &,Tp const &) like method
	void traverse(traverseMethod method)
	{
		if(root)
		{
			this->traverse(root,method);
		}
		else
		{
			return ;//do nothing
		}
	}

	///used to get the maximum unit in the tree
	///@return the maximum unit in the tree
	const Tp& findMax() const;

	///used to get the minimum unit in the tree
	///@return the minimum unit in the tree
	const Tp& findMin() const;

	///used to get the depth of the tree
	///@return the depth of the tree\n
	///		return 0 if the root is empty
	unsigned long int getDepth() const
	{
		if(root)
		{
			return getDepth(root);
		}
		else
		{
			return 0;
		}
	}

	///used to get a vector that contains the inserted unit,and sort them in order
	///@return the sorted unit vector
	std::vector<Tp> getUnitByOrder() const
	{
		std::vector<Tp> rtn;
		getUnitByOrder(root,rtn);
		return rtn;
	}

	//used to get the depth of the root

protected:
	////////////////////////////////////////////////
	/// private bstNodes,used for resource control
	///@todo may add some operator for new to make it allocate new spaces from the mem root
	////////////////////////////////////////////////
	class bstNode
	{
	public:
		///constructor
		///@param rfs
		///			the reference to source in creating new bst nodes\n
		///			concept check:\n
		///				the unit must have the ability of copy
		///@param lc
		///		this parameter was initialed for NULL, unless you want to add something to it
		///@param rc
		///		this paramter was initialed for NULL, unless you want to add something to it
		bstNode(Tp const & rfs,struct bstNode *lc = NULL,struct bstNode *rc = NULL)
		:kernel(rfs),lchild(lc),rchild(rc)
		{  }

		////////////////////////
		///the kernel unit
		////////////////////////
		Tp kernel;

		///////////////////////////////
		///left child of bst node
		///////////////////////////////
		bstNode *lchild;

		//////////////////////////////
		///right child of bst
		//////////////////////////////
		bstNode *rchild;


	};

	/////////////////////////////////////////////////////////////////////////////////////

	///////////////////////
	///the root of the bst
	//////////////////////
	bstNode *root;

	/////////////////////////////////////
	///private method: insert at the root
	/////////////////////////////////////
	void insert(Tp const &,bstNode *  root,cmpMethod method) const;

	/////////////////////////////////////
	///private method: remove at the root
	/////////////////////////////////////
	void remove(Tp const &,bstNode *  root,cmpMethod method) const;

	//////////////////////////////////////////////////////////////////////////
	///private method: display the tree from the root
	//////////////////////////////////////////////////////////////////////////
	void dispTree(bstNode *  root,std::ostream & stream,char sign);

	//////////////////////////////////////////////////////////////////////////
	///private method: clear unit from the root
	//////////////////////////////////////////////////////////////////////////
	void clear(bstNode *  root);

	//////////////////////////////////////////////////////////////////////////
	///private method: get depth from target node
	//////////////////////////////////////////////////////////////////////////
	unsigned long int getDepth(bstNode const * root) const;

	//////////////////////////////////////////////////////////////////////////
	///private method: traverse from root
	//////////////////////////////////////////////////////////////////////////
	void traverse(bstNode const * root,traverseMethod method);

	//////////////////////////////////////////////////////////////////////////
	///private method: check exist from root
	//////////////////////////////////////////////////////////////////////////
	bool exists(Tp const &,bstNode const * root,cmpMethod method) const;

	//////////////////////////////////////////////////////////////////////////
	///private method: get Units by Order
	//////////////////////////////////////////////////////////////////////////
	void getUnitByOrder(bstNode const * root,std::vector<Tp> & rfs) const;

};










/*-- Namespace Ender -------------------------------------------------------*/
}
}
/*--------------------------------------------------------------------------*/
#endif /* BST_GENERIC_HPP_ */