-- generic package to represent preference information for an
-- instance of the stable roommates problem

-- preferences are assumed to be strict, but there is no
-- restriction on the number of persons involved, and
-- preference lists can be incomplete and inconsistent

-- author: Rob Irving, University of Glasgow
-- last modified: 31 August 2000

generic
   Num_Persons : Natural; -- the actual number of persons  
package Rm_Pref_Info is

   type Pref_Info_Type is private; 

   procedure Get_Pref_Info (
         P :    out Pref_Info_Type ); 
   -- reads in preference information from standard input
   -- assumes each line contains the preference list of
   -- a person x in the form x : a b c . . .
   -- Person identifiers are strings of length <= 20

   procedure Put_Complete_Pref_Lists (
         P : in     Pref_Info_Type ); 
   -- writes the complete preference lists to standard output

   procedure List_Stable_Matching (
         P : in     Pref_Info_Type ); 
   -- writes to standard output a stable matching for the
   -- roommates instance specified by P; effect is not
   -- defined if no stable matching exists

   procedure Display_Stable_Matching (
         P : in     Pref_Info_Type ); 
   -- displays to standard output, in the form of annotated
   -- preference lists, a stable matching for the roommates
   -- in stance specified by P; effect is not defined if no
   -- stable matching exists

   procedure Put_Current_Pref_Lists (
         P : in     Pref_Info_Type ); 
   -- displays to standard output the current preference lists;
   -- for example, when called after Apply_Phase_1, will display
   -- the phase 1 lists

   procedure Apply_Phase_1 (
         P           : in out Pref_Info_Type; 
         Sm_Possible :    out Boolean         ); 
   -- applies phase 1 of the roommates algorithm; leaves the phase 1
   -- table represented in P; returns SM_Possible true unless the
   -- phase 1 table has an odd number of non-empty lists

   procedure Apply_Phase_2 (
         P        : in out Pref_Info_Type; 
         Sm_Found :    out Boolean         ); 
   -- applies phase 2 of the roommates algorithm; leaves a stable matching
   -- represented in P if one exists, otherwise returns SM_Found false

   Table_Overflow : exception;
   -- raised if the number of person identifiers exceeds
   -- the number of persons specified in the input

   Pref_List_Error : exception;
   -- raised if some person appears on his own preference list

private

   subtype Person_Index is Integer range 0 .. Num_Persons;
   subtype Rank_Index is Integer range 0 .. Num_Persons;

   type Person_Node is 
      record 
         Person      : Person_Index := 0;  
         Predecessor,  
         Successor   : Rank_Index;  
      end record; 

   type Pref_List_Type is array (Rank_Index) of Person_Node; 
   type Rank_Type is array (Person_Index) of Rank_Index; 

   type Person_Type is 
      record 
         Pref_List      : Pref_List_Type;  
         Rank           : Rank_Type      := (others => Num_Persons);  
         List_Length    : Natural        := 0;  
         Holds_Proposal : Boolean        := False;  
      end record; 

   type Pref_Info_Type is array (Person_Index) of Person_Type; 

end Rm_Pref_Info;