OpenEuphoria

associative arrays

• Posted by Jiri Babor <J.Babor at GNS.CRI.NZ> May 18, 2000
• 538 views

Hi, All (interested),

Associative arrays is the topic, as I promised earlier today. I call
them simply lists, because Rob kindly left the term vacant. For the
uninitiated, they are (labelled) containers for a bunch of 'key -
value' pairs. The key can be just about anything, but it's usually a
descriptive name, a string. The values can again be anything, even
lists, or lists of lists...

Simple enough concept, but very powerful. Whole languages can be built
around it, Brazilian Lua is a good example.

The lists are also very attractive in the Euphorian context,
especially since the promised namespace solution does not seem to be
forthcoming (is it really that tough, Rob?). They can be used to
simulate all sorts of things, for example structures, really simple
databases, or truly useful OO elements - without the extra namespace
pressure all other schemes tend to exert.

To my mind, there are only about three really simple designs possible.
The one used by Carl, basically just a sequence of alternating keys
and values. Obvious, very simple, but slow. Then the scheme I
originally used in my 'widgets' (see Archives): again a single
sequence, but this time all the keys bunched up in first half of the
sequence and all the values in the second half. Slightly faster,
because the searched length is obviously shorter, but it requires a
couple of calculations to determine the size of the list and to index
to the appropriate value. More recently, after a lot of tests, I
reverted to my original scheme: two separate 'parallel' subsequences
of equal length. It seems to be on average 20 to 50 % faster than the
second scheme. The routines in the attached include are an extract
from the version I am currently using for the widgets (unfinished,
unpublished).

Fancier implementation are of course possible. Rob described one
recently. Or you can have (pre)sorted lists, obviously faster for
larger sets when combined with a binary search. And some sort of
hashing is probably preferable for really huge lists. jiri

--  list.e
--  jiri babor
--  jbabor at paradise.net.nz
--  00-05-18
--  version 2.00  (trimmed)

include machine.e   -- crash_message()

global function index(sequence list, object key)
    -- return *key* index, or zero if key not found
    return find(key, list[1])
end function

global function fetch(sequence list, object key)
    -- return list item with indicated key
    integer i
    i = find(key, list[1])
    if i then
        return list[2][i]
    end if
    crash_message("fetch error: key \"" & key & "\" not found...\n")
end function -- fetch

global function Fetch(
    object list,        -- list from which value is to be fetched
    sequence keys       -- sequence of list keys, one for each level
                        -- last one directly associated with fetched
                        -- value
    )
    -- return item from *nested* list : 'deep' fetch
    for i=1 to length(keys) do
        list = fetch(list, keys[i])
    end for
    return list
end function -- Fetch

global function set(sequence list, object key, object new_value)
    -- replace specified list item with a new value
    -- return modified list

    integer i

    i = find(key, list[1])      -- key index
    if i then
        list[2][i] = new_value
        return list
    end if
    crash_message("store error: key \"" & key & "\" not found...\n")
end function -- set

global function Set (sequence list, sequence keys, object new_value)
    -- 'deep', recursive set for *nested* lists
    integer i,len
    len = length(keys)
    i = find(keys[1],list[1])
    if i then
        if len > 1 then
            list[2][i] = Set(list[2][i], keys[2..len], new_value)
        else
            list[2][i] = new_value
        end if
        return list
    end if
    crash_message("Set error: key \"" & keys[1] & "\" not found...\n")
end function -- Set

global function add(sequence list, object key, object val)
    -- append list
    return {append(list[1],key), append(list[2],val)}
end function -- add

global function join(sequence list1, sequence list2)
    -- concatenate list1 and list2
    return {list1[1] & list2[1],list1[2] & list2[2]}
end function

global function delete(sequence list, object key)
    -- delete item with the specified key from the list
    integer i,l
    i = find(key, list[1])      -- index
    if i then
        l = length(list[1])
        return {list[1][1..i-1] & list[1][i+1..l],
            list[2][1..i-1] & list[2][i+1..l]}
    end if
    crash_message("delete error: key \"" & key & "\" not found...\n")
end function -- delete