The Dictionary Module

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 ")">;
  };

Bibliography

[AHU1974] A.V.Aho, J.E.Hopcroft, and J.D.Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley. Reading, Mass.. 1974.