ALGOL 68/prelude: Difference between revisions
Added associative array definitions.
(Added a string in string implementation for use with implementations other than Algol 68.) |
(Added associative array definitions.) |
||
Line 83:
FI # string in string # ;</lang>
== aArray.a68 ==
An associative array MODE for STRING keys and values. THis is used by a number of Rosseta Code tasks.
<lang algol68># associative array for STRING elements and keys #
# 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;
PR read "aArrayBase.a68" PR</lang>
== aArrayBase.a68 ==
The MODEs for associative arrays. The AAKEY and AAVALUE MODEs must be defined as required.
<br>If AAKEY is not STRING, a suitable HASH operator will also need to be defined.
<lang algol68># associative array handling using hashing #
# AAKEY and AAVALUE modes and OP HASH(AAKEY)INT must be defined to use this #
# nil element value #
REF AAVALUE nil value = NIL;
# generates a hash value from a STRING - additional HASH operators should be #
# defined for other AAKEY modes #
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 #
# 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;
# 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; # // #
# returns TRUE if array contains key, FALSE otherwise #
PRIO CONTAINSKEY = 1;
OP CONTAINSKEY = ( REF AARRAY array, AAKEY key )BOOL:
BEGIN
# get the hash chain for the key #
REF AAELEMENTLIST element := ( elements OF array )[ HASH key ];
# 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 NOT found element
THEN
element := next OF element
FI
OD;
found element
END; # CONTAINSKEY #
# 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 #</lang>
=== The classic [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/wg21/ UNESCO IFIP Working Group 2.1]'s standard prelude contents ===
| |||