1.1 --- a/lf_update_suggestion_order.c	Sun Mar 17 17:13:45 2013 +0100
     1.2 +++ b/lf_update_suggestion_order.c	Sun Mar 17 20:03:01 2013 +0100
     1.3 @@ -25,18 +25,21 @@
     1.4    free(ptr);
     1.5  }
     1.6  
     1.7 +// column numbers when querying "individual_suggestion_ranking" view in function main():
     1.8  #define COL_MEMBER_ID     0
     1.9  #define COL_WEIGHT        1
    1.10  #define COL_PREFERENCE    2
    1.11  #define COL_SUGGESTION_ID 3
    1.12  
    1.13 +// data structure for a candidate (in this case a suggestion) to the proportional runoff system:
    1.14  struct candidate {
    1.15 -  char *key;
    1.16 -  double score_per_step;
    1.17 -  double score;
    1.18 -  int seat;
    1.19 +  char *key;              // identifier of the candidate, which is the "suggestion_id" string
    1.20 +  double score_per_step;  // added score per step
    1.21 +  double score;           // current score of candidate; a score of 1.0 is needed to survive a round
    1.22 +  int seat;               // equals 0 for unseated candidates, or contains rank number
    1.23  };
    1.24  
    1.25 +// compare two integers stored as strings (invocation like strcmp):
    1.26  static int compare_id(char *id1, char *id2) {
    1.27    int ldiff;
    1.28    ldiff = strlen(id1) - strlen(id2);
    1.29 @@ -44,13 +47,16 @@
    1.30    else return strcmp(id1, id2);
    1.31  }
    1.32  
    1.33 +// compare two candidates by their key (invocation like strcmp):
    1.34  static int compare_candidate(struct candidate *c1, struct candidate *c2) {
    1.35    return compare_id(c1->key, c2->key);
    1.36  }
    1.37  
    1.38 +// candidates are stored as global variables due to the constrained twalk() interface:
    1.39  static int candidate_count;
    1.40  static struct candidate *candidates;
    1.41  
    1.42 +// function to be passed to twalk() to store candidates ordered in candidates[] array:
    1.43  static void register_candidate(char **candidate_key, VISIT visit, int level) {
    1.44    if (visit == postorder || visit == leaf) {
    1.45      struct candidate *candidate;
    1.46 @@ -60,6 +66,7 @@
    1.47    }
    1.48  }
    1.49  
    1.50 +// performs a binary search in candidates[] array to lookup a candidate by its key (which is the suggestion_id):
    1.51  static struct candidate *candidate_by_key(char *candidate_key) {
    1.52    struct candidate *candidate;
    1.53    struct candidate compare;
    1.54 @@ -72,29 +79,36 @@
    1.55    return candidate;
    1.56  }
    1.57  
    1.58 +// section of a ballot with equally ranked candidates:
    1.59  struct ballot_section {
    1.60    int count;
    1.61    struct candidate **candidates;
    1.62  };
    1.63  
    1.64 +// ballot of the proportional runoff system:
    1.65  struct ballot {
    1.66 -  int weight;
    1.67 -  struct ballot_section sections[4];
    1.68 +  int weight;                         // if weight is greater than 1, then the ballot is counted multiple times
    1.69 +  struct ballot_section sections[4];  // 4 sections, most preferred candidates first
    1.70  };
    1.71  
    1.72 +// determine candidate, which is assigned the next seat (starting with the worst rank):
    1.73  static struct candidate *loser(int round_number, struct ballot *ballots, int ballot_count) {
    1.74 -  int i, j, k;
    1.75 -  int remaining;
    1.76 +  int i, j, k;    // index variables for loops
    1.77 +  int remaining;  // remaining candidates to be seated
    1.78 +  // reset scores of all candidates:
    1.79    for (i=0; i<candidate_count; i++) {
    1.80      candidates[i].score = 0.0;
    1.81    }
    1.82 +  // calculate remaining candidates to be seated:
    1.83    remaining = candidate_count - round_number;
    1.84 -  while (1) {
    1.85 -    double scale;
    1.86 -    if (remaining <= 1) break;
    1.87 +  // repeat following loop, if there is more than one remaining candidate:
    1.88 +  if (remaining > 1) while (1) {
    1.89 +    double scale;  // factor to be later multiplied with score_per_step:
    1.90 +    // reset score_per_step for all candidates:
    1.91      for (i=0; i<candidate_count; i++) {
    1.92        candidates[i].score_per_step = 0.0;
    1.93      }
    1.94 +    // calculate score_per_step for all candidates:
    1.95      for (i=0; i<ballot_count; i++) {
    1.96        for (j=0; j<4; j++) {
    1.97          int matches = 0;
    1.98 @@ -117,7 +131,8 @@
    1.99          }
   1.100        }
   1.101      }
   1.102 -    scale = (double)0.0;
   1.103 +    // calculate scale factor:
   1.104 +    scale = (double)0.0;  // 0.0 is used to indicate that there is no value yet
   1.105      for (i=0; i<candidate_count; i++) {
   1.106        double max_scale;
   1.107        if (candidates[i].score_per_step > 0.0) {
   1.108 @@ -127,28 +142,34 @@
   1.109          }
   1.110        }
   1.111      }
   1.112 +    // add scale*score_per_step to each candidates score:
   1.113      for (i=0; i<candidate_count; i++) {
   1.114        if (candidates[i].score_per_step > 0.0) {
   1.115          double max_scale;
   1.116          max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step;
   1.117          if (max_scale == scale) {
   1.118 +          // score of 1.0 should be reached, so we set score directly to avoid floating point errors:
   1.119            candidates[i].score = 1.0;
   1.120            remaining--;
   1.121          } else {
   1.122            candidates[i].score += scale * candidates[i].score_per_step;
   1.123            if (candidates[i].score >= 1.0) remaining--;
   1.124          }
   1.125 +        // when there is only one candidate remaining, then break loop:
   1.126          if (remaining <= 1) break;
   1.127        }
   1.128      }
   1.129    }
   1.130 -  for (i=candidate_count-1; i>=0; i--) {
   1.131 +  // return remaining candidate:
   1.132 +  for (i=0; i<candidate_count; i++) {
   1.133      if (candidates[i].score < 1.0 && !candidates[i].seat) return candidates+i;
   1.134    }
   1.135 +  // if there is no remaining candidate, then something went wrong:
   1.136    fprintf(stderr, "No remaining candidate (should not happen).");
   1.137    abort();
   1.138  }
   1.139  
   1.140 +// write results to database:
   1.141  static int write_ranks(PGconn *db, char *escaped_initiative_id, int final) {
   1.142    PGresult *res;
   1.143    char *cmd;
   1.144 @@ -226,19 +247,24 @@
   1.145    }
   1.146  }
   1.147  
   1.148 +// calculate ordering of suggestions for an initiative and call write_ranks() to write it to database:
   1.149  static int process_initiative(PGconn *db, PGresult *res, char *escaped_initiative_id, int final) {
   1.150 -  int err;
   1.151 -  int ballot_count = 1;
   1.152 -  struct ballot *ballots;
   1.153 -  int i;
   1.154 +  int err;                 // variable to store an error condition (0 = success)
   1.155 +  int ballot_count = 1;    // number of ballots, must be initiatized to 1, due to loop below
   1.156 +  struct ballot *ballots;  // data structure containing the ballots
   1.157 +  int i;                   // index variable for loops
   1.158 +  // create candidates[] and ballots[] arrays:
   1.159    {
   1.160 -    void *candidate_tree = NULL;
   1.161 -    int tuple_count;
   1.162 -    char *old_member_id = NULL;
   1.163 -    struct ballot *ballot;
   1.164 -    int candidates_in_sections[4] = {0, };
   1.165 +    void *candidate_tree = NULL;  // temporary structure to create a sorted unique list of all candidate keys
   1.166 +    int tuple_count;              // number of tuples returned from the database
   1.167 +    char *old_member_id = NULL;   // old member_id to be able to detect a new ballot in loops
   1.168 +    struct ballot *ballot;        // pointer to current ballot
   1.169 +    int candidates_in_sections[4] = {0, };  // number of candidates that have been placed in each section
   1.170 +    // reset candidate count:
   1.171      candidate_count = 0;
   1.172 +    // determine number of tuples:
   1.173      tuple_count = PQntuples(res);
   1.174 +    // trivial case, when there are no tuples:
   1.175      if (!tuple_count) {
   1.176        if (final) {
   1.177          printf("No suggestions found, but marking initiative as finally calculated.\n");
   1.178 @@ -250,6 +276,7 @@
   1.179          return 0;
   1.180        }
   1.181      }
   1.182 +    // calculate ballot_count and generate set of candidate keys (suggestion_id is used as key):
   1.183      for (i=0; i<tuple_count; i++) {
   1.184        char *member_id, *suggestion_id;
   1.185        member_id = PQgetvalue(res, i, COL_MEMBER_ID);
   1.186 @@ -264,21 +291,28 @@
   1.187        if (old_member_id && strcmp(old_member_id, member_id)) ballot_count++;
   1.188        old_member_id = member_id;
   1.189      }
   1.190 +    // print candidate count:
   1.191      printf("Candidate count: %i\n", candidate_count);
   1.192 +    // allocate memory for candidates[] array:
   1.193      candidates = malloc(candidate_count * sizeof(struct candidate));
   1.194      if (!candidates) {
   1.195        fprintf(stderr, "Insufficient memory while creating candidate list.\n");
   1.196        abort();
   1.197      }
   1.198 -    candidate_count = 0;
   1.199 +    // transform tree of candidate keys into sorted array:
   1.200 +    candidate_count = 0;  // needed by register_candidate()
   1.201      twalk(candidate_tree, (void *)register_candidate);
   1.202 +    // free memory of tree structure (tdestroy() is not available on all platforms):
   1.203      while (candidate_tree) tdelete(*(void **)candidate_tree, &candidate_tree, (void *)compare_id);
   1.204 +    // print ballot count:
   1.205      printf("Ballot count: %i\n", ballot_count);
   1.206 +    // allocate memory for ballots[] array:
   1.207      ballots = calloc(ballot_count, sizeof(struct ballot));
   1.208      if (!ballots) {
   1.209        fprintf(stderr, "Insufficient memory while creating ballot list.\n");
   1.210        abort();
   1.211      }
   1.212 +    // set ballot weights, determine ballot section sizes, and verify preference values:
   1.213      ballot = ballots;
   1.214      old_member_id = NULL;
   1.215      for (i=0; i<tuple_count; i++) {
   1.216 @@ -305,6 +339,7 @@
   1.217        ballot->sections[preference].count++;
   1.218        old_member_id = member_id;
   1.219      }
   1.220 +    // allocate memory for ballot sections:
   1.221      for (i=0; i<ballot_count; i++) {
   1.222        int j;
   1.223        for (j=0; j<4; j++) {
   1.224 @@ -317,6 +352,7 @@
   1.225          }
   1.226        }
   1.227      }
   1.228 +    // fill ballot sections with candidate references:
   1.229      old_member_id = NULL;
   1.230      ballot = ballots;
   1.231      for (i=0; i<tuple_count; i++) {
   1.232 @@ -338,12 +374,14 @@
   1.233      }
   1.234    }
   1.235  
   1.236 +  // calculate ranks based on constructed data structures:
   1.237    for (i=0; i<candidate_count; i++) {
   1.238      struct candidate *candidate = loser(i, ballots, ballot_count);
   1.239      candidate->seat = candidate_count - i;
   1.240      printf("Assigning rank #%i to suggestion #%s.\n", candidate_count - i, candidate->key);
   1.241    }
   1.242  
   1.243 +  // free ballots[] array:
   1.244    for (i=0; i<ballot_count; i++) {
   1.245      int j;
   1.246      for (j=0; j<4; j++) {
   1.247 @@ -354,6 +392,7 @@
   1.248    }
   1.249    free(ballots);
   1.250  
   1.251 +  // write results to database:
   1.252    if (final) {
   1.253      printf("Writing final ranks to database.\n");
   1.254    } else {
   1.255 @@ -362,8 +401,10 @@
   1.256    err = write_ranks(db, escaped_initiative_id, final);
   1.257    printf("Done.\n");
   1.258  
   1.259 +  // free candidates[] array:
   1.260    free(candidates);
   1.261  
   1.262 +  // return error code of write_ranks() call
   1.263    return err;
   1.264  }
   1.265