Associative array/Iteration: Difference between revisions
Content added Content deleted
(added ceylon) |
(Added Algol 68) |
||
Line 31: | Line 31: | ||
hello 1 |
hello 1 |
||
world 2 |
world 2 |
||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
Algol 68 does not have associative arrays as standard. |
|||
<br> |
|||
This sample defines a simple hash-based implementation with operators to iterate over the array. |
|||
<lang algol68># associative array handling using hashing # |
|||
# the modes allowed as associative array element values - change to suit # |
|||
MODE AAVALUE = STRING; |
|||
# the modes allowed as associative array element keys - change to suit # |
|||
MODE AAKEY = STRING; |
|||
# nil element value # |
|||
REF AAVALUE nil value = NIL; |
|||
# an element of an associative array # |
|||
MODE AAELEMENT = STRUCT( AAKEY key, REF AAVALUE value ); |
|||
# a list of associative array elements - the element values with a # |
|||
# particular hash value are stored in an AAELEMENTLIST # |
|||
MODE AAELEMENTLIST = STRUCT( AAELEMENT element, REF AAELEMENTLIST next ); |
|||
# nil element list reference # |
|||
REF AAELEMENTLIST nil element list = NIL; |
|||
# nil element reference # |
|||
REF AAELEMENT nil element = NIL; |
|||
# the hash modulus for the associative arrays # |
|||
INT hash modulus = 256; |
|||
# generates a hash value from an AAKEY - change to suit # |
|||
OP HASH = ( STRING key )INT: |
|||
BEGIN |
|||
INT result := ABS ( UPB key - LWB key ) MOD hash modulus; |
|||
FOR char pos FROM LWB key TO UPB key DO |
|||
result PLUSAB ( ABS key[ char pos ] - ABS " " ); |
|||
result MODAB hash modulus |
|||
OD; |
|||
result |
|||
END; # HASH # |
|||
# a mode representing an associative array # |
|||
MODE AARRAY = STRUCT( [ 0 : hash modulus - 1 ]REF AAELEMENTLIST elements |
|||
, INT curr hash |
|||
, REF AAELEMENTLIST curr position |
|||
); |
|||
# initialises an associative array so all the hash chains are empty # |
|||
OP INIT = ( REF AARRAY array )REF AARRAY: |
|||
BEGIN |
|||
FOR hash value FROM 0 TO hash modulus - 1 DO ( elements OF array )[ hash value ] := nil element list OD; |
|||
array |
|||
END; # INIT # |
|||
# gets a reference to the value corresponding to a particular key in an # |
|||
# associative array - the element is created if it doesn't exist # |
|||
PRIO // = 1; |
|||
OP // = ( REF AARRAY array, AAKEY key )REF AAVALUE: |
|||
BEGIN |
|||
REF AAVALUE result; |
|||
INT hash value = HASH key; |
|||
# get the hash chain for the key # |
|||
REF AAELEMENTLIST element := ( elements OF array )[ hash value ]; |
|||
# find the element in the list, if it is there # |
|||
BOOL found element := FALSE; |
|||
WHILE ( element ISNT nil element list ) |
|||
AND NOT found element |
|||
DO |
|||
found element := ( key OF element OF element = key ); |
|||
IF found element |
|||
THEN |
|||
result := value OF element OF element |
|||
ELSE |
|||
element := next OF element |
|||
FI |
|||
OD; |
|||
IF NOT found element |
|||
THEN |
|||
# the element is not in the list # |
|||
# - add it to the front of the hash chain # |
|||
( elements OF array )[ hash value ] |
|||
:= HEAP AAELEMENTLIST |
|||
:= ( HEAP AAELEMENT := ( key |
|||
, HEAP AAVALUE := "" |
|||
) |
|||
, ( elements OF array )[ hash value ] |
|||
); |
|||
result := value OF element OF ( elements OF array )[ hash value ] |
|||
FI; |
|||
result |
|||
END; # // # |
|||
# gets the first element (key, value) from the array # |
|||
OP FIRST = ( REF AARRAY array )REF AAELEMENT: |
|||
BEGIN |
|||
curr hash OF array := LWB ( elements OF array ) - 1; |
|||
curr position OF array := nil element list; |
|||
NEXT array |
|||
END; # FIRST # |
|||
# gets the next element (key, value) from the array # |
|||
OP NEXT = ( REF AARRAY array )REF AAELEMENT: |
|||
BEGIN |
|||
WHILE ( curr position OF array IS nil element list ) |
|||
AND curr hash OF array < UPB ( elements OF array ) |
|||
DO |
|||
# reached the end of the current element list - try the next # |
|||
curr hash OF array +:= 1; |
|||
curr position OF array := ( elements OF array )[ curr hash OF array ] |
|||
OD; |
|||
IF curr hash OF array > UPB ( elements OF array ) |
|||
THEN |
|||
# no more elements # |
|||
nil element |
|||
ELIF curr position OF array IS nil element list |
|||
THEN |
|||
# reached the end of the table # |
|||
nil element |
|||
ELSE |
|||
# have another element # |
|||
REF AAELEMENTLIST found element = curr position OF array; |
|||
curr position OF array := next OF curr position OF array; |
|||
element OF found element |
|||
FI |
|||
END; # NEXT # |
|||
# test the associative array # |
|||
BEGIN |
|||
# create an array and add some values # |
|||
REF AARRAY a1 := INIT LOC AARRAY; |
|||
a1 // "k1" := "k1 value"; |
|||
a1 // "z2" := "z2 value"; |
|||
a1 // "k1" := "new k1 value"; |
|||
a1 // "k2" := "k2 value"; |
|||
a1 // "2j" := "2j value"; |
|||
# iterate over the values # |
|||
REF AAELEMENT e := FIRST a1; |
|||
WHILE e ISNT nil element |
|||
DO |
|||
print( ( " (" + key OF e + ")[" + value OF e + "]", newline ) ); |
|||
e := NEXT a1 |
|||
OD |
|||
END</lang> |
|||
{{out}} |
|||
<pre> |
|||
(2j)[2j value] |
|||
(k1)[new k1 value] |
|||
(k2)[k2 value] |
|||
(z2)[z2 value] |
|||
</pre> |
</pre> |
||