/* elect.js
   Copyright © Richard Sabey 2003. All rights reserved.
   Last updated 28 November 2003.
*/
/* candidates: info about candidates.
   This is an associative array whose keys are the candidates' keys as given
   in the "candidateInfo" text area.
*/
var candidates;
var nC;         // how many candidates there are
var big = 1000000000;

/*******************************************************************************
    Candidates

A Candidates object is intended to contain, or point to, information about
all candidates. The info for each candidate is in a property whose name is that
candidate's key.

initialiseCandidates is intended to be called for a Candidates object. For each
candidate, it initialises the property <k> with the given value <val>, where <k>
is that candidate's key. This cannot be called for <this> in the constructor for
Candidates, or in the constructor for Candidate, because those constructors are
being used while the set of keys is being found. 
********************************************************************************
*/
function Candidates()
{
}

function initialiseCandidates(byC, val)
{
    for(k in candidates)
    {
        byC[k] = val;
    }
}

/*******************************************************************************
    Candidate

    Information about a candidate
name: the candidate's name, as given after the comma in a line in the list of
candidates 
nPairwiseWins: number of pairwise contests this candidate won
nPairwiseDraws: number of pairwise contests this candidate drew
nPairwiseLosses: number of pairwise contests this candidate lost
mostVotesAgainst: largest number of votes against this candidate in a pairwise
contest 
fewestVotesFor: smallest number of votes for this candidate in a pairwise
contest
worstDefeat: largest margin by which any other candidate in a pairwise
contest beat this
nVotesForMeAgainst: this is a Candidates object; where k is the key of another
candidate, this.nVotesForMeAgainst[k] is the number of votes for <this> in the
pairwise contest against <k>. 
CopelandScore: this candidate's score by the Copeland method
********************************************************************************
*/

/* Constructor for a Candidate.
   Although this constructor makes each property whose value is a Candidates
   object, it merely constructs the latter object without initialising it.
   Use the method <initialiseCandidates> to do that.
*/
function Candidate(name)
{
    this.name               = name;

    // Initialise properties for this candidate, that the Condorcet method needs
    this.nVotesForMeAgainst = new Candidates();

    // Initialise properties for this candidate, that the Copeland method needs
    this.CopelandScore      = 0;
} // function Candidate(name)

/*******************************************************************************
    Vote
********************************************************************************
*/
/* Constructor for a Vote. */

function Vote(voteLine)
{
    var i, r="", sep="";

    // Is there a vote-count on this line?
    piece = voteLine.match(/([^:]*):(.*)$/);
    if(piece == null)
    {
        // No; this vote line represents just one vote
        this.count = 1;
        voteString = voteLine;
    }
    else
    {
        var n = parseInt(piece[1]); // convert from string to number
        if(n == NaN) // this appears not to work; how do I find out if parseInt worked?
        {
            r = r + "Illegal vote-count: " + piece[1];
            throw new Error(r);
        }
        this.count = n;
        voteString = piece[2];
    }

    /* Split the vote-string into tokens. The characters '>' and '=' separate
       the candidates' keys mentioned in the vote. I must keep these separators
       in the token-array, to distinguish a clear preference from a list of
       candidates ranked equal.
    */
    /* The dodge of voteString.split(/([>=])/); to preserve the delimiters
       themselves in the array resulting from <split> appears not to work
       Thus introduce space around the tokens just so that I can split in the
       usual way.
    */
    voteString = voteString.replace(/[>]/g, " > ");
    voteString = voteString.replace(/[=]/g, " = ");
    var tokenisedVoteString = voteString.split(/\s+/);

    /* For each candidate, record his rank in this vote. Ranks go from 1
       (first choice) upwards, i.e. lower numbers beat higher ones.
       Each candidate not mentioned in the vote gets the highest-numbered rank
       possible, viz nC.
       Go through the elements of tokenisedVoteString by index, rather than
       using for...in, in case the order in which for...in takes them is unreliable.
    */

    var i, token, rank=1, nCSoFar = 0, byC,
        expectC = true; // means the next token is expected to be a candidate-key
    this.rankOfCandidate = new Candidates();

    initialiseCandidates(this.rankOfCandidate, nC);

    for(i=0; i<tokenisedVoteString.length; ++i)
    {
        token = tokenisedVoteString[i];
        if(token == ">")
        {
            if(expectC)
                r = r + sep + "'>' was found where a candidate-key was expected";
            else
            {
                rank=nCSoFar+1; // this is the rank which will be given to the next candidate
                expectC = true;
            }
        }
        else if(token == "=")
        {
            if(expectC)
                r = r + sep + "'=' was found where a candidate-key was expected";
            else
                expectC = true;
        }
        else if(token == "")
        {
            // Only if there is a blank line can this happen. Just ignore the line.
            throw new Error("Ignore");
        }
        else if(expectC)
        {
            if(this.rankOfCandidate[token] == nC)
            {
                // This token is the key for a candidate not so far mentioned in this vote
                this.rankOfCandidate[token] = rank;
                ++nCSoFar;
            }
            else if(this.rankOfCandidate[token] < nC)
                r = r + sep + "candidate " + token + " appears more than once";
            else // unrecognised?
                r = r + sep + "there is no candidate " + token + ".";
            expectC=false;
        }
        else
            r = r + sep + "a candidate-key " + token + " was found where a symbol was expected";

        if(r!="")
            sep="; ";
    }
    if(r!="")
        throw new Error(r);
} // function Vote(voteLine)

/*******************************************************************************
    Procedures

    makeReport is the entry point into this utility. It takes as parameters the
values in the text-areas in the form in the HTML file, and converts them into a
more manageable format before passing them to <elect>.
    
********************************************************************************
*/
function makeReport(candidatesInfoString, voteList)
{
    var r;

    reports = new Object();
    reports.condorcetSummary = "hello makeReport";
    reports.condorcetSummary = "";
    reports.condorcetReport = "";
    reports.schwartzsdSummary = "";
    reports.schwartzsdReport = "";
    reports.copelandSummary = "";
    reports.copelandReport = "";

    // Take each input string (which is the contents of a text area), and
    //turn it into an array of strings
    var candidatesInfoArray = candidatesInfoString.split(/[\n\r]+/);
    var voteArray           = voteList.split(/[\n\r]+/);

    candidates = new Candidates();

    r = parseCandidatesInfoString(candidatesInfoArray);
    if(r != "")
    {
        reports.condorcetSummary = "### Bad candidate list; see below ###";
        reports.condorcetReport = r;
        return reports;
    }

    elect(candidates, voteArray, reports);

    return reports;
} // function makeReport(candidatesInfoString, voteList)

function parseCandidatesInfoString(candidatesInfoArray)
{
    var report="";

    /* Count lines which are individually valid. The format is
       <key>,<name>
       where the key is a non-null string whose characters are all letters,
       digits or '_'. For example:
       1,Rachel Smith
       XYZ,Ralph Verry-Posh, Lord Something
       Bung these into the JavaScript associative array of the properties of the
       object <candidates>, and, while I'm at it, check for duplicate keys. 
    */
    var i, nLines, nValidLines=0, piece, nDuplicateKeys=0, duplicateKeyString="";
    var lineSyntax = /(\w+),(.*$)/;
    nLines = candidatesInfoArray.length;
    nC     = 0;
    for(i=0; i<nLines; ++i)
    {
        piece = candidatesInfoArray[i].match(lineSyntax);
        if(piece == null)
            ; /* take this as a comment line */
        else if(candidates[piece[1]] == null)
        {
            candidates[piece[1]] = new Candidate(piece[2]);
            ++nC;
        }
        else
        {
            ++nDuplicateKeys;
            if(duplicateKeyString=="")
                duplicateKeyString = piece[1];
            else
                duplicateKeyString = duplicateKeyString + ", " + piece[1];
        }
    }

    if(nDuplicateKeys>0)
    {
        if(nDuplicateKeys==1)
            report = "There's a duplicate candidate-key: " + duplicateKeyString;
        else
            report = "There are " + nDuplicateKeys + " duplicate candidate-keys: " + duplicateKeyString;
    }
/*
    else
        report = "hello parseCandidatesInfoString says OK";
*/
    return report;
} // function parseCandidatesInfoString(candidatesInfoArray)

/*******************************************************************************
    elect

    Hold elections by the Condorcet and Copeland methods, and report the results
********************************************************************************
*/
function elect(candidates, voteArray, reports)
{
    var c, v, o, voteString, voteNum, nVotes=0;
    var r="";

    //reports.condorcetReport = "hello - i am in elect 1";
    for(k in candidates)
    {
        c = candidates[k];
        initialiseCandidates(c.nVotesForMeAgainst, 0);
    }

    reports.nCandidates = nC;

    voteNum=0;
    for(voteIndex in voteArray)
    {
        ++voteNum;
        //r = r + "Read vote " + voteNum + " '" + voteArray[voteIndex] + "'\n";

        if(voteArray[voteIndex] != "")
        {
            try
            {
                v = new Vote(voteArray[voteIndex]);
                r = r + condorcetAnalyseVote(candidates, v);
                nVotes += v.count;
            }
            catch(e)
            {
//                if(e.message != "Ignore")
                    r = r + "Error in vote " + voteNum + ": " + e.message + "\n";
            }
        }
    }

    if(r!="")
    {
        reports.condorcetSummary = "### Error in vote list; see below ###";
        reports.condorcetReport  = r;
        return;
    }

    reports.nVotes      = nVotes;
    reports.condorcetReport = "hello - before condorcetInit\n";
    condorcetInit(candidates);
    reports.condorcetReport = reports.condorcetReport + "hello - after condorcetInit\n";
/*
    condorcetFindPairwiseScores(candidates);
    reports.condorcetReport = reports.condorcetReport + "hello - after condorcetFindPairwiseScores\n");
    condorcetFindWorstResults(candidates);
    reports.condorcetReport = reports.condorcetReport + "hello - after condorcetFindWorstResults\n");
    // Do we have an outright winner? There cannot be more than one.
    condorcetOutrightWinner = condorcetFindOutrightWinner(candidates);

    if(condorcetOutrightWinner == null)
    {
        reports.condorcetSummary = "hello no Cond winner";

        // There is no outright winner. The Condorcet method elects the
        //   candidate(s) with the lowest worst defeat. Note that there may be
        //   more than one.
        o = condorcetFindWinnerByLeastOpposition(candidates);
        reports.condorcetSummary = o.s;
        reports.condorcetReport = "According to the Condorcet method, there is no outright winner; no candidate won all pairwise contests.\n" + o.r;

        o = schwartzsdFindWinner(candidates);
        reports.schwartzsdSummary = o.s;
        reports.schwartzsdReport = o.r;

    }
    else
    {
        reports.condorcetSummary = "hello there is a Cond winner";

        c = candidates[condorcetOutrightWinner];
        reports.condorcetSummary = c.name;
        reports.condorcetReport = "According to the Condorcet method, " + c.name +
                          " wins outright, as having won the pairwise contests against all other candidates.\n";
        reports.condorcetReport = reports.condorcetReport + reportPairwiseResultsFor(condorcetOutrightWinner) + "\n";

        reports.schwartzsdSummary = "See Condorcet above";
        reports.schwartzsdReport =  "See Condorcet above";

    }

    o = copelandFindWinner(candidates);
    reports.copelandSummary = o.s;
    reports.copelandReport = o.r;
*/
} // function elect(candidates, voteArray)

/*******************************************************************************
    Procedures for implementing an election by the Condorcet method

    In these procedures, the Candidates object <candidates> will be used for
information pertaining to candidates. <relevantCandidates> will be used as an
indexing set for those candidates on which the Condorcet method is being run.
This needn't be all the candidates. 
********************************************************************************
*/
function condorcetAnalyseVote(relevantCandidates, v)
{
    var k1, k2, c1, c2, rank1, rank2, margin, s="";

aloop:
    for(k1 in relevantCandidates) // for every candidate
    {
        c1 = candidates[k1];
        for(k2 in relevantCandidates) // for every opponent...
        {
            if(k2==k1) // ... earlier in the candidate list
                continue aloop;
            c2 = candidates[k2];

            rank1 = v.rankOfCandidate[k1];
            rank2 = v.rankOfCandidate[k2];
            if(rank1 < rank2) // voter preferred c1 to c2
                c1.nVotesForMeAgainst[k2] += v.count;
            else if(rank2 < rank1) // voter preferred c2 to c1
                c2.nVotesForMeAgainst[k1] += v.count;
        }
    }
    return s;
} // function condorcetAnalyseVote(relevantCandidates, v)

/*******************************************************************************
    condorcetInit

    Initialise properties of <candidates> as appropriate for running a
Condorcet election. The votes have already been tallied. The results of the
pairwise contests are in <nVotesForMeAgainst> and don't need to be recalculated
for Condorcet elections on different subsets of the set of candidates.
********************************************************************************
*/
function condorcetInit(relevantCandidates)
{
    for(k in relevantCandidates)
    {
        c = candidates[k];
        c.nPairwiseWins      = 0;
        c.nPairwiseDraws     = 0;
        c.nPairwiseLosses    = 0;
    }
} // function condorcetInit(relevantCandidates)

/*******************************************************************************
    condorcetFindPairwiseScores

    Run the pairwise contests. For every two candidates A and B, a contest
between them is run, whereby each vote is counted as A>B, A=B or B>A as
appropriate.
********************************************************************************
*/
function condorcetFindPairwiseScores(relevantCandidates)
{
    reports.condorcetReport = reports.condorcetReport + "hello Entering condorcetFindPairwiseScores. ");
/*
bloop:
    for(k1 in relevantCandidates) // for every candidate
    {
        c1 = candidates[k1];
        for(k2 in relevantCandidates) // for every opponent...
        {
            if(k2==k1) // ... earlier in the candidate list
                continue bloop;
            c2 = candidates[k2];

            nPreferences1       = c1.nVotesForMeAgainst[k2];
            nPreferences2       = c2.nVotesForMeAgainst[k1];

            if(nPreferences1 > nPreferences2)
            {
                ++c1.nPairwiseWins;
                ++c2.nPairwiseLosses;
            }
            else if(nPreferences2 > nPreferences1)
            {
                ++c1.nPairwiseLosses;
                ++c2.nPairwiseWins;
            }
            else
            {
                ++c1.nPairwiseDraws;
                ++c2.nPairwiseDraws;
            }
        }
    }
*/
} // function condorcetFindPairwiseScores(relevantCandidates)

/*******************************************************************************
    condorcetFindWorstResults(relevantCandidates)

    For each relevant candidate A, find the result worst for A in any pairwise
contest AvB, for any relevant candidate B. In the Condorcet method (where all
candidates are relevant) and the Schwartz sequential dropping method (where only
candidates in the Schwartz set are relevant), "A's worst result" means the
greatest number of votes for B. Two alternative definitions are also used,
namely biggest margin of B's victory over A and smallest number of votes for A. 
    Note that this procedure might be called on a subset of the set of all
candidates (a Schwartz set).
    relevantCandidates: an associative array which has a key <k> iff <k> is the
key of a candidate relevant to this stage of the election process.
********************************************************************************
*/
function condorcetFindWorstResults(relevantCandidates)
{
    for(k1 in relevantCandidates) // for every candidate
    {
        c1 = candidates[k1];
        c1.mostVotesAgainst = 0;
        c1.worstDefeat      = 0;
        c1.fewestVotesFor   = big;
    }

cloop:
    for(k1 in relevantCandidates) // for every candidate
    {
        c1 = candidates[k1];
        for(k2 in relevantCandidates) // for every opponent...
        {
            if(k2==k1) // ... earlier in the candidate list
                continue cloop;
            c2 = candidates[k2];

            nPreferences1       = c1.nVotesForMeAgainst[k2];
            nPreferences2       = c2.nVotesForMeAgainst[k1];
            c1.mostVotesAgainst = max(c1.mostVotesAgainst, nPreferences2);
            c2.mostVotesAgainst = max(c2.mostVotesAgainst, nPreferences1);
            c1.worstDefeat      = max(c1.worstDefeat, nPreferences2-nPreferences1);
            c2.worstDefeat      = max(c2.worstDefeat, nPreferences1-nPreferences2);
            c1.fewestVotesFor   = min(c1.fewestVotesFor, nPreferences1);
            c2.fewestVotesFor   = min(c2.fewestVotesFor, nPreferences2);
        }
    }
} // function condorcetFindWorstResults(relevantCandidates)

/*******************************************************************************
    condorcetFindOutrightWinner

    A Condorcet winner in a contest among some candidates is one of them who
beat all the others. There might not be one. However, there cannot be two or
more, for that would entail them beating each other.
    I don't use c.nPairwiseLosses+c.nPairwiseDraws==0 because that expression
relates to the Condorcet contest run on *all* the candidates; this procedure
might be run on a subset.
    Returns the key of the outright winner; null is there is none.
********************************************************************************
*/
function condorcetFindOutrightWinner(relevantCandidates)
{
    var r="";
floop:
    for(k1 in relevantCandidates) // for every candidate
    {
        c1 = candidates[k1];
        // Is c1 the Condorcet winner? Not if there's a c2 who beat c1.
        for(k2 in relevantCandidates) // for every other candidate as opponent...
            if(k2 != k1)
            {
                c2 = candidates[k2];

                nPreferences1       = c1.nVotesForMeAgainst[k2];
                nPreferences2       = c2.nVotesForMeAgainst[k1];
                if(nPreferences1 <= nPreferences2)
                    continue floop; // c1 did not beat c2, so isn't a Condorcet winner
            }

        return k1;
    }

    return null;
} // function condorcetFindOutrightWinner(relevantCandidates)

/*******************************************************************************
    condorcetFindWinnerByLeastOpposition(relevantCandidates)

    In the contest among the relevant candidates, find the Condorcet winners,
i.e. those whose respective worst defeats For each relevant candidate A, find the worst defeat of A by any relevant
candidate B. In the Condorcet method (where all candidates are relevant) and
the Schwartz sequential dropping method (where only candidates in the Schwartz
set are relevant), "A's worst defeat" means the most votes for B in a pairwise
contest AvB. Two alternative definitions are also used.
    Note that this procedure might be called on a subset of the set of all
candidates (a Schwartz set).
    relevantCandidates: an associative array which has a key <k> iff <k> is the
key of a candidate relevant to this stage of the election process.
********************************************************************************
*/
function condorcetFindWinnerByLeastOpposition(relevantCandidates)
{
    var fewestMostVotesAgainst = big, nWinners1 = 0,
        bestWorstDefeat = big, nWinners2 = 0,
        mostFewestVotesFor = 0, nWinners3 = 0, s, r, sep;

    // For each winning criterion, find the value that a candidate must attain,
    //   to win by that criterion
    for(k in relevantCandidates)
    {
        c = candidates[k];
        fewestMostVotesAgainst = min(fewestMostVotesAgainst, c.mostVotesAgainst);
        bestWorstDefeat        = min(bestWorstDefeat,        c.worstDefeat);
        mostFewestVotesFor     = max(mostFewestVotesFor,     c.fewestVotesFor);
    }

    // For each winning criterion, find those candidates that win by that criterion
    for(k in relevantCandidates)
    {
        c = candidates[k];
        if(c.mostVotesAgainst == fewestMostVotesAgainst) // if c wins by "fewest most votes against"
            ++nWinners1;
        if(c.worstDefeat      == bestWorstDefeat) // if c wins by "best worst defeat"
            ++nWinners2;
        if(c.fewestVotesFor   == mostFewestVotesFor) // if c wins by "most fewest votes"
            ++nWinners3;
    }

    if(nWinners1 == 1)
        r = "The only candidate who got no more than " + fewestMostVotesAgainst + " votes against him in any pairwise contest is";
    else
        r = "There is a dead heat between those " + nWinners1 + " candidates who got no more than " + fewestMostVotesAgainst + " votes against them in any pairwise contest:";
    s = "";
    sep = "";
    for(k in relevantCandidates)
    {
        c = candidates[k];
        if(c.mostVotesAgainst==fewestMostVotesAgainst) // if c wins by "fewest most votes against"
        {
            s = s + sep + c.name;
            sep = ", ";
        }
    }
    s = s + ".";
    r = r + " " + s + "\n";

    r = r + "A variant method ";
    if(nWinners2 == 1)
        r = r + "elects the only candidate who was";
    else
        r = r + "declares a dead heat between those " + nWinners2 + " candidates who were";
    r = r + " never defeated";
    if(bestWorstDefeat == 1)
        r = r + " by more than one vote";
    else if(bestWorstDefeat > 1)
        r = r + " by more than " + bestWorstDefeat + " votes";
    sep = " in any pairwise contest: ";
    for(k in relevantCandidates)
    {
        c = candidates[k];
        if(c.worstDefeat      == bestWorstDefeat) // if c wins by "best worst defeat"
        {
            r = r + sep + c.name;
            sep = ", ";
        }
    }
    
    r = r + ".\nA variant method ";
    if(nWinners3 == 1)
        r = r + "elects the only candidate";
    else
        r = r + "declares a dead heat between those " + nWinners3 + " candidates";
    sep = " who got at least " + mostFewestVotesFor + " votes in each pairwise contest: ";
    for(k in relevantCandidates)
    {
        c = candidates[k];
        if(c.fewestVotesFor==mostFewestVotesFor) // if c wins by "most fewest votes"
        {
            r = r + sep + c.name;
            sep = ", ";
        }
    }
    
    r = r + ".\nDetailed info for joint winners:\n";
    for(k in relevantCandidates)
    {
        c = candidates[k];
        if(c.mostVotesAgainst==fewestMostVotesAgainst || c.fewestVotesFor==mostFewestVotesFor) // if c is a joint winner by either means
        {
            r = r + c.name + ": +" + c.nPairwiseWins + "=" + c.nPairwiseDraws + "-" + c.nPairwiseLosses;
            if(c.nPairwiseLosses > 0)
            {
                sep = "; lost to ";
                for(k2 in relevantCandidates)
                {
                    c2 = candidates[k2];
                    nFor = c.nVotesForMeAgainst[k2];
                    nAgainst = c2.nVotesForMeAgainst[k];
                    if(nAgainst > nFor)
                    {
                        r = r + sep + c2.name + " " + nAgainst + "-" + nFor;
                        sep = ", ";
                    }
                }
            }
            if(c.nPairwiseDraws > 0)
            {
                sep = "; drew with ";
                for(k2 in relevantCandidates)
                {
                    if(k2 != k)
                    {
                        c2 = candidates[k2];
                        nFor = c.nVotesForMeAgainst[k2];
                        nAgainst = c2.nVotesForMeAgainst[k];
                        if(nAgainst == nFor)
                        {
                            r = r + sep + c2.name;
                            sep = ", ";
                        }
                    }
                }
            }
            r = r + ".\n";
        }
    }

    // Package the 2 strings to be returned into an object, so that this procedure can return it.
    var o = new Object();
    o.s = s;
    o.r = r;
    return o;
} // function condorcetFindWinnerByLeastOpposition(relevantCandidates)

function reportPairwiseResultsFor(k)
{
    var c = candidates[k];
    var s = "Pairwise result for " + c.name, sep = ": ";

    for(k2 in candidates)
    {
        c2 = candidates[k2];
        if(c2 != c)
        {
            s = s + sep + k2 + ":" + c.nVotesForMeAgainst[k2] + "-" + c2.nVotesForMeAgainst[k];
            sep = ", ";
        }
    }
    return s;
}

/*******************************************************************************
    Procedures for implementing an election by the Condorcet method followed
by Schwartz sequential dropping. If the Condorcet method elected an outright
winner, there is no need to do this (and this procedure is not called).
    Find the Schwartz set. If it has just one member, that is the winner. If it
contains all candidates, Schwartz sequential dropping has proved futile.
Otherwise, run a Condorcet election on it.
********************************************************************************
*/
function schwartzsdFindWinner(relevantCandidates)
{
    var o, schwartz = new Candidates(), nSchwartz = 0;

    schwartzsdFindSchwartzSet(relevantCandidates, schwartz);
    itIsWorthDoing = false;
    for(k in relevantCandidates)
    {
        if(schwartz[k])
        {
            ++nSchwartz;
            schwartzOutrightWinner = k;
        }
        else
        {
            itIsWorthDoing = true;
        }
    }

    if(nSchwartz == 1)
    {
        /* The Schwartz set has just one candidate. That is the outright
           winner. */
        o = new Object();
        c = candidates[schwartzOutrightWinner];
        o.s = c.name + ".";
        o.r = "The Schwartz set consists only of " + c.name + ", who is accordingly elected.\n" + reportPairwiseResultsFor(schwartzOutrightWinner) + "\n";
    }
    else if(itIsWorthDoing)
    {
        r = "";
        sep = "A Condorcet election will be run on the candidates in the Schwartz set: ";
        for(k in schwartz)
        {
            c = candidates[k];
            r = r + sep + c.name;
            sep = ", ";
        }
        r = r + ".\n";

        // Run a Condorcet election on the Schwartz set.
        condorcetInit(schwartz);
        condorcetFindPairwiseScores(schwartz);
        condorcetFindWorstResults(schwartz);
        schwartzOutrightWinner = condorcetFindOutrightWinner(schwartz);

        if(schwartzOutrightWinner == null)
        {
            // There is no outright winner. The Condorcet method elects the
            // candidate(s) with the lowest worst defeat. Note that there may be
            // more than one.
            o = condorcetFindWinnerByLeastOpposition(schwartz);
            o.r = r + o.r;
/*
            r = "";
            for(k in o)
                r = r + " [" + k + "]='" + o[k] + "'";
            document.electform.schwartzsdReport.value = r;
*/
        }
        else
        {
            o = new Object();
            c = candidates[schwartzOutrightWinner];
            o.s = c.name + ".";
            o.r = r + "According to the Condorcet method, " +
                  c.name + " wins outright the election on the Schwartz set.\n" +
                  reportPairwiseResultsFor(schwartzOutrightWinner) + "\n";
        }
    }
    else
    {
        o = new Object();
        o.s = "See the Condorcet results.";
        o.r = "Every candidate is in the Schwartz set, so Schwartz sequential dropping achieves nothing.";
    }

    return o;
} // function schwartzsdFindWinner(relevantCandidates)

/*******************************************************************************
    schwartzsdFindSchwartzSet(relevantCandidates)

    Find the Schwartz set for the given set of candidates C. This is found as
follows. An unbeaten set is a set C1 such that no candidate in C\C1 beats
any in C1. A minimal unbeaten set is one that doesn't contain any unbeaten sets
except (trivially) itself and {}. The Schwartz set is the union of all the
minimal unbeaten sets.
    To find the Schwartz set, it's more convenient to implement another
definition of "unbeaten set": a set C1 such that any candidate who beats one in
C1 is in C1. For each candidate c, its unbeaten set is found by starting with
C1={c}, then repeatedly adding to C1 candidates in C\C1 that beat any in C1,
until no more are to be found. This is the smallest unbeaten set that includes
c, but is not necessarily minimal. Note that, for any two candidates' unbeaten
sets, either they are disjoint or one includes the other. Minimal unbeaten sets
are found as follows: for any candidate c1, for any candidate c2 in c1's
unbeaten set, if c2's is smaller, the c1's is not minimal. 
    Now, if c1's unbeaten set is minimal, it is a subset of the Schwartz set,
and, in particular, c1 is in the Schwartz set. Otherwise, c1 is not in the
Schwartz set. So the Schwartz set is all and only those candidates whose
unbeaten sets are minimal. 

schwartz: a Candidates object. In the course of running this procedure, for
each candidate in the Schwartz set, this object acquires a property keyed by
that candidate's key.
********************************************************************************
*/
function schwartzsdFindSchwartzSet(relevantCandidates, schwartz)
{
    var s="Find the Schwartz set of {", sep = "";

    for(k1 in relevantCandidates) // for every candidate
    {
        c1 = candidates[k1];
        s = s + sep + c1.name;
        sep = ", ";
    }
    s = s + "}:\n";

    for(k1 in relevantCandidates) // for every candidate
    {
        c1 = candidates[k1];
        s = s + "Candidates that beat " + c1.name;
        sep = ": ";
        for(k2 in relevantCandidates) // for every opponent...
        {
            c2 = candidates[k2];
            nPreferences1       = c1.nVotesForMeAgainst[k2];
            nPreferences2       = c2.nVotesForMeAgainst[k1];
            if(nPreferences2 > nPreferences1)
            {
                s = s + sep + c2.name;
                sep = ", ";
            } 
        }
        s = s + ".\n";
    }

    for(k1 in relevantCandidates) // for every candidate
    {
        c1 = candidates[k1];
        c1.unbeatenSet = new Candidates();
        c1.sizeOfUnbeatenSet = 1; // itself
    }

    for(k1 in relevantCandidates) // for every candidate
    {
        c1 = candidates[k1];
        c1.unbeatenSet[k1] = true; // seed c1's unbeaten set

        s = s + "U s for " + k1 + ":";

        thereIsWorkToDo = true;
        while(thereIsWorkToDo)
        {
            thereIsWorkToDo = false;
            loop2:
            for(k2 in relevantCandidates) // for every opponent...
            {
                c2 = candidates[k2];
                if(c1.unbeatenSet[k2])
                    continue; // c2 is already in
                // Seek a c3 in the set, whom c2 beats. If there is one, add c2.
                for(k3 in relevantCandidates)
                {
                    c3 = candidates[k3];
                    if(c1.unbeatenSet[k3] && (c2.nVotesForMeAgainst[k3] > c3.nVotesForMeAgainst[k2]))
                    {
                        // c3 is in and c2 beats c3, so add c2.
                        c1.unbeatenSet[k2] = true; // add c2
                        ++c1.sizeOfUnbeatenSet;
                        thereIsWorkToDo = true;

                        s = s + " add " + k2 + "(beat " + k3 + ")";

                        continue loop2;
                    }
                }
            }
        }

        s = s + " ";

        s = s + "The u s seeded by " + c1.name + " has " + c1.sizeOfUnbeatenSet;
        sep = " members: {";
        for(k2 in c1.unbeatenSet)
        {
            c2 = candidates[k2];
            s = s + sep + c2.name;
            sep = ", ";
        }
        s = s + "}.\n";
    }

gloop:
    for(k1 in relevantCandidates) // for every candidate
    {
        c1 = candidates[k1];
        for(k2 in c1.unbeatenSet)
        {
            c2 = candidates[k2];
            if(c2.sizeOfUnbeatenSet < c1.sizeOfUnbeatenSet)
                continue gloop; // c1's unbeaten set is not minimal, so c1 is not in the Schwartz set
        }

        // c1 is in the Schwartz set
        schwartz[k1] = true;
    }

    return s;
} // function schwartzsdFindSchwartzSet(relevantCandidates)

/*******************************************************************************
    Procedures for implementing an election by the Copeland method
********************************************************************************
*/
function copelandFindWinner(candidates)
{
    var score, bestScore = 0, nWinners1 = 0, r="", s="";

    condorcetInit(candidates);
    condorcetFindPairwiseScores(candidates);

    for(k in candidates)
    {
        c = candidates[k];
        score = 2*c.nPairwiseWins + c.nPairwiseDraws;
        c.CopelandScore = score;
        bestScore = max(bestScore, score);
    }

    for(k in candidates)
    {
        c = candidates[k];
        if(c.CopelandScore==bestScore)
        {
            ++nWinners1;
        }
    }
    if(nWinners1==1)
        r = "The Copeland method elects the only candidate";
    else
        r = "According to the Copeland method, there is no outright winner; this method declares a dead heat between the " +
            nWinners1 + " candidates";
    r = r + " who got a Copeland score of " + bestScore + ": ";

    sep = "";
    for(k in candidates)
    {
        c = candidates[k];
        if(c.CopelandScore==bestScore)
        {
            s = s + sep + c.name;
            r = r + sep + c.name + " (+" + c.nPairwiseWins + "=" + c.nPairwiseDraws + "-" + c.nPairwiseLosses + ")";
            sep = ", ";
        }
    }
    s = s + ".";
    r = r + ".";

    // Package the 2 strings to be returned into an object, so that this procedure can return it.
    var o = new Object();
    o.s = s;
    o.r = r;
    return o;
} // function copelandFindWinner(candidates)

/*******************************************************************************
    Odds and sods which should be in JavaScript
********************************************************************************
*/
function max(a, b)
{
    if(a>b) return a;
    return b;
}

function min(a, b)
{
    if(a<b) return a;
    return b;
}