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