--------------------------------------------------------------------------------

-- Procedure  Compress_Linked_trie  compresses  Linked_trie  by combining common
-- subtries.  The compression is effected by adjusting pointers and simply  dis-
-- regarding  redundant  nodes;  Linked_trie  is  not actually shortened, nor is
-- Linked_trie_last decremented.

With Data_structures;
Use  Data_structures;

Procedure Compress_Linked_trie is

Hash_table: array (0 .. 131100) of Trie_index := ( others=>0 );
Function First_matching_node ( I: in Trie_index ) return Trie_index is

   J: Natural;

begin

   J := ( 3142*Linked_trie(I).Right + 2718*Linked_trie(I).Down +
      1009*Linked_trie(I).Weights + Linked_trie(I).Char ) mod Hash_table'length;

   While Hash_table(J) /= 0 and then Linked_trie(Hash_table(J)) /=
      Linked_trie(I) loop

      If J = 0 then
         J := Hash_table'last;
      else
         J := J - 1;
      end if;

   end loop;

   If Hash_table(J) = 0 then Hash_table(J) := I; end if;
   Return Hash_table(J);

end First_matching_node;

--------------------------------------------------------------------------------

Function Compress ( I: in Trie_index ) return Trie_index is begin

   If I = 0 then Return 0;
   else

      Linked_trie(I).Down  := Compress( Linked_trie(I).Down  );
      Linked_trie(I).Right := Compress( Linked_trie(I).Right );

      Return First_matching_node( I );

   end if;

end Compress;

--------------------------------------------------------------------------------

--------------------------------------------------------------------------------

-- Function First_matching_node returns either the index of a given node, or  if
-- an  identical  node has already been encountered, the index of that node.  To
-- keep track of the nodes seen so far, we use the following hash table.




begin

   Linked_trie_root := Compress( Linked_trie_root );

end Compress_Linked_trie;

--------------------------------------------------------------------------------

--------------------------------------------------------------------------------

-- Function  Compress  performs a depth-first traversal of Linked_trie.  At each
-- node it recurses to compress the node's subtrie and right sibling,  and  then
-- updates the node with the new pointers.  Compress returns either the index of
-- the node, or if an identical node has been encountered previously, the  index
-- of  that node.  It is this last action, of course, that does the actual "com-
-- pressing."

