import java.util.*;
import java.util.HashMap;
public class ShippingMatcher {
private HashMap
<String, ArrayList
<Integer
>> internationals
= new HashMap
<String, ArrayList
<Integer
>>(); private HashMap
<String, ArrayList
<Integer
>> domestics
= new HashMap
<String, ArrayList
<Integer
>>();
//class to order the results so we can pick from the countries with the most people in them first
private static class SizeComparator implements Comparator<String> {
private HashMap
<String, ArrayList
<Integer
>> data
; private SizeComparator
(HashMap
<String, ArrayList
<Integer
>> data
) { this.data = data;
}
@Override
//assumes no nulls
Integer size1
= data.
get(s1
).
size(); Integer size2
= data.
get(s2
).
size(); return -1 * size1.compareTo(size2);
}
}
public List<? extends List<Integer>> getMatches(ArrayList<ArrayList> inputData) {
readData(inputData);
ArrayList<ArrayList<Integer>> matches = new ArrayList<ArrayList<Integer>>();
countryLabel:
for (String country
: domestics.
keySet()) { ArrayList<Integer> ids = domestics.get(country);
while (ids.size() < 2) {
//no valid chains, try to grab an international shipper and put them in here
if (internationals.get(country) == null) {
//can't make a valid domestic chain
//so make the domestics ship international
internationals.get(country).addAll(ids);
continue countryLabel;
}
ids.add(internationals.get(country).get(0));
internationals.get(country).remove(0);
if (internationals.get(country).size() == 0) {
internationals.remove(country);
}
}
for (int i = 0; i < ids.size() - 1; i++) {
ArrayList<Integer> match = new ArrayList<Integer>();
match.add(ids.get(i));
match.add(ids.get(i + 1));
matches.add(match);
}
ArrayList<Integer> match = new ArrayList<Integer>();
match.add(ids.get(ids.size()-1));
match.add(ids.get(0));
matches.add(match);
}
PriorityQueue<String> targets = new PriorityQueue<String>(internationals.size(), new SizeComparator(internationals));
targets.addAll(internationals.keySet());
//making a chain of international shippers
int[] ids = new int[2];
//record the next match index so we can complete the chain at the end
int startMatchIdx = matches.size();
countries[0] = targets.poll();
countries[1] = targets.poll();
while (internationals.size() > 1) {
ids[0] = internationals.get(countries[0]).get(0);
ids[1] = internationals.get(countries[1]).get(0);
ArrayList<Integer> match = new ArrayList<Integer>();
match.add(ids[0]);
match.add(ids[1]);
matches.add(match);
for (int i = 0; i < 2; i++) {
internationals.get(countries[i]).remove(0);
if (internationals.get(countries[i]).isEmpty()) {
internationals.remove(countries[i]);
} else {
targets.add(countries[i]);
}
}
countries[0] = targets.poll();
countries[1] = targets.poll();
}
if (internationals.size() == 1) {
//complete the chain
if (startMatchIdx < matches.size()) {
ArrayList<Integer> startMatch = matches.get(startMatchIdx);
ArrayList<Integer> match = new ArrayList<Integer>();
match.add(internationals.get(countries[0]).get(0));
match.add(startMatch.get(0));
matches.add(match);
internationals.get(countries[0]).remove(0);
}
//a little fubared, try to make a chain of internationals ship domestic
startMatchIdx = matches.size();
while (internationals.get(countries[0]).size() > 2) {
ids[0] = internationals.get(countries[0]).get(0);
ids[1] = internationals.get(countries[0]).get(1);
ArrayList<Integer> match = new ArrayList<Integer>();
match.add(ids[0]);
match.add(ids[1]);
matches.add(match);
internationals.get(countries[0]).remove(0);
internationals.get(countries[0]).remove(1);
}
if (startMatchIdx < matches.size()) {
ArrayList<Integer> startMatch = matches.get(startMatchIdx);
ArrayList<Integer> match = new ArrayList<Integer>();
match.add(internationals.get(countries[0]).get(0));
match.add(startMatch.get(0));
matches.add(match);
internationals.get(countries[0]).remove(0);
}
//wow this is fucked, just insert the dude into a love triangle with the last match
if (internationals.get(countries[0]).size() == 1) {
ArrayList<Integer> lastMatch = matches.get(matches.size()-1);
matches.remove(matches.size()-1);
ArrayList<Integer> match1 = new ArrayList<Integer>();
match1.add(lastMatch.get(0));
match1.add(internationals.get(countries[0]).get(0));
matches.add(match1);
ArrayList<Integer> match2 = new ArrayList<Integer>();
match2.add(internationals.get(countries[0]).get(0));
match2.add(lastMatch.get(1));
matches.add(match2);
}
}
return matches;
}
private void readData(ArrayList<ArrayList> inputData) {
internationals.clear();
domestics.clear();
try {
if (id != null && country != null && internationalShip != null) {
if (internationalShip) {
if (!internationals.containsKey(country)) {
internationals.put(country, new ArrayList<Integer>());
}
internationals.get(country).add(id);
} else {
if (!domestics.containsKey(country)) {
domestics.put(country, new ArrayList<Integer>());
}
domestics.get(country).add(id);
}
} else {
}
System.
err.
println("Caught bad participant data, skipping. " + e.
getMessage()); }
}
}
}