[MN-dev] [mndiff]: r176 - trunk/ffvotetov/ffvotetov.c

[michael]

Author: michael
Date: Fri Dec 18 19:50:50 2009
New Revision: 176

Log:
Add instant runoff voting support.

Modified:
   trunk/ffvotetov/ffvotetov.c

Modified: trunk/ffvotetov/ffvotetov.c
==============================================================================
--- trunk/ffvotetov/ffvotetov.c	Thu Dec 17 04:13:42 2009	(r175)
+++ trunk/ffvotetov/ffvotetov.c	Fri Dec 18 19:50:50 2009	(r176)
@@ -37,6 +37,9 @@ int pair_ranking_matrix[CANDIDATES_MAX][
 
 int64_t cssd_beats[CANDIDATES_MAX][CANDIDATES_MAX];
 
+int (*irv)[CANDIDATES_MAX];
+int vote_count;
+
 int contains_loop(const int matrix[CANDIDATES_MAX][CANDIDATES_MAX]){
     int m[CANDIDATES_MAX][CANDIDATES_MAX];
     int s[CANDIDATES_MAX]={0};
@@ -202,8 +205,55 @@ void do_condercets(void){
     }
 }
 
+void print_irv(void){
+    int droped_canditates[CANDIDATES_MAX]={0};
+    int i, j;
+
+    printf("Instant runoff winners:\n");
+    for(;;){
+        int votes[CANDIDATES_MAX]={0};
+        int min= INT_MAX;
+        int non_min= 0;
+
+        for(i=0; i<vote_count; i++){
+            for(j=0; j<canditate_count && irv[i][j] && droped_canditates[irv[i][j]-1]; j++);
+            if(irv[i][j])
+                votes[ irv[i][j]-1 ]++;
+        }
+        for(i=0; i<canditate_count; i++){
+            fprintf(stderr, "%3d", votes[i]);
+            if(!droped_canditates[i]){
+                if(min != INT_MAX && votes[i] != min)
+                    non_min=1;
+                if(votes[i] <= min){
+                    min=votes[i];
+                }
+            }
+        }
+        fprintf(stderr, "\n");
+        if(!non_min)
+            break;
+        for(i=0; i<canditate_count; i++){
+            if(votes[i] == min)
+                droped_canditates[i]=1;
+        }
+    }
+    for(i=0; i<canditate_count; i++)
+        if(!droped_canditates[i])
+            printf("  %s\n",  canditates[i]);
+}
+
 void add_vote(int vote[CANDIDATES_MAX]){
     int j,k;
+    int irv_count=0;
+
+    irv= realloc(irv, sizeof(*irv)*(vote_count+1));
+    if(!irv){
+        fprintf(stderr, "out of memory\n");
+        exit(1);
+    }
+    for(j=0; j<CANDIDATES_MAX; j++)
+        irv[vote_count][j]=0;
 
     for(j=0; j<CANDIDATES_MAX; j++){
         if(vote[j]>0 && vote[j] <=10){
@@ -218,7 +268,10 @@ void add_vote(int vote[CANDIDATES_MAX]){
             if(score_j > score_k)
                 pair_matrix[k][j]++;
         }
+        if(vote[j]>0 && vote[j]<=CANDIDATES_MAX)
+            irv[vote_count][ vote[j] - 1 ]= j+1;
     }
+    vote_count++;
 
     for(j=0; j<CANDIDATES_MAX; j++)
         vote[j]=0;
@@ -257,6 +310,8 @@ int main(){
     for(cand_idx=0; cand_idx<canditate_count; cand_idx++)
         printf(" Borda:%3d %3d\"%s\"\n", sums[cand_idx] + subs[cand_idx]*canditate_count, sums[cand_idx] + 10*subs[cand_idx], canditates[cand_idx]);
 
+    print_irv();
+
     printf("Condorcet methods based on votes:\n");
     do_condercets();