StableMarriage

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class StableMarriage
{
    public static void main(String[] args) throws FileNotFoundException
    {
        ArrayList<Person> men = importMen();
        ArrayList<Person> women = importWomen();

        Map<Person, Person> pairings = determinePairs(men, women);
        print(pairings);
    }
    public static ArrayList<Person> importMen() throws FileNotFoundException
    {
        Scanner boy = new Scanner(new File("Boys.txt"));
        ArrayList<Person> men = new ArrayList<>(50);

        while(boy.hasNext())
        {
            String person = boy.next();
            if(person.equals("END"))
            {
                break;
            }
            String name = person.substring(0, person.indexOf(":"));

            ArrayList<Integer> preferences = new ArrayList<>(50);

            while(boy.hasNextInt())
            {
                preferences.add(boy.nextInt());
            }
            preferences.trimToSize();
            men.add(new Person(name, preferences));
        }
        men.trimToSize();
        return men;
    }
    public static ArrayList<Person> importWomen() throws FileNotFoundException
    {
        Scanner girl = new Scanner(new File("Girls.txt"));
        ArrayList<Person> women = new ArrayList<>(50);

        while(girl.hasNext())
        {
            String person = girl.next();
            if(person.equals("END"))
            {
                break;
            }
            String name = person.substring(0, person.indexOf(":"));

            ArrayList<Integer> preferences = new ArrayList<>();

            while(girl.hasNextInt())
            {
                preferences.add(girl.nextInt());
            }
            preferences.trimToSize();
            women.add(new Person(name, preferences));
        }
        women.trimToSize();
        return women;
    }
    public static Map<Person, Person> determinePairs(ArrayList<Person> men, ArrayList<Person> women)
    {
        //set each person to be free
        Map<Person, Person> pairings = new HashMap<>();

        //while(some women w with a nonempty preference is free)
        while(pairings.size() < women.size())
        {
            for(int i = 0; i < women.size(); i++)
            {
                Person w = women.get(i);
                while(w.getPreferences().size() > 0 && !pairings.containsKey(w))
                {
                    //set m = first man on w's list
                    int firstMan = w.getPreferences().get(0);
                    Person m = men.get(firstMan);
                    //set woman free if engaged to man m
                    if(pairings.containsValue(m))
                    {
                        pairings.values().remove(m);
                    }
                    //set m and w to be engaged to each other
                    pairings.put(w, m);
                    //for each successor q of w on m's list
                    int q = m.getPreferences().indexOf(i);

                    for(int j = m.getPreferences().size() - 1; j > q; j--)
                    {
                        Person womanToDelete = women.get(m.getPreferences().get(j));
                        int manToDelete = womanToDelete.getPreferences().indexOf(firstMan);
                        //delete m from q's preference list
                        womanToDelete.getPreferences().remove(manToDelete);
                        //delete q from m's preference list
                        m.getPreferences().remove(j);
                    }
                }
            }
        }
        return pairings;
    }

    public static void print(Map<Person, Person> pairings)
    {
        for(Map.Entry<Person, Person> pair: pairings.entrySet())
        {
            System.out.println(pair.getKey().getName() + " and " + pair.getValue().getName() + " are engaged.");
        }
    }
}