#!/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" na página 22 de
# "Phragmén’s and Thiele’s election methods" por Svante Janson (2016).

export POSIXLY_CORRECT=1	# para que GNU Awk localize números

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

{
    aprovados[$0] }'
	then
	    sequencia=$(printf "$sequencia" | sed -e 's/^ //' -e 's/ $//')
	    printf "Voto \"$sequencia\" inválido: ignorado!\n" >&2
	    return 0
	fi
	printf "$sequencia\n" >> $TMP/grupos/$(printf "$sequencia" | cut -d ' ' -f 2)
    fi
    return 1
}

prompt ()
{
    printf "Aqui estão os $n candidatos em ordem de desempate:\n\n"
    nl -w 2 -s '. ' $TMP/candidatos | column -c 80
    read -p '
Digite a cédula, uma sequência de números em ordem decrescente de preferência,
ou nenhum dígito se não há mais votos: ' sequencia
    printf '\n'
    if invalido
    then
	printf '\n'
	prompt
    fi
}

if [ -z "$1" -o "$1" = "-h" -o "$1" = "--help" ]
then
    printf "Uso: $0 [-v] candidatos [votos...]

Uma candidata ou um candidato por linha não vazia de \"candidatos\".
Em caso de empate, quem está antes no arquivo vence.

Um voto por linha não vazia de \"votos\":
números dos candidatos, em ordem decrescente de preferência.\n"
    exit
fi

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

for arquivo in "$@"
do
    if [ ! -r "$arquivo" ]
    then
	printf "\"$arquivo\" não pode ser lido!\n" >&2
	exit 66
    fi
done

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

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

# Armazenar os votos, já criando os grupos iniciais, um por candidato
# posicionado primeiro
if [ -n "$2" ]
then
    shift
    cat "$@" | while read sequencia
    do
	invalido
    done
else
    prompt
    while [ "$sequencia" != " " ]
    do
	prompt
    done
fi

if  [ -n "$(ls $TMP/grupos)" ]
then
    # Inicializar $TMP/descr com, nesta ordem:
    # - o identificador de grupo
    # - o candidato favorito do grupo
    # - quantos votos no grupo
    # - a posição do grupo, 0 inicialmente
    for grupo in $TMP/grupos/*
    do
	printf "$(basename $grupo) $(basename $grupo) $(wc -l < $grupo) 0\n"
    done > $TMP/descr
fi

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

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

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

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

END {
    for (candidato in v)
        print "* " v[candidato] " / (1 + " q[candidato] ") = " v[candidato] / ++q[candidato] " voto(s) reduzido(s) para " nome[candidato]
    print "\nCom " v[eleito] / q[eleito] " voto(s) reduzido(s) e possível desempate, seguinte no ranqueamento: " nome[eleito] "\n" }' $TMP/candidatos $TMP/descr
    else
	sed -n ${eleito}p $TMP/candidatos
    fi

    # A partir dos grupos que acabaram de ser satisfeitos, criar novos
    # grupos, dependendo das próximas escolhas não eleitas, se tem
    satisfeitos=$(awk -v eleito=$eleito -v dir=" $TMP/grupos/" '$2 == eleito { printf dir $1 }' $TMP/descr)
    ranqueamento="$ranqueamento $eleito"
    awk -v ranqueamento="$ranqueamento " -v dir=$TMP/novos_grupos/ '
{
    for (i = 1; ranqueamento ~ " " $i " "; ++i)
        $i = "" }

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

    # Remover de $TMP/descr os grupos satisfeitos
    awk -v eleito=$eleito '$2 != eleito' $TMP/descr > $TMP/tmp
    mv $TMP/tmp $TMP/descr

    # Se há novos grupos, colocá-los com os antigos e definir as
    # posições deles
    if [ -n "$(ls $TMP/novos_grupos)" ]
    then
	w=$(printf "$top" | cut -f 1 | tr , .)
	for grupo in $TMP/novos_grupos/*
	do
	    n=$(expr $n + 1)
	    printf "$n $(basename $grupo) " >> $TMP/descr
	    awk -v w=$w 'END { print NR, NR / w }' $grupo >> $TMP/descr
	    if [ -n "$verbose" ]
	    then
		awk -v w=$w 'END { printf "* %d eleitor(es) satisfeito(s), agora em posição %d / %g = %g prefere(m) ", NR, NR, w, NR / w }' $grupo
		sed -n $(basename $grupo)p $TMP/candidatos
	    fi
	    mv $grupo $TMP/grupos/$n
	done
    fi
done