OpenEuphoria

JZ's ASSOC.E - FIXED!

• Posted by JEFF ZEITLIN <jeff.zeitlin at EXECNET.COM> Mar 31, 1997
• 938 views

I've fixed and recoded (enhanced speed/efficiency) my ASSOC.E -
the associative lists implementation.  I've added some (quite a
lot, in fact) comments up front, and a new routine has been
implemented.

8<------------->8 cut here 8<------------------->8
-- assoc.e - associative lists
-- by Jeff Zeitlin (jeff.zeitlin at execnet.com)

-- The idea for implementing associative lists in Euphoria comes from
-- several sources:
--      Some people suggested allowing arbitrary subscripts for Euphoria
--           sequences.
--      The LISP language supports them (associative lists) in the form
--           of "property lists"
--      The SNOBOL language supports them in the form of "tables"
--      The REXX language effectively supports them in the form of
--           "stem" variables

-- This implementation does not conform exactly to any of the above models
-- due to restrictions on implementability.  The following concepts have
-- been borrowed from each:

--    LISP uses a functional model for accessing property lists.  Because
--         it is not possible to extend the actual subscripting mechanism
--         in Euphoria, it is necessary to use a function model for access.
--    SNOBOL allows totally arbitrary subscripts to tables.  The LISP model
--         does not allow all possible subscripts; one cannot call a LISP
--         property by the name "4", for example.
--    REXX also allows arbitrary identifiers to be attached to stem names,
--         but each one is effectively a separate variable.  REXX also
--         provides the concept of the default value for non-existant
--         specific instances.

-- This Euphoria implementation takes DEFAULT VALUE storage from REXX,
-- ARBITRARY KEYS from SNOBOL, and FUNCTIONAL ACCESS from LISP.

-- A previous implementation structured the assoc_list as a sequence
-- containing sequences in the form of {key, value} pairs.  Upon reflection,
-- this proved to be a highly inefficient method of storing this information,
-- although quite obvious to read and understand if printed out in an ex.err
-- dump.

-- This implementation stores the assoc_list as three sequences - a default
-- value, a sequence containing the keys, and a sequence containing the values.
-- This is much less obvious for debugging purposes, but allows for
-- significantly shorter procedures and faster execution.

-- The interfaces for both implementations are the same; this new
-- implementation permits the deletion of an association, which function
-- was omitted (though conceivably implementable) from the last version.

-- the following types and procedures are supplied:

-- the type assoc_list

-- assoc_list l
-- l = alist_set(assoc_list alist, object key, object value)
--     Adds a new key/value association to the list if the current key does
--     not exist; changes the value of the existing association if it does.

-- object o
-- o = alist_reference(assoc_list alist, object key)
--     Retrieves and returns the value associated with a key, or the default
--     value if the key doesn't exist.

-- assoc_list l
-- l = alist_default(assoc_list list, object default)
--     Sets the default value for the assoc_list.

-- assoc_list l
-- l = alist_delete(assoc_list list, object key)
--     Deletes the association pair whose key is "key"

global type assoc_list(sequence s)
    if length(s) = 0 then                -- empty list?
        return 1                         -- yes, it is - and therefore valid
    end if
    if length(s) != 3 then               -- other than default, keys, values?
        return 0                         -- yes, bad structure, fail check.
    end if
    if length(s[2]) != length(s[3]) then -- other than one val for each key?
        return 0                         -- yes, bad structure, fail check.
    end if
    return 1
end type

global function alist_default(assoc_list list, object defval)
    assoc_list newlist

    if length(list) = 0 then          -- empty assoc_list?
        newlist = {{defval},{},{}}    -- yes, so create the default
    else
        newlist = list                -- copy the existing assoc_list
        newlist[1] = {defval}         -- change the default value
    end if
    return newlist
end function

global function alist_set(assoc_list list, object key, object val)
    assoc_list newlist
    integer index

    newlist = list
    if length(newlist) = 0 then
        newlist = {{},{},{}}
    end if
    index = find(key,newlist[2])
    if index = 0 then
        newlist[2]=append(newlist[2],key)
        newlist[3]=append(newlist[3],val)
    else
        newlist[3][index] = val
    end if
    return newlist
end function

global function alist_reference(assoc_list list, object key)
    integer index

    if length(list) = 0 then
        return {}
    end if
    index = find(key, list[2])
    if index = 0 then
        return list[1]
    else
        return list[3][index]
    end if
end function

global function alist_delete(assoc_list list, object key)
    integer index
    assoc_list newlist

    if length(list) = 0 then
        return {{},{},{}}
    end if
    index = find(key, list[2])
    if index = 0 then
        return list
    end if
    newlist = {list[1],
               list[2][1..index-1]&list[2][index+1..length(list[2])],
               list[3][1..index-1]&list[3][index+1..length(list[3])]}
    return newlist
 end function
8<------------->8 cut here 8<------------------->8

 =========================================================================
Jeff Zeitlin                                      jeff.zeitlin at execnet.com
---
 ~ OLXWin 1.00b ~ SYSOP: Snooty Yuppie Sitting On Potty