#!/bin/sh

# Copyright 2024 Loïc Cerf (lcerf@dcc.ufmg.br)

# 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 3 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.

# "Phragmén’s ordered method, formulation 3" on page 22 of "Phragmén’s
# and Thiele’s election methods" by Svante Janson (2016).

export POSIXLY_CORRECT=1	# to have GNU Awk localize numbers

invalid ()
{
    sequence=$(printf " $sequence" | tr -sc 0-9 ' ')
    if [ "$sequence" != " " ]
    then
	if ! printf "$sequence" | awk -v RS=' ' -v n=$n '
NF && ($0 < 1 || $0 > n || $0 in approved) {
    exit 1 }

{
    approved[$0] }'
	then
	    sequence=$(printf "$sequence" | sed -e 's/^ //' -e 's/ $//')
	    printf "Ballot \"$sequence\" invalid: ignored!\n" >&2
	    return 0
	fi
	printf "$sequence\n" >> $TMP/groups/$(printf "$sequence" | cut -d ' ' -f 2)
    fi
    return 1
}

prompt ()
{
    printf "Here are the $n candidates in tie-breaking order:\n\n"
    nl -w 2 -s '. ' $TMP/candidates | column -c 80
    read -p '
Type the ballot, a sequence of numbers in descending order of preference,
or no digit if there is no more votes: ' sequence
    printf '\n'
    if invalid
    then
	printf '\n'
	prompt
    fi
}

if [ -z "$1" -o "$1" = "-h" -o "$1" = "--help" ]
then
    printf "Usage: $0 [-v] candidates [ballots...]

One candidate per non-empty line of \"candidates\".
In case of tie, who is before in the file wins.

One ballot per non-empty line of \"ballots\":
candidate numbers, in descending order of preference.\n"
    exit
fi

if [ "$1" = "-v" -o "$1" = "--verbose" ]
then
    shift
    verbose=1
fi

for file in "$@"
do
    if [ ! -r "$file" ]
    then
	printf "\"$file\" cannot be read!\n" >&2
	exit 66
    fi
done

TMP=$(mktemp -dt seq-phragmen.XXXXXX)
trap "rm -r $TMP 2>/dev/null" 0

mkdir -p $TMP/groups $TMP/new_groups
grep -xv '[[:space:]]*' "$1" > $TMP/candidates
n=$(wc -l < $TMP/candidates)

# Store the ballots, already creating the initial groups, one per
# candidate positioned first
if [ -n "$2" ]
then
    shift
    cat "$@" | while read sequence
    do
	invalid
    done
else
    prompt
    while [ "$sequence" != " " ]
    do
	prompt
    done
fi

if  [ -n "$(ls $TMP/groups)" ]
then
    # Initialize $TMP/descr with, in that order:
    # - the group id
    # - the favorite candidate of the group
    # - how many ballots in the group
    # - the place number of the group, 0 initially
    for group in $TMP/groups/*
    do
	printf "$(basename $group) $(basename $group) $(wc -l < $group) 0\n"
    done > $TMP/descr
fi

while [ -s $TMP/descr ]
do
    # Elect a candidate
    top=$(awk '
{
    v[$2] += $3
    q[$2] += $4 }

END {
    for (candidate in v)
        print v[candidate] / ++q[candidate] "\t" candidate }' $TMP/descr | sort -k 1,1nr -k 2n | head -1)
    elected=$(printf "$top" | cut -f 2)

    if [ -n "$verbose" ]
    then
	awk -v elected=$elected '
FILENAME == ARGV[1] {
    name[NR] = $0 }

FILENAME == ARGV[2] {
    v[$2] += $3
    q[$2] += $4 }

END {
    for (candidate in v)
        print "* " v[candidate] " / (1 + " q[candidate] ") = " v[candidate] / ++q[candidate] " reduced vote(s) for " name[candidate]
    print "\nWith " v[elected] / q[elected] " reduced vote(s) and possible tie break, next in ranking: " name[elected] "\n" }' $TMP/candidates $TMP/descr
    else
	sed -n ${elected}p $TMP/candidates
    fi

    # From the groups that have just been satisfied, create new
    # groups, depending on their next non-elected choices, if any
    satisfied=$(awk -v elected=$elected -v dir=" $TMP/groups/" '$2 == elected { printf dir $1 }' $TMP/descr)
    ranking="$ranking $elected"
    awk -v ranking="$ranking " -v dir=$TMP/new_groups/ '
{
    for (i = 1; ranking ~ " " $i " "; ++i)
        $i = "" }

$i {
    print > dir $i }' $satisfied
    rm $satisfied

    # Remove from $TMP/descr the satisfied groups
    awk -v elected=$elected '$2 != elected' $TMP/descr > $TMP/tmp
    mv $TMP/tmp $TMP/descr

    # If there are new groups, move them with the old ones and define
    # their place numbers
    if [ -n "$(ls $TMP/new_groups)" ]
    then
	w=$(printf "$top" | cut -f 1 | tr , .)
	for group in $TMP/new_groups/*
	do
	    n=$(expr $n + 1)
	    printf "$n $(basename $group) " >> $TMP/descr
	    awk -v w=$w 'END { print NR, NR / w }' $group >> $TMP/descr
	    if [ -n "$verbose" ]
	    then
		awk -v w=$w 'END { printf "* %d satisfied voter(s), now with place number %d / %g = %g prefer(s) ", NR, NR, w, NR / w }' $group
		sed -n $(basename $group)p $TMP/candidates
	    fi
	    mv $group $TMP/groups/$n
	done
    fi
done