liquid_feedback_core
diff lf_update_issue_order.c @ 394:326dc0c3b859
Calculation of "order_in_admission_state"
author | jbe |
---|---|
date | Fri Oct 11 12:57:03 2013 +0200 (2013-10-11) |
parents | |
children | d93428e4edad |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/lf_update_issue_order.c Fri Oct 11 12:57:03 2013 +0200 1.3 @@ -0,0 +1,507 @@ 1.4 +#include <stdlib.h> 1.5 +#include <stdio.h> 1.6 +#include <string.h> 1.7 +#include <libpq-fe.h> 1.8 +#include <search.h> 1.9 + 1.10 +static int logging = 0; 1.11 + 1.12 +static char *escapeLiteral(PGconn *conn, const char *str, size_t len) { 1.13 + // provides compatibility for PostgreSQL versions prior 9.0 1.14 + // in future: return PQescapeLiteral(conn, str, len); 1.15 + char *res; 1.16 + size_t res_len; 1.17 + res = malloc(2*len+3); 1.18 + if (!res) return NULL; 1.19 + res[0] = '\''; 1.20 + res_len = PQescapeStringConn(conn, res+1, str, len, NULL); 1.21 + res[res_len+1] = '\''; 1.22 + res[res_len+2] = 0; 1.23 + return res; 1.24 +} 1.25 + 1.26 +static void freemem(void *ptr) { 1.27 + // to be used for "escapeLiteral" function 1.28 + // provides compatibility for PostgreSQL versions prior 9.0 1.29 + // in future: PQfreemem(ptr); 1.30 + free(ptr); 1.31 +} 1.32 + 1.33 +// column numbers when querying "issue_supporter_in_admission_state" view in function main(): 1.34 +#define COL_MEMBER_ID 0 1.35 +#define COL_WEIGHT 1 1.36 +#define COL_ISSUE_ID 2 1.37 + 1.38 +// data structure for a candidate (in this case a suggestion) to the proportional runoff system: 1.39 +struct candidate { 1.40 + char *key; // identifier of the candidate, which is the "suggestion_id" string 1.41 + double score_per_step; // added score per step 1.42 + double score; // current score of candidate; a score of 1.0 is needed to survive a round 1.43 + int seat; // equals 0 for unseated candidates, or contains rank number 1.44 +}; 1.45 + 1.46 +// compare two integers stored as strings (invocation like strcmp): 1.47 +static int compare_id(char *id1, char *id2) { 1.48 + int ldiff; 1.49 + ldiff = strlen(id1) - strlen(id2); 1.50 + if (ldiff) return ldiff; 1.51 + else return strcmp(id1, id2); 1.52 +} 1.53 + 1.54 +// compare two candidates by their key (invocation like strcmp): 1.55 +static int compare_candidate(struct candidate *c1, struct candidate *c2) { 1.56 + return compare_id(c1->key, c2->key); 1.57 +} 1.58 + 1.59 +// candidates are stored as global variables due to the constrained twalk() interface: 1.60 +static int candidate_count; 1.61 +static struct candidate *candidates; 1.62 + 1.63 +// function to be passed to twalk() to store candidates ordered in candidates[] array: 1.64 +static void register_candidate(char **candidate_key, VISIT visit, int level) { 1.65 + if (visit == postorder || visit == leaf) { 1.66 + struct candidate *candidate; 1.67 + candidate = candidates + (candidate_count++); 1.68 + candidate->key = *candidate_key; 1.69 + candidate->seat = 0; 1.70 + if (logging) printf("Candidate #%i is suggestion #%s.\n", candidate_count, candidate->key); 1.71 + } 1.72 +} 1.73 + 1.74 +// performs a binary search in candidates[] array to lookup a candidate by its key (which is the suggestion_id): 1.75 +static struct candidate *candidate_by_key(char *candidate_key) { 1.76 + struct candidate *candidate; 1.77 + struct candidate compare; 1.78 + compare.key = candidate_key; 1.79 + candidate = bsearch(&compare, candidates, candidate_count, sizeof(struct candidate), (void *)compare_candidate); 1.80 + if (!candidate) { 1.81 + fprintf(stderr, "Candidate not found (should not happen).\n"); 1.82 + abort(); 1.83 + } 1.84 + return candidate; 1.85 +} 1.86 + 1.87 +// ballot of the proportional runoff system: 1.88 +struct ballot { 1.89 + int weight; // if weight is greater than 1, then the ballot is counted multiple times 1.90 + int count; 1.91 + struct candidate **candidates; 1.92 +}; 1.93 + 1.94 +// determine candidate, which is assigned the next seat (starting with the worst rank): 1.95 +static struct candidate *loser(int round_number, struct ballot *ballots, int ballot_count) { 1.96 + int i, j; // index variables for loops 1.97 + int remaining; // remaining candidates to be seated 1.98 + // reset scores of all candidates: 1.99 + for (i=0; i<candidate_count; i++) { 1.100 + candidates[i].score = 0.0; 1.101 + } 1.102 + // calculate remaining candidates to be seated: 1.103 + remaining = candidate_count - round_number; 1.104 + // repeat following loop, as long as there is more than one remaining candidate: 1.105 + while (remaining > 1) { 1.106 + if (logging) printf("There are %i remaining candidates.\n", remaining); 1.107 + double scale; // factor to be later multiplied with score_per_step: 1.108 + // reset score_per_step for all candidates: 1.109 + for (i=0; i<candidate_count; i++) { 1.110 + candidates[i].score_per_step = 0.0; 1.111 + } 1.112 + // calculate score_per_step for all candidates: 1.113 + for (i=0; i<ballot_count; i++) { 1.114 + int matches = 0; 1.115 + for (j=0; j<ballots[i].count; j++) { 1.116 + struct candidate *candidate; 1.117 + candidate = ballots[i].candidates[j]; 1.118 + if (candidate->score < 1.0 && !candidate->seat) matches++; 1.119 + } 1.120 + if (matches) { 1.121 + double score_inc; 1.122 + score_inc = (double)ballots[i].weight / (double)matches; 1.123 + for (j=0; j<ballots[i].count; j++) { 1.124 + struct candidate *candidate; 1.125 + candidate = ballots[i].candidates[j]; 1.126 + if (candidate->score < 1.0 && !candidate->seat) { 1.127 + candidate->score_per_step += score_inc; 1.128 + } 1.129 + } 1.130 + } 1.131 + } 1.132 + // calculate scale factor: 1.133 + scale = (double)0.0; // 0.0 is used to indicate that there is no value yet 1.134 + for (i=0; i<candidate_count; i++) { 1.135 + double max_scale; 1.136 + if (candidates[i].score_per_step > 0.0) { 1.137 + max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step; 1.138 + if (scale == 0.0 || max_scale <= scale) { 1.139 + scale = max_scale; 1.140 + } 1.141 + } 1.142 + } 1.143 + // add scale*score_per_step to each candidates score: 1.144 + for (i=0; i<candidate_count; i++) { 1.145 + int log_candidate = 0; 1.146 + if (logging && candidates[i].score < 1.0 && !candidates[i].seat) log_candidate = 1; 1.147 + if (log_candidate) printf("Score for suggestion #%s = %.4f+%.4f*%.4f", candidates[i].key, candidates[i].score, scale, candidates[i].score_per_step); 1.148 + if (candidates[i].score_per_step > 0.0) { 1.149 + double max_scale; 1.150 + max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step; 1.151 + if (max_scale == scale) { 1.152 + // score of 1.0 should be reached, so we set score directly to avoid floating point errors: 1.153 + candidates[i].score = 1.0; 1.154 + remaining--; 1.155 + } else { 1.156 + candidates[i].score += scale * candidates[i].score_per_step; 1.157 + if (candidates[i].score >= 1.0) remaining--; 1.158 + } 1.159 + } 1.160 + if (log_candidate) { 1.161 + if (candidates[i].score >= 1.0) printf("=1\n"); 1.162 + else printf("=%.4f\n", candidates[i].score); 1.163 + } 1.164 + // when there is only one candidate remaining, then break inner (and thus outer) loop: 1.165 + if (remaining <= 1) { 1.166 + break; 1.167 + } 1.168 + } 1.169 + } 1.170 + // return remaining candidate: 1.171 + for (i=0; i<candidate_count; i++) { 1.172 + if (candidates[i].score < 1.0 && !candidates[i].seat) return candidates+i; 1.173 + } 1.174 + // if there is no remaining candidate, then something went wrong: 1.175 + fprintf(stderr, "No remaining candidate (should not happen)."); 1.176 + abort(); 1.177 +} 1.178 + 1.179 +// write results to database: 1.180 +static int write_ranks(PGconn *db, char *escaped_area_id) { 1.181 + PGresult *res; 1.182 + char *cmd; 1.183 + int i; 1.184 + if (asprintf(&cmd, "BEGIN; UPDATE \"issue\" SET \"order_in_admission_state\" = NULL WHERE \"area_id\" = %s AND (\"state\" = 'admission' OR \"order_in_admission_state\" NOTNULL)", escaped_area_id) < 0) { 1.185 + fprintf(stderr, "Could not prepare query string in memory.\n"); 1.186 + abort(); 1.187 + } 1.188 + res = PQexec(db, cmd); 1.189 + free(cmd); 1.190 + if (!res) { 1.191 + fprintf(stderr, "Error in pqlib while sending SQL command to initiate issue update.\n"); 1.192 + return 1; 1.193 + } else if ( 1.194 + PQresultStatus(res) != PGRES_COMMAND_OK && 1.195 + PQresultStatus(res) != PGRES_TUPLES_OK 1.196 + ) { 1.197 + fprintf(stderr, "Error while executing SQL command to initiate issue update:\n%s", PQresultErrorMessage(res)); 1.198 + PQclear(res); 1.199 + return 1; 1.200 + } else { 1.201 + PQclear(res); 1.202 + } 1.203 + for (i=0; i<candidate_count; i++) { 1.204 + char *escaped_issue_id; 1.205 + escaped_issue_id = escapeLiteral(db, candidates[i].key, strlen(candidates[i].key)); 1.206 + if (!escaped_issue_id) { 1.207 + fprintf(stderr, "Could not escape literal in memory.\n"); 1.208 + abort(); 1.209 + } 1.210 + if (asprintf(&cmd, "UPDATE \"issue\" SET \"order_in_admission_state\" = %i WHERE \"id\" = %s", candidates[i].seat, escaped_issue_id) < 0) { 1.211 + fprintf(stderr, "Could not prepare query string in memory.\n"); 1.212 + abort(); 1.213 + } 1.214 + freemem(escaped_issue_id); 1.215 + res = PQexec(db, cmd); 1.216 + free(cmd); 1.217 + if (!res) { 1.218 + fprintf(stderr, "Error in pqlib while sending SQL command to update issue order.\n"); 1.219 + } else if ( 1.220 + PQresultStatus(res) != PGRES_COMMAND_OK && 1.221 + PQresultStatus(res) != PGRES_TUPLES_OK 1.222 + ) { 1.223 + fprintf(stderr, "Error while executing SQL command to update issue order:\n%s", PQresultErrorMessage(res)); 1.224 + PQclear(res); 1.225 + } else { 1.226 + PQclear(res); 1.227 + continue; 1.228 + } 1.229 + res = PQexec(db, "ROLLBACK"); 1.230 + if (res) PQclear(res); 1.231 + return 1; 1.232 + } 1.233 + res = PQexec(db, "COMMIT"); 1.234 + if (!res) { 1.235 + fprintf(stderr, "Error in pqlib while sending SQL command to commit transaction.\n"); 1.236 + return 1; 1.237 + } else if ( 1.238 + PQresultStatus(res) != PGRES_COMMAND_OK && 1.239 + PQresultStatus(res) != PGRES_TUPLES_OK 1.240 + ) { 1.241 + fprintf(stderr, "Error while executing SQL command to commit transaction:\n%s", PQresultErrorMessage(res)); 1.242 + PQclear(res); 1.243 + return 1; 1.244 + } else { 1.245 + PQclear(res); 1.246 + return 0; 1.247 + } 1.248 +} 1.249 + 1.250 +// calculate ordering of issues in admission state for an area and call write_ranks() to write it to database: 1.251 +static int process_area(PGconn *db, PGresult *res, char *escaped_area_id) { 1.252 + int err; // variable to store an error condition (0 = success) 1.253 + int ballot_count = 1; // number of ballots, must be initiatized to 1, due to loop below 1.254 + struct ballot *ballots; // data structure containing the ballots 1.255 + int i; // index variable for loops 1.256 + // create candidates[] and ballots[] arrays: 1.257 + { 1.258 + void *candidate_tree = NULL; // temporary structure to create a sorted unique list of all candidate keys 1.259 + int tuple_count; // number of tuples returned from the database 1.260 + char *old_member_id = NULL; // old member_id to be able to detect a new ballot in loops 1.261 + struct ballot *ballot; // pointer to current ballot 1.262 + int candidates_in_ballot = 0; // number of candidates in ballot 1.263 + // reset candidate count: 1.264 + candidate_count = 0; 1.265 + // determine number of tuples: 1.266 + tuple_count = PQntuples(res); 1.267 + // trivial case, when there are no tuples: 1.268 + if (!tuple_count) { 1.269 + if (logging) printf("Nothing to do.\n"); 1.270 + return 0; 1.271 + } 1.272 + // calculate ballot_count and generate set of candidate keys (suggestion_id is used as key): 1.273 + for (i=0; i<tuple_count; i++) { 1.274 + char *member_id, *issue_id; 1.275 + member_id = PQgetvalue(res, i, COL_MEMBER_ID); 1.276 + issue_id = PQgetvalue(res, i, COL_ISSUE_ID); 1.277 + if (!candidate_tree || !tfind(issue_id, &candidate_tree, (void *)compare_id)) { 1.278 + candidate_count++; 1.279 + if (!tsearch(issue_id, &candidate_tree, (void *)compare_id)) { 1.280 + fprintf(stderr, "Insufficient memory while inserting into candidate tree.\n"); 1.281 + abort(); 1.282 + } 1.283 + } 1.284 + if (old_member_id && strcmp(old_member_id, member_id)) ballot_count++; 1.285 + old_member_id = member_id; 1.286 + } 1.287 + // allocate memory for candidates[] array: 1.288 + candidates = malloc(candidate_count * sizeof(struct candidate)); 1.289 + if (!candidates) { 1.290 + fprintf(stderr, "Insufficient memory while creating candidate list.\n"); 1.291 + abort(); 1.292 + } 1.293 + // transform tree of candidate keys into sorted array: 1.294 + candidate_count = 0; // needed by register_candidate() 1.295 + twalk(candidate_tree, (void *)register_candidate); 1.296 + // free memory of tree structure (tdestroy() is not available on all platforms): 1.297 + while (candidate_tree) tdelete(*(void **)candidate_tree, &candidate_tree, (void *)compare_id); 1.298 + // allocate memory for ballots[] array: 1.299 + ballots = calloc(ballot_count, sizeof(struct ballot)); 1.300 + if (!ballots) { 1.301 + fprintf(stderr, "Insufficient memory while creating ballot list.\n"); 1.302 + abort(); 1.303 + } 1.304 + // set ballot weights, determine ballot section sizes, and verify preference values: 1.305 + ballot = ballots; 1.306 + old_member_id = NULL; 1.307 + for (i=0; i<tuple_count; i++) { 1.308 + char *member_id; 1.309 + int weight; 1.310 + member_id = PQgetvalue(res, i, COL_MEMBER_ID); 1.311 + weight = (int)strtol(PQgetvalue(res, i, COL_WEIGHT), (char **)NULL, 10); 1.312 + if (weight <= 0) { 1.313 + fprintf(stderr, "Unexpected weight value.\n"); 1.314 + free(ballots); 1.315 + free(candidates); 1.316 + return 1; 1.317 + } 1.318 + if (old_member_id && strcmp(old_member_id, member_id)) ballot++; 1.319 + ballot->weight = weight; 1.320 + ballot->count++; 1.321 + old_member_id = member_id; 1.322 + } 1.323 + // allocate memory for ballot sections: 1.324 + for (i=0; i<ballot_count; i++) { 1.325 + if (ballots[i].count) { 1.326 + ballots[i].candidates = malloc(ballots[i].count * sizeof(struct candidate *)); 1.327 + if (!ballots[i].candidates) { 1.328 + fprintf(stderr, "Insufficient memory while creating ballot section.\n"); 1.329 + abort(); 1.330 + } 1.331 + } 1.332 + } 1.333 + // fill ballot sections with candidate references: 1.334 + old_member_id = NULL; 1.335 + ballot = ballots; 1.336 + for (i=0; i<tuple_count; i++) { 1.337 + char *member_id, *issue_id; 1.338 + member_id = PQgetvalue(res, i, COL_MEMBER_ID); 1.339 + issue_id = PQgetvalue(res, i, COL_ISSUE_ID); 1.340 + if (old_member_id && strcmp(old_member_id, member_id)) { 1.341 + ballot++; 1.342 + candidates_in_ballot = 0; 1.343 + } 1.344 + ballot->candidates[candidates_in_ballot++] = candidate_by_key(issue_id); 1.345 + old_member_id = member_id; 1.346 + } 1.347 + // print ballots, if logging is enabled: 1.348 + if (logging) { 1.349 + for (i=0; i<ballot_count; i++) { 1.350 + int j; 1.351 + printf("Ballot #%i: ", i+1); 1.352 + for (j=0; j<ballots[i].count; j++) { 1.353 + if (!j) printf("issues "); 1.354 + else printf(", "); 1.355 + printf("#%s", ballots[i].candidates[j]->key); 1.356 + } 1.357 + // if (!j) printf("empty"); // should not happen 1.358 + printf(".\n"); 1.359 + } 1.360 + } 1.361 + } 1.362 + 1.363 + // calculate ranks based on constructed data structures: 1.364 + for (i=0; i<candidate_count; i++) { 1.365 + struct candidate *candidate = loser(i, ballots, ballot_count); 1.366 + candidate->seat = candidate_count - i; 1.367 + if (logging) printf("Assigning rank #%i to issue #%s.\n", candidate_count-i, candidate->key); 1.368 + } 1.369 + 1.370 + // free ballots[] array: 1.371 + for (i=0; i<ballot_count; i++) { 1.372 + // if (ballots[i].count) { // count should not be zero 1.373 + free(ballots[i].candidates); 1.374 + // } 1.375 + } 1.376 + free(ballots); 1.377 + 1.378 + // write results to database: 1.379 + if (logging) printf("Writing ranks to database.\n"); 1.380 + err = write_ranks(db, escaped_area_id); 1.381 + if (logging) printf("Done.\n"); 1.382 + 1.383 + // free candidates[] array: 1.384 + free(candidates); 1.385 + 1.386 + // return error code of write_ranks() call 1.387 + return err; 1.388 +} 1.389 + 1.390 +int main(int argc, char **argv) { 1.391 + 1.392 + // variable declarations: 1.393 + int err = 0; 1.394 + int i, count; 1.395 + char *conninfo; 1.396 + PGconn *db; 1.397 + PGresult *res; 1.398 + 1.399 + // parse command line: 1.400 + if (argc == 0) return 1; 1.401 + if (argc == 1 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) { 1.402 + FILE *out; 1.403 + out = argc == 1 ? stderr : stdout; 1.404 + fprintf(out, "\n"); 1.405 + fprintf(out, "Usage: %s [-v|--verbose] <conninfo>\n", argv[0]); 1.406 + fprintf(out, "\n"); 1.407 + fprintf(out, "<conninfo> is specified by PostgreSQL's libpq,\n"); 1.408 + fprintf(out, "see http://www.postgresql.org/docs/9.1/static/libpq-connect.html\n"); 1.409 + fprintf(out, "\n"); 1.410 + fprintf(out, "Example: %s dbname=liquid_feedback\n", argv[0]); 1.411 + fprintf(out, "\n"); 1.412 + return argc == 1 ? 1 : 0; 1.413 + } 1.414 + { 1.415 + size_t len = 0; 1.416 + int argb = 1; 1.417 + if ( 1.418 + argc >= 2 && 1.419 + (!strcmp(argv[1], "-v") || !strcmp(argv[1], "--verbose")) 1.420 + ) { 1.421 + argb = 2; 1.422 + logging = 1; 1.423 + } 1.424 + for (i=argb; i<argc; i++) len += strlen(argv[i]) + 1; 1.425 + conninfo = malloc(len * sizeof(char)); 1.426 + if (!conninfo) { 1.427 + fprintf(stderr, "Error: Could not allocate memory for conninfo string.\n"); 1.428 + abort(); 1.429 + } 1.430 + conninfo[0] = 0; 1.431 + for (i=argb; i<argc; i++) { 1.432 + if (i>argb) strcat(conninfo, " "); 1.433 + strcat(conninfo, argv[i]); 1.434 + } 1.435 + } 1.436 + 1.437 + // connect to database: 1.438 + db = PQconnectdb(conninfo); 1.439 + if (!db) { 1.440 + fprintf(stderr, "Error: Could not create database handle.\n"); 1.441 + return 1; 1.442 + } 1.443 + if (PQstatus(db) != CONNECTION_OK) { 1.444 + fprintf(stderr, "Could not open connection:\n%s", PQerrorMessage(db)); 1.445 + return 1; 1.446 + } 1.447 + 1.448 + // go through areas: 1.449 + res = PQexec(db, "SELECT \"id\" FROM \"area\""); 1.450 + if (!res) { 1.451 + fprintf(stderr, "Error in pqlib while sending SQL command selecting areas to process.\n"); 1.452 + err = 1; 1.453 + } else if (PQresultStatus(res) != PGRES_TUPLES_OK) { 1.454 + fprintf(stderr, "Error while executing SQL command selecting areas to process:\n%s", PQresultErrorMessage(res)); 1.455 + err = 1; 1.456 + PQclear(res); 1.457 + } else if (PQnfields(res) < 1) { 1.458 + fprintf(stderr, "Too few columns returned by SQL command selecting areas to process.\n"); 1.459 + err = 1; 1.460 + PQclear(res); 1.461 + } else { 1.462 + count = PQntuples(res); 1.463 + if (logging) printf("Number of areas to process: %i\n", count); 1.464 + for (i=0; i<count; i++) { 1.465 + char *area_id, *escaped_area_id; 1.466 + char *cmd; 1.467 + PGresult *res2; 1.468 + area_id = PQgetvalue(res, i, 0); 1.469 + if (logging) printf("Processing area #%s:\n", area_id); 1.470 + escaped_area_id = escapeLiteral(db, area_id, strlen(area_id)); 1.471 + if (!escaped_area_id) { 1.472 + fprintf(stderr, "Could not escape literal in memory.\n"); 1.473 + abort(); 1.474 + } 1.475 + if (asprintf(&cmd, "SELECT \"member_id\", \"weight\", \"issue_id\" FROM \"issue_supporter_in_admission_state\" WHERE \"area_id\" = %s ORDER BY \"member_id\"", escaped_area_id) < 0) { 1.476 + fprintf(stderr, "Could not prepare query string in memory.\n"); 1.477 + abort(); 1.478 + } 1.479 + res2 = PQexec(db, cmd); 1.480 + free(cmd); 1.481 + if (!res2) { 1.482 + fprintf(stderr, "Error in pqlib while sending SQL command selecting issue supporter in admission state.\n"); 1.483 + err = 1; 1.484 + } else if (PQresultStatus(res2) != PGRES_TUPLES_OK) { 1.485 + fprintf(stderr, "Error while executing SQL command selecting issue supporter in admission state:\n%s", PQresultErrorMessage(res)); 1.486 + err = 1; 1.487 + PQclear(res2); 1.488 + } else if (PQnfields(res2) < 3) { 1.489 + fprintf(stderr, "Too few columns returned by SQL command selecting issue supporter in admission state.\n"); 1.490 + err = 1; 1.491 + PQclear(res2); 1.492 + } else { 1.493 + if (process_area(db, res2, escaped_area_id)) err = 1; 1.494 + PQclear(res2); 1.495 + } 1.496 + freemem(escaped_area_id); 1.497 + } 1.498 + PQclear(res); 1.499 + } 1.500 + 1.501 + // cleanup and exit: 1.502 + PQfinish(db); 1.503 + if (!err) { 1.504 + if (logging) printf("Successfully terminated.\n"); 1.505 + } else { 1.506 + fprintf(stderr, "Exiting with error code %i.\n", err); 1.507 + } 1.508 + return err; 1.509 + 1.510 +}