-- Program to solve arbitrary instances of the stable roommates problem

-- Author: Rob Irving, University of Glasgow
-- Date: August 2000

-- Input is as follows: 
   -- Line 1: N, a positive integer, size of instance
   -- Lines 2..N+1: the preference lists, each has form X : A B C ...
   -- where X is the owner and A, B, C, ... are entries in order;
   -- person identifiers are arbitrary strings of upt to 20 chars

-- Output consists of:
   -- the original preference lists;
   -- the so-called 'phase-1 table';
   -- an indication of whether a stable matching exists;
   -- if so, the preference lists annotated with one such matching
   -- and a list of the matched pairs
   
-- Assumptions
   -- each person's list is on a single line, with no trailing blanks;
   -- number of lists corresponds to input value of n
   -- lists need not be complete, nor need they be consistent

with Ada.Text_Io;
use Ada.Text_Io;
with Ada.Integer_Text_Io;
use Ada.Integer_Text_Io;

with Rm_Pref_Info;

procedure Solve_Roommates is 
   N : Natural;  
begin
   Get(N);  -- the number of persons in the instance
   Skip_Line;
   
   declare  -- block to allow instantiation of appropriate package
      package P is new Rm_Pref_Info(N); -- N is appropriate size for
                                        -- the preference structure 
      use P;

      P_I         : Pref_Info_Type;  -- the preference structure
      Sm_Possible : Boolean := True;
                    -- stable matching still possible while this true
      Sm_Found    : Boolean := False;
                    -- stable matching found when this true

   begin
      -- Get the preference lists
      Get_Pref_Info(P_I);
      
      -- Echo the given lists
      Put("Given preference lists:");
      New_Line(2);
      Put_Complete_Pref_Lists(P_I);
      New_Line(3);
      
      -- Apply phase 1 of the roommates algorithm
      Apply_Phase_1(P_I, Sm_Possible);
      Put_Line("Phase 1 Lists:");
      New_Line;
      Put_Current_Pref_Lists(P_I);
      New_Line(3);
      
      if not Sm_Possible then
         Put_Line("No stable matching exists");
      else
         -- apply phase 2 of the roomates algorithm
         Apply_Phase_2(P_I, Sm_Found);
         if Sm_Found then
            Put("Stable matching displayed as follows:");
            New_Line(2);
            Display_Stable_Matching(P_I);
            New_Line(3);
            Put("Stable matching listed as follows:");
            New_Line(2);
            List_Stable_Matching(P_I);
         else
            Put_Line("No stable matching exists");
         end if;
      end if;
      
   exception
      when Table_Overflow =>
         Put_Line("Too many names; perhaps a name was mis-spelt.");
         Put_Line("Please check data.");
      when Pref_List_Error =>
         Put_Line("Error in input.");
         Put_Line("Some person appears on his own preference list");
   end;
end Solve_Roommates;