ALGOL 68/prelude: Difference between revisions
Content added Content deleted
(Added a string in string implementation for use with implementations other than Algol 68.) |
(Added associative array definitions.) |
||
Line 83: | Line 83: | ||
FI # string in string # ;</lang> |
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 === |
=== The classic [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/wg21/ UNESCO IFIP Working Group 2.1]'s standard prelude contents === |