#include Once "window9.bi"

Type MAPNODE
	
	As Zstring Ptr nKey
	
	As Any Ptr nData
	
	As MAPNODE Ptr pLeft
	
	As MAPNODE Ptr pRight
	
	As Byte bHeight
	
End Type

Type TMAP
	
	As MAPNODE Ptr pRoot
	
	As Byte bFlagDelete
	
	As Long iSizeMap
	
	Declare Function GetSize() As Long
	
	Declare Function MapMax( a As Byte, b As Byte) As Byte
	
	Declare Function GetTreeHeight(pNode As MAPNODE Ptr) As Byte
	
	Declare Function RightRotate(y As MAPNODE Ptr) As MAPNODE Ptr
	
	Declare Function LeftRotate(x As MAPNODE Ptr) As MAPNODE Ptr
	
	Declare Function GetBalance(pNode As MAPNODE Ptr) As Byte
	
	Declare Function InsertNode(pNode As MAPNODE Ptr, nKey As String , nData As Any Ptr) As MAPNODE Ptr
	
	Declare Function InsertNodeS(pNode As MAPNODE Ptr, nKey As String , nData As Any Ptr) As MAPNODE Ptr
	
	Declare Function GetMinNode(pNode As MAPNODE Ptr) As MAPNODE Ptr
	
	Declare Function DelNode(pRoot As MAPNODE Ptr, nKey As String, bFlagFreeMemoryStrings As Long = 0) As MAPNODE Ptr	
	
	Declare Function FindNode(pNode As MAPNODE Ptr , nKey As String) As Any Ptr	
	
	Declare Sub DelTree(pRoot As MAPNODE Ptr , bFlagFreeMemoryStrings As Long = 0)	
	
	Declare Sub Insert(nKey As String , nData As Any Ptr , bFlagFreeMemoryStrings As Long = 0)
	
	Declare Sub DeleteNode(nKey As String, bFlagFreeMemoryStrings As Long = 0)
	
	Declare Function Find(nKey As String) As Any Ptr
	
	Declare Sub DeleteTree(bFlagFreeMemoryStrings As Long = 0)
	
End Type

Function TMAP.GetSize() As Long
	
	Return iSizeMap
	
End Function

Function TMAP.MapMax( a As Byte, b As Byte) As Byte
	
	Return Iif(a >b , a , b)
	
End Function

Function TMAP.GetTreeHeight(pNode As MAPNODE Ptr) As Byte
	
	If pNode =0 Then Return 0
	
	Return pNode->bHeight
	
End Function

Function TMAP.RightRotate(y As MAPNODE Ptr) As MAPNODE Ptr
	
	Dim As MAPNODE Ptr x =y->pLeft
	
	Dim As MAPNODE Ptr z =x->pRight
	
	x->pRight =y
	
	y->pLeft =z
	
	y->bHeight =MapMax(GetTreeHeight(y->pLeft), GetTreeHeight(y->pRight)) + 1
	
	x->bHeight =MapMax(GetTreeHeight(x->pLeft), GetTreeHeight(x->pRight)) + 1
	
	Return x
	
End Function

Function TMAP.LeftRotate(x As MAPNODE Ptr) As MAPNODE Ptr
	
	Dim As MAPNODE Ptr y =x->pRight
	
	Dim As MAPNODE Ptr z =y->pLeft
	
	y->pLeft =x
	
	x->pRight =z
	
	x->bHeight =MapMax(GetTreeHeight(x->pLeft), GetTreeHeight(x->pRight)) + 1
	
	y->bHeight =MapMax(GetTreeHeight(y->pLeft), GetTreeHeight(y->pRight)) + 1
	
	Return y
	
End Function

Function TMAP.GetBalance(pNode As MAPNODE Ptr) As Byte
	
	If pNode =0 Then Return 0
	
	Return GetTreeHeight(pNode->pLeft) -GetTreeHeight(pNode->pRight)
	
End Function

Function TMAP.InsertNode(pNode As MAPNODE Ptr, nKey As String , nData As Any Ptr) As MAPNODE Ptr
	
	If pNode =0 Then
		
		Dim As MAPNODE Ptr pNode =New MAPNODE	
		
		if pNode = 0 then
			
			print "Allocated memory error in TMAP.InsertNodeS!"
			
			return 0
			
		EndIf
		
		Dim As Zstring Ptr pszTemp =Callocate(Len(nKey)+1)
		
		If pszTemp Then
			
			*pszTemp =nKey
			
			pNode->nKey =pszTemp
			
		Endif
		
		pNode->nData =nData
		
		pNode->pLeft =0
		
		pNode->pRight =0
		
		pNode->bHeight =1
		
		iSizeMap +=1
		
		Return pNode
		
	Endif
	
	If nKey <*(pNode->nKey) Then
		
		pNode->pLeft =InsertNode(pNode->pLeft, nKey , nData)
		
	Elseif nKey >*(pNode->nKey) Then
		
		pNode->pRight =InsertNode(pNode->pRight, nKey , nData)
		
	Else
		
		pNode->nData =nData
		
		Return pNode
		
	Endif
	
	pNode->bHeight =1 + MapMax(GetTreeHeight(pNode->pLeft), GetTreeHeight(pNode->pRight))
	
	Dim As Byte bBalance =GetBalance(pNode)
	
	If bBalance >1 Andalso nKey <*(pNode->pLeft->nKey) Then Return RightRotate(pNode)
	
	If bBalance <-1 Andalso nKey >*(pNode->pRight->nKey) Then Return LeftRotate(pNode)
	
	If bBalance >1 Andalso nKey >*(pNode->pLeft->nKey) Then
		
		pNode->pLeft =LeftRotate(pNode->pLeft)
		
		Return RightRotate(pNode)
		
	Endif
	
	If bBalance <-1 Andalso nKey <*(pNode->pRight->nKey) Then
		
		pNode->pRight =RightRotate(pNode->pRight)
		
		Return LeftRotate(pNode)
		
	Endif
	
	Return pNode
	
End Function

' This function is almost identical to InsertNode , except for freeing memory.
' For performance, I decided to do this rather than use an extra parameter in the function, since it is recursive
Function TMAP.InsertNodeS(pNode As MAPNODE Ptr, nKey As String , nData As Any Ptr) As MAPNODE Ptr
	
	If pNode =0 Then
		
		Dim As MAPNODE Ptr pNode =New MAPNODE	
		
		if pNode = 0 then
			
			print "Allocated memory error in TMAP.InsertNodeS!"
			
			return 0
			
		EndIf
		
		Dim As Zstring Ptr pszTemp =Callocate(Len(nKey)+1)
		
		If pszTemp Then
			
			*pszTemp =nKey
			
			pNode->nKey =pszTemp
			
		Endif
		
		pNode->nData =nData
		
		pNode->pLeft =0
		
		pNode->pRight =0
		
		pNode->bHeight =1
		
		iSizeMap +=1
		
		Return pNode
		
	Endif
	
	If nKey <*(pNode->nKey) Then
		
		pNode->pLeft =InsertNodeS(pNode->pLeft, nKey , nData)
		
	Elseif nKey >*(pNode->nKey) Then
		
		pNode->pRight =InsertNodeS(pNode->pRight, nKey , nData)
		
	Else
		
		If pNode->nData Then
			
			Deallocate(pNode->nData)
			
		Endif
		
		pNode->nData =nData
		
		Return pNode
		
	Endif
	
	pNode->bHeight =1 + MapMax(GetTreeHeight(pNode->pLeft), GetTreeHeight(pNode->pRight))
	
	Dim As Byte bBalance =GetBalance(pNode)
	
	If bBalance >1 Andalso nKey <*(pNode->pLeft->nKey) Then Return RightRotate(pNode)
	
	If bBalance <-1 Andalso nKey >*(pNode->pRight->nKey) Then Return LeftRotate(pNode)
	
	If bBalance >1 Andalso nKey >*(pNode->pLeft->nKey) Then
		
		pNode->pLeft =LeftRotate(pNode->pLeft)
		
		Return RightRotate(pNode)
		
	Endif
	
	If bBalance <-1 Andalso nKey <*(pNode->pRight->nKey) Then
		
		pNode->pRight =RightRotate(pNode->pRight)
		
		Return LeftRotate(pNode)
		
	Endif
	
	Return pNode
	
End Function

Function TMAP.GetMinNode(pNode As MAPNODE Ptr) As MAPNODE Ptr
	
	Dim As MAPNODE Ptr pTemp =pNode
	
	While pTemp->pLeft <> 0
		
		pTemp =pTemp->pLeft
		
	Wend
	
	Return pTemp
	
End Function

Function TMAP.DelNode(pRoot As MAPNODE Ptr, nKey As String, bFlagFreeMemoryStrings As Long = 0) As MAPNODE Ptr
	
	If pRoot =0 Then Return 0
	
	If nKey <*(pRoot->nKey) Then
		
		pRoot->pLeft =delNode(pRoot->pLeft, nKey , bFlagFreeMemoryStrings)
		
	Elseif nKey >*(pRoot->nKey) Then
		
		pRoot->pRight =delNode(pRoot->pRight, nKey , bFlagFreeMemoryStrings)
		
	Else
		
		If pRoot->pLeft =0 Orelse pRoot->pRight =0 Then
			
			Dim As MAPNODE Ptr pTemp =Iif(pRoot->pLeft <> 0 , pRoot->pLeft , pRoot->pRight)
			
			If pTemp =0 Then
				
				If bFlagDelete =0 Then
					
					If pRoot->nKey Then 
						
						If bFlagFreeMemoryStrings Then
							
							If pRoot->nData Then
								
								Deallocate(pRoot->nData)
								
							Endif
							
						Endif
						
						Deallocate(pRoot->nKey)
						
					Endif
					
					pRoot->nKey =0
					
					pRoot->nData =0
					
				Endif
				
				pTemp =pRoot
				
				pRoot =0
				
			Else
				
				If bFlagDelete =0 Then
					
					If pRoot->nKey Then 
						
						If bFlagFreeMemoryStrings Then
							
							If pRoot->nData Then
								
								Deallocate(pRoot->nData)
								
							Endif
							
						Endif
						
						Deallocate(pRoot->nKey)
						
					Endif
					
					pRoot->nKey =0
					
					pRoot->nData =0
					
				Endif
				
				*pRoot =*pTemp
				
			Endif
			
			if pTemp then Delete pTemp
			
			pTemp =0
			
		Else
			
			Dim As MAPNODE Ptr pTemp =GetMinNode(pRoot->pRight)
			
			If pRoot->nKey Then 
				
				If bFlagFreeMemoryStrings Then
					
					If pRoot->nData Then
						
						Deallocate(pRoot->nData)
						
					Endif
					
				Endif
				
				Deallocate(pRoot->nKey)
				
			Endif
			
			pRoot->nKey =0
			
			pRoot->nData =0
			
			pRoot->nKey =pTemp->nKey
			
			bFlagDelete =1
			
			pRoot->nData =pTemp->nData
			
			pRoot->pRight =delNode(pRoot->pRight, *(pTemp->nKey) , bFlagFreeMemoryStrings)
			
		Endif
		
	Endif
	
	If pRoot =0 Then Return pRoot
	
	pRoot->bHeight =1 + MapMax(GetTreeHeight(pRoot->pLeft), GetTreeHeight(pRoot->pRight))
	
	Dim As Byte bBalance =GetBalance(pRoot)
	
	If bBalance >1 Andalso GetBalance(pRoot->pLeft) >= 0 Then Return RightRotate(pRoot)
	
	If bBalance >1 Andalso GetBalance(pRoot->pLeft) <0 Then
		
		pRoot->pLeft =LeftRotate(pRoot->pLeft)
		
		Return RightRotate(pRoot)
		
	Endif
	
	If bBalance <-1 Andalso GetBalance(pRoot->pRight) <= 0 Then Return LeftRotate(pRoot)
	
	If bBalance <-1 Andalso GetBalance(pRoot->pRight) >0 Then
		
		pRoot->pRight =RightRotate(pRoot->pRight)
		
		Return LeftRotate(pRoot)
		
	Endif
	
	Return pRoot
	
End Function

Function TMAP.FindNode(pNode As MAPNODE Ptr , nKey As String) As Any Ptr
	
	If pNode =0 Then
		
		Return 0
		
	Else
		
		If nKey <*(pNode->nKey) Then
			
			Return FindNode(pNode->pLeft , nKey)
			
		Else
			
			If nKey >*(pNode->nKey) Then
				
				Return FindNode(pNode->pRight , nKey)
				
			Else
				
				Return pNode->nData
				
			Endif
			
		Endif
		
	Endif
	
End Function

Sub TMAP.DelTree(pRoot As MAPNODE Ptr , bFlagFreeMemoryStrings As Long = 0)
	
	If pRoot <> 0 Then
		
		DelTree(pRoot->pLeft, bFlagFreeMemoryStrings)
		
		DelTree(pRoot->pRight, bFlagFreeMemoryStrings)
		
		If pRoot->nKey Then
			
			If bFlagFreeMemoryStrings Then
				
				If pRoot->nData Then
					
					Deallocate(pRoot->nData)
					
				Endif
				
			Endif
			
			Deallocate(pRoot->nKey)
			
		Endif
		
		pRoot->nKey =0
		
		pRoot->nData =0
		
		Delete (pRoot)
		
		pRoot =0
		
	Endif
	
End Sub

Sub TMAP.Insert(nKey As String , nData As Any Ptr , bFlagFreeMemoryStrings As Long = 0)
	
	If bFlagFreeMemoryStrings Then
		
		pRoot =InsertNodeS(pRoot, nKey , nData)
		
	Else
		
		pRoot =InsertNode(pRoot, nKey , nData)
		
	Endif
	
End Sub

Sub TMAP.DeleteNode(nKey As String , bFlagFreeMemoryStrings As Long = 0)
	
	If iSizeMap >0 Then
		
		bFlagDelete =0
		
		pRoot =DelNode(pRoot, nKey , bFlagFreeMemoryStrings)
		
		iSizeMap -=1
		
	Endif
	
End Sub

Function TMAP.Find(nKey As String) As Any Ptr
	
	Return FindNode(pRoot , nKey)
	
End Function

Sub TMAP.DeleteTree(bFlagFreeMemoryStrings As Long = 0)
	
	DelTree(pRoot , bFlagFreeMemoryStrings)
	
	pRoot =0
	
	iSizeMap =0
	
End Sub

' ============== GLOBAL FUNCTION ==================

Function CreateMap() As Any Ptr
	
	Return New TMAP
	
End Function

Function GetSizeMap(p As Any Ptr) As Long
	
	If p Then
		
		Return Cast(TMAP Ptr , p)->iSizeMap
		
	Endif
	
End Function

Function GetValueMap(p As Any Ptr , sKey As String) As Any Ptr
	
	If p Then
		
		Return Cast(TMAP Ptr , p)->find(sKey)
		
	Endif
	
End Function

Sub SetValueMap(p As Any Ptr , sKey As String , anyValue As Any Ptr)
	
	If p Then
		
		Cast(TMAP Ptr , p)->insert(sKey , anyValue)
		
	Endif
	
End Sub

Function GetValueStrMap(p As Any Ptr , sKey As String) As USTRING
	
	If p Then
		
		Dim As USTRING sRet
		
		#ifdef UNICODE
			Dim As Wstring Ptr pTemp = Cast(TMAP Ptr , p)->find(sKey)
		#else
			Dim As Zstring Ptr pTemp = Cast(TMAP Ptr , p)->find(sKey)
		#endif
		
		If pTemp Then
			
			sRet = *pTemp
			
		Endif
		
		Return sRet
		
	Endif
	
End Function

Sub SetValueStrMap(p As Any Ptr , sKey As String , anyValue As USTRING)
	
	If p Then
		
		#ifdef UNICODE
			Dim As Long iLen = Len(anyValue)
		#else
			Dim As Long iLen = Len(anyValue)
		#endif
		
		If iLen Then
			
			#ifdef UNICODE
				
				Dim As Wstring Ptr pws = Allocate(Sizeof(Wstring)*(iLen+1))
				
			#else
				
				Dim As Zstring Ptr pws = Allocate(iLen+1)
				
			#endif
			
			if pws then
				
				*pws = anyValue
				
				(*pws)[iLen] = 0
				
				Cast(TMAP Ptr , p)->insert(sKey , pws , 1)
				
			else
				
				print "Allocated memory error in SetValueStrMap!"
				
			endif
			
		Else
			
			Cast(TMAP Ptr , p)->insert(sKey , 0 , 1)
			
		Endif
		
	Endif
	
End Sub

Sub FreeMap(p As Any Ptr , bFlagFreeMemoryStrings As Long = 0)
	
	If p Then
		
		Cast(TMAP Ptr , p)->DeleteTree(bFlagFreeMemoryStrings)
		
	Endif
	
End Sub

Sub FreeKeyMap(p As Any Ptr , sKey As String , bFlagFreeMemoryStrings As Long = 0)
	
	If p Then
		
		Cast(TMAP Ptr , p)->DeleteNode(sKey , bFlagFreeMemoryStrings)
		
	Endif
	
End Sub

Sub DeleteMap(p As Any Ptr , bFlagFreeMemoryStrings As Long = 0)
	
	If p Then
		
		If Cast(TMAP Ptr , p)->iSizeMap Then
			
			Cast(TMAP Ptr , p)->DeleteTree(bFlagFreeMemoryStrings)
			
		Endif
		
		Delete Cast(TMAP Ptr , p)
		
	Endif
	
End Sub
