Associative array/Iteration: Difference between revisions
Added Algol 68
(added ceylon) |
(Added Algol 68) |
||
Line 31:
hello 1
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>
| |||