-
Notifications
You must be signed in to change notification settings - Fork 0
/
Matcher.java
152 lines (130 loc) · 4.12 KB
/
Matcher.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/* Matcher implements the Stable Marriage algorithm
* the objective is to create stable matches... match
* all people with their most preferred mate (who will have them)
* Some assumptions for this problem setup -
*
* a potential partnership requires both parties to desire a relation
* simplified by having each participant rank all potential mates
* a stable match is a match between the 'best' preferred potential mate
*
* 2/11/2018
* Derrick Stone
*/
public class Matcher {
/** The matcher class creates two arrays, one for the proposing
* party and one for the proposee party
*/
Person[] proposers;
Person[] proposees;
/** the number of pairs */
int numberOfMatches;
/** control output */
boolean verbose = false;
/** constructor - initialize arrays of people
* and generate their match preferences
* @param num
*/
public Matcher(int num, boolean showOutput) {
if (num <=0) {
throw new IllegalArgumentException("Number of pairs must be a positive integer.");
}
proposers = new Person[num];
proposees = new Person[num];
numberOfMatches=num;
verbose=showOutput;
// generate some people for this match!
for (int i = 0; i< numberOfMatches;i++) {
proposers[i] = new Person("pat-"+i,numberOfMatches);
proposees[i] = new Person("alex-"+i,numberOfMatches);
}
}
/** run the match routine */
public static void main(String[] args) {
Matcher m = new Matcher(300,false);
if (m.verbose) {
System.out.println(m);
}
// now let's hold some matching rounds
int count = 0;
boolean unmatchedCouplesExist = true;
while ( unmatchedCouplesExist ) {
m.makeProposals(); // good luck!
m.considerProposals(); // accept or reject proposals
unmatchedCouplesExist = false;
for ( Person p : m.proposers) {
if (p.hasMatch()==false) {
unmatchedCouplesExist=true;
break;
}
}
count++; // keep track of how much work is done
}
/** report on the outcome */
System.out.println("Success! All couples matched!");
if (m.verbose) {
for ( int l=0;l<m.proposers.length;l++) {
System.out.println(m.proposers[l].getName()+" matches with " + m.proposees[m.proposers[l].getMatch()].getName());
}
String word = "loop";
if ( count > 1 ) {
word = "loops";
}
System.out.println("Suitors confirmed matched in "+ count +" "+ word+".");
}
}
/** return true if proposals are made */
public void makeProposals() {
for (int i = 0; i<proposers.length;i++) {
if ( proposers[i].hasMatch() == false ) {
int targetIndex = proposers[i].setNextProposalTarget();
int target = proposers[i].spousalPicks[targetIndex];
if (verbose) {
System.out.println(proposers[i].getName() + " proposes to "+ proposees[target].getName() );
}
proposees[ target ].addProposal(i);
}
}
}
/** check the list of proposals- if any :( -and accept the most preferred
according to the preference order */
public void considerProposals() {
int bestPick = 0;
for (int i=0;i<proposees.length;i++) {
for ( int p=0;p<proposees[i].spousalPicks.length;p++) { //start search with most preferred
bestPick = proposees[i].spousalPicks[p];
if (proposees[i].proposals.contains(bestPick)) {
//this represents the highest match
proposers[ bestPick ].proposalAccepted();
if (verbose) {
System.out.println(proposees[i].getName() +" accepts " + proposers[bestPick].getName());
}
break; // leave this loop
}
}
// decline any other proposals
for ( Integer q : proposees[i].proposals) {
if ( q != bestPick) {
proposers[q].proposalDeclined();
if (verbose) {
System.out.println(proposees[i].getName() + " declines "+ proposers[q].getName());
}
}
}
// clear out the proposals
proposees[i].proposals.clear();
// save the accepted proposal
proposees[i].addProposal(bestPick);
}
}
public String toString() {
String returnString = "Proposers\n";
for (Person p : proposers) {
returnString+=p.toString();
}
returnString+="\nProposees\n";
for (Person p : proposees) {
returnString+=p.toString();
}
return returnString;
}
}