Stable mariage API

benaich · benaich · commit 4d8ace3fbe0d · 2015-02-08T16:23:26.000Z
diff --git a/StableMarriage/Person.java b/StableMarriage/Person.java
@@ -0,0 +1,73 @@
+package StableMarriage;
+
+import java.util.*;
+
+public class Person {
+    
+    private String name;
+    private Person partner;
+    private List<Person> candidates;
+    private int candidateIndex;
+
+    public List<Person> getCandidates() {
+        return candidates;
+    }
+
+    public int getCandidateIndex() {
+        return candidateIndex;
+    }
+
+    Person(String name) {
+        this.name = name;
+        this.partner = null;
+        this.candidates = new ArrayList<>(); 
+        this.candidateIndex = 0;
+    }
+
+    public void setCandidates(Person... candidates) {
+        this.candidates.addAll(Arrays.asList(candidates));
+    }
+
+    public void setCandidateIndex(int candidateIndex) {
+        this.candidateIndex = candidateIndex;
+    }
+    
+    public String getName(){
+        return this.name;
+    }
+    public void setName(String name) {
+        this.name = name;
+    }
+    
+    public Person getPartner(){
+        return this.partner;
+    }
+    public void setPartner(Person partner) {
+        this.partner = partner;
+    }
+    
+    /* get the prefered person from the available list */
+    public Person getNext(){
+        return (this.candidateIndex >= this.candidates.size()) ? null : this.candidates.get(this.candidateIndex++) ;
+    }
+    
+    /* get the rank of a person */
+    public int rank(Person p){
+        for (int i = 0; i < this.candidates.size(); i++) {
+            if(p == this.candidates.get(i)) return i;
+        }
+        return -1;
+    }
+    
+    /* compare the partner and the person */
+    public boolean prefers(Person p){
+        return (this.rank(p) < this.rank(this.partner));
+    }
+    
+    public void engageTo(Person p){
+        if(p.partner != null) p.partner.partner = null;
+        p.partner = this;
+        if(this.partner != null) this.partner.partner = null;
+        this.partner = p;
+    }
+}
diff --git a/StableMarriage/StableMarriage.java b/StableMarriage/StableMarriage.java
@@ -0,0 +1,64 @@
+package StableMarriage;
+import java.util.*;
+public class StableMarriage {
+
+    public static void main(String[] args) {
+        
+        Person man1 = new Person("man1");
+        Person man2  = new Person("man2");
+        Person man3  = new Person("man3");
+
+        Person woman1 = new Person("woman1");
+        Person woman2  = new Person("woman2");
+        Person woman3  = new Person("woman3");
+    
+        man1.setCandidates(woman2, woman3, woman1);
+        man2.setCandidates(woman3, woman2, woman1);
+        man3.setCandidates(woman2, woman1, woman3);
+        
+        woman1.setCandidates(man2, man1, man3);
+        woman2.setCandidates(man3, man1, man2);
+        woman3.setCandidates(man2, man1, man3);        
+        
+        List<Person> women = new ArrayList<>();
+        women.addAll(Arrays.asList(woman1, woman2, woman3));
+        
+        engageEveryone(women);
+        displayMarriage(women);
+    }
+    
+    /* check if this mariage is stable */
+    public static boolean isStable(List<Person> women, List<Person> men) {
+        for (Person women1 : women) {
+            for (Person men1 : men) {
+                if (women1.prefers(men1) && men1.prefers(women1)) {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+    
+    /* engage all women acording to their preferences */
+    public static void engageEveryone(List<Person> women) {
+        boolean done;
+        do {
+            done = true;
+            for (Person w : women) {
+                if (w.getPartner() == null) {
+                    done = false;
+                    Person man = w.getNext();
+                    if (man.getPartner() == null || man.prefers(w))
+                        w.engageTo(man);
+                }
+            }
+        } while (!done);
+    }
+    
+    /* print the couples name */
+    private static void displayMarriage(List<Person> women) {
+        for (Person woman : women) {
+            System.out.println("( " + woman.getName() + ", " + woman.getPartner().getName() + " )");
+        }
+    }
+}
