liquid_feedback_core
view lf_update_suggestion_order.c @ 356:4698b68e0942
Calculation of ranks in "lf_update_suggestion_order"
| author | jbe |
|---|---|
| date | Sun Mar 17 09:28:39 2013 +0100 (2013-03-17) |
| parents | accffcefeff7 |
| children | e22a4d2aea2d |
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 res[0] = '\'';
14 res_len = PQescapeStringConn(conn, res+1, str, len, NULL);
15 res[res_len+1] = '\'';
16 res[res_len+2] = 0;
17 return res;
18 }
20 static void freemem(void *ptr) {
21 // to be used for "escapeLiteral" function
22 // provides compatibility for PostgreSQL versions prior 9.0
23 // in future: PQfreemem(ptr);
24 free(ptr);
25 }
27 #define COL_MEMBER_ID 0
28 #define COL_WEIGHT 1
29 #define COL_PREFERENCE 2
30 #define COL_SUGGESTION_ID 3
32 struct candidate {
33 char *key;
34 double score_per_step;
35 int reaches_score;
36 double score;
37 int seat;
38 };
40 static int compare_candidate(struct candidate *c1, struct candidate *c2) {
41 return strcmp(c1->key, c2->key);
42 }
44 static int candidate_count;
45 static struct candidate *candidates;
47 static void register_candidate(char **candidate_key, VISIT visit, int level) {
48 if (visit == postorder || visit == leaf) {
49 struct candidate *candidate;
50 candidate = candidates + (candidate_count++);
51 candidate->key = *candidate_key;
52 candidate->seat = 0;
53 }
54 }
56 static struct candidate *candidate_by_key(char *candidate_key) {
57 struct candidate *candidate;
58 struct candidate compare;
59 compare.key = candidate_key;
60 candidate = bsearch(&compare, candidates, candidate_count, sizeof(struct candidate), (void *)compare_candidate);
61 if (!candidate) {
62 fprintf(stderr, "Candidate not found (should not happen).\n");
63 abort();
64 }
65 return candidate;
66 }
68 struct ballot_section {
69 int count;
70 struct candidate **candidates;
71 };
73 struct ballot {
74 int weight;
75 struct ballot_section sections[4];
76 };
78 static struct candidate *loser(int round_number, struct ballot *ballots, int ballot_count) {
79 int i, j, k;
80 int remaining;
81 for (i=0; i<candidate_count; i++) {
82 candidates[i].score = 0.0;
83 }
84 remaining = candidate_count - round_number;
85 while (1) {
86 double scale;
87 if (remaining <= 1) break;
88 for (i=0; i<candidate_count; i++) {
89 candidates[i].score_per_step = 0.0;
90 candidates[i].reaches_score = 0;
91 }
92 for (i=0; i<ballot_count; i++) {
93 for (j=0; j<4; j++) {
94 int matches = 0;
95 for (k=0; k<ballots[i].sections[j].count; k++) {
96 struct candidate *candidate;
97 candidate = ballots[i].sections[j].candidates[k];
98 if (candidate->score < 1.0 && !candidate->seat) matches++;
99 }
100 if (matches) {
101 double score_inc;
102 score_inc = 1.0 / (double)matches;
103 for (k=0; k<ballots[i].sections[j].count; k++) {
104 struct candidate *candidate;
105 candidate = ballots[i].sections[j].candidates[k];
106 if (candidate->score < 1.0 && !candidate->seat) {
107 candidate->score_per_step += score_inc;
108 }
109 }
110 break;
111 }
112 }
113 }
114 scale = (double)candidate_count;
115 for (i=0; i<candidate_count; i++) {
116 double max_scale;
117 if (candidates[i].score_per_step > 0.0) {
118 max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step;
119 if (max_scale <= scale) {
120 scale = max_scale;
121 candidates[i].reaches_score = 1;
122 }
123 }
124 }
125 for (i=0; i<candidate_count; i++) {
126 if (candidates[i].score_per_step > 0.0) {
127 if (candidates[i].reaches_score) {
128 candidates[i].score = 1.0;
129 remaining--;
130 } else {
131 candidates[i].score += scale * candidates[i].score_per_step;
132 if (candidates[i].score >= 1.0) remaining--;
133 }
134 if (remaining <= 1) break;
135 }
136 }
137 }
138 for (i=candidate_count-1; i>=0; i--) {
139 if (candidates[i].score < 1.0 && !candidates[i].seat) return candidates+i;
140 }
141 fprintf(stderr, "No remaining candidate (should not happen).");
142 abort();
143 }
145 static void process_initiative(PGresult *res) {
146 int ballot_count = 0;
147 struct ballot *ballots;
148 int i;
149 {
150 void *candidate_tree = NULL;
151 int tuple_count;
152 char *old_member_id = NULL;
153 struct ballot *ballot;
154 int candidates_in_sections[4] = {0, };
155 candidate_count = 0;
156 tuple_count = PQntuples(res);
157 for (i=0; i<=tuple_count; i++) {
158 char *member_id, *suggestion_id;
159 if (i<tuple_count) {
160 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
161 suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
162 if (!candidate_tree || !tfind(suggestion_id, &candidate_tree, (void *)strcmp)) {
163 candidate_count++;
164 if (!tsearch(suggestion_id, &candidate_tree, (void *)strcmp)) {
165 fprintf(stderr, "Insufficient memory while inserting into candidate tree.\n");
166 abort();
167 }
168 }
169 }
170 if (i==tuple_count || (old_member_id && strcmp(old_member_id, member_id))) {
171 ballot_count++;
172 }
173 old_member_id = member_id;
174 }
175 printf("Candidate count: %i\n", candidate_count);
176 candidates = malloc(candidate_count * sizeof(struct candidate));
177 if (!candidates) {
178 fprintf(stderr, "Insufficient memory while creating candidate list.\n");
179 abort();
180 }
181 candidate_count = 0;
182 twalk(candidate_tree, (void *)register_candidate);
183 while (candidate_tree) tdelete(*(void **)candidate_tree, &candidate_tree, (void *)strcmp);
184 printf("Ballot count: %i\n", ballot_count);
185 ballots = calloc(ballot_count, sizeof(struct ballot));
186 if (!ballots) {
187 fprintf(stderr, "Insufficient memory while creating ballot list.\n");
188 abort();
189 }
190 ballot = ballots;
191 for (i=0; i<tuple_count; i++) {
192 char *member_id, *suggestion_id;
193 int weight, preference;
194 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
195 suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
196 weight = (int)strtol(PQgetvalue(res, i, COL_WEIGHT), (char **)NULL, 10);
197 if (weight <= 0) {
198 fprintf(stderr, "Unexpected weight value.\n");
199 abort();
200 }
201 preference = (int)strtol(PQgetvalue(res, i, COL_PREFERENCE), (char **)NULL, 10);
202 if (preference < 1 || preference > 4) {
203 fprintf(stderr, "Unexpected preference value.\n");
204 abort();
205 }
206 preference--;
207 ballot->weight = weight;
208 ballot->sections[preference].count++;
209 if (old_member_id && strcmp(old_member_id, member_id)) ballot++;
210 old_member_id = member_id;
211 }
212 for (i=0; i<ballot_count; i++) {
213 int j;
214 for (j=0; j<4; j++) {
215 if (ballots[i].sections[j].count) {
216 ballots[i].sections[j].candidates = malloc(ballots[i].sections[j].count * sizeof(struct candidate *));
217 if (!ballots[i].sections[j].candidates) {
218 fprintf(stderr, "Insufficient memory while creating ballot section.\n");
219 abort();
220 }
221 }
222 }
223 }
224 ballot = ballots;
225 for (i=0; i<=tuple_count; i++) {
226 char *member_id, *suggestion_id;
227 int preference;
228 if (i<tuple_count) {
229 member_id = PQgetvalue(res, i, COL_MEMBER_ID);
230 suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
231 preference = (int)strtol(PQgetvalue(res, i, COL_PREFERENCE), (char **)NULL, 10);
232 preference--;
233 ballot->sections[preference].candidates[candidates_in_sections[preference]++] = candidate_by_key(suggestion_id);
234 }
235 if (i==tuple_count || (old_member_id && strcmp(old_member_id, member_id))) {
236 ballot++;
237 candidates_in_sections[0] = 0;
238 candidates_in_sections[1] = 0;
239 candidates_in_sections[2] = 0;
240 candidates_in_sections[3] = 0;
241 }
242 old_member_id = member_id;
243 }
244 }
246 for (i=0; i<candidate_count; i++) {
247 struct candidate *candidate = loser(i, ballots, ballot_count);
248 candidate->seat = candidate_count - i;
249 }
251 free(candidates);
252 for (i=0; i<ballot_count; i++) {
253 int j;
254 for (j=0; j<4; j++) {
255 if (ballots[i].sections[j].count) {
256 free(ballots[i].sections[j].candidates);
257 }
258 }
259 }
260 free(ballots);
261 }
263 int main(int argc, char **argv) {
265 // variable declarations:
266 int err = 0;
267 int i, count;
268 char *conninfo;
269 PGconn *db;
270 PGresult *res;
272 // parse command line:
273 if (argc == 0) return 1;
274 if (argc == 1 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
275 FILE *out;
276 out = argc == 1 ? stderr : stdout;
277 fprintf(stdout, "\n");
278 fprintf(stdout, "Usage: %s <conninfo>\n", argv[0]);
279 fprintf(stdout, "\n");
280 fprintf(stdout, "<conninfo> is specified by PostgreSQL's libpq,\n");
281 fprintf(stdout, "see http://www.postgresql.org/docs/9.1/static/libpq-connect.html\n");
282 fprintf(stdout, "\n");
283 fprintf(stdout, "Example: %s dbname=liquid_feedback\n", argv[0]);
284 fprintf(stdout, "\n");
285 return argc == 1 ? 1 : 0;
286 }
287 {
288 size_t len = 0;
289 for (i=1; i<argc; i++) len += strlen(argv[i]) + 1;
290 conninfo = malloc(len * sizeof(char));
291 if (!conninfo) {
292 fprintf(stderr, "Error: Could not allocate memory for conninfo string\n");
293 return 1;
294 }
295 conninfo[0] = 0;
296 for (i=1; i<argc; i++) {
297 if (i>1) strcat(conninfo, " ");
298 strcat(conninfo, argv[i]);
299 }
300 }
302 // connect to database:
303 db = PQconnectdb(conninfo);
304 if (!db) {
305 fprintf(stderr, "Error: Could not create database handle\n");
306 return 1;
307 }
308 if (PQstatus(db) != CONNECTION_OK) {
309 fprintf(stderr, "Could not open connection:\n%s", PQerrorMessage(db));
310 return 1;
311 }
313 // check initiatives:
314 res = PQexec(db, "SELECT \"initiative_id\", \"final\" FROM \"initiative_suggestion_order_calculation\"");
315 if (!res) {
316 fprintf(stderr, "Error in pqlib while sending SQL command selecting open issues\n");
317 err = 1;
318 } else if (PQresultStatus(res) != PGRES_TUPLES_OK) {
319 fprintf(stderr, "Error while executing SQL command selecting open issues:\n%s", PQresultErrorMessage(res));
320 err = 1;
321 PQclear(res);
322 } else {
323 count = PQntuples(res);
324 printf("Number of initiatives to process: %i\n", count);
325 for (i=0; i<count; i++) {
326 char *initiative_id, *escaped_initiative_id;
327 char *cmd;
328 PGresult *res2;
329 initiative_id = PQgetvalue(res, i, 0);
330 printf("Processing initiative_id: %s\n", initiative_id);
331 escaped_initiative_id = escapeLiteral(db, initiative_id, strlen(initiative_id));
332 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) {
333 fprintf(stderr, "Could not prepare query string in memory.\n");
334 abort();
335 }
336 res2 = PQexec(db, cmd);
337 free(cmd);
338 if (!res2) {
339 fprintf(stderr, "Error in pqlib while sending SQL command selecting open issues\n");
340 err = 1;
341 } else if (PQresultStatus(res2) != PGRES_TUPLES_OK) {
342 fprintf(stderr, "Error while executing SQL command selecting open issues:\n%s", PQresultErrorMessage(res));
343 err = 1;
344 PQclear(res2);
345 } else if (PQnfields(res2) < 4) {
346 fprintf(stderr, "Too few columns returned by SQL command selecting open issues.\n");
347 err = 1;
348 PQclear(res2);
349 } else {
350 if (PQntuples(res2) == 0) {
351 printf("Nothing to do.\n");
352 } else {
353 process_initiative(res2);
354 }
355 PQclear(res2);
356 }
357 freemem(escaped_initiative_id);
358 }
359 PQclear(res);
360 }
362 // cleanup and exit
363 PQfinish(db);
364 return err;
366 }