OpenEuphoria

Associative array

• Posted by menno Mar 06, 2011
• 2013 views

I have here example of a implementation of a Associative array (Content-addressable memory) , maybe usefull for somebody . Its build around a tullip (key,value)

Some example :

--Voorbeelden  
sequence klad={{},{}}  
-- klad = { keys , value } 
klad=cam_store(klad,{"123"},{}) 
klad=cam_store(klad,{"123"},{"456","bbb"}) 
klad=cam_store(klad,{"789","123","bb"},{{"987"},{"yyy"}}) 
klad=cam_store(klad,{"789","123","aa"},{{"456","aaa"},{"987","nnn"}}) 
?klad 
-- ? klad["789"]["123"]["bb"]["987"] 
?cam_fetch(klad,{"789","123","bb","987"}) 
-- klad["789"]["123"]["bb"]={{"987"},{"zzz"}} -- { key , value } 
klad=cam_store(klad,{"789","123","bb"},{{"987"},{"zzz"}}) 
?cam_fetch(klad,{"789","123","bb","987"}) 
-- klad["789"]["123"]["bb"]["987"]="xzx" 
klad=cam_store(klad,{"789","123","bb","987"},"xzx") 
?cam_fetch(klad,{"789","123","bb","987"}) 
-- klad["789"]["123"]["bb"][987]={1020,1021,1022,1023} 
klad=cam_store(klad,{"789","123","bb",987},{1020,1021,1022,1023}) 
-- ? klad["789"]["123"]["bb"][987] 
?cam_fetch(klad,{"789","123","bb",987}) 

It done by recursion . The search is used by bineary search .

global function cam_store(sequence var;key;val) 
integer index   
if length(key)>1 then  
 index=cam_key_index(var[1],key[1])  
-- printf(1,"indexs = %i key = %s \n",{index,key[1]}) 
 if index<0 then 
 index=-index-1 
 var[1]=insert(var[1],key[1],index) 
 var[2]=insert(var[2],{{},{}},index) 
 index+=1 
 end if   
 var[2][index]=cam_store(var[2][index],key[2..],val) 
else 
 index=cam_key_index(var[1],key[1])  
-- printf(1,"indes = %i key = %s \n",{index,key[1]}) 
 if index<0 then 
 index=-index-1 
 var[1]=insert(var[1],key[1],index) 
 var[2]=insert(var[2],val,index) 
 else   
 var[2][index]=val 
 end if 
end if 
return var  
end function  
 
global function cam_fetch(sequence var;key)  
integer index 
for i=1 to length(key) do  
index=cam_key_index(var[1],key[i]) 
if index>0 then 
var=var[2][index]                           
else 
return 0 
end if 
end for 
return var 
end function                       

cam_key_index is a bineary search (same as in search.e) .

function cam_key_index(sequence var;key)-- binary_search   
-- Find the record in the current table that contains the given key. 
-- If the key is not found, the place in the table where the key would go  
-- if it were inserted is returned as a negative record number. 
-- A binary search is used. 
    atom lo, hi, mid, c 
    lo = 1 
    hi = length(var) 
    mid = 1 
    c = 0 
    while lo <= hi do 
        mid = floor((lo + hi) / 2) 
        c = compare(key, var[mid]) 
        if c < 0 then 
            hi = mid - 1 
        elsif c > 0 then 
            lo = mid + 1 
        else 
            return mid 
        end if 
    end while 
    -- return the position it would have, if inserted now 
    if c > 0 then 
        mid += 1 
    end if 
    return -mid 
end function