liquid_feedback_core

view lf_update_suggestion_order.c @ 376:4a18576a359f

find changesets by author, revision, files, or words in the commit message
More verbose logging in lf_update_suggestion_order.c
author jbe
date Mon Mar 18 09:09:29 2013 +0100 (2013-03-18)
parents 3f7a89ad996d
children f65814f4d3fc
line source
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <libpq-fe.h>
5 #include <search.h>
6
7 static int logging = 0;
8
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 }
22
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 }
29
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
35
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 };
43
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 }
51
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 }
56
57 // candidates are stored as global variables due to the constrained twalk() interface:
58 static int candidate_count;
59 static struct candidate *candidates;
60
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 }
71
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 }
84
85 // section of a ballot with equally ranked candidates:
86 struct ballot_section {
87 int count;
88 struct candidate **candidates;
89 };
90
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 };
96
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) printf("%.4f.\n", candidates[i].score);
167 // when there is only one candidate remaining, then break inner (and thus outer) loop:
168 if (remaining <= 1) {
169 break;
170 }
171 }
172 }
173 // return remaining candidate:
174 for (i=0; i<candidate_count; i++) {
175 if (candidates[i].score < 1.0 && !candidates[i].seat) return candidates+i;
176 }
177 // if there is no remaining candidate, then something went wrong:
178 fprintf(stderr, "No remaining candidate (should not happen).");
179 abort();
180 }
181
182 // write results to database:
183 static int write_ranks(PGconn *db, char *escaped_initiative_id, int final) {
184 PGresult *res;
185 char *cmd;
186 int i;
187 if (final) {
188 if (asprintf(&cmd, "BEGIN; UPDATE \"initiative\" SET \"final_suggestion_order_calculated\" = TRUE WHERE \"id\" = %s; UPDATE \"suggestion\" SET \"proportional_order\" = 0 WHERE \"initiative_id\" = %s", escaped_initiative_id, escaped_initiative_id) < 0) {
189 fprintf(stderr, "Could not prepare query string in memory.\n");
190 abort();
191 }
192 } else {
193 if (asprintf(&cmd, "BEGIN; UPDATE \"suggestion\" SET \"proportional_order\" = 0 WHERE \"initiative_id\" = %s", escaped_initiative_id) < 0) {
194 fprintf(stderr, "Could not prepare query string in memory.\n");
195 abort();
196 }
197 }
198 res = PQexec(db, cmd);
199 free(cmd);
200 if (!res) {
201 fprintf(stderr, "Error in pqlib while sending SQL command to initiate suggestion update.\n");
202 return 1;
203 } else if (
204 PQresultStatus(res) != PGRES_COMMAND_OK &&
205 PQresultStatus(res) != PGRES_TUPLES_OK
206 ) {
207 fprintf(stderr, "Error while executing SQL command to initiate suggestion update:\n%s", PQresultErrorMessage(res));
208 PQclear(res);
209 return 1;
210 } else {
211 PQclear(res);
212 }
213 for (i=0; i<candidate_count; i++) {
214 char *escaped_suggestion_id;
215 escaped_suggestion_id = escapeLiteral(db, candidates[i].key, strlen(candidates[i].key));
216 if (!escaped_suggestion_id) {
217 fprintf(stderr, "Could not escape literal in memory.\n");
218 abort();
219 }
220 if (asprintf(&cmd, "UPDATE \"suggestion\" SET \"proportional_order\" = %i WHERE \"id\" = %s", candidates[i].seat, escaped_suggestion_id) < 0) {
221 fprintf(stderr, "Could not prepare query string in memory.\n");
222 abort();
223 }
224 freemem(escaped_suggestion_id);
225 res = PQexec(db, cmd);
226 free(cmd);
227 if (!res) {
228 fprintf(stderr, "Error in pqlib while sending SQL command to update suggestion order.\n");
229 } else if (
230 PQresultStatus(res) != PGRES_COMMAND_OK &&
231 PQresultStatus(res) != PGRES_TUPLES_OK
232 ) {
233 fprintf(stderr, "Error while executing SQL command to update suggestion order:\n%s", PQresultErrorMessage(res));
234 PQclear(res);
235 } else {
236 PQclear(res);
237 continue;
238 }
239 res = PQexec(db, "ROLLBACK");
240 if (res) PQclear(res);
241 return 1;
242 }
243 res = PQexec(db, "COMMIT");
244 if (!res) {
245 fprintf(stderr, "Error in pqlib while sending SQL command to commit transaction.\n");
246 return 1;
247 } else if (
248 PQresultStatus(res) != PGRES_COMMAND_OK &&
249 PQresultStatus(res) != PGRES_TUPLES_OK
250 ) {
251 fprintf(stderr, "Error while executing SQL command to commit transaction:\n%s", PQresultErrorMessage(res));
252 PQclear(res);
253 return 1;
254 } else {
255 PQclear(res);
256 return 0;
257 }
258 }
259
260 // calculate ordering of suggestions for an initiative and call write_ranks() to write it to database:
261 static int process_initiative(PGconn *db, PGresult *res, char *escaped_initiative_id, int final) {
262 int err; // variable to store an error condition (0 = success)
263 int ballot_count = 1; // number of ballots, must be initiatized to 1, due to loop below
264 struct ballot *ballots; // data structure containing the ballots
265 int i; // index variable for loops
266 // create candidates[] and ballots[] arrays:
267 {
268 void *candidate_tree = NULL; // temporary structure to create a sorted unique list of all candidate keys
269 int tuple_count; // number of tuples returned from the database
270 char *old_member_id = NULL; // old member_id to be able to detect a new ballot in loops
271 struct ballot *ballot; // pointer to current ballot
272 int candidates_in_sections[4] = {0, }; // number of candidates that have been placed in each section
273 // reset candidate count:
274 candidate_count = 0;
275 // determine number of tuples:
276 tuple_count = PQntuples(res);
277 // trivial case, when there are no tuples:
278 if (!tuple_count) {
279 if (final) {
280 if (logging) printf("No suggestions found, but marking initiative as finally calculated.\n");
281 err = write_ranks(db, escaped_initiative_id, final);
282 if (logging) printf("Done.\n");
283 return err;
284 } else {
285 if (logging) printf("Nothing to do.\n");
286 return 0;
287 }
288 }
289 // calculate ballot_count and generate set of candidate keys (suggestion_id is used as key):
290 for (i=0; i<tuple_count; i++) {
291 char *member_id, *suggestion_id;
292 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
293 suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
294 if (!candidate_tree || !tfind(suggestion_id, &candidate_tree, (void *)compare_id)) {
295 candidate_count++;
296 if (!tsearch(suggestion_id, &candidate_tree, (void *)compare_id)) {
297 fprintf(stderr, "Insufficient memory while inserting into candidate tree.\n");
298 abort();
299 }
300 }
301 if (old_member_id && strcmp(old_member_id, member_id)) ballot_count++;
302 old_member_id = member_id;
303 }
304 // allocate memory for candidates[] array:
305 candidates = malloc(candidate_count * sizeof(struct candidate));
306 if (!candidates) {
307 fprintf(stderr, "Insufficient memory while creating candidate list.\n");
308 abort();
309 }
310 // transform tree of candidate keys into sorted array:
311 candidate_count = 0; // needed by register_candidate()
312 twalk(candidate_tree, (void *)register_candidate);
313 // free memory of tree structure (tdestroy() is not available on all platforms):
314 while (candidate_tree) tdelete(*(void **)candidate_tree, &candidate_tree, (void *)compare_id);
315 // allocate memory for ballots[] array:
316 ballots = calloc(ballot_count, sizeof(struct ballot));
317 if (!ballots) {
318 fprintf(stderr, "Insufficient memory while creating ballot list.\n");
319 abort();
320 }
321 // set ballot weights, determine ballot section sizes, and verify preference values:
322 ballot = ballots;
323 old_member_id = NULL;
324 for (i=0; i<tuple_count; i++) {
325 char *member_id;
326 int weight, preference;
327 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
328 weight = (int)strtol(PQgetvalue(res, i, COL_WEIGHT), (char **)NULL, 10);
329 if (weight <= 0) {
330 fprintf(stderr, "Unexpected weight value.\n");
331 free(ballots);
332 free(candidates);
333 return 1;
334 }
335 preference = (int)strtol(PQgetvalue(res, i, COL_PREFERENCE), (char **)NULL, 10);
336 if (preference < 1 || preference > 4) {
337 fprintf(stderr, "Unexpected preference value.\n");
338 free(ballots);
339 free(candidates);
340 return 1;
341 }
342 preference--;
343 if (old_member_id && strcmp(old_member_id, member_id)) ballot++;
344 ballot->weight = weight;
345 ballot->sections[preference].count++;
346 old_member_id = member_id;
347 }
348 // allocate memory for ballot sections:
349 for (i=0; i<ballot_count; i++) {
350 int j;
351 for (j=0; j<4; j++) {
352 if (ballots[i].sections[j].count) {
353 ballots[i].sections[j].candidates = malloc(ballots[i].sections[j].count * sizeof(struct candidate *));
354 if (!ballots[i].sections[j].candidates) {
355 fprintf(stderr, "Insufficient memory while creating ballot section.\n");
356 abort();
357 }
358 }
359 }
360 }
361 // fill ballot sections with candidate references:
362 old_member_id = NULL;
363 ballot = ballots;
364 for (i=0; i<tuple_count; i++) {
365 char *member_id, *suggestion_id;
366 int preference;
367 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
368 suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
369 preference = (int)strtol(PQgetvalue(res, i, COL_PREFERENCE), (char **)NULL, 10);
370 preference--;
371 if (old_member_id && strcmp(old_member_id, member_id)) {
372 ballot++;
373 candidates_in_sections[0] = 0;
374 candidates_in_sections[1] = 0;
375 candidates_in_sections[2] = 0;
376 candidates_in_sections[3] = 0;
377 }
378 ballot->sections[preference].candidates[candidates_in_sections[preference]++] = candidate_by_key(suggestion_id);
379 old_member_id = member_id;
380 }
381 // print ballots, if logging is enabled:
382 if (logging) {
383 for (i=0; i<ballot_count; i++) {
384 int j;
385 printf("Ballot #%i: ", i+1);
386 for (j=0; j<4; j++) {
387 int k;
388 if (j) printf(", ");
389 printf("preference %i (", j+1);
390 for (k=0; k<ballots[i].sections[j].count; k++) {
391 if (k) printf(",");
392 printf("s#%s", ballots[i].sections[j].candidates[k]->key);
393 }
394 printf(")");
395 }
396 printf(".\n");
397 }
398 }
399 }
400
401 // calculate ranks based on constructed data structures:
402 for (i=0; i<candidate_count; i++) {
403 struct candidate *candidate = loser(i, ballots, ballot_count);
404 candidate->seat = candidate_count - i;
405 if (logging) printf("Assigning rank #%i to suggestion #%s.\n", candidate_count-i, candidate->key);
406 }
407
408 // free ballots[] array:
409 for (i=0; i<ballot_count; i++) {
410 int j;
411 for (j=0; j<4; j++) {
412 if (ballots[i].sections[j].count) {
413 free(ballots[i].sections[j].candidates);
414 }
415 }
416 }
417 free(ballots);
418
419 // write results to database:
420 if (final) {
421 if (logging) printf("Writing final ranks to database.\n");
422 } else {
423 if (logging) printf("Writing ranks to database.\n");
424 }
425 err = write_ranks(db, escaped_initiative_id, final);
426 if (logging) printf("Done.\n");
427
428 // free candidates[] array:
429 free(candidates);
430
431 // return error code of write_ranks() call
432 return err;
433 }
434
435 int main(int argc, char **argv) {
436
437 // variable declarations:
438 int err = 0;
439 int i, count;
440 char *conninfo;
441 PGconn *db;
442 PGresult *res;
443
444 // parse command line:
445 if (argc == 0) return 1;
446 if (argc == 1 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
447 FILE *out;
448 out = argc == 1 ? stderr : stdout;
449 fprintf(out, "\n");
450 fprintf(out, "Usage: %s [-v|--verbose] <conninfo>\n", argv[0]);
451 fprintf(out, "\n");
452 fprintf(out, "<conninfo> is specified by PostgreSQL's libpq,\n");
453 fprintf(out, "see http://www.postgresql.org/docs/9.1/static/libpq-connect.html\n");
454 fprintf(out, "\n");
455 fprintf(out, "Example: %s dbname=liquid_feedback\n", argv[0]);
456 fprintf(out, "\n");
457 return argc == 1 ? 1 : 0;
458 }
459 {
460 size_t len = 0;
461 int argb = 1;
462 if (
463 argc >= 2 &&
464 (!strcmp(argv[1], "-v") || !strcmp(argv[1], "--verbose"))
465 ) {
466 argb = 2;
467 logging = 1;
468 }
469 for (i=argb; i<argc; i++) len += strlen(argv[i]) + 1;
470 conninfo = malloc(len * sizeof(char));
471 if (!conninfo) {
472 fprintf(stderr, "Error: Could not allocate memory for conninfo string.\n");
473 abort();
474 }
475 conninfo[0] = 0;
476 for (i=argb; i<argc; i++) {
477 if (i>argb) strcat(conninfo, " ");
478 strcat(conninfo, argv[i]);
479 }
480 }
481
482 // connect to database:
483 db = PQconnectdb(conninfo);
484 if (!db) {
485 fprintf(stderr, "Error: Could not create database handle.\n");
486 return 1;
487 }
488 if (PQstatus(db) != CONNECTION_OK) {
489 fprintf(stderr, "Could not open connection:\n%s", PQerrorMessage(db));
490 return 1;
491 }
492
493 // check initiatives:
494 res = PQexec(db, "SELECT \"initiative_id\", \"final\" FROM \"initiative_suggestion_order_calculation\"");
495 if (!res) {
496 fprintf(stderr, "Error in pqlib while sending SQL command selecting initiatives to process.\n");
497 err = 1;
498 } else if (PQresultStatus(res) != PGRES_TUPLES_OK) {
499 fprintf(stderr, "Error while executing SQL command selecting initiatives to process:\n%s", PQresultErrorMessage(res));
500 err = 1;
501 PQclear(res);
502 } else if (PQnfields(res) < 2) {
503 fprintf(stderr, "Too few columns returned by SQL command selecting initiatives to process.\n");
504 err = 1;
505 PQclear(res);
506 } else {
507 count = PQntuples(res);
508 if (logging) printf("Number of initiatives to process: %i\n", count);
509 for (i=0; i<count; i++) {
510 char *initiative_id, *escaped_initiative_id;
511 int final;
512 char *cmd;
513 PGresult *res2;
514 initiative_id = PQgetvalue(res, i, 0);
515 final = (PQgetvalue(res, i, 1)[0] == 't') ? 1 : 0;
516 if (logging) printf("Processing initiative #%s:\n", initiative_id);
517 escaped_initiative_id = escapeLiteral(db, initiative_id, strlen(initiative_id));
518 if (!escaped_initiative_id) {
519 fprintf(stderr, "Could not escape literal in memory.\n");
520 abort();
521 }
522 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) {
523 fprintf(stderr, "Could not prepare query string in memory.\n");
524 abort();
525 }
526 res2 = PQexec(db, cmd);
527 free(cmd);
528 if (!res2) {
529 fprintf(stderr, "Error in pqlib while sending SQL command selecting individual suggestion rankings.\n");
530 err = 1;
531 } else if (PQresultStatus(res2) != PGRES_TUPLES_OK) {
532 fprintf(stderr, "Error while executing SQL command selecting individual suggestion rankings:\n%s", PQresultErrorMessage(res));
533 err = 1;
534 PQclear(res2);
535 } else if (PQnfields(res2) < 4) {
536 fprintf(stderr, "Too few columns returned by SQL command selecting individual suggestion rankings.\n");
537 err = 1;
538 PQclear(res2);
539 } else {
540 if (process_initiative(db, res2, escaped_initiative_id, final)) err = 1;
541 PQclear(res2);
542 }
543 freemem(escaped_initiative_id);
544 }
545 PQclear(res);
546 }
547
548 // cleanup and exit:
549 PQfinish(db);
550 if (!err) {
551 if (logging) printf("Successfully terminated.\n");
552 } else {
553 fprintf(stderr, "Exiting with error code %i.\n", err);
554 }
555 return err;
556
557 }

Impressum / About Us