#include <iostream>
#include <vector>

#include <stdlib.h>

// Excuse the hard-coded ballot indices; I'm doing this quick and
// dirty and don't feel like pulling in std::next_permutation, etc.

// "I have only made this hardcoded because I didn't have the time
// to make it flexible."

// Strict preference ballots for two candidates.
#define v_A_B 0
#define v_B_A 1

// Ballots when cloning A.
#define v_A1_A2_B 0
#define v_A2_A1_B 1
#define v_B_A1_A2 2
#define v_B_A2_A1 3

// Ballots when cloning B.
#define v_A_B1_B2 0
#define v_A_B2_B1 1
#define v_B1_B2_A 2
#define v_B2_B1_A 3

#define a_score first
#define b_score second

const int num_voters = 10;
const int num_elections = 2000; // Number of distinct elections to test
const int num_attempts = 1000; // Number of times to try to find a clone failure

const int VOTER_DIST_IMPARTIAL_CULTURE = 0; // Impartial culture
const int VOTER_DIST_SIMPLEX_MODEL = 1; // Simplex or Dirichlet model

// All Borda count scores assume that the lowest-ranked candidate gets one point.

std::pair<int, int> borda_scores_two_cddt(const std::vector<int> & election) {
	std::pair<int, int> score;

	score.a_score = 2 * election[v_A_B] + election[v_B_A];
	score.b_score = 2 * election[v_B_A] + election[v_A_B];

	return score;
}

std::pair<int, int> borda_scores_after_cloning_a(
	const std::vector<int> & a_cloned_election) {

	std::pair<int, int> score;

	int A1_score =	3 * a_cloned_election[v_A1_A2_B] +
					2 * a_cloned_election[v_A2_A1_B] +
					2 * a_cloned_election[v_B_A1_A2] +
					1 * a_cloned_election[v_B_A2_A1];

	int A2_score =	3 * a_cloned_election[v_A2_A1_B] +
					2 * a_cloned_election[v_A1_A2_B] +
					2 * a_cloned_election[v_B_A2_A1] +
					1 * a_cloned_election[v_B_A1_A2];

	int B_score =	3 * a_cloned_election[v_B_A2_A1] +
					3 * a_cloned_election[v_B_A1_A2] +
					1 * a_cloned_election[v_A1_A2_B] +
					1 * a_cloned_election[v_A2_A1_B];

	// A's score is the maximum of the clones' score since we're trying
	// to get A to win by cloning A. This makes it easier to just check
	// A's score without having to check *which* clone... and I can still
	// use std::pair... :-)
	score.a_score = std::max(A1_score, A2_score);
	score.b_score = B_score;

	return score;
}

// cut and paste...

std::pair<int, int> borda_scores_after_cloning_b(
	const std::vector<int> & b_cloned_election) {

	std::pair<int, int> score;

	int A_score =	3 * b_cloned_election[v_A_B2_B1] +
					3 * b_cloned_election[v_A_B1_B2] +
					1 * b_cloned_election[v_B1_B2_A] +
					1 * b_cloned_election[v_B2_B1_A];


	int B1_score =	3 * b_cloned_election[v_B1_B2_A] +
					2 * b_cloned_election[v_B2_B1_A] +
					2 * b_cloned_election[v_A_B1_B2] +
					1 * b_cloned_election[v_A_B2_B1];

	int B2_score =	3 * b_cloned_election[v_B2_B1_A] +
					2 * b_cloned_election[v_B1_B2_A] +
					2 * b_cloned_election[v_A_B2_B1] +
					1 * b_cloned_election[v_A_B1_B2];

	score.a_score = A_score;
	score.b_score = std::max(B1_score, B2_score);

	return score;
}

int random_upto(int maximum) {
	return random() % (maximum+1);
}

int get_num_clone_failures(int model_type) {

	std::vector<int> before_cloning(2, 0), after_cloning(4, 0);

	int num_clone_failures = 0;
	int i, j;

	for (i = 0; i < num_elections; ++i) {
		std::fill(before_cloning.begin(), before_cloning.end(), 0);

		switch (model_type) {
			case VOTER_DIST_IMPARTIAL_CULTURE:
				// Add one and one voter at random to either A>B or B>A
				// (impartial culture).
				for (j = 0; j < num_voters; ++j) {
					++before_cloning[random()%2];
				}
				break;
			case VOTER_DIST_SIMPLEX_MODEL:
				// Choose a random point on the line from x=0 to x=1 subject
				// to the constraint that y = 1-x; then multiply by the
				// number of voters and round off.
				before_cloning[v_A_B] = random_upto(num_voters);
				before_cloning[v_B_A] = num_voters - before_cloning[v_A_B];
				break;
			default:
				throw std::runtime_error("Unknown model specified!");
		}

		std::pair<int, int> before_cloning_score =
			borda_scores_two_cddt(before_cloning);

		// Try to force a clone failure.
		bool clone_failure = false;

		for (j = 0; j < num_attempts && !clone_failure; ++j) {
			std::fill(after_cloning.begin(), after_cloning.end(), 0);

			// Decide at random whether to clone A or B.
			bool clone_a = random() % 2;

			std::pair<int, int> after_cloning_score;

			if (clone_a) {
				// The actual distribution doesn't matter here.
				after_cloning[v_A1_A2_B] = random_upto(before_cloning[v_A_B]);
				after_cloning[v_A2_A1_B] = before_cloning[v_A_B] -
					after_cloning[v_A1_A2_B];

				after_cloning[v_B_A1_A2] = random_upto(before_cloning[v_B_A]);
				after_cloning[v_B_A2_A1] = before_cloning[v_B_A] -
					after_cloning[v_B_A1_A2];

				after_cloning_score = borda_scores_after_cloning_a(
					after_cloning);
			} else {
				after_cloning[v_A_B1_B2] = random_upto(before_cloning[v_A_B]);
				after_cloning[v_A_B2_B1] = before_cloning[v_A_B] -
					after_cloning[v_A_B1_B2];

				after_cloning[v_B1_B2_A] = random_upto(before_cloning[v_B_A]);
				after_cloning[v_B2_B1_A] = before_cloning[v_B_A] -
					after_cloning[v_B1_B2_A];

				after_cloning_score = borda_scores_after_cloning_b(
					after_cloning);
			}

			// A used to win with certainty, but not after cloning.
			bool A_lost =
				(before_cloning_score.a_score > before_cloning_score.b_score)&&
				(after_cloning_score.a_score <= after_cloning_score.b_score);

			// B used to win with certainty, but not after cloning.
			bool B_lost =
				(before_cloning_score.a_score < before_cloning_score.b_score)&&
				(after_cloning_score.a_score >= after_cloning_score.b_score);

			// If either happened, we have a clone failure.
			clone_failure |= A_lost || B_lost;
		}

		if (clone_failure) {
			++num_clone_failures;
		}
	}

	return num_clone_failures;
}

int main() {
	srandom(time(NULL)); // Seed the RNG

	int clone_failures_IC = get_num_clone_failures(
			VOTER_DIST_IMPARTIAL_CULTURE),
		clone_failures_simplex = get_num_clone_failures(
			VOTER_DIST_SIMPLEX_MODEL);

	std::cout << "Impartial culture: " <<
		clone_failures_IC << "/" << num_elections << " failures, rate: " <<
		clone_failures_IC/(double)num_elections << std::endl;
	std::cout << "Simplex model (Dirichlet): " <<
		clone_failures_simplex << "/" << num_elections << " failures, rate: " <<
		clone_failures_simplex/(double)num_elections << std::endl;
}