1.11.9. МОДУЛЬ РАБОТЫ СО СЛОВАРЕМ Словари реализованы в виде бинарных деревьев [АХУ 79]. Каждый узел дерева представлен ящиком, который содержит три символа: ключ, значение ключа, ссылки на левое поддерево и ссылки на правое поддерево. Пустое дерево представляется ссылкой на пустой ящик. Модуль CMPDIC имеет следующую реализацию: **
** File: CMPDIC.RF
**
$use BOX;
$use COMPARE;
$use ARITHM;
** Создание нового пустого словаря.
Make-Dic
= <Box>;
** Поиск в словаре s.Dic метки, связанной с ключом
** s.Key. Если ключа s.Key еще нет в словаре, он заносится
** в словарь и связывается с новой уникальной меткой.
Lookup-Dic s.Key s.Dic =
<? 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)> :
{
'<' = <Lookup-Dic s.Key s.DicL>;
'>' = <Lookup-Dic s.Key s.DicR>;
'=' = s.Ref1;
};
};
** Распределение памяти под метки, находящиеся в словаре.
** s.A - начальный адрес. Адреса, соответствующие меткам,
** заносятся в ящики, на которые указывают метки.
Allocate-Dic s.Dic s.A =
<? s.Dic> :
{
= s.A;
s.Key s.Ref s.DicL s.DicR =
<Allocate-Dic s.DicL s.A> :: s.A,
<Store s.Ref s.A>,
<"+" s.A 1> :: s.A,
= <Allocate-Dic s.DicR s.A>;
};
Write-Dic s.Dic =
<? s.Dic> :
{
= <Print "_">;
s.Key s.Ref s.DicL s.DicR =
<Print "(">, <Write-Dic s.DicL>, <Print " ">,
<Write s.Key>,
<? s.Ref> :
{
= ;
e.Value = <Print "->"> <Write e.Value>;
},
<Print " ">,
<Write-Dic s.DicR>, <Print ")">;
};