#ifndef _BSPTREE_BTREE_HPP_
#define _BSPTREE_BTREE_HPP_
#ifndef _COMMON_ASSERT_HPP_
#include <common/assert.hpp>
#endif
#ifndef _COMMON_WINDOWS_HPP_
#include <common/windows.hpp>
#endif
#ifndef _COMMON_ARRAY_HPP_
#include <common/array.hpp>
#endif
#ifndef _COMMON_BLOCK_HPP_
#include <common/block.hpp>
#endif
#ifndef _COMMON_ARRAY_HPP_
#include <common/array.hpp>
#endif
#ifndef _COMMON_SMARTPOINTER_HPP_
#include <common/pointer.hpp>
#endif
#ifndef _BSPTREE_TREENODE_HPP_
#include <bsptree/treenode.hpp>
#endif

template <class T>
class BTree
{
public:
	BTree(void);
	virtual ~BTree();
	BTree<T> &operator=(const BTree<T> &someBTree);
	DWORD leaves(void)const;
	WORD insert(const T &someItem,DWORD dupsOk=FALSE);
	WORD insert(Array<T> &vectorItems);
	void remove(const T &someItem);
  BOOL searchItem(T &someItem);
	BOOL find(T &someItem);  
	BOOL searchItem(const T &someItem);
  BOOL searchItem(const T &someItem,SmartPointer<T> &nodeItem);
	BOOL searchItems(const T &someItem,Block<SmartPointer<T> > &nodeItems);
  BOOL updateItem(T &someItem);
	void treeItems(Block<T> &blockItems)const;
	void treeItems(Array<T> &arrayItems)const;
	BOOL lastItemInserted(SmartPointer<T> &lastItemInserted);
	void remove(void);
protected:
	virtual TreeNode<T> *insertNode(TreeNode<T> *lpRootNode,TreeNode<T> *lpCurrentNode,const T &itemData);
	virtual TreeNode<T> *insertNodeDuplicate(TreeNode<T> *lpRootNode,TreeNode<T> *lpCurrentNode,const T &itemData);
	virtual T *searchNode(TreeNode<T> *lpRootNode,const T &someItem);
	virtual bool searchNodeDuplicate(TreeNode<T> *lpRootNode,const T &someItem,Block<SmartPointer<T> > &items);
	virtual TreeNode<T> *deleteBTree(TreeNode<T> *lpRootNode);
	TreeNode<T> *rootNode(void)const;
	TreeNode<T> *rootNode(TreeNode<T> *lpRootNode);
	void leaves(DWORD leaves);
private:
	BTree(const BTree<T> &someBTree);
  void remove(const T &someItem,TreeNode<T> *pCurrNode,TreeNode<T> *pParentNode);
	void retrieveNodes(TreeNode<T> *lpRootNode,Array<T> &arrayNodes,DWORD &arrayIndex)const;
	void retrieveNodes(TreeNode<T> *lpRootNode,Block<T> &blockNodes)const;

	TreeNode<T> *mlpRootNode;
	TreeNode<T> *mlpLastNodeInserted;
  DWORD mLeaves;
};

template <class T>
inline
BTree<T>::BTree(void)
: mlpRootNode(0), mlpLastNodeInserted(0), mLeaves(0)
{
}

template <class T>
inline
BTree<T>::BTree(const BTree<T> &/*someBTree*/)
: mlpRootNode(0), mlpLastNodeInserted(0), mLeaves(0)
{ // private implementation
}

template <class T>
inline
BTree<T>::~BTree()
{
  remove();
}

template <class T>
inline
WORD BTree<T>::insert(const T &someItem,DWORD dupsOk)
{
	DWORD itemCount(leaves());

	if(dupsOk)
	{
	  if(!mlpRootNode)leaves(leaves()+(0!=(mlpRootNode=insertNodeDuplicate(mlpRootNode,mlpRootNode,someItem))));
		else leaves(leaves()+(0!=insertNodeDuplicate(mlpRootNode,mlpRootNode,someItem)));
	}
	else
	{
		if(!mlpRootNode)leaves(leaves()+(0!=(mlpRootNode=insertNode(mlpRootNode,mlpRootNode,someItem))));
	  else leaves(leaves()+(0!=insertNode(mlpRootNode,mlpRootNode,someItem)));
	}
	return (!(itemCount==leaves()));
}

template <class T>
inline
BOOL BTree<T>::find(T &someItem)
{
  return searchItem(someItem);
}

template <class T>
inline
BOOL BTree<T>::searchItem(T &someItem)
{
  T *lpTempItem=(searchNode(mlpRootNode,someItem));
  if(lpTempItem){someItem=*lpTempItem;return TRUE;}
  else return FALSE;
}

template <class T>
inline
BOOL BTree<T>::searchItem(const T &someItem)
{
  T *lpTempItem=(searchNode(mlpRootNode,someItem));
  if(lpTempItem)return TRUE;
	return FALSE;
}

template <class T>
inline
BOOL BTree<T>::searchItem(const T &someItem,SmartPointer<T> &nodeItem)
{
  T *lpTempItem=(searchNode(mlpRootNode,someItem));
	if(lpTempItem){nodeItem=lpTempItem;return TRUE;}
	return FALSE;
}

template <class T>
inline
BOOL BTree<T>::searchItems(const T &someItem,Block<SmartPointer<T> > &nodeItems)
{
  return searchNodeDuplicate(mlpRootNode,someItem,nodeItems);
}

template <class T>
inline
void BTree<T>::remove(void)
{
  mlpRootNode=deleteBTree(mlpRootNode);
	mlpLastNodeInserted=0;
	leaves(0);
}

template <class T>
inline
TreeNode<T> *BTree<T>::rootNode(void)const
{
  return mlpRootNode;
}

template <class T>
inline
TreeNode<T> *BTree<T>::rootNode(TreeNode<T> *lpRootNode)
{
  remove();
  return mlpRootNode=lpRootNode;
}

template <class T>
inline
BOOL BTree<T>::lastItemInserted(SmartPointer<T> &lastItemInserted)
{
  if(!mlpLastNodeInserted)return FALSE;
	lastItemInserted=&mlpLastNodeInserted->item();
	return TRUE;
}

template <class T>
inline
DWORD BTree<T>::leaves(void)const
{
  return  mLeaves;
}

template <class T>
inline
void BTree<T>::leaves(DWORD leaves)
{
  mLeaves=leaves;
}
#if defined(_MSC_VER)
#include <bsptree/btree.tpp>
#endif
#endif