liquid_feedback_core: d93428e4edad lf_update_issue

liquid_feedback_core

view lf_update_issue_order.c @ 395:d93428e4edad

Always delete ordering ranks of issues (lf_update_issue_order.c)

author	jbe
date	Fri Oct 11 13:05:29 2013 +0200 (2013-10-11)
parents	326dc0c3b859
children	806561cce3b1

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 "issue_supporter_in_admission_state" view in function main():

31 #define COL_MEMBER_ID 0

32 #define COL_WEIGHT 1

33 #define COL_ISSUE_ID 2

35 // data structure for a candidate (in this case a suggestion) to the proportional runoff system:

36 struct candidate {

37 char *key; // identifier of the candidate, which is the "suggestion_id" string

38 double score_per_step; // added score per step

39 double score; // current score of candidate; a score of 1.0 is needed to survive a round

40 int seat; // equals 0 for unseated candidates, or contains rank number

41 };

43 // compare two integers stored as strings (invocation like strcmp):

44 static int compare_id(char *id1, char *id2) {

45 int ldiff;

46 ldiff = strlen(id1) - strlen(id2);

47 if (ldiff) return ldiff;

48 else return strcmp(id1, id2);

49 }

51 // compare two candidates by their key (invocation like strcmp):

52 static int compare_candidate(struct candidate *c1, struct candidate *c2) {

53 return compare_id(c1->key, c2->key);

54 }

56 // candidates are stored as global variables due to the constrained twalk() interface:

57 static int candidate_count;

58 static struct candidate *candidates;

60 // function to be passed to twalk() to store candidates ordered in candidates[] array:

61 static void register_candidate(char **candidate_key, VISIT visit, int level) {

62 if (visit == postorder || visit == leaf) {

63 struct candidate *candidate;

64 candidate = candidates + (candidate_count++);

65 candidate->key = *candidate_key;

66 candidate->seat = 0;

67 if (logging) printf("Candidate #%i is suggestion #%s.\n", candidate_count, candidate->key);

68 }

69 }

71 // performs a binary search in candidates[] array to lookup a candidate by its key (which is the suggestion_id):

72 static struct candidate *candidate_by_key(char *candidate_key) {

73 struct candidate *candidate;

74 struct candidate compare;

75 compare.key = candidate_key;

76 candidate = bsearch(&compare, candidates, candidate_count, sizeof(struct candidate), (void *)compare_candidate);

77 if (!candidate) {

78 fprintf(stderr, "Candidate not found (should not happen).\n");

79 abort();

80 }

81 return candidate;

82 }

84 // ballot of the proportional runoff system:

85 struct ballot {

86 int weight; // if weight is greater than 1, then the ballot is counted multiple times

87 int count;

88 struct candidate **candidates;

89 };

91 // determine candidate, which is assigned the next seat (starting with the worst rank):

92 static struct candidate *loser(int round_number, struct ballot *ballots, int ballot_count) {

93 int i, j; // index variables for loops

94 int remaining; // remaining candidates to be seated

95 // reset scores of all candidates:

96 for (i=0; i<candidate_count; i++) {

97 candidates[i].score = 0.0;

98 }

99 // calculate remaining candidates to be seated:

100 remaining = candidate_count - round_number;

101 // repeat following loop, as long as there is more than one remaining candidate:

102 while (remaining > 1) {

103 if (logging) printf("There are %i remaining candidates.\n", remaining);

104 double scale; // factor to be later multiplied with score_per_step:

105 // reset score_per_step for all candidates:

106 for (i=0; i<candidate_count; i++) {

107 candidates[i].score_per_step = 0.0;

108 }

109 // calculate score_per_step for all candidates:

110 for (i=0; i<ballot_count; i++) {

111 int matches = 0;

112 for (j=0; j<ballots[i].count; j++) {

113 struct candidate *candidate;

114 candidate = ballots[i].candidates[j];

115 if (candidate->score < 1.0 && !candidate->seat) matches++;

116 }

117 if (matches) {

118 double score_inc;

119 score_inc = (double)ballots[i].weight / (double)matches;

120 for (j=0; j<ballots[i].count; j++) {

121 struct candidate *candidate;

122 candidate = ballots[i].candidates[j];

123 if (candidate->score < 1.0 && !candidate->seat) {

124 candidate->score_per_step += score_inc;

125 }

126 }

127 }

128 }

129 // calculate scale factor:

130 scale = (double)0.0; // 0.0 is used to indicate that there is no value yet

131 for (i=0; i<candidate_count; i++) {

132 double max_scale;

133 if (candidates[i].score_per_step > 0.0) {

134 max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step;

135 if (scale == 0.0 || max_scale <= scale) {

136 scale = max_scale;

137 }

138 }

139 }

140 // add scale*score_per_step to each candidates score:

141 for (i=0; i<candidate_count; i++) {

142 int log_candidate = 0;

143 if (logging && candidates[i].score < 1.0 && !candidates[i].seat) log_candidate = 1;

144 if (log_candidate) printf("Score for suggestion #%s = %.4f+%.4f*%.4f", candidates[i].key, candidates[i].score, scale, candidates[i].score_per_step);

145 if (candidates[i].score_per_step > 0.0) {

146 double max_scale;

147 max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step;

148 if (max_scale == scale) {

149 // score of 1.0 should be reached, so we set score directly to avoid floating point errors:

150 candidates[i].score = 1.0;

151 remaining--;

152 } else {

153 candidates[i].score += scale * candidates[i].score_per_step;

154 if (candidates[i].score >= 1.0) remaining--;

155 }

156 }

157 if (log_candidate) {

158 if (candidates[i].score >= 1.0) printf("=1\n");

159 else printf("=%.4f\n", candidates[i].score);

160 }

161 // when there is only one candidate remaining, then break inner (and thus outer) loop:

162 if (remaining <= 1) {

163 break;

164 }

165 }

166 }

167 // return remaining candidate:

168 for (i=0; i<candidate_count; i++) {

169 if (candidates[i].score < 1.0 && !candidates[i].seat) return candidates+i;

170 }

171 // if there is no remaining candidate, then something went wrong:

172 fprintf(stderr, "No remaining candidate (should not happen).");

173 abort();

174 }

175

176 // write results to database:

177 static int write_ranks(PGconn *db, char *escaped_area_id) {

178 PGresult *res;

179 char *cmd;

180 int i;

181 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) {

182 fprintf(stderr, "Could not prepare query string in memory.\n");

183 abort();

184 }

185 res = PQexec(db, cmd);

186 free(cmd);

187 if (!res) {

188 fprintf(stderr, "Error in pqlib while sending SQL command to initiate issue update.\n");

189 return 1;

190 } else if (

191 PQresultStatus(res) != PGRES_COMMAND_OK &&

192 PQresultStatus(res) != PGRES_TUPLES_OK

193 ) {

194 fprintf(stderr, "Error while executing SQL command to initiate issue update:\n%s", PQresultErrorMessage(res));

195 PQclear(res);

196 return 1;

197 } else {

198 PQclear(res);

199 }

200 for (i=0; i<candidate_count; i++) {

201 char *escaped_issue_id;

202 escaped_issue_id = escapeLiteral(db, candidates[i].key, strlen(candidates[i].key));

203 if (!escaped_issue_id) {

204 fprintf(stderr, "Could not escape literal in memory.\n");

205 abort();

206 }

207 if (asprintf(&cmd, "UPDATE \"issue\" SET \"order_in_admission_state\" = %i WHERE \"id\" = %s", candidates[i].seat, escaped_issue_id) < 0) {

208 fprintf(stderr, "Could not prepare query string in memory.\n");

209 abort();

210 }

211 freemem(escaped_issue_id);

212 res = PQexec(db, cmd);

213 free(cmd);

214 if (!res) {

215 fprintf(stderr, "Error in pqlib while sending SQL command to update issue order.\n");

216 } else if (

217 PQresultStatus(res) != PGRES_COMMAND_OK &&

218 PQresultStatus(res) != PGRES_TUPLES_OK

219 ) {

220 fprintf(stderr, "Error while executing SQL command to update issue order:\n%s", PQresultErrorMessage(res));

221 PQclear(res);

222 } else {

223 PQclear(res);

224 continue;

225 }

226 res = PQexec(db, "ROLLBACK");

227 if (res) PQclear(res);

228 return 1;

229 }

230 res = PQexec(db, "COMMIT");

231 if (!res) {

232 fprintf(stderr, "Error in pqlib while sending SQL command to commit transaction.\n");

233 return 1;

234 } else if (

235 PQresultStatus(res) != PGRES_COMMAND_OK &&

236 PQresultStatus(res) != PGRES_TUPLES_OK

237 ) {

238 fprintf(stderr, "Error while executing SQL command to commit transaction:\n%s", PQresultErrorMessage(res));

239 PQclear(res);

240 return 1;

241 } else {

242 PQclear(res);

243 return 0;

244 }

245 }

246

247 // calculate ordering of issues in admission state for an area and call write_ranks() to write it to database:

248 static int process_area(PGconn *db, PGresult *res, char *escaped_area_id) {

249 int err; // variable to store an error condition (0 = success)

250 int ballot_count = 1; // number of ballots, must be initiatized to 1, due to loop below

251 struct ballot *ballots; // data structure containing the ballots

252 int i; // index variable for loops

253 // create candidates[] and ballots[] arrays:

254 {

255 void *candidate_tree = NULL; // temporary structure to create a sorted unique list of all candidate keys

256 int tuple_count; // number of tuples returned from the database

257 char *old_member_id = NULL; // old member_id to be able to detect a new ballot in loops

258 struct ballot *ballot; // pointer to current ballot

259 int candidates_in_ballot = 0; // number of candidates in ballot

260 // reset candidate count:

261 candidate_count = 0;

262 // determine number of tuples:

263 tuple_count = PQntuples(res);

264 // trivial case, when there are no tuples:

265 if (!tuple_count) {

266 // write results to database:

267 if (logging) printf("No supporters for any issue. Deleting ranks in database.\n");

268 err = write_ranks(db, escaped_area_id);

269 if (logging) printf("Done.\n");

270 return 0;

271 }

272 // calculate ballot_count and generate set of candidate keys (suggestion_id is used as key):

273 for (i=0; i<tuple_count; i++) {

274 char *member_id, *issue_id;

275 member_id = PQgetvalue(res, i, COL_MEMBER_ID);

276 issue_id = PQgetvalue(res, i, COL_ISSUE_ID);

277 if (!candidate_tree || !tfind(issue_id, &candidate_tree, (void *)compare_id)) {

278 candidate_count++;

279 if (!tsearch(issue_id, &candidate_tree, (void *)compare_id)) {

280 fprintf(stderr, "Insufficient memory while inserting into candidate tree.\n");

281 abort();

282 }

283 }

284 if (old_member_id && strcmp(old_member_id, member_id)) ballot_count++;

285 old_member_id = member_id;

286 }

287 // allocate memory for candidates[] array:

288 candidates = malloc(candidate_count * sizeof(struct candidate));

289 if (!candidates) {

290 fprintf(stderr, "Insufficient memory while creating candidate list.\n");

291 abort();

292 }

293 // transform tree of candidate keys into sorted array:

294 candidate_count = 0; // needed by register_candidate()

295 twalk(candidate_tree, (void *)register_candidate);

296 // free memory of tree structure (tdestroy() is not available on all platforms):

297 while (candidate_tree) tdelete(*(void **)candidate_tree, &candidate_tree, (void *)compare_id);

298 // allocate memory for ballots[] array:

299 ballots = calloc(ballot_count, sizeof(struct ballot));

300 if (!ballots) {

301 fprintf(stderr, "Insufficient memory while creating ballot list.\n");

302 abort();

303 }

304 // set ballot weights, determine ballot section sizes, and verify preference values:

305 ballot = ballots;

306 old_member_id = NULL;

307 for (i=0; i<tuple_count; i++) {

308 char *member_id;

309 int weight;

310 member_id = PQgetvalue(res, i, COL_MEMBER_ID);

311 weight = (int)strtol(PQgetvalue(res, i, COL_WEIGHT), (char **)NULL, 10);

312 if (weight <= 0) {

313 fprintf(stderr, "Unexpected weight value.\n");

314 free(ballots);

315 free(candidates);

316 return 1;

317 }

318 if (old_member_id && strcmp(old_member_id, member_id)) ballot++;

319 ballot->weight = weight;

320 ballot->count++;

321 old_member_id = member_id;

322 }

323 // allocate memory for ballot sections:

324 for (i=0; i<ballot_count; i++) {

325 if (ballots[i].count) {

326 ballots[i].candidates = malloc(ballots[i].count * sizeof(struct candidate *));

327 if (!ballots[i].candidates) {

328 fprintf(stderr, "Insufficient memory while creating ballot section.\n");

329 abort();

330 }

331 }

332 }

333 // fill ballot sections with candidate references:

334 old_member_id = NULL;

335 ballot = ballots;

336 for (i=0; i<tuple_count; i++) {

337 char *member_id, *issue_id;

338 member_id = PQgetvalue(res, i, COL_MEMBER_ID);

339 issue_id = PQgetvalue(res, i, COL_ISSUE_ID);

340 if (old_member_id && strcmp(old_member_id, member_id)) {

341 ballot++;

342 candidates_in_ballot = 0;

343 }

344 ballot->candidates[candidates_in_ballot++] = candidate_by_key(issue_id);

345 old_member_id = member_id;

346 }

347 // print ballots, if logging is enabled:

348 if (logging) {

349 for (i=0; i<ballot_count; i++) {

350 int j;

351 printf("Ballot #%i: ", i+1);

352 for (j=0; j<ballots[i].count; j++) {

353 if (!j) printf("issues ");

354 else printf(", ");

355 printf("#%s", ballots[i].candidates[j]->key);

356 }

357 // if (!j) printf("empty"); // should not happen

358 printf(".\n");

359 }

360 }

361 }

362

363 // calculate ranks based on constructed data structures:

364 for (i=0; i<candidate_count; i++) {

365 struct candidate *candidate = loser(i, ballots, ballot_count);

366 candidate->seat = candidate_count - i;

367 if (logging) printf("Assigning rank #%i to issue #%s.\n", candidate_count-i, candidate->key);

368 }

369

370 // free ballots[] array:

371 for (i=0; i<ballot_count; i++) {

372 // if (ballots[i].count) { // count should not be zero

373 free(ballots[i].candidates);

374 // }

375 }

376 free(ballots);

377

378 // write results to database:

379 if (logging) printf("Writing ranks to database.\n");

380 err = write_ranks(db, escaped_area_id);

381 if (logging) printf("Done.\n");

382

383 // free candidates[] array:

384 free(candidates);

385

386 // return error code of write_ranks() call

387 return err;

388 }

389

390 int main(int argc, char **argv) {

391

392 // variable declarations:

393 int err = 0;

394 int i, count;

395 char *conninfo;

396 PGconn *db;

397 PGresult *res;

398

399 // parse command line:

400 if (argc == 0) return 1;

401 if (argc == 1 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {

402 FILE *out;

403 out = argc == 1 ? stderr : stdout;

404 fprintf(out, "\n");

405 fprintf(out, "Usage: %s [-v|--verbose] <conninfo>\n", argv[0]);

406 fprintf(out, "\n");

407 fprintf(out, "<conninfo> is specified by PostgreSQL's libpq,\n");

408 fprintf(out, "see http://www.postgresql.org/docs/9.1/static/libpq-connect.html\n");

409 fprintf(out, "\n");

410 fprintf(out, "Example: %s dbname=liquid_feedback\n", argv[0]);

411 fprintf(out, "\n");

412 return argc == 1 ? 1 : 0;

413 }

414 {

415 size_t len = 0;

416 int argb = 1;

417 if (

418 argc >= 2 &&

419 (!strcmp(argv[1], "-v") || !strcmp(argv[1], "--verbose"))

420 ) {

421 argb = 2;

422 logging = 1;

423 }

424 for (i=argb; i<argc; i++) len += strlen(argv[i]) + 1;

425 conninfo = malloc(len * sizeof(char));

426 if (!conninfo) {

427 fprintf(stderr, "Error: Could not allocate memory for conninfo string.\n");

428 abort();

429 }

430 conninfo[0] = 0;

431 for (i=argb; i<argc; i++) {

432 if (i>argb) strcat(conninfo, " ");

433 strcat(conninfo, argv[i]);

434 }

435 }

436

437 // connect to database:

438 db = PQconnectdb(conninfo);

439 if (!db) {

440 fprintf(stderr, "Error: Could not create database handle.\n");

441 return 1;

442 }

443 if (PQstatus(db) != CONNECTION_OK) {

444 fprintf(stderr, "Could not open connection:\n%s", PQerrorMessage(db));

445 return 1;

446 }

447

448 // go through areas:

449 res = PQexec(db, "SELECT \"id\" FROM \"area\"");

450 if (!res) {

451 fprintf(stderr, "Error in pqlib while sending SQL command selecting areas to process.\n");

452 err = 1;

453 } else if (PQresultStatus(res) != PGRES_TUPLES_OK) {

454 fprintf(stderr, "Error while executing SQL command selecting areas to process:\n%s", PQresultErrorMessage(res));

455 err = 1;

456 PQclear(res);

457 } else if (PQnfields(res) < 1) {

458 fprintf(stderr, "Too few columns returned by SQL command selecting areas to process.\n");

459 err = 1;

460 PQclear(res);

461 } else {

462 count = PQntuples(res);

463 if (logging) printf("Number of areas to process: %i\n", count);

464 for (i=0; i<count; i++) {

465 char *area_id, *escaped_area_id;

466 char *cmd;

467 PGresult *res2;

468 area_id = PQgetvalue(res, i, 0);

469 if (logging) printf("Processing area #%s:\n", area_id);

470 escaped_area_id = escapeLiteral(db, area_id, strlen(area_id));

471 if (!escaped_area_id) {

472 fprintf(stderr, "Could not escape literal in memory.\n");

473 abort();

474 }

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) {

476 fprintf(stderr, "Could not prepare query string in memory.\n");

477 abort();

478 }

479 res2 = PQexec(db, cmd);

480 free(cmd);

481 if (!res2) {

482 fprintf(stderr, "Error in pqlib while sending SQL command selecting issue supporter in admission state.\n");

483 err = 1;

484 } else if (PQresultStatus(res2) != PGRES_TUPLES_OK) {

485 fprintf(stderr, "Error while executing SQL command selecting issue supporter in admission state:\n%s", PQresultErrorMessage(res));

486 err = 1;

487 PQclear(res2);

488 } else if (PQnfields(res2) < 3) {

489 fprintf(stderr, "Too few columns returned by SQL command selecting issue supporter in admission state.\n");

490 err = 1;

491 PQclear(res2);

492 } else {

493 if (process_area(db, res2, escaped_area_id)) err = 1;

494 PQclear(res2);

495 }

496 freemem(escaped_area_id);

497 }

498 PQclear(res);

499 }

500

501 // cleanup and exit:

502 PQfinish(db);

503 if (!err) {

504 if (logging) printf("Successfully terminated.\n");

505 } else {

506 fprintf(stderr, "Exiting with error code %i.\n", err);

507 }

508 return err;

509

510 }