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

-- Procedure  Load_pattern_file_into_Linked_trie loads the patterns contained in
-- a "pattern file" into Linked_trie.  This procedure may  not  be  called  more
-- than once to load in more than one pattern file.  The pattern file is assumed
-- to be open on entry and is not closed on return.

With Data_structures, Text_IO;
Use  Data_structures, Text_IO;

Procedure Load_pattern_file_into_Linked_trie ( Pattern_file: in File_type ) is

   H: Hyphenation_weight_array (0..Maximum_pattern_length);
   Length: Natural;
   Line: String (1..32767);
   N: Positive;
   P: Pattern (1..Maximum_pattern_length);

   Hash_table: array (0 .. 520) of Weight_location_table_index := ( others=>0 );
Procedure Convert_representation ( S: in String; P: out Pattern; P_length: out
   Positive; H: out Hyphenation_weight_array ) is

   J: Natural := 0;
   Nonzero_weight_encountered: Boolean := False;

   Pattern_string_contains_illegal_hyphenation_weight: Exception;
   Pattern_string_contains_no_nonzero_weight: Exception;
   Pattern_string_contains_null_character: Exception;
   Pattern_string_has_zero_length: Exception;
   Pattern_string_is_longer_than_80_characters: Exception;

begin

   H := ( others=>0 );

   For I in S'range loop
      If S(I) in '0' .. '9' then

         -- The character is a digit, and hence must be an inter-letter hyphena-
         -- tion weight.  Note that J starts out being zero,  so  that  a  digit
         -- before any pattern character is correctly put in H(0).

         If I < S'last and then S(I+1) in '0' .. '9' then
            Raise Pattern_string_contains_illegal_hyphenation_weight;
         end if;

         If S(I) /= '0' then Nonzero_weight_encountered := True; end if;
         H(J) := Character'pos( S(I) ) - Character'pos( '0' );

      else

         -- The  character is a non-digit character, and hence must be a pattern
         -- character.  There is no ambiguity in mapping periods to  255s  since
         -- the  Character  type uses only values 0 through 127.  We assume here
         -- that Maximum_pattern_length is 80.

         J := J + 1;
         If J > P'last then
            Raise Pattern_string_is_longer_than_80_characters;
         end if;

         If S(I) = ASCII.NUL then
            Raise Pattern_string_contains_null_character;
         end if;

         If S(I) = '.' then
            P(J) := 255;
         else
            P(J) := Character'pos( S(I) );
         end if;

      end if;
   end loop;

   If J = 0 then Raise Pattern_string_has_zero_length; end if;
   P_length := J;

   If not Nonzero_weight_encountered then
      Raise Pattern_string_contains_no_nonzero_weight;
   end if;

end Convert_representation;

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

-- Once the pattern string has been converted to the Pattern/Hyphenation_weight_
-- array representation, we use a straight-forward loop to insert the pattern in
-- our linked trie.  The pattern's nonzero weights are inserted into the  weight
-- location table at this time.

Function Load_weight_location ( W: in Weight_location ) return
   Weight_location_table_index is

   I: Natural;
   Weight_location_table_has_overflowed: Exception;

begin

   -- To  eliminate redundancy in the table, we see if an identical weight loca-
   -- tion is already in the table.  If there is, we simply return its index; if
   -- not,  we  create  a new entry in the table.  This check uses the following
   -- hash table to quickly locate the given weight location.


   I := ( 361*W.Next + W.Weight + 313*W.Offset ) mod Hash_table'length;

   While Hash_table(I) /= 0 and then Weight_location_table(Hash_table(I)) /= W
      loop

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

   end loop;

   -- At this point, either we found the given weight location  and  can  simply
   -- return its index, or we must add the location to the table, which is fair-
   -- ly straight-forward.

   If Hash_table(I) = 0 then

      If Weight_location_table_last = Weight_location_table'last then
         Raise Weight_location_table_has_overflowed;
      end if;

      Weight_location_table_last := Weight_location_table_last + 1;
      Weight_location_table(Weight_location_table_last) := W;
      Hash_table(I) := Weight_location_table_last;

   end if;

   Return Hash_table(I);

end Load_weight_location;

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

Function Load_weight_array_into_Weight_location_table ( H: in
   Hyphenation_weight_array ) return Weight_location_table_index is

   Link: Weight_location_table_index := 0;

begin

   For I in reverse H'range loop
      If H(I) /= 0 then
         Link := Load_weight_location( ( Next=>Link, Weight=>H(I),
            Offset=>H'last-I ) );
      end if;
   end loop;

   Return Link;

end Load_weight_array_into_Weight_location_table;

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

-- Function Load_weight_location loads a single weight location into the  weight
-- location  table, and returns its index.  If there is insufficient room in the
-- table, an exception is raised.

Procedure Load_pattern ( P: in Pattern; H: in Hyphenation_weight_array ) is

   At_first_member: Boolean;
   F: Trie_index;
   L: Trie_index;
   Linked_trie_has_overflowed: Exception;
   Pattern_file_contains_duplicate_pattern: Exception;

begin

   -- To  insert  the  pattern into the linked trie, we use two pointers, L (the
   -- leader) and F (the follower).  L walks across and down the trie,  stepping
   -- down  once for each letter in the pattern.  F does the same, but stays one
   -- node behind L at all times.

   F := 0;
   For I in P'range loop

      -- At  this  point in the loop we're ready to process another character in
      -- the pattern.  To do so we drop down to the current node's subfamily (or
      -- to  the  first  family  if  we're on the first character) and then scan
      -- across the family until we hit either the end of the family or  a  node
      -- that is greater than or equal to the current character.

      If F = 0 then L := Linked_trie_root;
      else
         L := Linked_trie(F).Down;
      end if;
      At_first_member := True;

      While L /= 0 and then Linked_trie(L).Char < P(I) loop
         F := L;
         L := Linked_trie(F).Right;
         At_first_member := False;
      end loop;

      -- There  are three possibilities at this point:  either we hit the end of
      -- the family (or there was no family to begin with), or we're at  a  node
      -- which  is  greater than the current character, or we're at a node which
      -- is equal to the current character.  In the last case, we simply  conti-
      -- nue looping; in the first two cases we need to create a new node.

      If L = 0 or else Linked_trie(L).Char > P(I) then

         If Linked_trie_last = Linked_trie'last then
            Raise Linked_trie_has_overflowed;
         end if;

         Linked_trie_last := Linked_trie_last + 1;
         Linked_trie(Linked_trie_last) := ( Right=>L, Down=>0, Weights=>0,
            Char=>P(I) );
         L := Linked_trie_last;

         If F = 0 then
            Linked_trie_root := L;
         else
            If At_first_member then
               Linked_trie(F).Down  := L;
            else
               Linked_trie(F).Right := L;
            end if;
         end if;

      end if;

      -- The last step is to set the following pointer to the leading pointer so
      -- that on the next iteration we drop down another level.

      F := L;

   end loop;

   -- If the Weights component of the current (and final) node is nonzero, some-
   -- thing is wrong...

   If Linked_trie(F).Weights /= 0 then
      Raise Pattern_file_contains_duplicate_pattern;
   else
      Linked_trie(F).Weights := Load_weight_array_into_Weight_location_table(
         H );
   end if;

end Load_pattern;

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

-- Function Load_weight_array_into_Weight_location_table loads the nonzero hyph-
-- enation  weights  in a weight array into a linked list in the weight location
-- table, and returns the index of the first weight location.



begin

   While not End_of_file( Pattern_file ) loop

      Get_line( Pattern_file, Line, Length );

      If Length > 0 then
         Convert_representation( Line (1..Length), P, N, H );
         Load_pattern( P (1..N), H (0..N) );
      end if;

   end loop;

end Load_pattern_file_into_Linked_trie;

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

-- A  line  in a pattern file either is empty or is a pattern string.  A pattern
-- string is an alternate representation of a pattern that is used only in  pat-
-- tern  files.   Pattern strings are immediately converted to the Pattern/Hyph-
-- enation_weight_array representation, which is used throughout the program.

-- A pattern string consists primarily of a string of one  or  more  characters;
-- the  characters may be any characters but ASCII.NUL and '0' through '9'.  The
-- mapping from a pattern string to a Pattern is the straight-forward mapping of
-- characters  to  Letters:   characters  are  mapped to the corresponding ASCII
-- codes, except for periods which are mapped to 255s.  Between  any  two  char-
-- acters in a pattern string, and before the first and after the last character
-- in a pattern string, is a digit character that  represents  the  inter-letter
-- hyphenation  weight  at  that point.  Zero weights may be omitted.  A pattern
-- string must have at least one nonzero hyphenation weight.

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

-- The  following  procedure  validates  a pattern string and converts it to the
-- Pattern/Hyphenation_weight_array representation.

