jbe@394: #include jbe@394: #include jbe@394: #include jbe@394: #include jbe@394: #include jbe@394: jbe@394: static int logging = 0; jbe@394: jbe@394: static char *escapeLiteral(PGconn *conn, const char *str, size_t len) { jbe@394: // provides compatibility for PostgreSQL versions prior 9.0 jbe@394: // in future: return PQescapeLiteral(conn, str, len); jbe@394: char *res; jbe@394: size_t res_len; jbe@394: res = malloc(2*len+3); jbe@394: if (!res) return NULL; jbe@394: res[0] = '\''; jbe@394: res_len = PQescapeStringConn(conn, res+1, str, len, NULL); jbe@394: res[res_len+1] = '\''; jbe@394: res[res_len+2] = 0; jbe@394: return res; jbe@394: } jbe@394: jbe@394: static void freemem(void *ptr) { jbe@394: // to be used for "escapeLiteral" function jbe@394: // provides compatibility for PostgreSQL versions prior 9.0 jbe@394: // in future: PQfreemem(ptr); jbe@394: free(ptr); jbe@394: } jbe@394: jbe@394: // column numbers when querying "issue_supporter_in_admission_state" view in function main(): jbe@394: #define COL_MEMBER_ID 0 jbe@394: #define COL_WEIGHT 1 jbe@394: #define COL_ISSUE_ID 2 jbe@394: jbe@407: // data structure for a candidate (in this case an issue) to the proportional runoff system: jbe@394: struct candidate { jbe@407: char *key; // identifier of the candidate, which is the "issue_id" string jbe@394: double score_per_step; // added score per step jbe@394: double score; // current score of candidate; a score of 1.0 is needed to survive a round jbe@394: int seat; // equals 0 for unseated candidates, or contains rank number jbe@394: }; jbe@394: jbe@394: // compare two integers stored as strings (invocation like strcmp): jbe@394: static int compare_id(char *id1, char *id2) { jbe@394: int ldiff; jbe@394: ldiff = strlen(id1) - strlen(id2); jbe@394: if (ldiff) return ldiff; jbe@394: else return strcmp(id1, id2); jbe@394: } jbe@394: jbe@394: // compare two candidates by their key (invocation like strcmp): jbe@394: static int compare_candidate(struct candidate *c1, struct candidate *c2) { jbe@394: return compare_id(c1->key, c2->key); jbe@394: } jbe@394: jbe@394: // candidates are stored as global variables due to the constrained twalk() interface: jbe@394: static int candidate_count; jbe@394: static struct candidate *candidates; jbe@394: jbe@394: // function to be passed to twalk() to store candidates ordered in candidates[] array: jbe@394: static void register_candidate(char **candidate_key, VISIT visit, int level) { jbe@394: if (visit == postorder || visit == leaf) { jbe@394: struct candidate *candidate; jbe@394: candidate = candidates + (candidate_count++); jbe@394: candidate->key = *candidate_key; jbe@394: candidate->seat = 0; jbe@407: if (logging) printf("Candidate #%i is issue #%s.\n", candidate_count, candidate->key); jbe@394: } jbe@394: } jbe@394: jbe@407: // performs a binary search in candidates[] array to lookup a candidate by its key (which is the issue_id): jbe@394: static struct candidate *candidate_by_key(char *candidate_key) { jbe@394: struct candidate *candidate; jbe@394: struct candidate compare; jbe@394: compare.key = candidate_key; jbe@394: candidate = bsearch(&compare, candidates, candidate_count, sizeof(struct candidate), (void *)compare_candidate); jbe@394: if (!candidate) { jbe@394: fprintf(stderr, "Candidate not found (should not happen).\n"); jbe@394: abort(); jbe@394: } jbe@394: return candidate; jbe@394: } jbe@394: jbe@402: // ballot of the proportional runoff system, containing only one preference section: jbe@394: struct ballot { jbe@394: int weight; // if weight is greater than 1, then the ballot is counted multiple times jbe@402: int count; // number of candidates jbe@402: struct candidate **candidates; // all candidates equally preferred jbe@394: }; jbe@394: jbe@394: // determine candidate, which is assigned the next seat (starting with the worst rank): jbe@394: static struct candidate *loser(int round_number, struct ballot *ballots, int ballot_count) { jbe@394: int i, j; // index variables for loops jbe@394: int remaining; // remaining candidates to be seated jbe@394: // reset scores of all candidates: jbe@394: for (i=0; i 1) { jbe@394: if (logging) printf("There are %i remaining candidates.\n", remaining); jbe@394: double scale; // factor to be later multiplied with score_per_step: jbe@394: // reset score_per_step for all candidates: jbe@394: for (i=0; iscore < 1.0 && !candidate->seat) matches++; jbe@394: } jbe@394: if (matches) { jbe@394: double score_inc; jbe@394: score_inc = (double)ballots[i].weight / (double)matches; jbe@394: for (j=0; jscore < 1.0 && !candidate->seat) { jbe@394: candidate->score_per_step += score_inc; jbe@394: } jbe@394: } jbe@394: } jbe@394: } jbe@394: // calculate scale factor: jbe@394: scale = (double)0.0; // 0.0 is used to indicate that there is no value yet jbe@394: for (i=0; i 0.0) { jbe@394: max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step; jbe@394: if (scale == 0.0 || max_scale <= scale) { jbe@394: scale = max_scale; jbe@394: } jbe@394: } jbe@394: } jbe@394: // add scale*score_per_step to each candidates score: jbe@394: for (i=0; i 0.0) { jbe@394: double max_scale; jbe@394: max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step; jbe@394: if (max_scale == scale) { jbe@394: // score of 1.0 should be reached, so we set score directly to avoid floating point errors: jbe@394: candidates[i].score = 1.0; jbe@394: remaining--; jbe@394: } else { jbe@394: candidates[i].score += scale * candidates[i].score_per_step; jbe@394: if (candidates[i].score >= 1.0) remaining--; jbe@394: } jbe@394: } jbe@394: if (log_candidate) { jbe@394: if (candidates[i].score >= 1.0) printf("=1\n"); jbe@394: else printf("=%.4f\n", candidates[i].score); jbe@394: } jbe@394: // when there is only one candidate remaining, then break inner (and thus outer) loop: jbe@394: if (remaining <= 1) { jbe@394: break; jbe@394: } jbe@394: } jbe@394: } jbe@394: // return remaining candidate: jbe@394: for (i=0; iweight = weight; jbe@394: ballot->count++; jbe@394: old_member_id = member_id; jbe@394: } jbe@394: // allocate memory for ballot sections: jbe@394: for (i=0; icandidates[candidates_in_ballot++] = candidate_by_key(issue_id); jbe@394: old_member_id = member_id; jbe@394: } jbe@394: // print ballots, if logging is enabled: jbe@394: if (logging) { jbe@394: for (i=0; ikey); jbe@394: } jbe@394: // if (!j) printf("empty"); // should not happen jbe@394: printf(".\n"); jbe@394: } jbe@394: } jbe@394: } jbe@394: jbe@394: // calculate ranks based on constructed data structures: jbe@394: for (i=0; iseat = candidate_count - i; jbe@394: if (logging) printf("Assigning rank #%i to issue #%s.\n", candidate_count-i, candidate->key); jbe@394: } jbe@394: jbe@394: // free ballots[] array: jbe@394: for (i=0; i\n", argv[0]); jbe@394: fprintf(out, "\n"); jbe@394: fprintf(out, " is specified by PostgreSQL's libpq,\n"); jbe@394: fprintf(out, "see http://www.postgresql.org/docs/9.1/static/libpq-connect.html\n"); jbe@394: fprintf(out, "\n"); jbe@394: fprintf(out, "Example: %s dbname=liquid_feedback\n", argv[0]); jbe@394: fprintf(out, "\n"); jbe@394: return argc == 1 ? 1 : 0; jbe@394: } jbe@394: { jbe@394: size_t len = 0; jbe@394: int argb = 1; jbe@394: if ( jbe@394: argc >= 2 && jbe@394: (!strcmp(argv[1], "-v") || !strcmp(argv[1], "--verbose")) jbe@394: ) { jbe@394: argb = 2; jbe@394: logging = 1; jbe@394: } jbe@394: for (i=argb; iargb) strcat(conninfo, " "); jbe@394: strcat(conninfo, argv[i]); jbe@394: } jbe@394: } jbe@394: jbe@394: // connect to database: jbe@394: db = PQconnectdb(conninfo); jbe@394: if (!db) { jbe@394: fprintf(stderr, "Error: Could not create database handle.\n"); jbe@394: return 1; jbe@394: } jbe@394: if (PQstatus(db) != CONNECTION_OK) { jbe@394: fprintf(stderr, "Could not open connection:\n%s", PQerrorMessage(db)); jbe@394: return 1; jbe@394: } jbe@394: jbe@410: // create missing "issue_order_in_admission_state" entries for issues jbe@410: res = PQexec(db, "INSERT INTO \"issue_order_in_admission_state\" (\"id\") SELECT \"issue\".\"id\" FROM \"issue\" NATURAL LEFT JOIN \"issue_order_in_admission_state\" WHERE \"issue\".\"state\" = 'admission'::\"issue_state\" AND \"issue_order_in_admission_state\".\"id\" ISNULL"); jbe@410: if (!res) { jbe@410: fprintf(stderr, "Error in pqlib while sending SQL command creating new issue order entries.\n"); jbe@410: err = 1; jbe@410: } else if ( jbe@410: PQresultStatus(res) != PGRES_COMMAND_OK && jbe@410: PQresultStatus(res) != PGRES_TUPLES_OK jbe@410: ) { jbe@410: fprintf(stderr, "Error while executing SQL command creating new issue order entries:\n%s", PQresultErrorMessage(res)); jbe@410: err = 1; jbe@410: PQclear(res); jbe@410: } else { jbe@410: if (logging) printf("Created %s new issue order entries.\n", PQcmdTuples(res)); jbe@410: PQclear(res); jbe@410: } jbe@410: jbe@394: // go through areas: jbe@394: res = PQexec(db, "SELECT \"id\" FROM \"area\""); jbe@394: if (!res) { jbe@394: fprintf(stderr, "Error in pqlib while sending SQL command selecting areas to process.\n"); jbe@394: err = 1; jbe@394: } else if (PQresultStatus(res) != PGRES_TUPLES_OK) { jbe@394: fprintf(stderr, "Error while executing SQL command selecting areas to process:\n%s", PQresultErrorMessage(res)); jbe@394: err = 1; jbe@394: PQclear(res); jbe@394: } else if (PQnfields(res) < 1) { jbe@394: fprintf(stderr, "Too few columns returned by SQL command selecting areas to process.\n"); jbe@394: err = 1; jbe@394: PQclear(res); jbe@394: } else { jbe@394: count = PQntuples(res); jbe@394: if (logging) printf("Number of areas to process: %i\n", count); jbe@394: for (i=0; i