jbe@352: #include <stdlib.h>
jbe@352: #include <stdio.h>
jbe@352: #include <string.h>
jbe@352: #include <libpq-fe.h>
jbe@352: #include <search.h>
jbe@352: 
jbe@352: static char *escapeLiteral(PGconn *conn, const char *str, size_t len) {
jbe@352:   // provides compatibility for PostgreSQL versions prior 9.0
jbe@352:   // in future: return PQescapeLiteral(conn, str, len);
jbe@352:   char *res;
jbe@352:   size_t res_len;
jbe@352:   res = malloc(2*len+3);
jbe@358:   if (!res) return NULL;
jbe@352:   res[0] = '\'';
jbe@352:   res_len = PQescapeStringConn(conn, res+1, str, len, NULL);
jbe@352:   res[res_len+1] = '\'';
jbe@352:   res[res_len+2] = 0;
jbe@352:   return res;
jbe@352: }
jbe@352: 
jbe@352: static void freemem(void *ptr) {
jbe@352:   // to be used for "escapeLiteral" function
jbe@352:   // provides compatibility for PostgreSQL versions prior 9.0
jbe@352:   // in future: PQfreemem(ptr);
jbe@352:   free(ptr);
jbe@352: }
jbe@352: 
jbe@352: #define COL_MEMBER_ID     0
jbe@352: #define COL_WEIGHT        1
jbe@352: #define COL_PREFERENCE    2
jbe@352: #define COL_SUGGESTION_ID 3
jbe@352: 
jbe@353: struct candidate {
jbe@353:   char *key;
jbe@356:   double score_per_step;
jbe@356:   int reaches_score;
jbe@353:   double score;
jbe@353:   int seat;
jbe@353: };
jbe@353: 
jbe@353: static int compare_candidate(struct candidate *c1, struct candidate *c2) {
jbe@353:   return strcmp(c1->key, c2->key);
jbe@353: }
jbe@352: 
jbe@353: static int candidate_count;
jbe@353: static struct candidate *candidates;
jbe@353: 
jbe@353: static void register_candidate(char **candidate_key, VISIT visit, int level) {
jbe@352:   if (visit == postorder || visit == leaf) {
jbe@353:     struct candidate *candidate;
jbe@353:     candidate = candidates + (candidate_count++);
jbe@353:     candidate->key   = *candidate_key;
jbe@353:     candidate->seat  = 0;
jbe@352:   }
jbe@352: }
jbe@352: 
jbe@353: static struct candidate *candidate_by_key(char *candidate_key) {
jbe@353:   struct candidate *candidate;
jbe@353:   struct candidate compare;
jbe@353:   compare.key = candidate_key;
jbe@353:   candidate = bsearch(&compare, candidates, candidate_count, sizeof(struct candidate), (void *)compare_candidate);
jbe@353:   if (!candidate) {
jbe@356:     fprintf(stderr, "Candidate not found (should not happen).\n");
jbe@352:     abort();
jbe@352:   }
jbe@353:   return candidate;
jbe@352: }
jbe@352: 
jbe@352: struct ballot_section {
jbe@352:   int count;
jbe@353:   struct candidate **candidates;
jbe@352: };
jbe@352: 
jbe@352: struct ballot {
jbe@352:   int weight;
jbe@352:   struct ballot_section sections[4];
jbe@352: };
jbe@352: 
jbe@356: static struct candidate *loser(int round_number, struct ballot *ballots, int ballot_count) {
jbe@356:   int i, j, k;
jbe@356:   int remaining;
jbe@356:   for (i=0; i<candidate_count; i++) {
jbe@356:     candidates[i].score = 0.0;
jbe@356:   }
jbe@356:   remaining = candidate_count - round_number;
jbe@356:   while (1) {
jbe@356:     double scale;
jbe@356:     if (remaining <= 1) break;
jbe@356:     for (i=0; i<candidate_count; i++) {
jbe@356:       candidates[i].score_per_step = 0.0;
jbe@356:       candidates[i].reaches_score = 0;
jbe@356:     }
jbe@356:     for (i=0; i<ballot_count; i++) {
jbe@356:       for (j=0; j<4; j++) {
jbe@356:         int matches = 0;
jbe@356:         for (k=0; k<ballots[i].sections[j].count; k++) {
jbe@356:           struct candidate *candidate;
jbe@356:           candidate = ballots[i].sections[j].candidates[k];
jbe@356:           if (candidate->score < 1.0 && !candidate->seat) matches++;
jbe@356:         }
jbe@356:         if (matches) {
jbe@356:           double score_inc;
jbe@356:           score_inc = 1.0 / (double)matches;
jbe@356:           for (k=0; k<ballots[i].sections[j].count; k++) {
jbe@356:             struct candidate *candidate;
jbe@356:             candidate = ballots[i].sections[j].candidates[k];
jbe@356:             if (candidate->score < 1.0 && !candidate->seat) {
jbe@356:               candidate->score_per_step += score_inc;
jbe@356:             }
jbe@356:           }
jbe@356:           break;
jbe@356:         }
jbe@356:       }
jbe@356:     }
jbe@356:     scale = (double)candidate_count;
jbe@356:     for (i=0; i<candidate_count; i++) {
jbe@356:       double max_scale;
jbe@356:       if (candidates[i].score_per_step > 0.0) {
jbe@356:         max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step;
jbe@356:         if (max_scale <= scale) {
jbe@356:           scale = max_scale;
jbe@356:           candidates[i].reaches_score = 1;
jbe@356:         }
jbe@356:       }
jbe@356:     }
jbe@356:     for (i=0; i<candidate_count; i++) {
jbe@356:       if (candidates[i].score_per_step > 0.0) {
jbe@356:         if (candidates[i].reaches_score) {
jbe@356:           candidates[i].score = 1.0;
jbe@356:           remaining--;
jbe@356:         } else {
jbe@356:           candidates[i].score += scale * candidates[i].score_per_step;
jbe@356:           if (candidates[i].score >= 1.0) remaining--;
jbe@356:         }
jbe@356:         if (remaining <= 1) break;
jbe@356:       }
jbe@356:     }
jbe@356:   }
jbe@356:   for (i=candidate_count-1; i>=0; i--) {
jbe@356:     if (candidates[i].score < 1.0 && !candidates[i].seat) return candidates+i;
jbe@356:   }
jbe@356:   fprintf(stderr, "No remaining candidate (should not happen).");
jbe@356:   abort();
jbe@356: }
jbe@356: 
jbe@358: static int write_ranks(PGconn *db, char *escaped_initiative_id) {
jbe@358:   PGresult *res;
jbe@358:   char *cmd;
jbe@358:   int i;
jbe@358:   if (asprintf(&cmd, "BEGIN; UPDATE \"suggestion\" SET \"proportional_order\" = NULL WHERE \"initiative_id\" = %s", escaped_initiative_id) < 0) {
jbe@358:     fprintf(stderr, "Could not prepare query string in memory.\n");
jbe@358:     abort();
jbe@358:   }
jbe@358:   res = PQexec(db, cmd);
jbe@358:   free(cmd);
jbe@358:   if (!res) {
jbe@358:     fprintf(stderr, "Error in pqlib while sending SQL command to initiate suggestion update.\n");
jbe@358:     return 1;
jbe@358:   } else if (
jbe@358:     PQresultStatus(res) != PGRES_COMMAND_OK &&
jbe@358:     PQresultStatus(res) != PGRES_TUPLES_OK
jbe@358:   ) {
jbe@358:     fprintf(stderr, "Error while executing SQL command to initiate suggestion update:\n%s", PQresultErrorMessage(res));
jbe@358:     PQclear(res);
jbe@358:     return 1;
jbe@358:   } else {
jbe@358:     PQclear(res);
jbe@358:   }
jbe@358:   for (i=0; i<candidate_count; i++) {
jbe@358:     char *escaped_suggestion_id;
jbe@358:     escaped_suggestion_id = escapeLiteral(db, candidates[i].key, strlen(candidates[i].key));
jbe@358:     if (!escaped_suggestion_id) {
jbe@358:       fprintf(stderr, "Could not escape literal in memory.\n");
jbe@358:       abort();
jbe@358:     }
jbe@358:     if (asprintf(&cmd, "UPDATE \"suggestion\" SET \"proportional_order\" = %i WHERE \"id\" = %s", candidates[i].seat, escaped_suggestion_id) < 0) {
jbe@358:       fprintf(stderr, "Could not prepare query string in memory.\n");
jbe@358:       abort();
jbe@358:     }
jbe@358:     freemem(escaped_suggestion_id);
jbe@358:     res = PQexec(db, cmd);
jbe@358:     free(cmd);
jbe@358:     if (!res) {
jbe@358:       fprintf(stderr, "Error in pqlib while sending SQL command to update suggestion order.\n");
jbe@358:     } else if (
jbe@358:       PQresultStatus(res) != PGRES_COMMAND_OK &&
jbe@358:       PQresultStatus(res) != PGRES_TUPLES_OK
jbe@358:     ) {
jbe@358:       fprintf(stderr, "Error while executing SQL command to update suggestion order:\n%s", PQresultErrorMessage(res));
jbe@358:       PQclear(res);
jbe@358:     } else {
jbe@358:       PQclear(res);
jbe@358:       continue;
jbe@358:     }
jbe@358:     res = PQexec(db, "ROLLBACK");
jbe@358:     if (res) PQclear(res);
jbe@358:     return 1;
jbe@358:   }
jbe@358:   res = PQexec(db, "COMMIT");
jbe@358:   if (!res) {
jbe@358:     fprintf(stderr, "Error in pqlib while sending SQL command to commit transaction.\n");
jbe@358:     return 1;
jbe@358:   } else if (
jbe@358:     PQresultStatus(res) != PGRES_COMMAND_OK &&
jbe@358:     PQresultStatus(res) != PGRES_TUPLES_OK
jbe@358:   ) {
jbe@358:     fprintf(stderr, "Error while executing SQL command to commit transaction:\n%s", PQresultErrorMessage(res));
jbe@358:     PQclear(res);
jbe@358:     return 1;
jbe@358:   } else {
jbe@358:     PQclear(res);
jbe@358:     return 0;
jbe@358:   }
jbe@358: }
jbe@358: 
jbe@358: static int process_initiative(PGconn *db, PGresult *res, char *escaped_initiative_id) {
jbe@358:   int err;
jbe@352:   int ballot_count = 0;
jbe@356:   struct ballot *ballots;
jbe@355:   int i;
jbe@355:   {
jbe@355:     void *candidate_tree = NULL;
jbe@355:     int tuple_count;
jbe@355:     char *old_member_id = NULL;
jbe@355:     struct ballot *ballot;
jbe@355:     int candidates_in_sections[4] = {0, };
jbe@355:     candidate_count = 0;
jbe@355:     tuple_count = PQntuples(res);
jbe@355:     for (i=0; i<=tuple_count; i++) {
jbe@355:       char *member_id, *suggestion_id;
jbe@355:       if (i<tuple_count) {
jbe@355:         member_id = PQgetvalue(res, i, COL_MEMBER_ID);
jbe@355:         suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
jbe@355:         if (!candidate_tree || !tfind(suggestion_id, &candidate_tree, (void *)strcmp)) {
jbe@355:           candidate_count++;
jbe@355:           if (!tsearch(suggestion_id, &candidate_tree, (void *)strcmp)) {
jbe@356:             fprintf(stderr, "Insufficient memory while inserting into candidate tree.\n");
jbe@355:             abort();
jbe@355:           }
jbe@352:         }
jbe@352:       }
jbe@355:       if (i==tuple_count || (old_member_id && strcmp(old_member_id, member_id))) {
jbe@355:         ballot_count++;
jbe@355:       }
jbe@355:       old_member_id = member_id;
jbe@352:     }
jbe@355:     printf("Candidate count: %i\n", candidate_count);
jbe@355:     candidates = malloc(candidate_count * sizeof(struct candidate));
jbe@355:     if (!candidates) {
jbe@356:       fprintf(stderr, "Insufficient memory while creating candidate list.\n");
jbe@353:       abort();
jbe@352:     }
jbe@355:     candidate_count = 0;
jbe@355:     twalk(candidate_tree, (void *)register_candidate);
jbe@355:     while (candidate_tree) tdelete(*(void **)candidate_tree, &candidate_tree, (void *)strcmp);
jbe@355:     printf("Ballot count: %i\n", ballot_count);
jbe@355:     ballots = calloc(ballot_count, sizeof(struct ballot));
jbe@355:     if (!ballots) {
jbe@356:       fprintf(stderr, "Insufficient memory while creating ballot list.\n");
jbe@353:       abort();
jbe@352:     }
jbe@355:     ballot = ballots;
jbe@355:     for (i=0; i<tuple_count; i++) {
jbe@355:       char *member_id, *suggestion_id;
jbe@355:       int weight, preference;
jbe@352:       member_id = PQgetvalue(res, i, COL_MEMBER_ID);
jbe@352:       suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
jbe@355:       weight = (int)strtol(PQgetvalue(res, i, COL_WEIGHT), (char **)NULL, 10);
jbe@355:       if (weight <= 0) {
jbe@356:         fprintf(stderr, "Unexpected weight value.\n");
jbe@358:         free(ballots);
jbe@358:         free(candidates);
jbe@358:         return 1;
jbe@355:       }
jbe@352:       preference = (int)strtol(PQgetvalue(res, i, COL_PREFERENCE), (char **)NULL, 10);
jbe@352:       if (preference < 1 || preference > 4) {
jbe@356:         fprintf(stderr, "Unexpected preference value.\n");
jbe@358:         free(ballots);
jbe@358:         free(candidates);
jbe@358:         return 1;
jbe@352:       }
jbe@352:       preference--;
jbe@355:       ballot->weight = weight;
jbe@355:       ballot->sections[preference].count++;
jbe@355:       if (old_member_id && strcmp(old_member_id, member_id)) ballot++;
jbe@355:       old_member_id = member_id;
jbe@355:     }
jbe@355:     for (i=0; i<ballot_count; i++) {
jbe@355:       int j;
jbe@355:       for (j=0; j<4; j++) {
jbe@355:         if (ballots[i].sections[j].count) {
jbe@355:           ballots[i].sections[j].candidates = malloc(ballots[i].sections[j].count * sizeof(struct candidate *));
jbe@355:           if (!ballots[i].sections[j].candidates) {
jbe@356:             fprintf(stderr, "Insufficient memory while creating ballot section.\n");
jbe@355:             abort();
jbe@355:           }
jbe@355:         }
jbe@355:       }
jbe@352:     }
jbe@355:     ballot = ballots;
jbe@355:     for (i=0; i<=tuple_count; i++) {
jbe@355:       char *member_id, *suggestion_id;
jbe@355:       int preference;
jbe@355:       if (i<tuple_count) {
jbe@355:         member_id = PQgetvalue(res, i, COL_MEMBER_ID);
jbe@355:         suggestion_id = PQgetvalue(res, i, COL_SUGGESTION_ID);
jbe@355:         preference = (int)strtol(PQgetvalue(res, i, COL_PREFERENCE), (char **)NULL, 10);
jbe@355:         preference--;
jbe@355:         ballot->sections[preference].candidates[candidates_in_sections[preference]++] = candidate_by_key(suggestion_id);
jbe@355:       }
jbe@355:       if (i==tuple_count || (old_member_id && strcmp(old_member_id, member_id))) {
jbe@355:         ballot++;
jbe@355:         candidates_in_sections[0] = 0;
jbe@355:         candidates_in_sections[1] = 0;
jbe@355:         candidates_in_sections[2] = 0;
jbe@355:         candidates_in_sections[3] = 0;
jbe@355:       }
jbe@355:       old_member_id = member_id;
jbe@352:     }
jbe@352:   }
jbe@355: 
jbe@356:   for (i=0; i<candidate_count; i++) {
jbe@356:     struct candidate *candidate = loser(i, ballots, ballot_count);
jbe@356:     candidate->seat = candidate_count - i;
jbe@358:     printf("Assigning rank #%i to suggestion #%s.\n", candidate_count - i, candidate->key);
jbe@356:   }
jbe@356: 
jbe@354:   for (i=0; i<ballot_count; i++) {
jbe@354:     int j;
jbe@354:     for (j=0; j<4; j++) {
jbe@354:       if (ballots[i].sections[j].count) {
jbe@354:         free(ballots[i].sections[j].candidates);
jbe@354:       }
jbe@354:     }
jbe@354:   }
jbe@354:   free(ballots);
jbe@358: 
jbe@358:   printf("Writing ranks to database.\n");
jbe@358:   err = write_ranks(db, escaped_initiative_id);
jbe@358:   printf("Done.\n");
jbe@358: 
jbe@358:   free(candidates);
jbe@358: 
jbe@358:   return err;
jbe@352: }
jbe@352: 
jbe@352: int main(int argc, char **argv) {
jbe@352: 
jbe@352:   // variable declarations:
jbe@352:   int err = 0;
jbe@352:   int i, count;
jbe@352:   char *conninfo;
jbe@352:   PGconn *db;
jbe@352:   PGresult *res;
jbe@352: 
jbe@352:   // parse command line:
jbe@352:   if (argc == 0) return 1;
jbe@352:   if (argc == 1 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
jbe@352:     FILE *out;
jbe@352:     out = argc == 1 ? stderr : stdout;
jbe@352:     fprintf(stdout, "\n");
jbe@352:     fprintf(stdout, "Usage: %s <conninfo>\n", argv[0]);
jbe@352:     fprintf(stdout, "\n");
jbe@352:     fprintf(stdout, "<conninfo> is specified by PostgreSQL's libpq,\n");
jbe@352:     fprintf(stdout, "see http://www.postgresql.org/docs/9.1/static/libpq-connect.html\n");
jbe@352:     fprintf(stdout, "\n");
jbe@352:     fprintf(stdout, "Example: %s dbname=liquid_feedback\n", argv[0]);
jbe@352:     fprintf(stdout, "\n");
jbe@352:     return argc == 1 ? 1 : 0;
jbe@352:   }
jbe@352:   {
jbe@352:     size_t len = 0;
jbe@352:     for (i=1; i<argc; i++) len += strlen(argv[i]) + 1;
jbe@352:     conninfo = malloc(len * sizeof(char));
jbe@352:     if (!conninfo) {
jbe@358:       fprintf(stderr, "Error: Could not allocate memory for conninfo string.\n");
jbe@358:       abort();
jbe@352:     }
jbe@352:     conninfo[0] = 0;
jbe@352:     for (i=1; i<argc; i++) {
jbe@352:       if (i>1) strcat(conninfo, " ");
jbe@352:       strcat(conninfo, argv[i]);
jbe@352:     }
jbe@352:   }
jbe@352: 
jbe@352:   // connect to database:
jbe@352:   db = PQconnectdb(conninfo);
jbe@352:   if (!db) {
jbe@358:     fprintf(stderr, "Error: Could not create database handle.\n");
jbe@352:     return 1;
jbe@352:   }
jbe@352:   if (PQstatus(db) != CONNECTION_OK) {
jbe@352:     fprintf(stderr, "Could not open connection:\n%s", PQerrorMessage(db));
jbe@352:     return 1;
jbe@352:   }
jbe@352: 
jbe@352:   // check initiatives:
jbe@352:   res = PQexec(db, "SELECT \"initiative_id\", \"final\" FROM \"initiative_suggestion_order_calculation\"");
jbe@352:   if (!res) {
jbe@358:     fprintf(stderr, "Error in pqlib while sending SQL command selecting initiatives to process.\n");
jbe@352:     err = 1;
jbe@352:   } else if (PQresultStatus(res) != PGRES_TUPLES_OK) {
jbe@358:     fprintf(stderr, "Error while executing SQL command selecting initiatives to process:\n%s", PQresultErrorMessage(res));
jbe@352:     err = 1;
jbe@352:     PQclear(res);
jbe@352:   } else {
jbe@352:     count = PQntuples(res);
jbe@352:     printf("Number of initiatives to process: %i\n", count);
jbe@352:     for (i=0; i<count; i++) {
jbe@352:       char *initiative_id, *escaped_initiative_id;
jbe@352:       char *cmd;
jbe@352:       PGresult *res2;
jbe@352:       initiative_id = PQgetvalue(res, i, 0);
jbe@352:       printf("Processing initiative_id: %s\n", initiative_id);
jbe@352:       escaped_initiative_id = escapeLiteral(db, initiative_id, strlen(initiative_id));
jbe@358:       if (!escaped_initiative_id) {
jbe@358:         fprintf(stderr, "Could not escape literal in memory.\n");
jbe@358:         abort();
jbe@358:       }
jbe@352:       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) {
jbe@352:         fprintf(stderr, "Could not prepare query string in memory.\n");
jbe@355:         abort();
jbe@352:       }
jbe@352:       res2 = PQexec(db, cmd);
jbe@352:       free(cmd);
jbe@352:       if (!res2) {
jbe@358:         fprintf(stderr, "Error in pqlib while sending SQL command selecting individual suggestion rankings.\n");
jbe@352:         err = 1;
jbe@352:       } else if (PQresultStatus(res2) != PGRES_TUPLES_OK) {
jbe@358:         fprintf(stderr, "Error while executing SQL command selecting individual suggestion rankings:\n%s", PQresultErrorMessage(res));
jbe@352:         err = 1;
jbe@352:         PQclear(res2);
jbe@356:       } else if (PQnfields(res2) < 4) {
jbe@358:         fprintf(stderr, "Too few columns returned by SQL command selecting individual suggestion rankings.\n");
jbe@356:         err = 1;
jbe@356:         PQclear(res2);
jbe@352:       } else {
jbe@352:         if (PQntuples(res2) == 0) {
jbe@352:           printf("Nothing to do.\n");
jbe@352:         } else {
jbe@358:           if (process_initiative(db, res2, escaped_initiative_id)) err = 1;
jbe@352:         }
jbe@352:         PQclear(res2);
jbe@352:       }
jbe@352:       freemem(escaped_initiative_id);
jbe@352:     }
jbe@352:     PQclear(res);
jbe@352:   }
jbe@352: 
jbe@352:   // cleanup and exit
jbe@352:   PQfinish(db);
jbe@358:   if (!err) printf("Successfully terminated.\n");
jbe@358:   else fprintf(stderr, "Exiting with error code #%i.\n", err);
jbe@352:   return err;
jbe@352: 
jbe@352: }