/*  dhondt - d'Hondt vote counting
    Copyright © 2007 Antti-Juhani Kaijanaho

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

    The author's current contact information as of September 2007 is

        Antti-Juhani Kaijanaho
        Sienitie 2 B 27
        40640 JYVÄSKYLÄ
        FINLAND

        antti-juhani@kaijanaho.fi

    -----------------------------------------------------------------------

    Changes:

    Version 1.0 by Antti-Juhani Kaijanaho (2007-09-02)
  
      * Original version

    -----------------------------------------------------------------------

    Requires a C99 hosted implementation.

    Reads input from standard input; name of input file can also be
    given on the command line.  Sends output to standard output or to
    the file named with the -o option.

    Input has the following form:

    NAME OF CONSTITUENCY (NUMBER OF SEATS)

    Name of party               number of votes
    Name of party               number of votes
    Name of party               number of votes
    Name of party               number of votes
    Name of party               number of votes
    Name of party               number of votes
    Name of party               number of votes
    Name of party               number of votes

    For example:

    JYVÄSKYLÄN KAUPUNKI (59)

    Perussuomalaiset                           95
    Ruotsalainen kansanpuolue                  78
    Suomen Keskusta                          7009
    Suomen Kommunistinen Puolue              1291
    Vihreä liitto                            4211
    Kansallinen Kokoomus                     7338
    Rauhan ja Sosialismin Puolesta - \
    Kommunistinen Työväenpuolue                28
    Vasemmistoliitto                         3301
    Suomen Sosialidemokraattinen Puolue     10929
    Suomen Kristillisdemokraatit             2324

 */

#include <assert.h>
#include <errno.h>
#include <limits.h>
#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <wchar.h>
#include <wctype.h>

#ifdef __GNUC__
#  define NORETURN(x) x __attribute__((noreturn))
#else
#  define NORETURN(x) x
#endif

#define NOTREACHED do { \
    fprintf(stderr, "%s:%d (%s): internal error: reached NOTREACHED",\
            __FILE__, __LINE__, __func__);\
    abort();\
} while(0)

const char *argv0;

NORETURN(void enomem(void));

void enomem(void)
{
        fprintf(stderr, "%s: "
                "memory allocation request failed\n",
                argv0);
        exit(EXIT_FAILURE);
}


enum file_mode { M_READ, M_WRITE };

FILE *open_file(const char **fnameptr, enum file_mode mode)
{
        // stdin / stdout are not constants so cannot be stored in this array
        static const struct {
                const char *mstr;
                const char *descr;
        } modes[2] = { [M_READ]  = { .mstr = "r",
                                     .descr = "reading" },
                       [M_WRITE] = { .mstr = "w",
                                     .descr = "writing" } };

        if (*fnameptr == NULL || strcmp(*fnameptr, "-") == 0) {
                switch (mode) {
                case M_READ:
                        *fnameptr = "(stdin)";
                        return stdin;
                case M_WRITE:
                        *fnameptr = "(stdout)";
                        return stdout;
                }
                NOTREACHED;
        } else {
                FILE *rv = fopen(*fnameptr, modes[mode].mstr);
                if (rv == NULL) {
                        fprintf(stderr, "%s: failed to open %s for %s\n",
                                argv0, *fnameptr, modes[mode].descr);
                        exit(EXIT_FAILURE);
                }
                return rv;
        }
}

wint_t my_getwc(FILE *fp, const char *fname)
{
        errno = 0;
        wint_t c = getwc(fp);
        if (c == WEOF) {
                if (errno != 0) {
                        fprintf(stderr, "%s: error reading %s: %s\n",
                                argv0, fname, strerror(errno));
                        exit(EXIT_FAILURE);
                }
                if (ferror(fp)) {
                        fprintf(stderr, "%s: error reading %s\n",
                                argv0, fname);
                        exit(EXIT_FAILURE);
                }
                assert(feof(fp));
        }
        return c;
}

/* Returns the next line (up to the next newline not preceded by a
 * backslash, with any backslash-newline pairs elided) as a
 * newly-malloced nul-terminated buffer.  Final newline is not
 * included.  */
wchar_t *getline(FILE *fp, const char *fname)
{
        assert(fp != NULL);
        assert(fname != NULL);

        static size_t bufmax = 0;
        static wchar_t *buf = NULL;

        size_t n = 0;

        while (1) {
                errno = 0;
                wint_t c = my_getwc(fp, fname);
                if (c == WEOF) {
                        if (n == 0) return NULL;
                        break;
                }
                if (c == L'\\') {
                        wint_t c1 = my_getwc(fp,fname);
                        if (c1 == WEOF || c1 == L'\n') {
                                continue;
                        }
                        wint_t ok = ungetwc(c1, fp);
                        assert(ok == c1);
                }
                if (c == L'\n') break;
                assert(n <= bufmax);
                if (n == bufmax) {
                        bufmax = bufmax == 0 ? 4 : 2*bufmax;
                        buf = realloc(buf, bufmax * sizeof *buf);
                        if (buf == NULL) enomem();                
                }
                buf[n++] = (unsigned char)c;
        }
        wchar_t *rv = malloc(n * sizeof *rv);
        if (rv == NULL) enomem();
        memcpy(rv, buf, n * sizeof *rv);
        rv[n] = L'\0';
        return rv;
}

/* The line must end in base-10 digits enclosed in parentheses.  Those
 * digits, interpreted as a base-10 numeral, are returned, and the
 * whole parenthesis-digit device is removed from the line. */
int extract_num_seats(wchar_t *line, const char *fname)
{
        wchar_t *p = wcsrchr(line, L'(');
        if (p == NULL) {
                fprintf(stderr, "%s:%s: "
                        "cannot find the total number of seats\n",
                        argv0, fname);
                exit(EXIT_FAILURE);
        }
        *p++ = L'\0'; // delete the device
        int rv = 0;
        while (iswdigit(*p)) rv = 10*rv + *(p++) - L'0';
        if (*p != L')') {
                fprintf(stderr, "%s:%s: missing ')'\n", argv0, fname);
                exit(EXIT_FAILURE);
        }
        return rv;
}

/* Removes whitespace from the beginning and the end of s.  */
void trim(wchar_t **s)
{
        while (iswspace(**s)) ++*s;
        wchar_t *p = *s;
        while (*p != L'\0') p++;
        while (iswspace(p[-1])) --p;
        *p = L'\0';
}

struct party {
        wchar_t *name;
        long votes;
        int seats;
};

int cmp_parties(const void *av, const void *bv)
{
        const struct party *a = av;
        const struct party *b = bv;
        if (a->seats > b->seats) return -1;
        if (a->seats < b->seats) return +1;
        return 0;
}

struct loser {
        wchar_t *name;
        double quot;
};

int cmp_losers(const void *av, const void *bv)
{
        const struct loser *a = av;
        const struct loser *b = bv;
        if (a->quot > b->quot) return -1;
        if (a->quot < b->quot) return +1;
        return 0;
}


int main(int argc, char *argv[])
{
        setlocale(LC_CTYPE, "");

        _Bool print_help = 0;
        const char *ifname = NULL;
        const char *ofname = NULL;

        argv0 = argv[0] == NULL ? "dhondt" : argv[0];

        /* option parser */
        int argi;
        for (argi = 1; argi < argc; argi++) {
                char *arg = argv[argi];
                if (arg[0] != '-' || arg[1] == '\0') {
                        // not an argion
                        break;
                }
                assert(arg[0] == '-');
                if (arg[1] == '-' && arg[2] == '\0') {
                        // "--" stops argion processing
                        argi++;
                        break;
                }
                assert(arg[1] != '\0');
                for (int i = 1; i < INT_MAX && arg[i] != '\0'; i++) {
                        switch (arg[i]) {
                        case 'o':
                                if (arg[i+1] == '\0') {
                                        ofname = argv[++argi];
                                        goto break_for_i;
                                } else {
                                        ofname = arg+i+1;
                                        goto break_for_i;
                                }
                                NOTREACHED;
                        case 'h':
                                print_help = 1;
                                break;
                        default:
                                fprintf(stderr, "%s: unknown option '%c'\n",
                                        argv0, arg[i]);
                                exit(EXIT_FAILURE);
                        }
                }break_for_i:;
        }

        if (argi < argc) {
                ifname = argv[argi++];
        }

        if (argi < argc) {
                fprintf(stderr, "%s: too many arguments\n", argv0);
                exit(EXIT_FAILURE);
        }

        if (print_help) {
                printf("Usage: %s [-o OUTFILE] [INFILE]\n", argv0);
                exit(EXIT_SUCCESS);
        }

        FILE *ifi = open_file(&ifname, M_READ);
        FILE *ofi = open_file(&ofname, M_WRITE);

        wchar_t *title = getline(ifi, ifname);

        trim(&title);

        int num_seats = extract_num_seats(title, ifname);

        trim(&title);

        fwprintf(ofi, 
                 L"%ls\n\nTotal seats: %d\n\n",
                 title, num_seats);

        struct party parties[50];
        size_t num_parties = 0;
        long total_votes = 0;

        while (num_parties < sizeof parties / sizeof *parties) {
                struct party *party = &parties[num_parties];
                party->seats = 0;

                party->name = getline(ifi, ifname);
                if (party->name == NULL) break;
                
                trim(&party->name);

                if (party->name[0] == L'\0') {
                        continue;
                }

                // find the vote count
                wchar_t *p = party->name;
                while (*p != L'\0') p++;
                while (iswdigit(p[-1])) --p;
                party->votes = 0;
                while (*p != L'\0') {
                        party->votes = 10*party->votes + *p - L'0';
                        *p = L'\0';
                        ++p;
                }

                total_votes += party->votes;

                trim(&party->name);                

                ++num_parties;
        }

        fwprintf(ofi,
                 L"ALLOCATION OF SEATS\n\n"
                 L"Party of the candidate                                "
                 L"                  Quotient\n"
                 L"------------------------------------------------------"
                 L"--------------------------\n");

        for (int i = 0; i < num_seats; i++) {
                double best_quot = 0;
                size_t choice = 0;
                for (size_t j = 0; j < num_parties; j++) {
                        double quot = parties[j].votes / 
                                (double)(parties[j].seats + 1);
                        if (quot > best_quot) {
                                choice = j;
                                best_quot = quot;
                        }
                }
                fwprintf(ofi, L"%-73ls %6.1f\n",
                         parties[choice].name, best_quot);
                parties[choice].seats += 1;
        }

        qsort(parties, num_parties, sizeof *parties, cmp_parties);

        struct loser losers[num_parties];

        for (size_t i = 0; i < num_parties; i++) {
                losers[i].name = parties[i].name;
                losers[i].quot = parties[i].votes / 
                        (double)(parties[i].seats+1);
        }
 
        qsort(losers, num_parties, sizeof *losers, cmp_losers);

        fwprintf(ofi,
                 L"------------------------------------------------------"
                 L"--------------------------\n\n"
                 L"First loser's quotient per party\n"
                 L"------------------------------------------------------"
                 L"--------------------------\n");

        for (size_t i = 0; i < num_parties; i++) {
                fwprintf(ofi, L"%-73ls %6.1f\n",
                         losers[i].name,
                         losers[i].quot);
        }
 
        fwprintf(ofi,
                 L"------------------------------------------------------"
                 L"--------------------------\n\n"
                 L"SUMMARY REPORT\n\n"
                 L"Party                                                 "
                 L"               Votes Seats\n"
                 L"------------------------------------------------------"
                 L"--------------------------\n");
        for (size_t i = 0; i < num_parties; i++) {
                fwprintf(ofi, L"%-67.67ls %6ld%6d\n",
                         parties[i].name,
                         parties[i].votes,
                         parties[i].seats);
        }
        fwprintf(ofi,

                 L"------------------------------------------------------"
                 L"--------------------------\n"
                 L"Totals:                                               "
                 L"              %6ld%6d\n\n",
                 total_votes, num_seats);

        return 0;
}