/*
 * stv:  run a stv vote.
 */
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <unistd.h>
#include <ctype.h>
#include <dbm.h>

/*
 * each candidate
 */
struct vt {
    char *who;		/* the candidate */
    int votes;		/* how many votes they got this round */
    int eliminated;	/* have they been eliminated from the race */
} *candidates;

int nr_candidates = 0;

#define RANKINGS 10	/* 10 candidates max */

/*
 * each voter
 */
struct vote {
    char *who;			/* voters From: address */
    int choice[RANKINGS];	/* their preferences */
} *votes;

int nr_votes = 0;

char bfr[2000];
char key[1000];

/*
 * more_candidates() -- adds another candidate to the list
 */
more_candidates(char *who)
{
    fflush(stdout);
    candidates = realloc(candidates, (1+nr_candidates)*sizeof candidates[0]);
    candidates[nr_candidates].who = strdup(who);
    candidates[nr_candidates].votes = 0;
    candidates[nr_candidates].eliminated = 0;
    nr_candidates++;
}

/*
 * do a round of voting. 
 */
pick_votes(int round)
{
    int i, j, cand, total, least, deleted;

    printf("%*svoting, round %d", round, "", round);
    fflush(stdout);

    /* initialize votes */
    for (i=0; i<nr_candidates; i++)
	candidates[i].votes = 0;

    /* vote for everyone */
    for (total=i=0; i<nr_votes; i++) {
	cand = votes[i].choice[0];
	if (cand >= 0 && cand < RANKINGS) {
	    candidates[cand].votes++;
	    total++;
	}
    }
    printf("...");
    fflush(stdout);

    if (total == 0) {
	printf("ran out of ballots without a winner ?\n");
	return 0;
    }

    /* check if somebody won */
    for (i=0; i<nr_candidates; i++)
	if ((candidates[i].votes+candidates[i].votes) > total) {
	    printf("[%s] wins with %d (of %d) votes\n",
		    candidates[i].who, candidates[i].votes, nr_votes);
	    return 1;
	}

    /* delete worst candidate, percolate choices */

    least = total;
    for (i=0; i<nr_candidates; i++)
	if (candidates[i].eliminated == 0 && candidates[i].votes < least)
	    least = candidates[i].votes;

    /* pick a random starting point and direction, then walk the
     * candidate list looking for someone who's got the least #
     * of votes, and dropping the first one found.
     */
    cand = -1;
    i = j = random()%nr_candidates;

    if (random()%1) {
	/* ascending search */
	do {
	    if (candidates[i].eliminated == 0 && candidates[i].votes == least) {
		cand = i;
		break;
	    }
	    i = (1+i) % nr_candidates;
	} while (i != j);
    }
    else {
	/* descending */
	do {
	    if (candidates[i].eliminated == 0 && candidates[i].votes == least) {
		cand = i;
		break;
	    }
	    i = ((i==0) ? nr_candidates : i)-1;
	} while (i != j);
    }

    if (cand < 0) {
	/* oops */
	printf("unable to find someone to delete?\n");
	return 0;
    }
    printf("dropping candidate [%s] (%d of %d votes)\n",
	    candidates[cand].who, least, nr_votes);
    candidates[cand].eliminated++;

    for (i=0; i<nr_votes; i++) {
	do {
	    deleted = 0;
	    cand = votes[i].choice[0];
	    if (cand >= 0 && cand < RANKINGS && candidates[cand].eliminated) {
		deleted = 1;
		for (j=1; j<RANKINGS; j++)
		    votes[i].choice[j-1] = votes[i].choice[j];
	    }
	} while (deleted);
    }
    return pick_votes(1+round);
}

main(int argc, char **argv)
{
    datum vote;
    datum ballot;
    int i, j;
    char *p;

    if (argc < 2)
	exit(0);

    srand(time() & 0x7fe);
    candidates = malloc(1);
    votes = malloc(1);

    printf("counting ballots");
    fflush(stdout);

    dbminit(argv[1]);
    for (vote = firstkey(); vote.dptr && (vote.dsize > 0); vote = nextkey(vote)) {
	int pick;

	ballot = fetch(vote);
	if (ballot.dsize == 0)
	    continue;
	votes = realloc(votes, (1+nr_votes) * sizeof *votes);
	strncpy(bfr, vote.dptr, vote.dsize);
	bfr[vote.dsize] = 0;
	votes[nr_votes].who = strdup(bfr);
	for (pick=0; pick<RANKINGS; pick++)
	    votes[nr_votes].choice[pick] = -1;

	strncpy(bfr, ballot.dptr, ballot.dsize);
	bfr[ballot.dsize] = 0;
	for (pick=0, p=strtok(bfr, "|"); p; p=strtok((char*)0, "|")) {
	    for (j=0; j<nr_candidates; j++)
		if (strcmp(p, candidates[j].who) == 0) {
		    votes[nr_votes].choice[pick] = j;
		    goto contin;
		}
	    more_candidates(p);
	    votes[nr_votes].choice[pick] = nr_candidates-1;
    contin: pick++;
	}
	nr_votes++;
	if (nr_votes % 20 == 0) {
	    putchar('.');
	    fflush(stdout);
	}
    }
    putchar('\n');
    printf("%d ballot%s, %d candidate%s\n",
	    nr_votes, (nr_votes!=1)?"s":"",
	    nr_candidates, (nr_candidates!=1)?"s":"");

    pick_votes(0);
}