/*****************************************/
/* B-Bäume als Templates                 */
/*                                       */
/* Autor:  Michael Sonntag               */
/* Datum:  21.11.1997                    */
/*****************************************/


/* Template class TBTreeItem */
template<class T,short K> class TBTreeItem
{
public:
	short nCount;
	T data[2*K];
	TBTreeItem<T,K> *son[2*K+1];

	TBTreeItem();
	BOOL BinSearch(T key, short &loc, short &down);
protected:
	void SplitNode(T &dOfl,TBTreeItem<T,K> *&pOfl,short down);

	friend class CBTree<T,K>;
	friend class CBTreeIterator<T,K>;
	friend class CBTreeIteratorBFS<T,K>;
	friend class CBTreeIteratorDFS<T,K>;
};

/* Template class CBTree */
template<class T,short K> class CBTree : public CObject
{
protected:
	TBTreeItem<T,K> *pRoot;

	void DoClear(TBTreeItem<T,K> *node);
	DWORD DoCount(TBTreeItem<T,K> *node) const;
	T *SearchRec(TBTreeItem<T,K> *node,T &key) const;
	BOOL HInsert(TBTreeItem<T,K> *node,T &dOfl,TBTreeItem<T,K> *&pOfl,T key);
	BOOL HDelete(TBTreeItem<T,K> *node,T key,BOOL &bUnderflow);
	void DelSymPred(TBTreeItem<T,K> *pSon,TBTreeItem<T,K> *node,short pos,BOOL &bUnderflow);
	void Underflow(TBTreeItem<T,K> *parent,TBTreeItem<T,K> *node,short pos,BOOL &bUnderflow);

public:
	CBTree();
	virtual ~CBTree();
	inline TBTreeItem<T,K> *GetRoot() {return pRoot;}
	void Clear();
	void Add(T data);
	BOOL Remove(T data);
	inline T *Search(T &key) const;
	inline DWORD GetCount() const;
	void Serialize(CArchive &ar);
	inline BOOL IsEmpty() const;

#ifdef _DEBUG
	void Dump(CDumpContext &dc) const;
#endif

	friend class CBTreeIterator<T,K>;
	friend class CBTreeIteratorBFS<T,K>;
	friend class CBTreeIteratorDFS<T,K>;
};

/* Template class CBTreeIterator */
template<class T,short K> class CBTreeIterator
{
protected:
	struct TItem
	{
		TBTreeItem<T,K> *node;
		short nPos;
		short nLevel;
		TItem *pNext;
	};

	CBTree<T,K> *pTree;
	TItem *pHead;

	void Clear();
	TItem *NewElem(TBTreeItem<T,K> *node, short level);
	virtual void Initialize() = 0;	// ABSTRACT
	virtual void NextStep() = 0;	// ABSTRACT

public:
	CBTreeIterator(CBTree<T,K> &tree);
	virtual ~CBTreeIterator();
	inline T &Current() const;
	inline short GetLevel() const;
	T &operator ++();
	T &operator ++(int);
	inline operator BOOL () {return pHead!=NULL;}
	void Reset();
};

/* Template CBTreeIteratorBFS: Breadth first search */
template<class T,short K> 
class CBTreeIteratorBFS : public CBTreeIterator<T,K>
{
protected:
	TItem *pTail;

	virtual void Initialize();
	virtual void NextStep();

public:
	CBTreeIteratorBFS(CBTree<T,K> &tree) : CBTreeIterator<T,K>(tree) {Initialize();}
};

/* Template CBTreeIteratorDFS: Depth first search; InOrder */
template<class T,short K>
class CBTreeIteratorDFS : public CBTreeIterator<T,K>
{
protected:
	void GoDown(TBTreeItem<T,K> *node, short pos, short level);
	virtual void Initialize();
	virtual void NextStep();

public:
	CBTreeIteratorDFS(CBTree<T,K> &tree) : CBTreeIterator<T,K>(tree) {Initialize();}
};


template<class T,short K> TBTreeItem<T,K>::TBTreeItem()
{
	for(short i=0;i<2*K+1;i++)
			son[i]=NULL;
	nCount=0;
}

template<class T,short K> BOOL TBTreeItem<T,K>::BinSearch(T key, short &loc, short &down)
{
	short lb=1; // 0 contains no data, only pointer
	short ub=nCount;
	if(!ub)
	{
		loc=0;down=0;
		return FALSE;
	}
	do
	{
		loc=(lb+ub)/2;
		if(key<=data[loc-1])
			ub=loc-1;
		if(key>=data[loc-1])
			lb=loc+1;
	}while(lb<=ub);
	down=ub;
	return lb-ub>1;
}

template<class T,short K> void TBTreeItem<T,K>::SplitNode(T &dOfl,TBTreeItem<T,K> *&pOfl,short down)
{
	short i;
	TBTreeItem<T,K> *second;
	T dBak=dOfl;
	TBTreeItem<T,K> *pBak=pOfl;
	second=new TBTreeItem<T,K>;
	ASSERT(second!=NULL);
	if(down>K)
	{	// New element is in right half
		dOfl=data[K];
		pOfl=son[K+1];
		for(i=K+1;i<down;i++)
		{
			second->son[i-K]=son[i+1];
			second->data[i-K-1]=data[i];
		}
		second->son[down-K]=pBak;
		second->data[down-K-1]=dBak;
		for(i=down+1;i<=2*K;i++)
		{
			second->son[i-K]=son[i];
			second->data[i-K-1]=data[i-1];
		}
	}
	else if (down<K)
	{	// New element is in left half
		dOfl=data[K-1];
		pOfl=son[K];
		for(i=K;i>=down+2;i--)
		{
			son[i]=son[i-1];
			data[i-1]=data[i-2];
		}
		son[down+1]=pBak;
		data[down]=dBak;
		for(i=1;i<=K;i++)
		{
			second->son[i]=son[i+K];
			second->data[i-1]=data[i+K-1];
		}
	}
	else
	{	// New element is the middle one
		dOfl=dBak;
		pOfl=pBak;
		for(i=1;i<=K;i++)
		{
			second->son[i]=son[i+K];
			second->data[i-1]=data[i+K-1];
		}
	}
	second->nCount=K;
	nCount=K;
	second->son[0]=pOfl;
	pOfl=second;
}

template<class T,short K> CBTree<T,K>::CBTree()
{
	pRoot=new TBTreeItem<T,K>;
	ASSERT(pRoot!=NULL);
	pRoot->nCount=0;
	pRoot->son[0]=NULL;
}


template<class T,short K> CBTree<T,K>::~CBTree()
{
	Clear();
	if(pRoot)
		delete pRoot;	// Remove last node
}
template<class T,short K> BOOL CBTree<T,K>::IsEmpty() const
{
	return !pRoot || pRoot->nCount==0;
}

template<class T,short K> void CBTree<T,K>::DoClear(TBTreeItem<T,K> *node)
{
	for(short i=0;i<=node->nCount;i++)
		if(node->son[i])
			DoClear(node->son[i]);
	delete node;
}

template<class T,short K> void CBTree<T,K>::Clear()
{
	if(pRoot && pRoot->nCount)
	{	// Last node shall stay
		for(short i=0;i<=pRoot->nCount;i++)
			if(pRoot->son[i])
				DoClear(pRoot->son[i]);
		pRoot->nCount=0;
		pRoot->son[0]=NULL;
	}
}

#ifdef _DEBUG
template<class T,short K> void CBTree<T,K>::Dump(CDumpContext &dc) const
{
	struct TDumpData
	{
		TBTreeItem<T,K> *p;
		TDumpData	*pNext;
		short		h;
	};

	TDumpData *pDumpList, *dummy, *pLast;
	DWORD	  dwCount = 0;
	short	  i = 0;

	CObject::Dump(dc);
	if(!pRoot) {
		dc << "No elements in tree.\n"; return;
	}  /* if */
	pDumpList=new TDumpData;
	ASSERT(pDumpList!=NULL);
	pDumpList->p=pRoot;
	pDumpList->h=0;
	pDumpList->pNext=NULL;
	pLast=pDumpList;
	while(pDumpList) { // BFS output
		TBTreeItem<T,K> *cur = pDumpList->p;
		if(pDumpList->h != i) // Check for new level
		{
			i=pDumpList->h;
			dc << "\nNew level: " << i << "\n";
		}  
		dc << "New node: " << "Number of elements: " << cur->nCount << "\n";
		for(short j=0;j<=cur->nCount;j++)
		{
			if(j)	// Index 0 has no data, just pointer!
				dc << cur->data[j-1];
			if(cur->son[j])
			{
				dummy=new TDumpData;
				ASSERT(dummy!=NULL);
				dummy->p=cur->son[j];
				dummy->pNext=NULL;
				dummy->h=i+1;
				pLast->pNext=dummy;
				pLast=dummy;
			}
		}
		dc << "\n";
		dwCount+=cur->nCount;
		dummy=pDumpList; pDumpList=pDumpList->pNext; delete dummy;
	}
	dc << "\nTotal number of Elements: " << dwCount;
	dc << "\nHeight: " << i << "\n";
}
#endif

template<class T,short K> BOOL CBTree<T,K>::HInsert(TBTreeItem<T,K> *node,T &dOfl,TBTreeItem<T,K> *&pOfl,T key)
{
	short pos,down;
	if(!node)
	{   // key ist not in node, Overflow starts from bottom up
		dOfl=key;
		pOfl=NULL;
		return TRUE;
	}
	// Search key in node node (binary search)
	if(node->BinSearch(key,pos,down))
		return FALSE;
	// Go down
	if(HInsert(node->son[down],dOfl,pOfl,key))
	{	// Overflow in subtree
		BOOL propagate=node->nCount>=2*K;
		if(propagate)
			node->SplitNode(dOfl,pOfl,down);
		else
		{
			node->nCount++;
			for(short i=node->nCount;i>=down+2;i--)
			{
				node->son[i]=node->son[i-1];
				node->data[i-1]=node->data[i-2];
			}
			node->data[down]=dOfl;
			node->son[down+1]=pOfl;
		}
		return propagate;
	}
	return FALSE;
}

template<class T,short K> void CBTree<T,K>::Add(T data)
{
	T dOfl;
	TBTreeItem<T,K> *pOfl,*pNew;
	if(HInsert(pRoot,dOfl,pOfl,data))
	{	// Have to split root-node
		pNew=new TBTreeItem<T,K>;
		ASSERT(pNew!=NULL);
		pNew->nCount=pRoot->nCount;
		for(short i=0;i<=pRoot->nCount;i++)
		{
			pNew->son[i]=pRoot->son[i];
			pNew->data[i-1]=pRoot->data[i-1];
		}
		pRoot->nCount=1;
		pRoot->son[0]=pNew;
		pRoot->son[1]=pOfl;
		pRoot->data[0]=dOfl;
	}
}

template<class T,short K> void CBTree<T,K>::Underflow(TBTreeItem<T,K> *parent,TBTreeItem<T,K> *node,short pos,BOOL &bUnderflow)
{
	TBTreeItem<T,K> *neigh;
	short i,borrow;
	if (pos<parent->nCount) // try right neighbour
	{
		pos++;
		neigh=parent->son[pos];
		borrow=(neigh->nCount-K+1)/2;
		node->data[K-1]=parent->data[pos-1];	// Move element in parent one down
		node->son[K]=neigh->son[0];
		if(borrow>0) // Can we transfer from neighbour?
		{
			for(i=1;i<borrow;i++)
			{
				node->data[i+K-1]=neigh->data[i-1];
				node->son[i+K]=neigh->son[i];
			}
			parent->data[pos-1]=neigh->data[borrow-1];
			parent->son[pos]=neigh;
			neigh->son[0]=neigh->son[borrow];
			neigh->nCount-=borrow;
			for(i=1;i<=neigh->nCount;i++)
			{
				neigh->data[i-1]=neigh->data[i+borrow-1];
				neigh->son[i]=neigh->son[i+borrow];
			}
			node->nCount=K-1+borrow;
			bUnderflow=FALSE;
		}
		else
		{	// Merge both nodes
			for(i=1;i<=K;i++)
			{
				node->data[i+K-1]=neigh->data[i-1];
				node->son[i+K]=neigh->son[i];
			}
			for(i=pos;i<parent->nCount;i++)
			{
				parent->data[i-1]=parent->data[i];
				parent->son[i]=parent->son[i+1];
			}
			node->nCount=2*K;
			parent->nCount--;
			bUnderflow=parent->nCount<K;
			delete neigh;
		}
	}
	else // No right neighbour -> try left one
	{
		neigh=parent->son[pos-1];
		borrow=(neigh->nCount-K+1)/2;
		if(borrow>0)
		{
			for(i=K-1;i>0;i--)
			{
				node->data[i+borrow-1]=node->data[i-1];
				node->son[i+borrow]=node->son[i];
			}
			node->data[borrow-1]=parent->data[pos-1];
			node->son[borrow]=neigh->son[neigh->nCount];
			for(i=borrow-1;i>0;i--)
			{
				node->data[i-1]=neigh->data[i+neigh->nCount-borrow];
				node->son[i]=neigh->son[i+neigh->nCount-borrow+1];
			}
			node->son[0]=neigh->son[neigh->nCount-borrow+1];
			parent->data[pos-1]=neigh->data[neigh->nCount-borrow];
			parent->son[pos]=node;
			neigh->nCount-=borrow;
			node->nCount=K-1+borrow;
			bUnderflow=FALSE;
		}
		else
		{
			neigh->data[neigh->nCount]=parent->data[pos-1];
			neigh->son[neigh->nCount+1]=node->son[0];
			for(i=1;i<K;i++)
			{
				neigh->data[i+neigh->nCount]=node->data[i-1];
				neigh->son[i+neigh->nCount+1]=node->son[i];
			}
			neigh->nCount=2*K;
			parent->nCount--;
			bUnderflow=parent->nCount<K;
			delete node;
		}
	}
}

template<class T,short K> void CBTree<T,K>::DelSymPred(TBTreeItem<T,K> *pSon,TBTreeItem<T,K> *node,short pos,BOOL &bUnderflow)
{
	TBTreeItem<T,K> *cur=pSon->son[pSon->nCount];
	if(cur)
	{	// Recursive down
		DelSymPred(cur,node,pos,bUnderflow);
		if(bUnderflow)
			Underflow(pSon,cur,pSon->nCount,bUnderflow);
	}
	else
	{	// Move up symmetrical predecessor and delete in leaf
		node->data[pos-1]=pSon->data[pSon->nCount-1];
		pSon->nCount--;
		bUnderflow=pSon->nCount<K;
	}
}

template<class T,short K> BOOL CBTree<T,K>::HDelete(TBTreeItem<T,K> *node,T key,BOOL &bUnderflow)
{
	short i,pos,down;
	BOOL res=FALSE;
	TBTreeItem<T,K> *pSon;
	if(!node)
	{
		bUnderflow=FALSE;
		return FALSE;
	}
	node->BinSearch(key,pos,down);
	if(key>node->data[pos-1])
		pos++;
	pSon=node->son[pos-1];
	if(pos<=node->nCount && node->data[pos-1]==key)
	{	// We found it
		res=TRUE;
		if(!pSon)
		{	// Node is a leaf
			node->nCount--;
			bUnderflow=node->nCount<K;
			for(i=pos;i<=node->nCount;i++)
			{
				node->data[i-1]=node->data[i];
				node->son[i]=node->son[i+1];
			}
		}
		else
		{	// Delete symmetrical predecessor
			DelSymPred(pSon,node,pos,bUnderflow);
			if (bUnderflow)
				Underflow(node,pSon,pos-1,bUnderflow);
		}
	}
	else
	{
		res=HDelete(pSon,key,bUnderflow);
		if (bUnderflow)
			Underflow(node,pSon,pos-1,bUnderflow);
	}
	return res;
}

template<class T,short K> BOOL CBTree<T,K>::Remove(T data)
{
	BOOL bUnderflow=FALSE;
	BOOL res=HDelete(pRoot,data,bUnderflow);
	if(bUnderflow)
	{
		if(!pRoot->nCount) // Remove root?
		{
			if(pRoot->son[0])	// If we have a son, remove this node
			{	// Last node shall stay, even if empty
				TBTreeItem<T,K> *temp=pRoot;
				pRoot=pRoot->son[0];
				delete temp;
			}
		}
	}
	return res;
}

template<class T,short K> T *CBTree<T,K>::SearchRec(TBTreeItem<T,K> *node,T &key) const
{
  short pos,down;
  if(!node)
	  return NULL;
  if(node->BinSearch(key,pos,down))
	  return &node->data[pos-1];
  return SearchRec(node->son[down],key);
}

template<class T,short K> T *CBTree<T,K>::Search(T &key) const
{
	return SearchRec(pRoot,key);
}

template<class T,short K> DWORD CBTree<T,K>::DoCount(TBTreeItem<T,K> *node) const
{
	DWORD count=0;
	if(node)
	{
		count=DoCount(node->son[0]);
		for(short i=1;i<=node->nCount;i++)
			count+=1+DoCount(node->son[i]);
	}
	return count;
}

template<class T,short K> DWORD CBTree<T,K>::GetCount() const
{
	return DoCount(pRoot);
}

template<class T,short K> void CBTree<T,K>::Serialize(CArchive &ar)
{
	DWORD dwCount;
	if(ar.IsStoring())
	{
		dwCount=GetCount();
		ar << dwCount;
		CBTreeIteratorDFS<T,K> iter(*this);
		while(iter)
			ar << iter++;
	}
	else
	{
		T data;
		ar >> dwCount;
		for(DWORD i=0;i<dwCount;i++)
		{
			ar >> data;
			Add(data);
		}
	}
}
	
template<class T,short K> CBTreeIterator<T,K>::CBTreeIterator(CBTree<T,K> &tree)
{
	pTree=&tree;
	pHead=NULL;
}

template<class T,short K> CBTreeIterator<T,K>::~CBTreeIterator()
{
	Clear();
}

template<class T,short K> void CBTreeIterator<T,K>::Clear()
{
	TItem *cur=pHead, *del;
	while(cur)
	{
		del=cur;
		cur=cur->pNext;
		delete del;
	}
	pHead=NULL;
}

template<class T,short K> T &CBTreeIterator<T,K>::Current() const
{
	if(pHead)
	{
		if(pHead->nPos==0)
			pHead->nPos=1;
		ASSERT(pHead->nPos>0);
		ASSERT(pHead->node!=NULL);
		ASSERT(pHead->nPos<=pHead->node->nCount);
		return pHead->node->data[pHead->nPos-1];
	}
	return *((T*)NULL);
}

template<class T,short K> short CBTreeIterator<T,K>::GetLevel() const
{
	return pHead?pHead->nLevel:-1;
}

template<class T,short K> T &CBTreeIterator<T,K>::operator ++()
{
	NextStep();
	return Current();
}

template<class T,short K> T &CBTreeIterator<T,K>::operator ++(int)
{
	T &t=Current();
	NextStep();
	return t;
}

template<class T,short K> CBTreeIterator<T,K>::TItem *CBTreeIterator<T,K>::NewElem(TBTreeItem<T,K> *node, short level)
{
	TItem *pNew=new TItem;
	ASSERT(pNew!=NULL);
	pNew->node=node;
	pNew->nPos=0;
	pNew->nLevel=level;
	pNew->pNext=NULL;
	return pNew;
}

template<class T,short K> void CBTreeIterator<T,K>::Reset()
{
	Clear();
	Initialize();
}


template<class T,short K> void CBTreeIteratorBFS<T,K>::Initialize()
{
	if(pTree->pRoot && pTree->pRoot->nCount>0)	// Last is special case for empty root node
	{
		pHead=NewElem(pTree->pRoot,0);
		pTail=pHead;
		NextStep(); // Move to first element
	}
}

template<class T,short K> void CBTreeIteratorBFS<T,K>::NextStep()
{
	TItem *cur=pHead, *pNew=NULL;

	if(!cur)
		return;
	if(cur->node->son[cur->nPos])
	{
		pNew=NewElem(cur->node->son[cur->nPos],cur->nLevel+1);
		pTail->pNext=pNew;
		pTail=pNew;
	}
	if(cur->nPos<cur->node->nCount)
		cur->nPos++;
	else
	{
		pHead=cur->pNext;
		delete cur;
		NextStep();	// Step over index 0
	}
}


template<class T,short K> void CBTreeIteratorDFS<T,K>::GoDown(TBTreeItem<T,K> *node, short pos, short level)
{
	while(node && node->nCount>0 && node->son[pos])
	{
		TItem *pNew=NewElem(node->son[pos],level);
		pNew->pNext=pHead;
		pHead=pNew;
		node=node->son[pos];
		level++;
		pos=0;
	}
}

template<class T,short K> void CBTreeIteratorDFS<T,K>::Initialize()
{
	if(pTree->pRoot && pTree->pRoot->nCount>0)	// Last is special case for empty root node
	{
		pHead=NewElem(pTree->pRoot,0);
		GoDown(pTree->pRoot,0,1);
	}
}

template<class T,short K> void CBTreeIteratorDFS<T,K>::NextStep()
{
	TItem *cur=pHead;
	if(!cur)
		return;
	if(cur->nPos==0)
		cur->nPos=1;
	cur->nPos++;
	if(cur->nPos>cur->node->nCount)
	{
		if(cur->nPos==cur->node->nCount+1 && cur->node->son[cur->nPos-1])
		{	// Go down last pointer if exists
			GoDown(cur->node,cur->nPos-1,cur->nLevel+1);
			return;
		}
		while(cur && cur->nPos>cur->node->nCount) // Go back up from last son
		{ // Retreat one level
			pHead=cur->pNext;
			delete cur;
			cur=pHead;
		}
		return;
	}
	GoDown(cur->node,cur->nPos-1,cur->nLevel+1);
}