/*
 * By Chuck Connell, December 2007, for COMP 160 Algorithms at Tufts Univ.
 * Based on the Gale-Shapley algorithm (1962).
 *
 */

// package stablemarriage;   not needed to run from .class file

import java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;

public class StableMarriage {
        
   //  public StableMarriage() {   }    not needed for one-class program
    
    public static void main(String[] args) throws IOException  {
        
        int InputHeaderLines = 14;  // # of comment lines in the input file
        BufferedReader InputFile = null;
        String InputPath;  // location of input file
        String InputLine;   // one line of input
        String[] InputValues;   // a parsed input line
        int Pairs;  // how many pairs of men-women are there?
        int [][] ManPrefers;  // men's preferences for women as [man #][list of women #s]
        int [][] WomanPrefers;  // women's preferences for men as [woman #][list of men #s]
        int[] ManIsEngagedTo;  // who is each man engaged to?
        int[] WomanIsEngagedTo; // who is each woman engaged to?
        boolean EveryoneEngaged;  // does everyone have a mate?
        int ThisMan;  // which man is proposing now?
        int[] ProposalRank;  // where is each man in his order of proposals?
        int ChosenWoman; // what woman is the current man proposing to?
        int i, j;  // general purpose counters
        boolean SwitchMen;  // should a woman switch from her current man to the new proposal?
        boolean ManFound;  // after being proposed to by a man, can the woman find the man in her preference list?
        int ManLoopCount=0, WomanLoopCount=0; // for time analysis
        
        try {   // main try block
            
            // Get the command line args.
            if (args.length != 1) {
                System.out.println("Usage: StableMarriage <input-file>");
                return;
            }
            InputPath = new String(args[0]);
            
            // Open the input file.
            InputFile = new BufferedReader( new FileReader( InputPath ) );
            
            // Skip some header lines.
            for (i=0; i<InputHeaderLines; i++) {
                InputFile.readLine();
            }
            
            // How many pairs of men-women are in the input?
            Pairs = Integer.parseInt(InputFile.readLine());
            
            // Skip a blank line.
            InputFile.readLine();
            
            //Read the men's preference for women
            ManPrefers = new int[Pairs][Pairs];
            for (i=0; i<Pairs; i++) {
                InputLine = InputFile.readLine();
                InputValues = InputLine.split(" ");
                for (j=0; j<Pairs; j++) {
                    ManPrefers[i][j] = Integer.parseInt(InputValues[j]);
                }
            }
            
            // Skip a blank line.
            InputFile.readLine();
            
            //Read the women's preference for men
            WomanPrefers = new int[Pairs][Pairs];
            for (i=0; i<Pairs; i++) {
                InputLine = InputFile.readLine();
                InputValues = InputLine.split(" ");
                for (j=0; j<Pairs; j++) {
                    WomanPrefers[i][j] = Integer.parseInt(InputValues[j]);
                }
            }
            
            // Initialize some arrays that will hold various information.
            ManIsEngagedTo = new int[Pairs];
            WomanIsEngagedTo = new int[Pairs];
            ProposalRank = new int[Pairs];
            for (i=0; i<Pairs; i++) {
                ManIsEngagedTo[i] = -1;  // who is each man engaged to? no one now. see #1 in readme
                WomanIsEngagedTo[i] = -1;   // who is each woman engaged? no one now
                ProposalRank[i] = 0;   // where is each man in his order of proposals?
            }
            
            // Main loop that goes until every man is engaged at the same time.
            EveryoneEngaged = false;
            while (EveryoneEngaged == false) {
                
                // Assume that everyone is engaged when we start each set of proposals, then
                // see if it is really true.
                EveryoneEngaged = true;
                
                //Give each man a chance to propose, if he is not engaged.
                for (ThisMan=0; ThisMan<Pairs; ThisMan++){
                    
                    ManLoopCount++; // for time analysis
                    
                    // If this man is already engaged, go to the next man.
                    if (ManIsEngagedTo[ThisMan]!= -1) continue;
                    
                    // At least one person is not engaged.
                    EveryoneEngaged = false;
                    
                    // This man will propose to the next women in his list.
                    ChosenWoman = ManPrefers[ThisMan][ProposalRank[ThisMan]];  // see #2 in readme
                    
                    // The next time he has to ask someone, this man will propose to the next
                    // woman in his list.
                    ProposalRank[ThisMan]++;
                    
                    // If the woman is not engaged, she accepts. Then we are done with this man, for now.
                    if (WomanIsEngagedTo[ChosenWoman] == -1) {
                        WomanIsEngagedTo[ChosenWoman] = ThisMan;
                        ManIsEngagedTo[ThisMan] = ChosenWoman;
                        continue;
                    };
                    
                    // The woman chosen by this man is already engaged, but she might prefer this new man. 
                    // Check this by looking through the list of preferences for this woman, 
                    // to see who we come to first: the man she is currently engaged to, or the
                    // new man. If the latter, the woman will switch engagements, and the previous man will
                    // become unengaged.

                    ManFound = false; // make sure this woman finds this man in her list, a sanity check
                    SwitchMen = false;  // does this woman want to switch engagements?
                    
                    for (i=0; i<Pairs; i++){  // look through the men for this woman, see #3 in readme
                        WomanLoopCount++;   // for time analysis
                        if (ThisMan == WomanPrefers[ChosenWoman][i]){   // this new man is preferred
                            ManFound = true;
                            SwitchMen = true;
                            break;
                        };
                        if (WomanIsEngagedTo[ChosenWoman] == WomanPrefers[ChosenWoman][i]){ // previous engagement is preferred
                            ManFound = true;
                            SwitchMen = false;
                            break;
                        };
                    };
                    if (ManFound == false) { 
                        System.out.println("Internal error. Man not found in woman preference ranking. Man is " + ThisMan + ". Woman is " + ChosenWoman + ".");
                        return;
                    };
                    
                    // If this woman is not going to switch men, we are done here. This man
                    // is still not engaged.
                    if (SwitchMen == false) {
                        continue;   // go on to the next man
                    }
                    
                    // The chosen woman is going to switch to this new man.
                    else {
                        ManIsEngagedTo[WomanIsEngagedTo[ChosenWoman]] = -1;  // cancel previous engagement, see #4 in readme
                        WomanIsEngagedTo[ChosenWoman] = ThisMan;
                        ManIsEngagedTo[ThisMan] = ChosenWoman;
                    };
                    
                };  // for loop over each man
                
            };  // while not EveryoneEngage
            
            // Show the pairings.
            for (i=0; i<Pairs; i++) {
                System.out.println("Man " + i + " marries woman " + ManIsEngagedTo[i] + ".");
            };
            
            // Print time analysis info.
            System.out.println("Man loop count is " + ManLoopCount + ". Woman loop count is " + WomanLoopCount + ".");
            
        }   // end of main try block
        
        // main block finally
        finally {
            if (InputFile != null) {
                InputFile.close();
            }
        }
        
    }   // end main routine
    
}  // end StableMarriage class