[ Aleksandar Ružičić @ 24.05.2008. 18:17 ] @
Malopre sam prvi put pokusao da napravim hash table tip podataka i uspelo mi iz prve :) ja sam mislio da je to mnogo komplikovanije... elem, evo uradio sam PHP-like asocijativni niz, tj niz koji kao kljuceve (keys) moze da ima i stringove i brojeve (integer), evo makroa: Code: #Define ASSOC_ARRAY_LOG_COLLISIONS ' ' Paul Hsieh's SuperFastHash ' http://www.azillionmonkeys.com/qed/hash.html ' Function SuperFastHash(Key As Const String) As UInteger #Define get16bits(d) ((Cast(UInteger, Cast(UByte Ptr, d)[1]) Shl 8) + Cast(UInteger, Cast(UByte Ptr, d)[0])) Dim As UInteger length = Len(Key), hash = length, tmp Dim As Integer r Dim As ZString Ptr chars = StrPtr(Key) If length = 0 Then Return 0 r = length And 3 length Shr= 2 Do While length > 0 hash += get16bits(chars) tmp = (get16bits(chars + 2) Shl 11) Xor hash hash = (hash Shl 16) Xor tmp chars += 2 * SizeOf(UShort) hash += hash Shr 11 length -= 1 Loop Select Case r Case 3 hash += get16bits(chars) hash Xor= hash Shr 16 hash Xor= chars[SizeOf(UShort)] Shl 18 hash += hash Shr 11 Case 2 hash += get16bits(chars) hash Xor= hash Shl 11 hash += hash Shr 17 Case 1 hash += *Cast(UByte Ptr, chars) hash Xor= hash Shl 10 hash += hash Shr 1 End Select hash Xor= hash Shl 3 hash += hash Shr 5 hash Xor= hash Shl 4 hash += hash Shr 17 hash Xor= hash Shl 25 hash += hash Shr 6 Return hash #Undef get16bits End Function Type HashFunc As Function(Key As Const String) As UInteger Enum KeyType Undefined IntegerKey StringKey End Enum #Macro DefineAssocArrayType(_TYPE_) #Ifndef __ASSOC_ARRAY_TYPE_##_TYPE_ #Define __ASSOC_ARRAY_TYPE_##_TYPE_ Type _TYPE_##ArrayItem Value As _TYPE_ Key As KeyType Union iKey As Integer Ptr sKey As String Ptr End Union Declare Sub Clear Declare Destructor End Type Sub _TYPE_##ArrayItem.Clear Select Case Key Case IntegerKey: DeAllocate iKey Case StringKey: DeAllocate sKey End Select End Sub Destructor _TYPE_##ArrayItem This.Clear End Destructor Type _TYPE_##Array Public: Declare Property Item(ByVal Key As Integer) As _TYPE_ Declare Property Item(ByVal Key As Integer, Value As _TYPE_) Declare Property Item(ByVal Key As String) As _TYPE_ Declare Property Item(ByVal Key As String, Value As _TYPE_) Declare Constructor(numBuckets As Integer = 10007, numItems As Integer = 31, hashfunc As HashFunc = ProcPtr(SuperFastHash)) Declare Destructor Private: hash As HashFunc table As _TYPE_##ArrayItem Pointer Pointer numBuckets As Integer itemsPerBucket As Integer End Type Constructor _TYPE_##Array(numBuckets As Integer = 10007, numItems As Integer = 31, hashfunc As HashFunc = ProcPtr(SuperFastHash)) This.numBuckets = numBuckets itemsPerBucket = numItems hash = hashfunc table = New _TYPE_##ArrayItem Pointer[numBuckets] For i As Integer = 0 To numBuckets - 1 table[i] = New _TYPE_##ArrayItem[itemsPerBucket] Next End Constructor Destructor _TYPE_##Array For i As Integer = 0 To numBuckets - 1 Delete[] table[i] Next Delete[] table End Destructor Property _TYPE_##Array.Item(ByVal Key As Integer) As _TYPE_ Dim As UInteger keyHash = hash(Chr(1) + Str(Key)) Return table[keyHash Mod numBuckets][keyHash Mod itemsPerBucket].Value End Property Property _TYPE_##Array.Item(ByVal Key As Integer, Value As _TYPE_) Dim As UInteger keyHash = hash(Chr(1) + Str(Key)) With table[keyHash Mod numBuckets][keyHash Mod itemsPerBucket] If .Key <> Undefined Then ' collision - DAMMIT! If Not (.Key = IntegerKey And *.iKey = Key) Then .Clear #Ifdef ASSOC_ARRAY_LOG_COLLISIONS Print "collision: (integer)"; Key; " with "; Select Case .Key Case IntegerKey: Print " (integer) "; .iKey Case StringKey: Print " (string) "; .sKey End Select #EndIf EndIf EndIf .Value = Value .Key = IntegerKey .iKey = Allocate(SizeOf(Integer)) *.iKey = Key End With End Property Property _TYPE_##Array.Item(ByVal Key As String) As _TYPE_ Dim As UInteger keyHash = hash(Key) Return table[keyHash Mod numBuckets][keyHash Mod itemsPerBucket].Value End Property Property _TYPE_##Array.Item(ByVal Key As String, Value As _TYPE_) Dim As UInteger keyHash = hash(Key) With table[keyHash Mod numBuckets][keyHash Mod itemsPerBucket] If .Key <> Undefined Then ' collision - DAMMIT! If Not (.Key = StringKey And *.sKey = Key) Then .Clear #Ifdef ASSOC_ARRAY_LOG_COLLISIONS Print "collision: (string)"; Key; " with "; Select Case .Key Case IntegerKey: Print " (integer) "; .iKey Case StringKey: Print " (string) "; .sKey End Select #EndIf EndIf EndIf .Value = Value .Key = StringKey .sKey = Callocate(SizeOf(String)) *.sKey = Key End With End Property #EndIf #EndMacro ovo ubacite u neki fajl, recimo assocarray.bi i onda ovako koristite: Code: #include "assocarray.bi" DefineAssocArrayType( Integer ) ' asocijativni niz koji sadrzi Integer vrednosti DefineAssocArrayType( String ) ' asocijativni niz koji sadrzi String vrednosti Dim As IntegerArray array Dim As StringArray s array.Item("bla") = 123 array.Item(123) = 124 array.Item(123) = 124324 Print array.Item("bla"), array.Item(123) s.item("color") = "red" s.item("fruit") = "oranges" s.item(1) = "one" Print s.item("color"), s.item("fruit"), s.item(1) Sleep ukoliko iskombinujete Mixed tip onda mozete da imate ovakav tip (koji je skoro identican PHP-ovim nizovima): Code: #include "assocarray.bi" #include "mixed.bi" DefineAssocArrayType( Mixed ) Dim array As MixedArray array.Item("color name") = "red" array.Item("color value") = &HFF0000 array.Item(10) = "Ten" array.Item(100) = 100 |