package stablemarriage;

/**
 * 
 * An implementation of the stable marriage algorithm from
 * Chapter 1-2 in "Algorithm Design" by Kleinberg and Tardos.
 *
 * @author Stefan Nilsson
 * @version 2008.10.23
 * 
 * Modified by Ahmed Abdelmeged on 2011.9.11
 * 
 */
public class StableMarriage
{
	/**
	 * Returns a stable marriage in the form an int array v,
	 * where v[i] is the man married to woman i.
	 */
	public static Marriages GaleShapley(Preference pref) {
		int n = pref.getN();
		Marriages marriages = new Marriages(n);
		// next[i] is the next woman to whom i has not yet proposed.
		int[] next = new int[n];
		int numIterations = 0;
		while (marriages.freeMan().isSome()){
			numIterations++;
			int m = marriages.freeMan().get();
			int w = pref.getManPreference(m, next[m]);
			next[m]++;
			if (marriages.isWomanAvailable(w)){
				marriages.addMarriage(w, m);
			} else {
				int m1 = marriages.husband(w);
				if (pref.womanPrefers(w, m, m1)) {
					marriages.addMarriage(w, m);
				}
			}	    
		}
		System.out.println("n: "+ n);
		System.out.println("Number of Iterations: "+ numIterations);
		double quality = numIterations/(double) (n * n);
		System.out.println("Quality (number of iterations / n^2): "+ quality);
		return marriages;	
	}
}