Dictionaries are represented by binary trees [AHU1974]. Each tree node is represented by a box containing three symbols: a key, a
value associated with the key, a reference to the left subtree, and a reference to the right
subtree. An empty tree is represented by a reference to an empty box.
The module CmpDic has the following implementation:
//
// File: CmpDic.rf
//
$use Box Compare Arithm StdIO;
// Creates an empty dictionary.
MakeDic = <Box>;
// Looks up the dictionary s.Dic for the label associated
// with the key s.Key. If the key s.Key is not registered
// in the dictionary, the dictionary is updated:
// the key s.Key is associated with a new unique label.
LookupDic s.Key s.Dic =
<Get s.Dic> :
{
=
<Box> :: s.Ref,
<Store s.Dic s.Key s.Ref <Box> <Box>>,
= s.Ref;
s.Key1 s.Ref1 s.DicL s.DicR =
<Compare (s.Key)(s.Key1)> :
{
'<' = <LookupDic s.Key s.DicL>;
'>' = <LookupDic s.Key s.DicR>;
'=' = s.Ref1;
};
};
// Allocates memory for the labels registered in
// the dictionary. s.A is the start address.
// The address corresponding to a label is put
// into the box referred to by the label.
AllocateDic s.Dic s.A =
<Get s.Dic> :
{
= s.A;
s.Key s.Ref s.DicL s.DicR =
<AllocateDic s.DicL s.A> :: s.A1,
<Store s.Ref s.A1>,
<Add s.A1 1> :: s.A2,
= <AllocateDic s.DicR s.A2>;
};
WriteDic s.Dic =
<Get s.Dic> :
{
= <Print "_">;
s.Key s.Ref s.DicL s.DicR =
<Print "(">, <WriteDic s.DicL>, <Print " ">,
<Write s.Key>,
<Get s.Ref> :
{
= ;
e.Value = <Print "->"> <Write e.Value>;
},
<Print " ">,
<WriteDic s.DicR>, <Print ")">;
};