# SPDX-License-Identifier: MIT

# elections — decide who wins an election under each counting method, find
# that no one does, refuse to decide while a count is disputed, and share a
# house's seats among states or parties.
#
# THIS MODULE IS NOT LEGAL OR ELECTORAL ADVICE. It states published counting
# methods as rules and calculations over the ballots and populations you
# record. It certifies no election and counts no real ballot for anyone: which
# method an election uses, who may vote and what a ballot says are decided by
# the law and the officials who run it. A winner here is a verdict over the
# numbers you wrote, under the method named.
#
# Two halves that share nothing but the subject.
#
# STRUCTURE. You record facts; standing rules conclude, each with its proof.
#
# Elections (`elections.Election`) and their candidates
# (`elections.Candidate`), written by `election()` with two candidates or more.
# A candidate's name is its own across all your elections, and an election's
# candidates are fixed once written. Ballots (`elections.Ballot`), written by
# `ballot()`: a ranking of every candidate of one election, first to last, and
# the number of voters who cast it, written once, on the ballot. `ballot()`
# also writes, for each pair of candidates, which of the two the ballot ranks
# higher, and writing a ballot again replaces it.
#
# The rules conclude, for each candidate:
#   - `plurality`, where no candidate of the same election is the first choice
#     of more voters;
#   - `majority`, where more than half of the voters put it first;
#   - `condorcet`, where it beats every other candidate head to head: for each
#     other, more voters rank it higher than rank it lower;
#   - `condorcet_loser`, where every other candidate beats it head to head;
#   - `borda_winner`, where no candidate has a higher Borda score. A candidate's
#     Borda score is the sum of its head-to-head tallies: over every ballot and
#     every other candidate, the voters who rank it higher. That is the Borda
#     count with n - 1 points for a first place down to 0 for a last.
# and, for each election, `no_condorcet` where no candidate beats every other,
# as when the head-to-head counts run in a cycle, A over B, B over C and C over
# A. A tie head to head is no win, and no loss either.
#
#     import elections
#     elections.election("tn", ["memphis", "nashville", "chattanooga", "knoxville"])
#     elections.ballot("m", "tn", 42.0, ["memphis", "nashville", "chattanooga", "knoxville"])
#     elections.ballot("n", "tn", 26.0, ["nashville", "chattanooga", "knoxville", "memphis"])
#     elections.ballot("c", "tn", 15.0, ["chattanooga", "knoxville", "nashville", "memphis"])
#     elections.ballot("k", "tn", 17.0, ["knoxville", "chattanooga", "nashville", "memphis"])
#     print(elections.winners("tn"))
#     print(elections.runoff("tn"))
#
# A count in dispute. A rule that adds up a fact adds every value it holds, so
# a second count of a ballot, from a second source, would be added to the
# first, and a winner concluded from the total would be the winner under
# neither count. `recount()` writes such a second count. While any ballot of
# an election holds a second claim on its count, ranking or first choice,
# `disputed` is concluded for the election, no winner is concluded for it, and
# its readers refuse; `why_not` on a winner names the dispute. Forgetting the
# claim that is not to stand settles it, and every verdict returns.
#
#     elections.recount("n", 30.0, "recount")
#     print(elections.disputed_elections())
#     forget(elections.Ballot.n.count, 30.0, "recount")
#
# `why_not` on a candidate's `condorcet` says that something its rule asks to
# be missing was found, in the words "`condorcet_winner__none1` to be absent,
# and it is present"; `why` on that cell names the head-to-head count that
# beats the candidate, and under it each ballot's preference and count:
#
#     n = why_not(elections.Candidate.memphis.condorcet)
#     w = why(elections.Candidate.memphis.condorcet_winner__none1)
#
# CALCULATION. Value scripts that return a value and write nothing: an
# instant-runoff count, round by round, from the ballots you recorded; the Hare
# and Droop quotas; a house's seats by largest remainders (Hamilton's method)
# and by the highest averages of D'Hondt (Jefferson's), Sainte-Laguë
# (Webster's) and Huntington–Hill; and a Huntington–Hill priority value. The
# seat methods compare in whole numbers only, so a tie is found exactly, and a
# tie for the last seat refuses rather than be broken.
#
#     print(elections.largest_remainder({"a": 6, "b": 6, "c": 2}, 10))
#     print(elections.highest_averages({"a": 100000, "b": 80000, "c": 30000, "d": 20000}, 8, "dhondt"))
#
# Sources, read 2026-11-10:
#   - A Condorcet winner: "In each pairing the winner is the candidate preferred
#     by a majority of voters" (https://en.wikipedia.org/wiki/Condorcet_method).
#   - The paradox: "majority rule can be self-contradictory as majority
#     preferences can become intransitive with three or more options"
#     (https://en.wikipedia.org/wiki/Condorcet_paradox).
#   - The Borda count: "Each candidate is assigned a number of points from each
#     ballot equal to the number of candidates to whom he or she is preferred"
#     (https://en.wikipedia.org/wiki/Borda_count).
#   - Plurality: "The system does not require that the winner have a majority,
#     only a plurality" (https://en.wikipedia.org/wiki/Plurality_voting).
#   - The four cities of the examples, their shares and their rankings, are
#     the example those pages share
#     (https://en.wikipedia.org/wiki/Template:Tenn_voting_example).
#   - The Hare quota "is equal to the number of votes divided by the number of
#     seats" (https://en.wikipedia.org/wiki/Hare_quota); the exact Droop quota
#     is "total votes / (k + 1)" (https://en.wikipedia.org/wiki/Droop_quota).
#   - Largest remainders by the Hare quota "is sometimes called Hamilton's
#     method" (https://en.wikipedia.org/wiki/Largest_remainder_method); the
#     D'Hondt method divides by one, two, three and on
#     (https://en.wikipedia.org/wiki/D%27Hondt_method); Sainte-Laguë by one,
#     three, five and on (https://en.wikipedia.org/wiki/Sainte-Lagu%C3%AB_method);
#     Huntington–Hill gives each state a seat and then ranks P / √(n(n + 1))
#     (https://en.wikipedia.org/wiki/Huntington%E2%80%93Hill_method).
#   - The Alabama paradox, "where increasing the total number of items would
#     decrease one of the shares" (https://en.wikipedia.org/wiki/Apportionment_paradox).

import math

# ── Elections, candidates and ballots ────────────────────────────────────────

class Election:
    # An election, by a name you choose: how many candidates it has, written by
    # `election()`. The rules conclude `total`, the voters over all its
    # ballots; `matches`, `firstclaims`, `rankclaims` and `ballots`, which
    # `disputed` compares; and `disputed` and `no_condorcet`, each True.
    candidates: real
    total: real
    matches: real
    firstclaims: real
    rankclaims: real
    ballots: real
    disputed: bool
    no_condorcet: bool

class Candidate:
    # A candidate, by a name you choose, and the election it stands in. The
    # rules conclude `firsts`, the voters who put it first, and `borda`, its
    # Borda score, and the verdicts `plurality`, `majority`, `condorcet`,
    # `condorcet_loser` and `borda_winner`, each True.
    election: string
    firsts: real
    twice: real = firsts * 2.0
    borda: real
    plurality: bool
    majority: bool
    condorcet: bool
    condorcet_loser: bool
    borda_winner: bool

class Ballot:
    # A ballot, by a name you choose: its election, its first choice, its
    # ranking written as the candidates' names joined by ">", and the number of
    # voters who cast it.
    election: string
    first: string
    ranking: string
    count: real

class Pref:
    # For one ballot and one pair of candidates, which of the two it ranks
    # higher (`over`) and which lower (`under`). Written by `ballot()`.
    ballot: string
    over: string
    under: string

class Duel:
    # One ordered pair of candidates of an election, `a` against `b`. The
    # rules conclude `ab`, the voters ranking `a` over `b`, and `ba`, the
    # voters ranking `b` over `a`; `margin` is the difference.
    election: string
    a: string
    b: string
    ab: real
    ba: real
    margin: real = ab - ba

@rule
def first_preferences():
    for c in Candidate, b in Ballot:
        if b.first == c:
            c.firsts = sum(b.count)

@rule
def election_total():
    for e in Election, b in Ballot:
        if b.election == e:
            e.total = sum(b.count)

@rule
def duel_for():
    for d in Duel, p in Pref, b in Ballot:
        if p.over == d.a and p.under == d.b and p.ballot == b:
            d.ab = sum(b.count)

@rule
def duel_against():
    for d in Duel, p in Pref, b in Ballot:
        if p.over == d.b and p.under == d.a and p.ballot == b:
            d.ba = sum(b.count)

@rule
def borda_score():
    for c in Candidate, d in Duel:
        if d.a == c:
            c.borda = sum(d.ab)

@rule
def election_matches():
    for e in Election, b in Ballot:
        if b.election == e and b.count > -1.0:
            e.matches = count(b)

@rule
def election_first_matches():
    for e in Election, b in Ballot:
        if b.election == e and b.first != ">":
            e.firstclaims = count(b)

@rule
def election_rank_matches():
    for e in Election, b in Ballot:
        if b.election == e and b.ranking != ">":
            e.rankclaims = count(b)

@rule
def election_ballots():
    for e in Election, b in Ballot:
        if b.election == e:
            e.ballots = distinct(b)

@rule
def election_disputed():
    for e in Election:
        if e.matches > e.ballots:
            e.disputed = True

@rule
def election_disputed_first():
    for e in Election:
        if e.firstclaims > e.ballots:
            e.disputed = True

@rule
def election_disputed_ranking():
    for e in Election:
        if e.rankclaims > e.ballots:
            e.disputed = True

@rule
def plurality_winner():
    for c in Candidate, e in Election:
        if c.election == e and absent(e.disputed) and c.firsts > 0.0 and none(o in Candidate: o.election == c.election and o.firsts > c.firsts):
            c.plurality = True

@rule
def majority_winner():
    for c in Candidate, e in Election:
        if c.election == e and absent(e.disputed) and c.twice > e.total:
            c.majority = True

@rule
def condorcet_winner():
    for c in Candidate, e in Election:
        if c.election == e and absent(e.disputed) and none(d in Duel: d.a == c and d.margin <= 0.0):
            c.condorcet = True

@rule
def condorcet_loser():
    for c in Candidate, e in Election:
        if c.election == e and absent(e.disputed) and none(d in Duel: d.a == c and d.margin >= 0.0):
            c.condorcet_loser = True

@rule
def borda_winner():
    for c in Candidate, e in Election:
        if c.election == e and absent(e.disputed) and c.borda > 0.0 and none(o in Candidate: o.election == c.election and o.borda > c.borda):
            c.borda_winner = True

@rule
def no_condorcet_winner():
    for e in Election:
        if e.total > 0.0 and absent(e.disputed) and none(c in Candidate: c.election == e and c.condorcet == True):
            e.no_condorcet = True

# ── Writing an election and its ballots ──────────────────────────────────────

def strings(values: claim_list) -> dict<string, string>:
    # Each subject's string, from the values read.
    out = {}
    for v in values:
        parts = v.path.split(".")
        match v.value:
            case string as x:
                out[parts[len(parts) - 2]] = x
            case default:
                raise ValueError("a record holds a value that is not a string")
    return out

def candidates_of(name: string) -> list<string>:
    # The candidates of an election, by name.
    ve = list_values(Candidate.election)
    out = []
    for v in ve:
        parts = v.path.split(".")
        s = parts[len(parts) - 2]
        if v.value == name and s not in out:
            out.append(s)
    return sorted(out)

def election(name: string, roster: list<string>):
    # An election and its candidates, two or more, each named once. An
    # election's candidates are fixed once written, and a candidate's name is
    # its own across all your elections.
    if len(roster) < 2:
        raise ValueError("an election has two candidates or more")
    if "__" in name or ">" in name:
        raise ValueError("a name holds neither \"__\" nor \">\"")
    seen = []
    for c in roster:
        if c in seen:
            raise ValueError(c + " is named twice")
        if "__" in c or ">" in c:
            raise ValueError("a name holds neither \"__\" nor \">\"")
        seen.append(c)
    vn = list_values(Election.candidates)
    for v in vn:
        parts = v.path.split(".")
        if parts[len(parts) - 2] == name:
            raise ValueError("election " + name + " is already written, and its candidates are fixed")
    vh = list_values(Candidate.election)
    held = strings(vh)
    for c in roster:
        if c in held:
            raise ValueError(c + " already stands in election " + held[c])
    update(Election(name).candidates, float(len(roster)), "election")
    z = name + "__baseline"
    update(Ballot(z).election, name, "election")
    update(Ballot(z).first, "", "election")
    update(Ballot(z).ranking, "", "election")
    update(Ballot(z).count, 0.0, "election")
    for x in roster:
        update(Candidate(x).election, name, "election")
        for y in roster:
            if x != y:
                k = x + "__" + y
                update(Duel(k).election, name, "election")
                update(Duel(k).a, x, "election")
                update(Duel(k).b, y, "election")
                pk = z + "__" + k
                update(Pref(pk).ballot, z, "election")
                update(Pref(pk).over, x, "election")
                update(Pref(pk).under, y, "election")

def ballot(name: string, poll: string, voters: float, order: list<string>):
    # A ballot of an election: every one of its candidates ranked once, first
    # to last, and the number of voters who cast it. Write it again to correct
    # it.
    if voters < 0.0:
        raise ValueError("a count is not negative")
    if "__" in name or ">" in name:
        raise ValueError("a name holds neither \"__\" nor \">\"")
    names = candidates_of(poll)
    if len(names) == 0:
        raise ValueError("election " + poll + " is not written")
    if len(order) != len(names):
        raise ValueError("a ballot ranks every candidate of its election once")
    for x in order:
        if x not in names:
            raise ValueError(x + " is not a candidate of election " + poll)
    seen = []
    for x in order:
        if x in seen:
            raise ValueError(x + " is ranked twice")
        seen.append(x)
    update(Ballot(name).election, poll, "ballot")
    update(Ballot(name).first, order[0], "ballot")
    update(Ballot(name).ranking, ">".join(order), "ballot")
    update(Ballot(name).count, voters, "ballot")
    i = 0
    for x in order:
        j = 0
        for y in order:
            if i < j:
                if x < y:
                    pk = name + "__" + x + "__" + y
                else:
                    pk = name + "__" + y + "__" + x
                update(Pref(pk).ballot, name, "ballot")
                update(Pref(pk).over, x, "ballot")
                update(Pref(pk).under, y, "ballot")
            j = j + 1
        i = i + 1

def recount(name: string, voters: float, reason: string):
    # A second count of a ballot, from another source. It puts the ballot's
    # election in dispute until one of the two claims is forgotten.
    if reason == "ballot":
        raise ValueError("a recount names a source other than \"ballot\"; write the ballot again to correct it")
    update(Ballot(name).count, voters, reason)

# ── Reading what the rules concluded ─────────────────────────────────────────
#
# Each reader refuses an election that is not written and one whose count is
# disputed, since a verdict over a disputed count is a verdict under neither.

def names_of(values: claim_list) -> list<string>:
    out = []
    for v in values:
        parts = v.path.split(".")
        s = parts[len(parts) - 2]
        if v.value == True and s not in out:
            out.append(s)
    return sorted(out)

def disputed_elections() -> list<string>:
    # The elections whose count is in dispute.
    vd = list_values(Election.disputed)
    return names_of(vd)

def without_condorcet_winner() -> list<string>:
    # The elections in which no candidate beats every other head to head.
    vn = list_values(Election.no_condorcet)
    return names_of(vn)

def settled(name: string) -> list<string>:
    # The candidates of an election whose count is not disputed.
    names = candidates_of(name)
    if len(names) == 0:
        raise ValueError("election " + name + " is not written")
    if name in disputed_elections():
        raise ValueError("the count of election " + name + " is disputed, and disputed_elections() names it")
    return names

def chosen(values: claim_list, names: list<string>) -> list<string>:
    out = []
    for s in names_of(values):
        if s in names:
            out.append(s)
    return out

def winners(name: string) -> dict<string, list<string>>:
    # The winners of an election under each method, and its Condorcet loser.
    # A list is empty where no candidate wins, and holds more than one where
    # candidates tie.
    names = settled(name)
    vp = list_values(Candidate.plurality)
    vm = list_values(Candidate.majority)
    vc = list_values(Candidate.condorcet)
    vl = list_values(Candidate.condorcet_loser)
    vb = list_values(Candidate.borda_winner)
    return {"plurality": chosen(vp, names), "majority": chosen(vm, names), "condorcet": chosen(vc, names), "condorcet_loser": chosen(vl, names), "borda": chosen(vb, names)}

def tallies(values: claim_list, names: list<string>) -> dict<string, float>:
    out = {}
    for v in values:
        parts = v.path.split(".")
        s = parts[len(parts) - 2]
        if s in names:
            match v.value:
                case real as x:
                    out[s] = x
                case default:
                    raise ValueError("a tally is a number")
    for s in names:
        if s not in out:
            out[s] = 0.0
    return out

def first_choices(name: string) -> dict<string, float>:
    # The voters who put each candidate first.
    names = settled(name)
    vf = list_values(Candidate.firsts)
    return tallies(vf, names)

def borda_scores(name: string) -> dict<string, float>:
    # Each candidate's Borda score.
    names = settled(name)
    vb = list_values(Candidate.borda)
    return tallies(vb, names)

def head_to_head(name: string) -> dict<string, float>:
    # For each ordered pair "a>b" of an election's candidates, the voters who
    # rank a over b.
    names = settled(name)
    va = list_values(Duel.a)
    vb = list_values(Duel.b)
    vab = list_values(Duel.ab)
    a = strings(va)
    b = strings(vb)
    keys = []
    for k in a:
        if a[k] in names:
            keys.append(k)
    ab = tallies(vab, keys)
    out = {}
    for k in sorted(keys):
        out[a[k] + ">" + b[k]] = ab[k]
    return out

def runoff(name: string) -> list<dict<string, float>>:
    # An instant-runoff count: each round, every ballot counts for the highest
    # candidate on it still standing, and the candidate with the fewest votes
    # is eliminated, until one stands. One tally per round. A tie for last
    # place refuses, since the method names no way to break it.
    names = settled(name)
    ve = list_values(Ballot.election)
    vr = list_values(Ballot.ranking)
    el = strings(ve)
    rk = strings(vr)
    vc = list_values(Ballot.count)
    cn = {}
    for v in vc:
        parts = v.path.split(".")
        match v.value:
            case real as x:
                cn[parts[len(parts) - 2]] = x
            case default:
                raise ValueError("a count is a number")
    left = []
    for c in names:
        left.append(c)
    rounds = []
    for r in range(len(names)):
        tally = {}
        for c in left:
            tally[c] = 0.0
        for b in sorted(el):
            if el[b] == name and rk[b] != "":
                for c in rk[b].split(">"):
                    if c in tally:
                        tally[c] = tally[c] + cn[b]
                        break
        rounds.append(tally)
        if len(left) == 1:
            break
        low = left[0]
        for c in left:
            if tally[c] < tally[low]:
                low = c
        tied = 0
        for c in left:
            if tally[c] == tally[low]:
                tied = tied + 1
        if tied > 1:
            raise ValueError("a tie for last place in round " + str(r + 1))
        left.remove(low)
    return rounds

# ── Calculations ─────────────────────────────────────────────────────────────
#
# Each returns a value and writes nothing. The seat methods take whole numbers
# and compare only whole numbers.

def hare_quota(votes: int, seats: int) -> float:
    # Votes over seats.
    if seats <= 0:
        raise ValueError("a quota needs one seat or more")
    return float(votes) / float(seats)

def droop_quota(votes: int, seats: int) -> float:
    # The exact Droop quota, votes over seats + 1. Droop's original is one more.
    if seats <= 0:
        raise ValueError("a quota needs one seat or more")
    return float(votes) / float(seats + 1)

def checked(populations: dict<string, int>, seats: int):
    if len(populations) == 0:
        raise ValueError("there is no state to give a seat")
    if seats < 0:
        raise ValueError("a house has no fewer than no seats")
    for k in populations:
        if populations[k] <= 0:
            raise ValueError("the population of " + k + " is not positive")

def largest_remainder(populations: dict<string, int>, seats: int) -> dict<string, int>:
    # Hamilton's method: each state takes the whole part of its share of the
    # seats, and the seats left go one each to the largest remainders. A tie
    # for the last seat refuses.
    checked(populations, seats)
    total = 0
    for k in populations:
        total = total + populations[k]
    out = {}
    rem = {}
    given = 0
    for k in populations:
        out[k] = populations[k] * seats // total
        rem[k] = populations[k] * seats % total
        given = given + out[k]
    left = seats - given
    for i in range(left):
        best = ""
        for k in populations:
            if rem[k] >= 0:
                if best == "" or rem[k] > rem[best]:
                    best = k
        tied = 0
        for k in populations:
            if rem[k] == rem[best]:
                tied = tied + 1
        if tied > left - i:
            raise ValueError("a tie for the last seat")
        out[best] = out[best] + 1
        rem[best] = -1
    return out

def wide(x: int, p: int) -> list<int>:
    # x times p as two halves of 31 bits, high and low.
    lo = (x % 2147483648) * p
    hi = (x // 2147483648) * p + lo // 2147483648
    return [hi, lo % 2147483648]

def wide_compare(x: int, p: int, y: int, q: int) -> int:
    u = wide(x, p)
    v = wide(y, q)
    if u[0] > v[0] or (u[0] == v[0] and u[1] > v[1]):
        return 1
    if u[0] < v[0] or (u[0] == v[0] and u[1] < v[1]):
        return -1
    return 0

def ahead(a: int, na: int, b: int, nb: int, method: string) -> int:
    # Whether a state of population a holding na seats has a higher priority
    # for the next seat than one of population b holding nb: 1, 0 or -1.
    if method == "dhondt":
        x = a * (nb + 1)
        y = b * (na + 1)
    elif method == "sainte_lague":
        x = a * (2 * nb + 1)
        y = b * (2 * na + 1)
    else:
        return wide_compare(a * a, nb * (nb + 1), b * b, na * (na + 1))
    if x > y:
        return 1
    if x < y:
        return -1
    return 0

def highest_averages(populations: dict<string, int>, seats: int, method: string) -> dict<string, int>:
    # Seats one at a time, each to the state with the highest priority: its
    # population over 1, 2, 3 and on by "dhondt", over 1, 3, 5 and on by
    # "sainte_lague", and over √(n(n + 1)) by "huntington_hill", which first
    # gives every state one seat. A tie for the last seat refuses.
    checked(populations, seats)
    if method != "dhondt" and method != "sainte_lague" and method != "huntington_hill":
        raise ValueError("a method is \"dhondt\", \"sainte_lague\" or \"huntington_hill\"")
    out = {}
    left = seats
    for k in populations:
        if method == "huntington_hill":
            if populations[k] > 3037000499:
                raise ValueError("a population above 3,037,000,499 is beyond this method's exact comparison")
            out[k] = 1
            left = left - 1
        else:
            out[k] = 0
    if left < 0:
        raise ValueError("Huntington–Hill gives every state a seat, and there are fewer seats than states")
    for i in range(left):
        best = ""
        for k in populations:
            if best == "":
                best = k
            else:
                c = ahead(populations[k], out[k], populations[best], out[best], method)
                if c > 0:
                    best = k
        tied = 0
        for k in populations:
            c = ahead(populations[k], out[k], populations[best], out[best], method)
            if c == 0:
                tied = tied + 1
        if tied > left - i:
            raise ValueError("a tie for the last seat")
        out[best] = out[best] + 1
    return out

def priority_value(population: int, held: int) -> float:
    # Huntington–Hill's priority for a state's next seat, holding `held`:
    # population / √(held (held + 1)).
    if held < 1:
        raise ValueError("a state holds one seat or more before its priority is ranked")
    return float(population) / math.sqrt(float(held * (held + 1)))