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

Package Data_structures is

-- Fundamental definitions.  Words and patterns are sequences  of  one  or  more
-- letters; letters are integers in the range 1 .. 254.  In patterns, letter 255
-- matches word boundaries.  Zero is included in the definition of  type  Letter
-- as a value which no letter matches.  The maximum length of a pattern is arbi-
-- trary.

Subtype Letter is Integer range 0 .. 255;

Type Pattern is array (Positive range <>) of Letter;
Maximum_pattern_length: constant Integer := 80;

-- The  inter-letter  hyphenation weights for a pattern P (1..N) are stored in a
-- hyphenation weight array H (0..N).  H(i) is the weight for a  hyphen  between
-- P(i) and P(i+1).

Subtype Hyphenation_weight is Integer range 0 .. 9;
Type Hyphenation_weight_array is array (Natural range <>) of Hyphenation_weight;

-- A nonzero hyphenation weight H(i) for a pattern P (1..N) is  described  by  a
-- Weight_location  record  W with W.Weight = H(i) and W.Offset = N-i.  The non-
-- zero weights for a pattern are described by a linked list of such records  in
-- Weight_location_table.   Weight_location_table(0) is not used, so a zero Next
-- component indicates the end of a linked list.  Weight_location_table_last  is
-- the last entry in Weight_location_table that is in use.

Subtype Weight_location_table_index is Integer range 0 .. 255;

Type Weight_location is record
   Next: Weight_location_table_index;
   Weight: Hyphenation_weight;
   Offset: Integer range 0 .. Maximum_pattern_length;
end record;

Weight_location_table: array (Weight_location_table_index) of Weight_location;
Weight_location_table_last: Weight_location_table_index;

-- The  patterns  are  initially  placed  in Linked_trie, which is just that:  a
-- linked trie.  For a given node N,  N.Right  points  to  the  node's  sibling,
-- N.Down  points to the first member of the node's subfamily, and N.Char is the
-- letter associated with the node.  N.Weights is nonzero if the node is the end
-- of  a  pattern,  in  which case it points to the linked list of the pattern's
-- weights.  Linked_trie(0) is not used, so  zero  serves  as  a  null  pointer.
-- Linked_trie_last  is the last node in Linked_trie that is in use, and Linked_
-- trie_root is the root of the trie.

Subtype Trie_index is Integer range 0 .. 65535;

Type Linked_trie_node is record
   Right: Trie_index;
   Down: Trie_index;
   Weights: Weight_location_table_index;
   Char: Letter;
end record;

Linked_trie: array (Trie_index) of Linked_trie_node;
Linked_trie_last: Trie_index;
Linked_trie_root: Trie_index;

-- The  final repository for the patterns is Packed_trie, a packed trie.  For an
-- entry E, E.Next is a pointer to the base of the next family to transition  to
-- if  the current letter matches E.Char.  If E.Char is zero the transition is a
-- null transition.  E.Weights is nonzero if the entry is the end of a  pattern,
-- in which case it points to the linked list of the pattern's weights.  Packed_
-- trie_last is the last entry in Packed_trie that is in use.

Type Packed_trie_entry is record
   Next: Trie_index;
   Weights: Weight_location_table_index;
   Char: Letter;
end record;

Packed_trie: array (Trie_index) of Packed_trie_entry;
Packed_trie_last: Trie_index;

-- Exception words are stored in Exception_pool.  The letters associated with  a
-- given  exception  word  consist  of a letter whose value is the length of the
-- word in letters; followed by the word itself; followed by zero or  more  let-
-- ters  whose  values describe the valid hyphen positions within the word; fol-
-- lowed by letter 0.  A hyphen that can occur between letters i and i+1  of  an
-- exception  word (1..N) is described by the value i.  Exception_pool(0) is not
-- used.  Exception_pool_last is the last letter in Exception_pool  that  is  in
-- use.   Exception_table  is an ordered hash table that maps exception words to
-- the exception word descriptions in Exception_pool.  The length of  Exception_
-- table is arbitrary.

Subtype Exception_pool_index is Integer range 0 .. 65535;

Exception_pool: array (Exception_pool_index) of Letter;
Exception_pool_last: Exception_pool_index;

Exception_table: array (0 .. 520) of Exception_pool_index;

end Data_structures;

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

Package body Data_structures is begin

   Weight_location_table_last := 0;
   Linked_trie_last := 0;
   Linked_trie_root := 0;
   Packed_trie := ( others=>( 0, 0, 0 ) );
   Packed_trie_last := 0;
   Exception_pool_last := 0;
   Exception_table := ( others=>0 );

end Data_structures;

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