#ifndef _BSPTREE_BTREE_HPP_
#error BTREE.HPP must precede BTREE.TPP
#endif
#ifndef _BSPTREE_BTREE_TPP_
#define _BSPTREE_BTREE_TPP_

template <class T>
BTree<T> &BTree<T>::operator=(const BTree<T> &someBTree)
{
	Block<T> items;

  remove();
	if(!someBTree.leaves())return *this;
	someBTree.treeItems(items);
	for(int index=0;index<items.size();index++)insert(items[index]);
	return *this;
}

template <class T>
void BTree<T>::treeItems(Array<T> &arrayItems)const
{
	DWORD itemIndex(0);
  arrayItems.size(leaves());
	retrieveNodes(mlpRootNode,arrayItems,itemIndex);
}

template <class T>
void BTree<T>::treeItems(Block<T> &blockItems)const
{
	blockItems.remove();
  retrieveNodes(mlpRootNode,blockItems);
}

template <class T>
void BTree<T>::retrieveNodes(TreeNode<T> *lpRootNode,Block<T> &blockNodes)const
{
	if(!lpRootNode)return;
	retrieveNodes(lpRootNode->leftNode(),blockNodes);
	blockNodes.insert(&lpRootNode->item());
  retrieveNodes(lpRootNode->rightNode(),blockNodes);
}

template <class T>
void BTree<T>::retrieveNodes(TreeNode<T> *lpRootNode,Array<T> &arrayNodes,DWORD &arrayIndex)const
{
  if(!lpRootNode)return;
	retrieveNodes(lpRootNode->leftNode(),arrayNodes,arrayIndex);
	arrayNodes[arrayIndex++]=lpRootNode->item();
	retrieveNodes(lpRootNode->rightNode(),arrayNodes,arrayIndex);
}

template <class T>
TreeNode<T> *BTree<T>::insertNode(TreeNode<T> *lpRootNode,TreeNode<T> *lpCurrentNode,const T &someItem)
{
  if(!lpCurrentNode)
  {
	 lpCurrentNode=mlpLastNodeInserted=::new TreeNode<T>(someItem);
	 assert(0!=lpCurrentNode);
	 if(!lpRootNode)return lpCurrentNode;
	 if(someItem<lpRootNode->item())lpRootNode->leftNode(lpCurrentNode);
	 else lpRootNode->rightNode(lpCurrentNode);
	 return lpCurrentNode;
	}
  if(someItem<lpCurrentNode->item())return insertNode(lpCurrentNode,lpCurrentNode->leftNode(),someItem);
	else if(lpCurrentNode->item()<someItem)return insertNode(lpCurrentNode,lpCurrentNode->rightNode(),someItem);
  return 0;
}

template <class T>
TreeNode<T> *BTree<T>::insertNodeDuplicate(TreeNode<T> *lpRootNode,TreeNode<T> *lpCurrentNode,const T &someItem)
{
	if(!lpCurrentNode)
	{
	 lpCurrentNode=mlpLastNodeInserted=::new TreeNode<T>(someItem);
	 assert(0!=lpCurrentNode);
	 if(!lpRootNode)return lpCurrentNode;
	 if(someItem<lpRootNode->item())lpRootNode->leftNode(lpCurrentNode);
	 else if(someItem==lpRootNode->item())lpRootNode->leftNode(lpCurrentNode);
	 else lpRootNode->rightNode(lpCurrentNode);
	 return lpCurrentNode;
	}
	if(someItem<lpCurrentNode->item())return insertNodeDuplicate(lpCurrentNode,lpCurrentNode->leftNode(),someItem);
  else if(someItem==lpCurrentNode->item())return insertNodeDuplicate(lpCurrentNode,lpCurrentNode->leftNode(),someItem);
	return insertNodeDuplicate(lpCurrentNode,lpCurrentNode->rightNode(),someItem);
}

template <class T>
T *BTree<T>::searchNode(TreeNode<T> *lpRootNode,const T &someItem)
{
  while(lpRootNode&&!(someItem==lpRootNode->item()))
  {
	 if(someItem<lpRootNode->item())lpRootNode=lpRootNode->leftNode();
	 else lpRootNode=lpRootNode->rightNode();
	}
  if(!lpRootNode)return 0;
  return &lpRootNode->item();
}

template <class T>
bool BTree<T>::searchNodeDuplicate(TreeNode<T> *lpRootNode,const T &someItem,Block<SmartPointer<T> > &items)
{
  items.remove();
  while(lpRootNode&&!(someItem==lpRootNode->item()))
  {
	 if(someItem<lpRootNode->item())lpRootNode=lpRootNode->leftNode();
	 else lpRootNode=lpRootNode->rightNode();
	}
	while(lpRootNode&&someItem==lpRootNode->item())
	{
//	  items.insert(&SmartPointer<T>(&lpRootNode->item()));
	  items.insert(new SmartPointer<T>(&lpRootNode->item()));
		lpRootNode=lpRootNode->leftNode();
	}
	return items.size()?true:false;
}

template <class T>
TreeNode<T> *BTree<T>::deleteBTree(TreeNode<T> *lpRootNode)
{
  if(!lpRootNode)return 0;
  deleteBTree(lpRootNode->leftNode());
  deleteBTree(lpRootNode->rightNode());
  ::delete lpRootNode;
  return lpRootNode=0;
}

template <class T>
WORD BTree<T>::insert(Array<T> &vectorItems)
{
  WORD size((WORD)vectorItems.size());
  WORD insertCount(0);

  if(!size)return 0;
  for(LONG index=0;index<size;index++)
  {
	 if(!mlpRootNode)insertCount=((0!=(mlpRootNode=insertNode(mlpRootNode,mlpRootNode,vectorItems[index])))?insertCount+1:insertCount);
	 else insertCount=((0!=insertNode(mlpRootNode,mlpRootNode,vectorItems[index]))?insertCount+1:insertCount);
	}
  leaves(leaves()+insertCount);
  return insertCount;
}

template <class T>
void BTree<T>::remove(const T &someItem)
{
  remove(someItem,mlpRootNode,0);
}

template <class T>
void BTree<T>::remove(const T &someItem,TreeNode<T> *pCurrNode,TreeNode<T> *pParentNode)
{
  TreeNode<T> *pTmpNode;

	if(!pCurrNode)return;
	if(someItem<pCurrNode->item())remove(someItem,pCurrNode->leftNode(),pCurrNode);
	else if(someItem>pCurrNode->item())remove(someItem,pCurrNode->rightNode(),pCurrNode);
	else
	{
	  if(!pCurrNode->leftNode()&&!pCurrNode->rightNode())
		{
		  if(pCurrNode==mlpRootNode)mlpRootNode=0;
			if(pParentNode)
			{
			  if(pParentNode->leftNode()==pCurrNode)pParentNode->leftNode(0);
				else pParentNode->rightNode(0);
			}
		}
		else if(!pCurrNode->rightNode())
		{
			if(pParentNode)
			{
		    if(pParentNode->leftNode()==pCurrNode)pParentNode->leftNode(pCurrNode->leftNode());
		    else pParentNode->rightNode(pCurrNode->leftNode());
			}
			else mlpRootNode=pCurrNode->leftNode();
		}
		else if(!pCurrNode->leftNode())
		{
		  if(pParentNode)
			{
		    if(pParentNode->leftNode()==pCurrNode)pParentNode->leftNode(pCurrNode->rightNode());
			  else pParentNode->rightNode(pCurrNode->rightNode());
			}
			else mlpRootNode=pCurrNode->rightNode();
		}
		else
		{
		  TreeNode<T> *pCursorNode=0;
			TreeNode<T> *pRootNode=0;
		  pTmpNode=pCurrNode->leftNode();
			while(pTmpNode->rightNode()){pCursorNode=pTmpNode;pTmpNode=pTmpNode->rightNode();}
			if(pCursorNode)pCursorNode->rightNode(0);
			pRootNode=pTmpNode;
      pRootNode->rightNode(pCurrNode->rightNode());
      pCursorNode=0;
			if(pTmpNode!=pCurrNode->leftNode())
			{
			  while(pTmpNode->leftNode())pTmpNode=pTmpNode->leftNode();
			  pTmpNode->leftNode(pCurrNode->leftNode());
			}
      if(!pParentNode)mlpRootNode=pRootNode;
			else
			{
			  if(pParentNode->leftNode()==pCurrNode)pParentNode->leftNode(pCurrNode->leftNode());
				else pParentNode->rightNode(pCurrNode->leftNode());
			}
		}
		::delete pCurrNode;
		leaves(leaves()-1);
	}
}
#include <bsptree/treenode.tpp>
#endif