[ 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