-- Generic package to represent preference information for an
-- instance of the stable marriage problem

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

-- Author: Rob Irving, University of Glasgow
-- Last modified: 5 September 2000

generic

   Num_Men   : Natural; -- the number of men 
   Num_Women : Natural; -- the number of women 
package Sm_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 first n lines contain the preference list of
   -- man i (i = 1,..,n) in the form i : a b c . . .
   -- next m lines contain the preference list of
   -- woman j (j = 1,..,m) in the form j : a b c . .
   -- here, n = Num_Men, m = Num_Women

   procedure Put_Complete_Pref_Lists (
         P : in     Pref_Info_Type ); 
   -- writes the complete preference lists to standard output
   -- men's lists, one per line, a blank line, then
   -- women's lists one per line, in same format as input

   procedure List_M_Opt_Matching (
         P : in     Pref_Info_Type ); 
   -- writes to standard output the man optimal stable matching
   -- for the stable marriage instance specified by P;
   -- the matching is listed by man, and then separately by woman

   procedure List_W_Opt_Matching (
         P : in     Pref_Info_Type ); 
   -- writes to standard output the woman optimal stable matching
   -- for the stable marriage instance specified by P;
   -- the matching is listed by woman, and then separately by man

   procedure Display_M_Opt_Matching (
         P : in     Pref_Info_Type ); 
   -- displays to standard output, in the form of annotated
   -- preference lists, the man optimal stable matching
   -- for the stable marriage instance specified by P

   procedure Display_W_Opt_Matching (
         P : in     Pref_Info_Type ); 
   -- displays to standard output, in the form of annotated
   -- preference lists, the woman optimal stable matching
   -- for the stable marriage instance specified by P

   procedure Put_Current_Pref_Lists (
         P : in     Pref_Info_Type ); 
   -- displays to standard output the current preference lists;
   -- for example, when called after the G-S algorithm has been
   -- executed, will display the appropriate GS-lists

   procedure Apply_Gs_M (
         P : in out Pref_Info_Type ); 
   -- applies the GS-algorithm from the men's side; 
   -- leaves the reduced lists represented in P

   procedure Apply_Gs_W (
         P : in out Pref_Info_Type ); 
   -- applies the GS-algorithm from the women's side;
   -- leaves the reduced lists represented in P

   Table_Overflow : exception;
   -- raised if the number of man or woman identifiers
   -- exceeds the number as specified in the input


private

   subtype Man_Index is Integer range 0 .. Num_Men;
   subtype Woman_Index is Integer range 0 .. Num_Women;
   subtype Man_Rank_Index is Integer range 0 .. Num_Men+1;
   subtype Woman_Rank_Index is Integer range 0 .. Num_Women+1;

   type Man_Node is 
      record 
         Man         : Man_Index      := 0;  
         Predecessor,  
         Successor   : Man_Rank_Index;  
      end record; 

   type Woman_Node is 
      record 
         Woman       : Woman_Index      := 0;  
         Predecessor,  
         Successor   : Woman_Rank_Index;  
      end record; 

   type Man_Pref_List_Type is array (Woman_Rank_Index) of Woman_Node; 
   type Woman_Pref_List_Type is array (Man_Rank_Index) of Man_Node; 
   type Man_Rank_Type is array (Woman_Index) of Woman_Rank_Index; 
   type Woman_Rank_Type is array (Man_Index) of Man_Rank_Index; 

   type Man_Type is 
      record 
         Pref_List   : Man_Pref_List_Type;  
         Rank        : Man_Rank_Type      := (others => Num_Women + 1); 
           
         List_Length : Natural            := 0;  
         Assigned    : Boolean            := False;  
      end record; 

   type Woman_Type is 
      record 
         Pref_List   : Woman_Pref_List_Type;  
         Rank        : Woman_Rank_Type      := (others => Num_Men + 1); 
           
         List_Length : Natural              := 0;  
         Assigned    : Boolean              := False;  
      end record; 

   type Man_Pref_Info_Type is array (Man_Index) of Man_Type; 
   type Woman_Pref_Info_Type is array (Woman_Index) of Woman_Type; 

   type Pref_Info_Type is 
      record 
         Men   : Man_Pref_Info_Type;  
         Women : Woman_Pref_Info_Type;  
      end record; 

end Sm_Pref_Info;