jbe@352: #include jbe@352: #include jbe@352: #include jbe@352: #include jbe@352: #include jbe@352: jbe@374: static int logging = 0; jbe@374: 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@372: // column numbers when querying "individual_suggestion_ranking" view in function main(): 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@372: // data structure for a candidate (in this case a suggestion) to the proportional runoff system: jbe@353: struct candidate { jbe@372: char *key; // identifier of the candidate, which is the "suggestion_id" string jbe@372: double score_per_step; // added score per step jbe@372: double score; // current score of candidate; a score of 1.0 is needed to survive a round jbe@372: int seat; // equals 0 for unseated candidates, or contains rank number jbe@353: }; jbe@353: jbe@372: // compare two integers stored as strings (invocation like strcmp): jbe@369: static int compare_id(char *id1, char *id2) { jbe@369: int ldiff; jbe@369: ldiff = strlen(id1) - strlen(id2); jbe@369: if (ldiff) return ldiff; jbe@369: else return strcmp(id1, id2); jbe@369: } jbe@369: jbe@372: // compare two candidates by their key (invocation like strcmp): jbe@353: static int compare_candidate(struct candidate *c1, struct candidate *c2) { jbe@369: return compare_id(c1->key, c2->key); jbe@353: } jbe@352: jbe@372: // candidates are stored as global variables due to the constrained twalk() interface: jbe@353: static int candidate_count; jbe@353: static struct candidate *candidates; jbe@353: jbe@372: // function to be passed to twalk() to store candidates ordered in candidates[] array: 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@382: candidate->key = *candidate_key; jbe@382: candidate->seat = 0; jbe@376: if (logging) printf("Candidate #%i is suggestion #%s.\n", candidate_count, candidate->key); jbe@352: } jbe@352: } jbe@352: jbe@372: // performs a binary search in candidates[] array to lookup a candidate by its key (which is the suggestion_id): 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@372: // section of a ballot with equally ranked candidates: jbe@352: struct ballot_section { jbe@352: int count; jbe@353: struct candidate **candidates; jbe@352: }; jbe@352: jbe@372: // ballot of the proportional runoff system: jbe@352: struct ballot { jbe@372: int weight; // if weight is greater than 1, then the ballot is counted multiple times jbe@372: struct ballot_section sections[4]; // 4 sections, most preferred candidates first jbe@352: }; jbe@352: jbe@372: // determine candidate, which is assigned the next seat (starting with the worst rank): jbe@356: static struct candidate *loser(int round_number, struct ballot *ballots, int ballot_count) { jbe@372: int i, j, k; // index variables for loops jbe@372: int remaining; // remaining candidates to be seated jbe@372: // reset scores of all candidates: jbe@356: for (i=0; i 1) { jbe@376: if (logging) printf("There are %i remaining candidates.\n", remaining); jbe@372: double scale; // factor to be later multiplied with score_per_step: jbe@372: // reset score_per_step for all candidates: jbe@356: for (i=0; iscore < 1.0 && !candidate->seat) matches++; jbe@356: } jbe@356: if (matches) { jbe@356: double score_inc; jbe@368: score_inc = (double)ballots[i].weight / (double)matches; jbe@356: for (k=0; kscore < 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@372: // calculate scale factor: jbe@372: scale = (double)0.0; // 0.0 is used to indicate that there is no value yet jbe@356: for (i=0; i 0.0) { jbe@356: max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step; jbe@368: if (scale == 0.0 || max_scale <= scale) { jbe@356: scale = max_scale; jbe@356: } jbe@356: } jbe@356: } jbe@372: // add scale*score_per_step to each candidates score: jbe@356: for (i=0; i 0.0) { jbe@370: double max_scale; jbe@370: max_scale = (1.0-candidates[i].score) / candidates[i].score_per_step; jbe@370: if (max_scale == scale) { jbe@372: // score of 1.0 should be reached, so we set score directly to avoid floating point errors: 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@376: } jbe@377: if (log_candidate) { jbe@377: if (candidates[i].score >= 1.0) printf("=1\n"); jbe@377: else printf("=%.4f\n", candidates[i].score); jbe@377: } jbe@376: // when there is only one candidate remaining, then break inner (and thus outer) loop: jbe@376: if (remaining <= 1) { jbe@376: break; jbe@356: } jbe@356: } jbe@356: } jbe@372: // return remaining candidate: jbe@372: for (i=0; i 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@366: if (old_member_id && strcmp(old_member_id, member_id)) ballot++; jbe@355: ballot->weight = weight; jbe@355: ballot->sections[preference].count++; jbe@355: old_member_id = member_id; jbe@355: } jbe@372: // allocate memory for ballot sections: jbe@355: for (i=0; isections[preference].candidates[candidates_in_sections[preference]++] = candidate_by_key(suggestion_id); jbe@355: old_member_id = member_id; jbe@352: } jbe@376: // print ballots, if logging is enabled: jbe@376: if (logging) { jbe@376: for (i=0; ikey); jbe@376: } jbe@377: if (!k) printf("empty"); jbe@377: printf(".\n"); jbe@376: } jbe@376: } jbe@376: } jbe@352: } jbe@355: jbe@372: // calculate ranks based on constructed data structures: jbe@356: for (i=0; iseat = candidate_count - i; jbe@376: if (logging) printf("Assigning rank #%i to suggestion #%s.\n", candidate_count-i, candidate->key); jbe@356: } jbe@356: jbe@372: // free ballots[] array: jbe@354: for (i=0; i\n", argv[0]); jbe@362: fprintf(out, "\n"); jbe@362: fprintf(out, " is specified by PostgreSQL's libpq,\n"); jbe@362: fprintf(out, "see http://www.postgresql.org/docs/9.1/static/libpq-connect.html\n"); jbe@362: fprintf(out, "\n"); jbe@362: fprintf(out, "Example: %s dbname=liquid_feedback\n", argv[0]); jbe@362: fprintf(out, "\n"); jbe@352: return argc == 1 ? 1 : 0; jbe@352: } jbe@352: { jbe@352: size_t len = 0; jbe@374: int argb = 1; jbe@374: if ( jbe@374: argc >= 2 && jbe@374: (!strcmp(argv[1], "-v") || !strcmp(argv[1], "--verbose")) jbe@374: ) { jbe@374: argb = 2; jbe@374: logging = 1; jbe@374: } jbe@374: for (i=argb; iargb) 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@359: } else if (PQnfields(res) < 2) { jbe@359: fprintf(stderr, "Too few columns returned by SQL command selecting initiatives to process.\n"); jbe@359: err = 1; jbe@359: PQclear(res); jbe@352: } else { jbe@352: count = PQntuples(res); jbe@374: if (logging) printf("Number of initiatives to process: %i\n", count); jbe@352: for (i=0; i