OpenEuphoria

1. Associative array

• Posted by menno Mar 06, 2011
• 2010 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 

3. Re: Associative array

• Posted by menno Mar 09, 2011
• 1778 views

Hum I wasn't , but forgot to change the PEU syntax into Euphoria syntax . Something as sequence a;b;c means sequence a,sequence b, sequence c . Here the converted code witch I test with Euphoria version 2.5 . That why I had to implement a insert() function .

--De var =  {{key's}{value's}}   
--cam = content adresseble memory    
function cam_key_index(sequence var, sequence 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 
 
global function insert(sequence org, sequence what, integer where)  
if where then  
return org[1..where]&{what}&org[where+1..length(org)] 
else 
return {what}&org[where+1..length(org)] 
end if 
end function                 
 
global function cam_store(sequence var, sequence key, sequence val) 
integer index   
if atom(key) then key={key} end if 
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..length(key)],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, sequence key)  
integer index 
if atom(key) then key={key} end if  
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                       

Menno .

5. Re: Associative array

• Posted by petelomax Mar 09, 2011
• 1735 views

Ah, your implementation of insert() does not work the same as RDS Eu 4.
(I assume the 2.5 compatible version you gave works the same as PEU)
I ran this on Eu 4:

?insert({1,2,4},{3},3) 
global function Minsert(sequence org, sequence what, integer where)  
if where then   
return org[1..where]&{what}&org[where+1..length(org)]  
else  
return {what}&org[where+1..length(org)]  
end if  
end function  
?Minsert({1,2,4},{3},3) 
if getc(0) then end if 

which gave me

{ 
  1, 
  2, 
  {3}, 
  4 
} 
{ 
  1, 
  2, 
  4, 
  {3} 
} 

FWIW, I think this is compatible with Eu 4:

global function insert(sequence target, object what, integer index) 
  return target[1..index-1] & {what} & target[index..length(target)] 
end function 

Regards, Pete

7. Re: Associative array

• Posted by petelomax Mar 09, 2011
• 1710 views

A function simply named "insert()" rather than "insert_before()" or "insert_after()" is inherently ambiguous, however I think the questions you should focus on are:

• how much legacy code must I change?
• how much do I want RDS Eu code to run unchanged on PEU?
• is the RDS Eu team likely to deprecate insert in favor of insert_before/after?

HTH,
Pete

9. Re: Associative array

• Posted by mattlewis (admin) Mar 09, 2011
• 1725 views

I don't think it's ambiguous. It says to me: Insert something. Put it here. The result follows logically from that.

The one I have trouble with is replace. The start parameter is obvious. But I can never remember if the second one is length or end position (it's the end position). I do that with just about any sort of substring function in just about any language, though.

Matt

PS It's OpenEuphoria now.