liquid_feedback_core
view lf_update_suggestion_order.c @ 378:e88d0606891f
Bugfix regarding "proportional_order" of suggestions:
Use NULL values explicitly to be sorted last
(includes new suggestions as well as suggestions without any individual rankings)
Use NULL values explicitly to be sorted last
(includes new suggestions as well as suggestions without any individual rankings)
author | jbe |
---|---|
date | Mon Mar 18 09:36:21 2013 +0100 (2013-03-18) |
parents | f65814f4d3fc |
children | eda636259846 |
line source
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <libpq-fe.h>
5 #include <search.h>
7 static int logging = 0;
9 static char *escapeLiteral(PGconn *conn, const char *str, size_t len) {
10 // provides compatibility for PostgreSQL versions prior 9.0
11 // in future: return PQescapeLiteral(conn, str, len);
12 char *res;
13 size_t res_len;
14 res = malloc(2*len+3);
15 if (!res) return NULL;
16 res[0] = '\'';
17 res_len = PQescapeStringConn(conn, res+1, str, len, NULL);
18 res[res_len+1] = '\'';
19 res[res_len+2] = 0;
20 return res;
21 }
23 static void freemem(void *ptr) {
24 // to be used for "escapeLiteral" function
25 // provides compatibility for PostgreSQL versions prior 9.0
26 // in future: PQfreemem(ptr);
27 free(ptr);
28 }
30 // column numbers when querying "individual_suggestion_ranking" view in function main():
31 #define COL_MEMBER_ID 0
32 #define COL_WEIGHT 1
33 #define COL_PREFERENCE 2
34 #define COL_SUGGESTION_ID 3
36 // data structure for a candidate (in this case a suggestion) to the proportional runoff system:
37 struct candidate {
38 char *key; // identifier of the candidate, which is the "suggestion_id" string
39 double score_per_step; // added score per step
40 double score; // current score of candidate; a score of 1.0 is needed to survive a round
41 int seat; // equals 0 for unseated candidates, or contains rank number
42 };
44 // compare two integers stored as strings (invocation like strcmp):
45 static int compare_id(char *id1, char *id2) {
46 int ldiff;
47 ldiff = strlen(id1) - strlen(id2);
48 if (ldiff) return ldiff;
49 else return strcmp(id1, id2);
50 }
52 // compare two candidates by their key (invocation like strcmp):
53 static int compare_candidate(struct candidate *c1, struct candidate *c2) {
54 return compare_id(c1->key, c2->key);
55 }
57 // candidates are stored as global variables due to the constrained twalk() interface:
58 static int candidate_count;
59 static struct candidate *candidates;
61 // function to be passed to twalk() to store candidates ordered in candidates[] array:
62 static void register_candidate(char **candidate_key, VISIT visit, int level) {
63 if (visit == postorder || visit == leaf) {
64 struct candidate *candidate;
65 candidate = candidates + (candidate_count++);
66 candidate->key = *candidate_key;
67 candidate->seat = 0;
68 if (logging) printf("Candidate #%i is suggestion #%s.\n", candidate_count, candidate->key);
69 }
70 }
72 // performs a binary search in candidates[] array to lookup a candidate by its key (which is the suggestion_id):
73 static struct candidate *candidate_by_key(char *candidate_key) {
74 struct candidate *candidate;
75 struct candidate compare;
76 compare.key = candidate_key;
77 candidate = bsearch(&compare, candidates, candidate_count, sizeof(struct candidate), (void *)compare_candidate);
78 if (!candidate) {
79 fprintf(stderr, "Candidate not found (should not happen).\n");
80 abort();
81 }
82 return candidate;
83 }
85 // section of a ballot with equally ranked candidates:
86 struct ballot_section {
87 int count;
88 struct candidate **candidates;
89 };
91 // ballot of the proportional runoff system:
92 struct ballot {
93 int weight; // if weight is greater than 1, then the ballot is counted multiple times
94 struct ballot_section sections[4]; // 4 sections, most preferred candidates first
95 };
97 // determine candidate, which is assigned the next seat (starting with the worst rank):
98 static struct candidate *loser(int round_number, struct ballot *ballots, int ballot_count) {
99 int i, j, k; // index variables for loops
100 int remaining; // remaining candidates to be seated
101 // reset scores of all candidates:
102 for (i=0; i<candidate_count; i++) {
103 candidates[i].score = 0.0;
104 }
105 // calculate remaining candidates to be seated:
106 remaining = candidate_count - round_number;
107 // repeat following loop, as long as there is more than one remaining candidate:
108 while (remaining > 1) {
109 if (logging) printf("There are %i remaining candidates.\n", remaining);
110 double scale; // factor to be later multiplied with score_per_step:
111 // reset score_per_step for all candidates:
112 for (i=0; i<candidate_count; i++) {
113 candidates[i].score_per_step = 0.0;
114 }
115 // calculate score_per_step for all candidates:
116 for (i=0; i<ballot_count; i++) {
117 for (j=0; j<4; j++) {
118 int matches = 0;
119 for (k=0; k<ballots[i].sections[j].count; k++) {
120 struct candidate *candidate;
121 candidate = ballots[i].sections[j].candidates[k];
122 if (candidate->score < 1.0 && !candidate->seat) matches++;
123 }
124 if (matches) {
125 double score_inc;
126 score_inc = (double)ballots[i].weight / (double)matches;
127 for (k=0; k<ballots[i].sections[j].count; k++) {
128 struct candidate *candidate;
129 candidate = ballots[i].sections[j].candidates[k];
130 if (candidate->score < 1.0 && !candidate->seat) {
131 candidate->score_per_step += score_inc;
132 }
133 }
134 break;
135 }
136 }
137 }
138 // calculate scale factor:
139 scale = (double)0.0; // 0.0 is used to indicate that there is no value yet
140 for (i=0; i<candidate_count; i++) {
141 double max_scale;
142 if (candidates[i].score_per_step > 0.0) {
143 max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step;
144 if (scale == 0.0 || max_scale <= scale) {
145 scale = max_scale;
146 }
147 }
148 }
149 // add scale*score_per_step to each candidates score:
150 for (i=0; i<candidate_count; i++) {
151 int log_candidate = 0;
152 if (logging && candidates[i].score < 1.0 && !candidates[i].seat) log_candidate = 1;
153 if (log_candidate) printf("Score for suggestion #%s = %.4f+%.4f*%.4f", candidates[i].key, candidates[i].score, scale, candidates[i].score_per_step);
154 if (candidates[i].score_per_step > 0.0) {
155 double max_scale;
156 max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step;
157 if (max_scale == scale) {
158 // score of 1.0 should be reached, so we set score directly to avoid floating point errors:
159 candidates[i].score = 1.0;
160 remaining--;
161 } else {
162 candidates[i].score += scale * candidates[i].score_per_step;
163 if (candidates[i].score >= 1.0) remaining--;
164 }
165 }
166 if (log_candidate) {
167 if (candidates[i].score >= 1.0) printf("=1\n");
168 else printf("=%.4f\n", candidates[i].score);
169 }
170 // when there is only one candidate remaining, then break inner (and thus outer) loop:
171 if (remaining <= 1) {
172 break;
173 }
174 }
175 }
176 // return remaining candidate:
177 for (i=0; i<candidate_count; i++) {
178 if (candidates[i].score < 1.0 && !candidates[i].seat) return candidates+i;
179 }
180 // if there is no remaining candidate, then something went wrong:
181 fprintf(stderr, "No remaining candidate (should not happen).");
182 abort();
183 }
185 // write results to database:
186 static int write_ranks(PGconn *db, char *escaped_initiative_id, int final) {
187 PGresult *res;
188 char *cmd;
189 int i;
190 if (final) {
191 if (asprintf(&cmd, "BEGIN; UPDATE \"initiative\" SET \"final_suggestion_order_calculated\" = TRUE WHERE \"id\" = %s; UPDATE \"suggestion\" SET \"proportional_order\" = NULL WHERE \"initiative_id\" = %s", escaped_initiative_id, escaped_initiative_id) < 0) {
192 fprintf(stderr, "Could not prepare query string in memory.\n");
193 abort();
194 }
195 } else {
196 if (asprintf(&cmd, "BEGIN; UPDATE \"suggestion\" SET \"proportional_order\" = NULL WHERE \"initiative_id\" = %s", escaped_initiative_id) < 0) {
197 fprintf(stderr, "Could not prepare query string in memory.\n");
198 abort();
199 }
200 }
201 res = PQexec(db, cmd);
202 free(cmd);
203 if (!res) {
204 fprintf(stderr, "Error in pqlib while sending SQL command to initiate suggestion update.\n");
205 return 1;
206 } else if (
207 PQresultStatus(res) != PGRES_COMMAND_OK &&
208 PQresultStatus(res) != PGRES_TUPLES_OK
209 ) {
210 fprintf(stderr, "Error while executing SQL command to initiate suggestion update:\n%s", PQresultErrorMessage(res));
211 PQclear(res);
212 return 1;
213 } else {
214 PQclear(res);
215 }
216 for (i=0; i<candidate_count; i++) {
217 char *escaped_suggestion_id;
218 escaped_suggestion_id = escapeLiteral(db, candidates[i].key, strlen(candidates[i].key));
219 if (!escaped_suggestion_id) {
220 fprintf(stderr, "Could not escape literal in memory.\n");
221 abort();
222 }
223 if (asprintf(&cmd, "UPDATE \"suggestion\" SET \"proportional_order\" = %i WHERE \"id\" = %s", candidates[i].seat, escaped_suggestion_id) < 0) {
224 fprintf(stderr, "Could not prepare query string in memory.\n");
225 abort();
226 }
227 freemem(escaped_suggestion_id);
228 res = PQexec(db, cmd);
229 free(cmd);
230 if (!res) {
231 fprintf(stderr, "Error in pqlib while sending SQL command to update suggestion order.\n");
232 } else if (
233 PQresultStatus(res) != PGRES_COMMAND_OK &&
234 PQresultStatus(res) != PGRES_TUPLES_OK
235 ) {
236 fprintf(stderr, "Error while executing SQL command to update suggestion order:\n%s", PQresultErrorMessage(res));
237 PQclear(res);
238 } else {
239 PQclear(res);
240 continue;
241 }
242 res = PQexec(db, "ROLLBACK");
243 if (res) PQclear(res);
244 return 1;
245 }
246 res = PQexec(db, "COMMIT");
247 if (!res) {
248 fprintf(stderr, "Error in pqlib while sending SQL command to commit transaction.\n");
249 return 1;
250 } else if (
251 PQresultStatus(res) != PGRES_COMMAND_OK &&
252 PQresultStatus(res) != PGRES_TUPLES_OK
253 ) {
254 fprintf(stderr, "Error while executing SQL command to commit transaction:\n%s", PQresultErrorMessage(res));
255 PQclear(res);
256 return 1;
257 } else {
258 PQclear(res);
259 return 0;
260 }
261 }
263 // calculate ordering of suggestions for an initiative and call write_ranks() to write it to database:
264 static int process_initiative(PGconn *db, PGresult *res, char *escaped_initiative_id, int final) {
265 int err; // variable to store an error condition (0 = success)
266 int ballot_count = 1; // number of ballots, must be initiatized to 1, due to loop below
267 struct ballot *ballots; // data structure containing the ballots
268 int i; // index variable for loops
269 // create candidates[] and ballots[] arrays:
270 {
271 void *candidate_tree = NULL; // temporary structure to create a sorted unique list of all candidate keys
272 int tuple_count; // number of tuples returned from the database
273 char *old_member_id = NULL; // old member_id to be able to detect a new ballot in loops
274 struct ballot *ballot; // pointer to current ballot
275 int candidates_in_sections[4] = {0, }; // number of candidates that have been placed in each section
276 // reset candidate count:
277 candidate_count = 0;
278 // determine number of tuples:
279 tuple_count = PQntuples(res);
280 // trivial case, when there are no tuples:
281 if (!tuple_count) {
282 if (final) {
283 if (logging) printf("No suggestions found, but marking initiative as finally calculated.\n");
284 err = write_ranks(db, escaped_initiative_id, final);
285 if (logging) printf("Done.\n");
286 return err;
287 } else {
288 if (logging) printf("Nothing to do.\n");
289 return 0;
290 }
291 }
292 // calculate ballot_count and generate set of candidate keys (suggestion_id is used as key):
293 for (i=0; i<tuple_count; i++) {
294 char *member_id, *suggestion_id;
295 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
296 suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
297 if (!candidate_tree || !tfind(suggestion_id, &candidate_tree, (void *)compare_id)) {
298 candidate_count++;
299 if (!tsearch(suggestion_id, &candidate_tree, (void *)compare_id)) {
300 fprintf(stderr, "Insufficient memory while inserting into candidate tree.\n");
301 abort();
302 }
303 }
304 if (old_member_id && strcmp(old_member_id, member_id)) ballot_count++;
305 old_member_id = member_id;
306 }
307 // allocate memory for candidates[] array:
308 candidates = malloc(candidate_count * sizeof(struct candidate));
309 if (!candidates) {
310 fprintf(stderr, "Insufficient memory while creating candidate list.\n");
311 abort();
312 }
313 // transform tree of candidate keys into sorted array:
314 candidate_count = 0; // needed by register_candidate()
315 twalk(candidate_tree, (void *)register_candidate);
316 // free memory of tree structure (tdestroy() is not available on all platforms):
317 while (candidate_tree) tdelete(*(void **)candidate_tree, &candidate_tree, (void *)compare_id);
318 // allocate memory for ballots[] array:
319 ballots = calloc(ballot_count, sizeof(struct ballot));
320 if (!ballots) {
321 fprintf(stderr, "Insufficient memory while creating ballot list.\n");
322 abort();
323 }
324 // set ballot weights, determine ballot section sizes, and verify preference values:
325 ballot = ballots;
326 old_member_id = NULL;
327 for (i=0; i<tuple_count; i++) {
328 char *member_id;
329 int weight, preference;
330 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
331 weight = (int)strtol(PQgetvalue(res, i, COL_WEIGHT), (char **)NULL, 10);
332 if (weight <= 0) {
333 fprintf(stderr, "Unexpected weight value.\n");
334 free(ballots);
335 free(candidates);
336 return 1;
337 }
338 preference = (int)strtol(PQgetvalue(res, i, COL_PREFERENCE), (char **)NULL, 10);
339 if (preference < 1 || preference > 4) {
340 fprintf(stderr, "Unexpected preference value.\n");
341 free(ballots);
342 free(candidates);
343 return 1;
344 }
345 preference--;
346 if (old_member_id && strcmp(old_member_id, member_id)) ballot++;
347 ballot->weight = weight;
348 ballot->sections[preference].count++;
349 old_member_id = member_id;
350 }
351 // allocate memory for ballot sections:
352 for (i=0; i<ballot_count; i++) {
353 int j;
354 for (j=0; j<4; j++) {
355 if (ballots[i].sections[j].count) {
356 ballots[i].sections[j].candidates = malloc(ballots[i].sections[j].count * sizeof(struct candidate *));
357 if (!ballots[i].sections[j].candidates) {
358 fprintf(stderr, "Insufficient memory while creating ballot section.\n");
359 abort();
360 }
361 }
362 }
363 }
364 // fill ballot sections with candidate references:
365 old_member_id = NULL;
366 ballot = ballots;
367 for (i=0; i<tuple_count; i++) {
368 char *member_id, *suggestion_id;
369 int preference;
370 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
371 suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
372 preference = (int)strtol(PQgetvalue(res, i, COL_PREFERENCE), (char **)NULL, 10);
373 preference--;
374 if (old_member_id && strcmp(old_member_id, member_id)) {
375 ballot++;
376 candidates_in_sections[0] = 0;
377 candidates_in_sections[1] = 0;
378 candidates_in_sections[2] = 0;
379 candidates_in_sections[3] = 0;
380 }
381 ballot->sections[preference].candidates[candidates_in_sections[preference]++] = candidate_by_key(suggestion_id);
382 old_member_id = member_id;
383 }
384 // print ballots, if logging is enabled:
385 if (logging) {
386 for (i=0; i<ballot_count; i++) {
387 int j;
388 for (j=0; j<4; j++) {
389 int k;
390 printf("Ballot #%i, ", i+1);
391 if (j==0) printf("1st");
392 if (j==1) printf("2nd");
393 if (j==2) printf("3rd");
394 if (j==3) printf("4th");
395 printf(" preference: ");
396 for (k=0; k<ballots[i].sections[j].count; k++) {
397 if (!k) printf("suggestions ");
398 else printf(", ");
399 printf("#%s", ballots[i].sections[j].candidates[k]->key);
400 }
401 if (!k) printf("empty");
402 printf(".\n");
403 }
404 }
405 }
406 }
408 // calculate ranks based on constructed data structures:
409 for (i=0; i<candidate_count; i++) {
410 struct candidate *candidate = loser(i, ballots, ballot_count);
411 candidate->seat = candidate_count - i;
412 if (logging) printf("Assigning rank #%i to suggestion #%s.\n", candidate_count-i, candidate->key);
413 }
415 // free ballots[] array:
416 for (i=0; i<ballot_count; i++) {
417 int j;
418 for (j=0; j<4; j++) {
419 if (ballots[i].sections[j].count) {
420 free(ballots[i].sections[j].candidates);
421 }
422 }
423 }
424 free(ballots);
426 // write results to database:
427 if (final) {
428 if (logging) printf("Writing final ranks to database.\n");
429 } else {
430 if (logging) printf("Writing ranks to database.\n");
431 }
432 err = write_ranks(db, escaped_initiative_id, final);
433 if (logging) printf("Done.\n");
435 // free candidates[] array:
436 free(candidates);
438 // return error code of write_ranks() call
439 return err;
440 }
442 int main(int argc, char **argv) {
444 // variable declarations:
445 int err = 0;
446 int i, count;
447 char *conninfo;
448 PGconn *db;
449 PGresult *res;
451 // parse command line:
452 if (argc == 0) return 1;
453 if (argc == 1 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
454 FILE *out;
455 out = argc == 1 ? stderr : stdout;
456 fprintf(out, "\n");
457 fprintf(out, "Usage: %s [-v|--verbose] <conninfo>\n", argv[0]);
458 fprintf(out, "\n");
459 fprintf(out, "<conninfo> is specified by PostgreSQL's libpq,\n");
460 fprintf(out, "see http://www.postgresql.org/docs/9.1/static/libpq-connect.html\n");
461 fprintf(out, "\n");
462 fprintf(out, "Example: %s dbname=liquid_feedback\n", argv[0]);
463 fprintf(out, "\n");
464 return argc == 1 ? 1 : 0;
465 }
466 {
467 size_t len = 0;
468 int argb = 1;
469 if (
470 argc >= 2 &&
471 (!strcmp(argv[1], "-v") || !strcmp(argv[1], "--verbose"))
472 ) {
473 argb = 2;
474 logging = 1;
475 }
476 for (i=argb; i<argc; i++) len += strlen(argv[i]) + 1;
477 conninfo = malloc(len * sizeof(char));
478 if (!conninfo) {
479 fprintf(stderr, "Error: Could not allocate memory for conninfo string.\n");
480 abort();
481 }
482 conninfo[0] = 0;
483 for (i=argb; i<argc; i++) {
484 if (i>argb) strcat(conninfo, " ");
485 strcat(conninfo, argv[i]);
486 }
487 }
489 // connect to database:
490 db = PQconnectdb(conninfo);
491 if (!db) {
492 fprintf(stderr, "Error: Could not create database handle.\n");
493 return 1;
494 }
495 if (PQstatus(db) != CONNECTION_OK) {
496 fprintf(stderr, "Could not open connection:\n%s", PQerrorMessage(db));
497 return 1;
498 }
500 // check initiatives:
501 res = PQexec(db, "SELECT \"initiative_id\", \"final\" FROM \"initiative_suggestion_order_calculation\"");
502 if (!res) {
503 fprintf(stderr, "Error in pqlib while sending SQL command selecting initiatives to process.\n");
504 err = 1;
505 } else if (PQresultStatus(res) != PGRES_TUPLES_OK) {
506 fprintf(stderr, "Error while executing SQL command selecting initiatives to process:\n%s", PQresultErrorMessage(res));
507 err = 1;
508 PQclear(res);
509 } else if (PQnfields(res) < 2) {
510 fprintf(stderr, "Too few columns returned by SQL command selecting initiatives to process.\n");
511 err = 1;
512 PQclear(res);
513 } else {
514 count = PQntuples(res);
515 if (logging) printf("Number of initiatives to process: %i\n", count);
516 for (i=0; i<count; i++) {
517 char *initiative_id, *escaped_initiative_id;
518 int final;
519 char *cmd;
520 PGresult *res2;
521 initiative_id = PQgetvalue(res, i, 0);
522 final = (PQgetvalue(res, i, 1)[0] == 't') ? 1 : 0;
523 if (logging) printf("Processing initiative #%s:\n", initiative_id);
524 escaped_initiative_id = escapeLiteral(db, initiative_id, strlen(initiative_id));
525 if (!escaped_initiative_id) {
526 fprintf(stderr, "Could not escape literal in memory.\n");
527 abort();
528 }
529 if (asprintf(&cmd, "SELECT \"member_id\", \"weight\", \"preference\", \"suggestion_id\" FROM \"individual_suggestion_ranking\" WHERE \"initiative_id\" = %s ORDER BY \"member_id\", \"preference\"", escaped_initiative_id) < 0) {
530 fprintf(stderr, "Could not prepare query string in memory.\n");
531 abort();
532 }
533 res2 = PQexec(db, cmd);
534 free(cmd);
535 if (!res2) {
536 fprintf(stderr, "Error in pqlib while sending SQL command selecting individual suggestion rankings.\n");
537 err = 1;
538 } else if (PQresultStatus(res2) != PGRES_TUPLES_OK) {
539 fprintf(stderr, "Error while executing SQL command selecting individual suggestion rankings:\n%s", PQresultErrorMessage(res));
540 err = 1;
541 PQclear(res2);
542 } else if (PQnfields(res2) < 4) {
543 fprintf(stderr, "Too few columns returned by SQL command selecting individual suggestion rankings.\n");
544 err = 1;
545 PQclear(res2);
546 } else {
547 if (process_initiative(db, res2, escaped_initiative_id, final)) err = 1;
548 PQclear(res2);
549 }
550 freemem(escaped_initiative_id);
551 }
552 PQclear(res);
553 }
555 // cleanup and exit:
556 PQfinish(db);
557 if (!err) {
558 if (logging) printf("Successfully terminated.\n");
559 } else {
560 fprintf(stderr, "Exiting with error code %i.\n", err);
561 }
562 return err;
564 }