MAP (ассоциативный контейнер или словарь)
Реализация MAP , ассоциативного контейнера или чаще известного как словарь. Реализован на основе AVL дерева.
Платформы: Windows, Linux
'\\\\\\\\\\\\\\\\\\\\\\\\\ руководство по использованию \\\\\\\\\\\\\\\\\\\\\\\' 'для создания ассоциативного контейнера необходимо выполнить макрос: 'MapCreate(MapPTR , MapTypeKey , MapTypeData , MapReplaceDataFlag) '-------MapPTR - любое уникальное имя , будущий указатель (с помощью его происходит доступ ко всему интерфейсу) '-------MapTypeKey - тип данных для ключа (Byte , String и другие) , по которому происходит вставка\поиск\удаление в MAP '-------MapTypeData - тип для самих данных (Byte , String и другие) '-------MapReplaceDataFlag - необязательный флаг для перезаписи данных по уже имеющемуся ключу (если не указывать параметр или 0 , то не перезаписывать, если 1 - перезаписывать ) 'После выполнения макроса , можно: '1) выполнять вставку с помощью INSERT: 'INSERT (KEY , DATA) '-------KEY - уникальный ключ , имеющий тип , указанный в MapTypeKey '-------DATA - любые данные , имеющие тип , указанный в MapTypeData '2) удалять один элемент с помощью DELETENODE: 'DELETENODE(KEY) '-------KEY - уникальный ключ , имеющий тип , указанный в MapTypeKey '3) искать и получать данные с помощью FIND: 'FIND(KEY) '-------KEY - уникальный ключ , имеющий тип , указанный в MapTypeKey '4) Удалить все данные из MAP с помощью DeleteTree: 'DeleteTree() '--------------------------------------- 'Далее идут малозначимые и малопригодные возможности и функции '-------------------------------------- ' '5) можно получить указатель на текущий корень дерева, примерно так: ' 'MapPTR->pRoot ' '6) узнать высоту дерева можно примерно так: ' 'MapPTR->GetTreeHeight(MapPTR->pRoot) ' '7) можно распечатать в консоли все ключи и данные с помощью InOrder: 'InOrder(MapPTR->pRoot) '8) можно распечатать псевдографический вид дерева с помощью printTreePseudographic (дерево повернуто на бок): 'printTreePseudographic(MapPTR->pRoot) 'пример можно найти в самом внизу ' Реализация MAP с помощью AVL дерева #MACRO map_type (ctkey , ctdata , MapReplaceDataFlag...) #IFNDEF container_type_key##ctkey Type container_type_key##ctkey As ctkey #ENDIF #IFNDEF Type container_type_data##ctdata As ctdata #ENDIF #IFNDEF Node##ctkey##ctdata Type Node##ctkey##ctdata #IF ctkey = String As Zstring Ptr nKey #ELSE As container_type_key##ctkey nKey #ENDIF #IF ctdata = String As Zstring Ptr nData #ELSE As container_type_data##ctdata nData #ENDIF As Node##ctkey##ctdata Ptr pLeft As Node##ctkey##ctdata Ptr pRight As Byte bHeight End Type #ENDIF #IFNDEF Tmap##ctkey##ctdata Type Tmap##ctkey##ctdata As Node##ctkey##ctdata Ptr pRoot As Byte bFlagDelete Declare Function Max( a As Byte, b As Byte) As Byte Declare Function GetTreeHeight(pNode As Node##ctkey##ctdata Ptr) As Byte Declare Function RightRotate(y As Node##ctkey##ctdata Ptr) As Node##ctkey##ctdata Ptr Declare Function LeftRotate(x As Node##ctkey##ctdata Ptr) As Node##ctkey##ctdata Ptr Declare Function GetBalance(pNode As Node##ctkey##ctdata Ptr) As Byte Declare Function InsertNode(pNode As Node##ctkey##ctdata Ptr, nKey As container_type_key##ctkey , nData As container_type_data##ctdata) As Node##ctkey##ctdata Ptr Declare Function GetMinNode(pNode As Node##ctkey##ctdata Ptr) As Node##ctkey##ctdata Ptr Declare Function DelNode(pRoot As Node##ctkey##ctdata Ptr, nKey As container_type_key##ctkey) As Node##ctkey##ctdata Ptr #IF ctdata = String Declare Function FindNode(pNode As Node##ctkey##ctdata Ptr , nKey As container_type_key##ctkey) As Zstring Ptr #ELSE Declare Function FindNode(pNode As Node##ctkey##ctdata Ptr , nKey As container_type_key##ctkey) As container_type_data##ctdata #ENDIF Declare Sub DelTree(pRoot As Node##ctkey##ctdata Ptr) ' user interface Declare Sub Insert(nKey As container_type_key##ctkey , nData As container_type_data##ctdata) Declare Sub DeleteNode(nKey As container_type_key##ctkey) Declare Function Find(nKey As container_type_key##ctkey) As container_type_data##ctdata Declare Sub DeleteTree() End Type Dim Shared As Byte m_gg_m##ctkey##ctdata(MapReplaceDataFlag) Function Tmap##ctkey##ctdata.Max( a As Byte, b As Byte) As Byte Return Iif(a > b , a , b) End Function Function Tmap##ctkey##ctdata.GetTreeHeight(pNode As Node##ctkey##ctdata Ptr) As Byte If pNode = 0 Then Return 0 Return pNode->bHeight End Function Function Tmap##ctkey##ctdata.RightRotate(y As Node##ctkey##ctdata Ptr) As Node##ctkey##ctdata Ptr Dim As Node##ctkey##ctdata Ptr x = y->pLeft Dim As Node##ctkey##ctdata Ptr z = x->pRight x->pRight = y y->pLeft = z y->bHeight = Max(GetTreeHeight(y->pLeft), GetTreeHeight(y->pRight)) + 1 x->bHeight = Max(GetTreeHeight(x->pLeft), GetTreeHeight(x->pRight)) + 1 Return x End Function Function Tmap##ctkey##ctdata.LeftRotate(x As Node##ctkey##ctdata Ptr) As Node##ctkey##ctdata Ptr Dim As Node##ctkey##ctdata Ptr y = x->pRight Dim As Node##ctkey##ctdata Ptr z = y->pLeft y->pLeft = x x->pRight = z x->bHeight = Max(GetTreeHeight(x->pLeft), GetTreeHeight(x->pRight)) + 1 y->bHeight = Max(GetTreeHeight(y->pLeft), GetTreeHeight(y->pRight)) + 1 Return y End Function Function Tmap##ctkey##ctdata.GetBalance(pNode As Node##ctkey##ctdata Ptr) As Byte If pNode = 0 Then Return 0 Return GetTreeHeight(pNode->pLeft) - GetTreeHeight(pNode->pRight) End Function Function Tmap##ctkey##ctdata.InsertNode(pNode As Node##ctkey##ctdata Ptr, nKey As container_type_key##ctkey , nData As container_type_data##ctdata) As Node##ctkey##ctdata Ptr If pNode = 0 Then Dim As Node##ctkey##ctdata Ptr pNode = New Node##ctkey##ctdata #IF ctkey = String Dim As Zstring Ptr pszTemp = Callocate(Len(nData)+1) *pszTemp = nKey pNode->nKey = pszTemp #ELSE pNode->nKey = nKey #ENDIF #IF ctdata = String Dim As Zstring Ptr pszTemp2 = Callocate(Len(nData)+1) *pszTemp2 = nData pNode->nData = pszTemp2 #ELSE pNode->nData = nData #ENDIF pNode->pLeft = 0 pNode->pRight = 0 pNode->bHeight = 1 Return pNode Endif #IF ctkey = String 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 Select Case Ubound(m_gg_m##ctkey##ctdata) Case 1 #IF ctdata = String *(pNode->nData) = nData #ELSE pNode->nData = nData #ENDIF End Select Return pNode Endif pNode->bHeight = 1 + Max(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 #ELSE 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 Select Case Ubound(m_gg_m##ctkey##ctdata) Case 1 #IF ctdata = String *(pNode->nData) = nData #ELSE pNode->nData = nData #ENDIF End Select Return pNode Endif pNode->bHeight = 1 + Max(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 #ENDIF Return pNode End Function Function Tmap##ctkey##ctdata.GetMinNode(pNode As Node##ctkey##ctdata Ptr) As Node##ctkey##ctdata Ptr Dim As Node##ctkey##ctdata Ptr pTemp = pNode While pTemp->pLeft <> 0 pTemp = pTemp->pLeft Wend Return pTemp End Function Function Tmap##ctkey##ctdata.DelNode(pRoot As Node##ctkey##ctdata Ptr, nKey As container_type_key##ctkey) As Node##ctkey##ctdata Ptr If pRoot = 0 Then Return 0 #IF ctkey = String If nKey < *(pRoot->nKey) Then pRoot->pLeft = delNode(pRoot->pLeft, nKey) Elseif nKey > *(pRoot->nKey) Then pRoot->pRight = delNode(pRoot->pRight, nKey) Else If pRoot->pLeft = 0 orelse pRoot->pRight = 0 Then Dim As Node##ctkey##ctdata Ptr pTemp = Iif(pRoot->pLeft <> 0 , pRoot->pLeft , pRoot->pRight) If pTemp = 0 Then If bFlagDelete = 0 Then Deallocate(pRoot->nKey) #IF ctdata = String Deallocate(pRoot->nData) #ENDIF Endif pTemp = pRoot pRoot = 0 Else If bFlagDelete = 0 Then Deallocate(pRoot->nKey) #IF ctdata = String Deallocate(pRoot->nData) #ENDIF Endif *pRoot = *pTemp Endif Delete pTemp Else Dim As Node##ctkey##ctdata Ptr pTemp = GetMinNode(pRoot->pRight) Deallocate(pRoot->nKey) #IF ctdata = String Deallocate(pRoot->nData) #ENDIF pRoot->nKey = pTemp->nKey bFlagDelete = 1 pRoot->nData = pTemp->nData pRoot->pRight = delNode(pRoot->pRight, *(pTemp->nKey)) Endif Endif #ELSE If nKey < pRoot->nKey Then pRoot->pLeft = delNode(pRoot->pLeft, nKey) Elseif nKey > pRoot->nKey Then pRoot->pRight = delNode(pRoot->pRight, nKey) Else If pRoot->pLeft = 0 orelse pRoot->pRight = 0 Then Dim As Node##ctkey##ctdata Ptr pTemp = Iif(pRoot->pLeft <> 0 , pRoot->pLeft , pRoot->pRight) If pTemp = 0 Then #IF ctdata = String If bFlagDelete = 0 Then Deallocate(pRoot->nData) Endif #ENDIF pTemp = pRoot pRoot = 0 Else #IF ctdata = String If bFlagDelete = 0 Then Deallocate(pRoot->nData) Endif #ENDIF *pRoot = *pTemp Endif Delete pTemp Else Dim As Node##ctkey##ctdata Ptr pTemp = GetMinNode(pRoot->pRight) #IF ctdata = String Deallocate(pRoot->nData) #ENDIF pRoot->nKey = pTemp->nKey bFlagDelete = 1 pRoot->nData = pTemp->nData pRoot->pRight = delNode(pRoot->pRight, pTemp->nKey) Endif Endif #ENDIF If pRoot = 0 Then Return pRoot pRoot->bHeight = 1 + Max(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 #IF ctdata = String Type map__return__find__##ctkey##ctdata As Zstring Ptr #ELSE Type map__return__find__##ctkey##ctdata As container_type_data##ctdata #ENDIF #IF ctkey = String Function Tmap##ctkey##ctdata.FindNode(pNode As Node##ctkey##ctdata Ptr , nKey As container_type_key##ctkey) As map__return__find__##ctkey##ctdata 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 #ELSE Function Tmap##ctkey##ctdata.FindNode(pNode As Node##ctkey##ctdata Ptr , nKey As container_type_key##ctkey) As map__return__find__##ctkey##ctdata 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 #ENDIF Sub Tmap##ctkey##ctdata.DelTree(pRoot As Node##ctkey##ctdata Ptr) If pRoot <> 0 Then DelTree(pRoot->pLeft) DelTree(pRoot->pRight) #IF ctkey = String Deallocate(pRoot->nKey) #ENDIF #IF ctdata = String Deallocate(pRoot->nData) #ENDIF Delete (pRoot) Endif End Sub Sub Tmap##ctkey##ctdata.Insert(nKey As container_type_key##ctkey , nData As container_type_data##ctdata) pRoot = InsertNode(pRoot, nKey , nData) End Sub Sub Tmap##ctkey##ctdata.DeleteNode(nKey As container_type_key##ctkey) bFlagDelete = 0 pRoot = DelNode(pRoot, nKey) End Sub Function Tmap##ctkey##ctdata.Find(nKey As container_type_key##ctkey) As container_type_data##ctdata #IF ctdata = String Dim As Zstring Ptr pszTemp = FindNode(pRoot , nKey) If pszTemp Then Return *pszTemp #ELSE Return FindNode(pRoot , nKey) #ENDIF End Function Sub Tmap##ctkey##ctdata.DeleteTree() DelTree(pRoot) End Sub Sub InOrder Overload(pRoot As Node##ctkey##ctdata Ptr) If pRoot <> 0 Then inOrder(pRoot->pLeft) #IF ctkey = String #IF ctdata = String Print *(pRoot->nKey) ; " " ; *(pRoot->nData) #ELSE Print *(pRoot->nKey) ; " " ; pRoot->nData #ENDIF #ELSE #IF ctdata = String Print pRoot->nKey ; " " ; *(pRoot->nData) #ELSE Print pRoot->nKey ; " " ; pRoot->nData #ENDIF #ENDIF inOrder(pRoot->pRight) Endif End Sub Sub printTreePseudographic Overload(pRoot As Node##ctkey##ctdata Ptr , k As Uinteger = 0) If pRoot <> 0 Then printTreePseudographic(pRoot->pRight , k+3) For i As Integer = 0 To k-1 ? " " ; Next #IF ctkey = String ? *(pRoot->nKey) #ELSE ? pRoot->nKey #ENDIF printTreePseudographic(pRoot->pLeft , k+3) Endif End Sub #ENDIF #EndMacro #MACRO MapCreate (mapNamePtr , MapKey , MapData , MapReplaceDataFlag...) map_type (MapKey , MapData , MapReplaceDataFlag) Dim mapNamePtr As Tmap##MapKey##MapData Ptr = New Tmap##MapKey##MapData #EndMacro '''''''''''''''''''Пример''''''''''''''''''''''''' ? "Create MAP (string,string)" MapCreate(map_ss , String , String) For i As Long = 1 To 7 map_ss->insert(Str(i) , Str(i*100)) Next ? "height tree= "; map_ss->GetTreeHeight(map_ss->pRoot); Chr(10) ? "-----Print all tree" ? "key ";"data" InOrder(map_ss->pRoot) ? Chr(10);"Press Any key" Sleep Cls ? Chr(10);"-----Print the tree in the printTreePseudographic view:" printTreePseudographic(map_ss->pRoot) ? Chr(10); "Value from 5 Key = " ; map_ss->Find("5") map_ss->DeleteTree() ? Chr(10);"Press Any key" Sleep() Cls ? "Create MAP (integer,integer)" MapCreate(map_ii , Integer , Integer , 0) For i As Long = 25 To 35 map_ii->insert(i , i*100) Next ? "-----Print all tree" ? "key ";"data" InOrder(map_ii->pRoot) ? Chr(10);"Press Any key" Sleep Cls ? Chr(10);"-----Print the tree in the printTreePseudographic view:" printTreePseudographic(map_ii->pRoot) map_ii->DeleteTree() ? Chr(10);"Press Any key" Sleep
