STV

_STV.md

STV

This started out as a Google Sheets function for Single Transferable Vote, but now offers an index.html for usage locally. Open the relevant Google Sheet, copy the input values into the text field. There is also a save button to keep a track of past votes locally.

code.js

const KEEP_DEACTIVATED_QUESTIONS = false;

const PROTECTED_QUESTION_TYPES = [FormApp.ItemType.TEXT, FormApp.ItemType.PAGE_BREAK];

function formRegenerator(e) {
  const spreadsheet = SpreadsheetApp.getActive();
  const workingFlag = spreadsheet.getRangeByName("Working")
  if (!e || e.range.columnStart != 1 || e.range.getSheet().getName() != "Manager") return;
  if (workingFlag.getValue()) return;
  try {
    workingFlag.setValue(true);
    confirmedFormRegenerator();
  } finally {
    workingFlag.setValue(false);
  }
}

function confirmedFormRegenerator() {
  const spreadsheet = SpreadsheetApp.getActive();
  const questions = getQuestionMap(spreadsheet);
  let anyActive = questions.some(q => q.active);


  const formURL = spreadsheet.getFormUrl();
  const form = FormApp.openByUrl(formURL);
  const FPTP2 = spreadsheet.getRangeByName("FPTPMulti").getValue();
  const STV = spreadsheet.getRangeByName("STV").getValue();
  const FPTP2desc = spreadsheet.getRangeByName("FPTPMultiDesc").getValue();
  const STVdesc = spreadsheet.getRangeByName("STVdesc").getValue();
  form.setAcceptingResponses(false);

  let pageSplit = form.getItems(FormApp.ItemType.PAGE_BREAK)[0];
  if (KEEP_DEACTIVATED_QUESTIONS) {
    if (pageSplit === undefined) {
      pageSplit = form.addPageBreakItem();
      pageSplit.setTitle("Deactivated questions");
      pageSplit.setGoToPage(FormApp.PageNavigationType.SUBMIT);
    }
  } else if (pageSplit !== undefined) form.deleteItem(pageSplit);

  const formQuestions = form.getItems().filter(question => PROTECTED_QUESTION_TYPES.indexOf(question.getType()) < 0);
  for (const formQuestion of formQuestions) {
    const formQuestionTitle = formQuestion.getTitle();
    const filteredQuestions = questions.filter(q => q.question == formQuestionTitle);

    const question = filteredQuestions[0];

    if (question === undefined) {
      form.deleteItem(formQuestion.getIndex());
    } else question.formQuestion = formQuestion;
  }

  for (const question of questions) {
    if (question.type == FPTP2) {
      const positions = parseInt(question.param);
      if (question.formQuestion && question.formQuestion.getType() != FormApp.ItemType.GRID) {
        form.deleteItem(question.formQuestion.getIndex());
        delete question.formQuestion;
      }
      if (!question.formQuestion) question.formQuestion = form.addGridItem();
      else question.formQuestion = question.formQuestion.asGridItem();
      question.formQuestion.setHelpText(FPTP2desc.replace("2", positions));
      question.formQuestion.setColumns(question.answers);
      const rows = 'ABCDEFGHIJKLMNOQRSTUVWXYZ'.split('').slice(0, positions).map(letter => "Vote " + letter);
      if (JSON.stringify(rows) != JSON.stringify(question.formQuestion.getRows())) {
        question.formQuestion.setRows(rows);
      }
    } else if (question.type == STV) {
      const positions = parseInt(question.param);
      if (question.formQuestion && question.formQuestion.getType() != FormApp.ItemType.GRID) {
        form.deleteItem(question.formQuestion.getIndex());
        delete question.formQuestion;
      }
      if (!question.formQuestion) question.formQuestion = form.addGridItem();
      else question.formQuestion = question.formQuestion.asGridItem();
      question.formQuestion.setHelpText(STVdesc);
      question.formQuestion.setValidation(FormApp.createGridValidation().setHelpText("You cannot vote for the same candidate in multiple positions.").requireLimitOneResponsePerColumn().build())
      question.formQuestion.setColumns(question.answers);
      const rows = question.answers.map((_, i) => "Preference #" + (i + 1));
      if (JSON.stringify(rows) != JSON.stringify(question.formQuestion.getRows())) {
        question.formQuestion.setRows(rows);
      }
    } else {
      if (question.formQuestion && question.formQuestion.getType() != FormApp.ItemType.MULTIPLE_CHOICE) {
        form.deleteItem(question.formQuestion.getIndex());
        delete question.formQuestion;
      }
      if (!question.formQuestion) question.formQuestion = form.addMultipleChoiceItem();
      else question.formQuestion = question.formQuestion.asMultipleChoiceItem();
      question.formQuestion.setChoiceValues(question.answers);
    }
    question.formQuestion.setTitle(question.question);
    if (KEEP_DEACTIVATED_QUESTIONS) {
      moveToAboveOrBelow(form, question.formQuestion.getIndex(), pageSplit.getIndex(), question.active);
    }
  }
  form.setAcceptingResponses(anyActive);
}

function moveToAboveOrBelow(form, current, heading, before) {
  if (!before && heading > current) form.moveItem(current, heading);
  else if (before && heading < current) form.moveItem(current, heading);
}

function getSheetRange(spreadsheet, name) {
  const range = spreadsheet.getRangeByName(name).getValues();
  return range.slice(1);
}

function getSheetColumn(spreadsheet, name) {
  return getColumn(getSheetRange(spreadsheet, name));
}

function extractQuestionMap(questions, questionTypes, questionParams, actives, argcs, argvs) {
  const questionMap = questions.map((question, i) => ({ question, type: questionTypes[i], param: questionParams[i], answers: argvs[i].slice(0, argcs[i]), i, active: !!actives[i] }));
  return questionMap.filter(q => q.question != "" && q.answers.length != 0 && (q.active || KEEP_DEACTIVATED_QUESTIONS));
}

function getQuestionMap(spreadsheet) {
  return extractQuestionMap(
    getSheetColumn(spreadsheet, "Questions"),
    getSheetColumn(spreadsheet, "QuestionTypes"),
    getSheetColumn(spreadsheet, "QuestionParams"),
    getSheetColumn(spreadsheet, "Actives"),
    getSheetColumn(spreadsheet, "AnswerCounts"),
    getSheetRange(spreadsheet, "Answers")
  );
}

function getColumn(grid) {
  return grid.map(row => row[0]);
}

/**
* @customfunction
*/
function COORD_LAST(csy, csx, range) {
  const xs = csx.split(',');
  const ys = csy.split(',');
  return LAST(ys.map(y => xs.map(x => range[y - 1][x - 1])));
}

function COORDS_LAST(csy, csx, range) {
  const xss = csx[0].map(xs => xs.split(',').filter(x => x));
  const yss = csy.map(ys => ys[0].split(',').filter(y => y));
  return yss.map(ys => xss.map(xs => LAST(ys.map(y => xs.map(x => range[y - 1][x - 1])))));
}

/**
* Takes the last non-empty cell in a range.
*
* @param {number|number[][]} cells The cells to look for a value in.
* @return The last value in the range.
* @customfunction
*/
function LAST(cells) {
  if (cells.map) {
    cells = cells.flatMap(x => x);
  } else cells = [cells];
  cells = cells.filter(x => x !== undefined && x !== "");
  cells = cells[cells.length - 1];
  return cells;
}

function onlyUnique(value, index, self) {
  return self.indexOf(value) === index;
}

/**
* @customfunction
*/
function RUN_MULTI_FPTP(allVotes, ron) {
  const candidates = {};
  function placeVote(name) {
    candidates[name] = (candidates[name] || 0) + 1;
  }
  let voters = 0;
  for (const row of allVotes) {
    if (row.filter(entry => entry).length > 0) voters++;
    // Count non-rons
    const votes = row.filter(entry => entry && entry != ron).filter(onlyUnique);
    for (const vote of votes) placeVote(vote);

    // Count rons
    const theseRons = row.filter(entry => entry && entry == ron).length;
    for (let i = 1; i <= theseRons; i++) placeVote("RON," + i);
  }
  if (Object.entries(candidates).length == 0) return "No votes";
  return [Object.entries(candidates).sort((a, b) => b[1] - a[1]).map(([name, count]) => name.split(',')[0] + " (" + count + ", " + ((count / voters) * 100).toFixed(1) + "%)")];
}

// Cut an array off at the first undefined/empty value
function cutOffArray(array) {
  const emptyIndex = array.findIndex(x => typeof x === "undefined" || x === "");
  if (emptyIndex >= 0) array.length = emptyIndex;
  return array;
}

/**
 * @customfunction
 */
function RUN_STV(allVotes, headings, ron, positions) {
  allVotes = allVotes.map ? allVotes : [[allVotes]];
  headings = headings.map ? headings[0] : [headings];
  const preferencePositions = [];
  headings.forEach(function (title, i) {
    const [first, second] = title.split('#');
    if (!second) return;
    const position = parseInt(second);
    if (isNaN(position)) return;
    preferencePositions[position - 1] = i;
  });
  // if a single position is missing from the form, remove all subsequent position votes
  cutOffArray(preferencePositions);

  const voteArrays = allVotes.flatMap(function (vote) {
    const row = preferencePositions.map((col) => vote[col]);
    cutOffArray(row);
    if (row.length) return [row];
    else return [];
  });
  //return JSON.stringify(voteArrays);
  try {
    const { log, winners } = executeSTV(voteArrays, ron, positions);
    return [[...winners.map(x => x.name), log.map(entry => entry.sort((a, b) => a.candidate.name.localeCompare(b.candidate.name))).join('\n')]];
  } catch (e) {
    return e.message + '\n' + e.stack.toString();
  }
}

executeSTV.js

function executeSTV(/** @type {string[][]} */ voteArrays, /** @type {string} */ ron, positions, /** @type {string[]} */ allCandidates) {
  // throw new Error(JSON.stringify({voteArrays, ron, positions}));
  /** @type {Record<string, Candidate>} */
  const candidateMap = {};

  const votes = voteArrays.map(function (vote) {
    const row = vote.map((candidateString) => {
      if (!candidateMap[candidateString]) {
        const index = allCandidates.indexOf(candidateString);
        candidateMap[candidateString] =
          candidateString == ron
            ? STV.Candidate.ron(index)
            : new STV.Candidate(candidateString, index);
      }
      return candidateMap[candidateString];
    });
    return new STV.Vote(row);
  });
  const candidatesWithVotes = Object.values(candidateMap);
  const candidates = candidatesWithVotes.concat(
    ...allCandidates.map((candidateString, i) =>
    candidateString !== ron && candidatesWithVotes.find(candidate => candidate.name === candidateString) === undefined ?
        new STV.Candidate(candidateString, i) :
        null
    ).filter(Boolean)
  );

  const log = [];

  const winners = STV.determineWinnersIteratively(
    positions,
    votes,
    candidates,
    log
  );
  return { log, winners };
}

fraction.js

// @ts-check

'use strict';
// https://github.com/ekg/fraction.js
/*
fraction.js
A Javascript fraction library.
Copyright (c) 2009  Erik Garrison <erik@hypervolu.me>
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/

/* Fractions */
/*
 *
 * Fraction objects are comprised of a numerator and a denomenator.  These
 * values can be accessed at fraction.numerator and fraction.denomenator.
 *
 * Fractions are always returned and stored in lowest-form normalized format.
 * This is accomplished via Fraction.normalize.
 *
 * The following mathematical operations on fractions are supported:
 *
 * Fraction.equals
 * Fraction.add
 * Fraction.subtract
 * Fraction.multiply
 * Fraction.divide
 *
 * These operations accept both numbers and fraction objects.  (Best results
 * are guaranteed when the input is a fraction object.)  They all return a new
 * Fraction object.
 *
 * Usage:
 *
 * TODO
 *
 */

/**
 * The Fraction constructor takes one of:
 *   an explicit numerator (integer) and denominator (integer),
 *   a string representation of the fraction (string),
 *   or a floating-point number (float)
 *
 * These initialization methods are provided for convenience.  Because of
 * rounding issues the best results will be given when the fraction is
 * constructed from an explicit integer numerator and denomenator, and not a
 * decimal number.
 *
 *
 * e.g. new Fraction(1, 2) --> 1/2
 *      new Fraction('1/2') --> 1/2
 *      new Fraction('2 3/4') --> 11/4  (prints as 2 3/4)
 *
 * @returns {Fraction}
 */
function Fraction(numerator, denominator) {
  if (!(this instanceof Fraction)) return new Fraction(numerator, denominator);
  /* double argument invocation */
  if (typeof numerator !== 'undefined' && denominator) {
    if (
      (typeof numerator === 'number' || numerator instanceof Number) &&
      (typeof denominator === 'number' || denominator instanceof Number)
    ) {
      this.numerator = numerator;
      this.denominator = denominator;
    } else if (
      (typeof numerator === 'string' || numerator instanceof String) &&
      (typeof denominator === 'string' || denominator instanceof String)
    ) {
      // what are they?
      // hmm....
      // assume they are floats?
      this.numerator = parseFloat(numerator.replace(',', '.'));
      this.denominator = parseFloat(denominator.replace(',', '.'));
    }
    // TODO: should we handle cases when one argument is String and another is Number?
    /* single-argument invocation */
  } else if (typeof denominator === 'undefined') {
    var num = numerator; // swap variable names for legibility
    if (num instanceof Fraction) {
      this.numerator = num.numerator;
      this.denominator = num.denominator;
    } else if (typeof num === 'number' || num instanceof Number) {
      // just a straight number init
      this.numerator = num;
      this.denominator = 1;
    } else if (typeof num === 'string' || num instanceof String) {
      var a, b; // hold the first and second part of the fraction, e.g. a = '1' and b = '2/3' in 1 2/3
      // or a = '2/3' and b = undefined if we are just passed a single-part number
      var arr = num.split(' ');
      if (arr[0]) a = arr[0];
      if (arr[1]) b = arr[1];
      /* compound fraction e.g. 'A B/C' */
      //  if a is an integer ...
      if (parseFloat(a) % 1 === 0 && b && b.match('/')) {
        return new Fraction(a).add(new Fraction(b));
      } else if (a && !b) {
        /* simple fraction e.g. 'A/B' */
        if (typeof a === 'string' && a.match('/')) {
          // it's not a whole number... it's actually a fraction without a whole part written
          var f = a.split('/');
          this.numerator = f[0];
          this.denominator = f[1];
          /* string floating point */
        } else if (typeof a === 'string' && a.match('.')) {
          return new Fraction(parseFloat(a.replace(',', '.')));
          /* whole number e.g. 'A' */
        } else {
          // just passed a whole number as a string
          this.numerator = parseInt(a);
          this.denominator = 1;
        }
      } else {
        return undefined; // could not parse
      }
    }
  }
  this.normalize();
}

Fraction.prototype.clone = function () {
  return new Fraction(this.numerator, this.denominator);
};

/* round down */
Fraction.prototype.floor = function () {
  if (isNaN(this.denominator)) return NaN;
  return Math.floor(this.numerator / this.denominator);
};

Fraction.prototype.signum = function () {
  if (this.denominator == 0) return NaN;
  if (this.numerator == 0) return 0;
  if (this.numerator > 0 == this.denominator > 0) return 1;
  return -1;
};

/** @returns {number} */
Fraction.prototype.valueOf = function () {
  if (this.denominator == 0) return NaN;
  return this.numerator / this.denominator;
};

Fraction.prototype.compare = function (other) {
  return this.subtract(other).signum();
};

/* pretty-printer, converts fractions into whole numbers and fractions */
Fraction.prototype.toString = function () {
  if (isNaN(this.denominator))
    //	if (this.denominator !== this.denominator) //They say it would be faster. (?)
    return 'NaN';
  var result = '';
  if (this.numerator < 0 != this.denominator < 0) result = '-';
  var numerator = Math.abs(this.numerator);
  var denominator = Math.abs(this.denominator);

  var wholepart = Math.floor(numerator / denominator);
  numerator = numerator % denominator;
  if (wholepart != 0) result += wholepart;
  if (numerator != 0) {
    if (wholepart != 0) result += ' ';
    result += numerator + '/' + denominator;
  }
  return result.length > 0 ? result : '0';
};

/* destructively rescale the fraction by some integral factor */
Fraction.prototype.rescale = function (factor) {
  this.numerator *= factor;
  this.denominator *= factor;
  return this;
};

/** @returns {Fraction} */
Fraction.prototype.add = function (/** @type {Fraction|number|string} */ b) {
  var a = this.clone();
  if (b instanceof Fraction) {
    b = b.clone();
  } else {
    b = new Fraction(b);
  }
  var td = a.denominator;
  a.rescale(b.denominator);
  a.numerator += b.numerator * td;

  return a.normalize();
};

/** @returns {Fraction} */
Fraction.prototype.subtract = function (
  /** @type {Fraction|number|string} */ b
) {
  var a = this.clone();
  if (b instanceof Fraction) {
    b = b.clone(); // we scale our argument destructively, so clone
  } else {
    b = new Fraction(b);
  }
  var td = a.denominator;
  a.rescale(b.denominator);
  a.numerator -= b.numerator * td;

  return a.normalize();
};

/** @returns {Fraction} */
Fraction.prototype.multiply = function (
  /** @type {Fraction|number|string} */ b
) {
  var a = this.clone();
  if (b instanceof Fraction) {
    a.numerator *= b.numerator;
    a.denominator *= b.denominator;
  } else if (typeof b === 'number') {
    a.numerator *= b;
  } else {
    return a.multiply(new Fraction(b));
  }
  return a.normalize();
};

/** @returns {Fraction} */
Fraction.prototype.divide = function (/** @type {Fraction|number|string} */ b) {
  var a = this.clone();
  if (b instanceof Fraction) {
    a.numerator *= b.denominator;
    a.denominator *= b.numerator;
  } else if (typeof b === 'number') {
    a.denominator *= b;
  } else {
    return a.divide(new Fraction(b));
  }
  return a.normalize();
};

/** @returns {boolean} */
Fraction.prototype.equals = function (/** @type {Fraction|number|string} */ b) {
  b = b instanceof Fraction ? b : new Fraction(b);

  // fractions that are equal should have equal normalized forms
  var a = this.clone().normalize();
  b = b.clone().normalize();
  return (
    a.numerator === /** @type {Fraction} */ (b).numerator &&
    a.denominator === /** @type {Fraction} */ (b).denominator
  );
};

/* Utility functions */

/* Destructively normalize the fraction to its smallest representation.
 * e.g. 4/16 -> 1/4, 14/28 -> 1/2, etc.
 * This is called after all math ops.
 */
/** @returns {Fraction} */
Fraction.prototype.normalize = function () {
  var isFloat = function (n) {
    return (
      typeof n === 'number' &&
      ((n > 0 && n % 1 > 0 && n % 1 < 1) ||
        (n < 0 && n % -1 < 0 && n % -1 > -1))
    );
  };

  var roundToPlaces = function (n, places) {
    if (!places) {
      return Math.round(n);
    } else {
      var scalar = Math.pow(10, places);
      return Math.round(n * scalar) / scalar;
    }
  };

  // XXX hackish.  Is there a better way to address this issue?
  //
  /* first check if we have decimals, and if we do eliminate them
    * multiply by the 10 ^ number of decimal places in the number
    * round the number to nine decimal places
    * to avoid js floating point funnies
    */
  if (isFloat(this.denominator)) {
    var rounded = roundToPlaces(this.denominator, 9);
    var scaleup = Math.pow(10, rounded.toString().split('.')[1].length);
    this.denominator = Math.round(this.denominator * scaleup); // this !!! should be a whole number
    this.numerator *= scaleup;
  }
  if (isFloat(this.numerator)) {
    var rounded = roundToPlaces(this.numerator, 9);
    var scaleup = Math.pow(10, rounded.toString().split('.')[1].length);
    this.numerator = Math.round(this.numerator * scaleup); // this !!! should be a whole number
    this.denominator *= scaleup;
  }
  var gcf = Fraction.gcf(this.numerator, this.denominator);
  this.numerator /= gcf;
  this.denominator /= gcf;
  if (this.denominator < 0) {
    this.numerator *= -1;
    this.denominator *= -1;
  }
  return this;
}

/* Takes two numbers and returns their greatest common factor. */
//Adapted from Ratio.js
/** @returns {number} */
Fraction.gcf = function (/** @type {number} */ a, /** @type {number} */ b) {
  if (arguments.length < 2) {
    return a;
  }
  var c;
  a = Math.abs(a);
  b = Math.abs(b);
  /*  //It seems to be no need in these checks
  // Same as isNaN() but faster
  if (a !== a || b !== b) {
  return NaN;
  }
  //Same as !isFinite() but faster
  if (a === Infinity || a === -Infinity || b === Infinity || b === -Infinity) {
  return Infinity;
  }
  // Checks if a or b are decimals
  if ((a % 1 !== 0) || (b % 1 !== 0)) {
  throw new Error("Can only operate on integers");
  }
  */

  while (b) {
    c = a % b;
    a = b;
    b = c;
  }
  return a;
};

//Not needed now
// Adapted from:
// http://www.btinternet.com/~se16/js/factor.htm
Fraction.primeFactors = function (n) {
  var num = Math.abs(n);
  var factors = [];
  var _factor = 2; // first potential prime factor

  while (_factor * _factor <= num) {
    // should we keep looking for factors?
    if (num % _factor === 0) {
      // this is a factor
      factors.push(_factor); // so keep it
      num = num / _factor; // and divide our search point by it
    } else {
      _factor++; // and increment
    }
  }

  if (num != 1) {
    // If there is anything left at the end...
    // ...this must be the last prime factor
    factors.push(num); //    so it too should be recorded
  }

  return factors; // Return the prime factors
};

Fraction.prototype.snap = function (max, threshold) {
  if (!threshold) threshold = 0.0001;
  if (!max) max = 100;

  var negative = this.numerator < 0;
  var decimal = this.numerator / this.denominator;
  var fraction = Math.abs(decimal % 1);
  var remainder = negative ? Math.ceil(decimal) : Math.floor(decimal);

  for (var denominator = 1; denominator <= max; ++denominator) {
    for (var numerator = 0; numerator <= max; ++numerator) {
      var approximation = Math.abs(numerator / denominator);
      if (Math.abs(approximation - fraction) < threshold) {
        return new Fraction(
          remainder * denominator + numerator * (negative ? -1 : 1),
          denominator
        );
      }
    }
  }

  return new Fraction(this.numerator, this.denominator);
};

index.html

<!DOCTYPE html>
<html>
  <script src="fraction.js"></script>
  <script src="stv.js"></script>
  <script src="executeSTV.js"></script>
  <p>Paste the output of Google Sheets here (in Google Sheets, Ctrl-A, Ctrl-C):</p>
  <div>
    <textarea id="input" autocomplete="off" rows="6"></textarea>
  </div>
  <p>
    <button id="submit">Submit</button>
    <button id="reload" hidden>Clear</button>
  </p>
  <pre id="output"></pre>
  <p>
    <button id="save" hidden>Save to history</button>
  </p>
  <p>
    <button id="showHistory">Show history</button>
  </p>
  <table hidden>
    <thead>
      <tr>
        <th colspan="3">History</th>
      </tr>
      <tr><th>Date</th><th>Input</th><th>Output</th></tr>
    </thead>
    <tbody></tbody>
    <tfoot>
      <tr>
        <td colspan="3">
          <button id="clearHistory">Clear history</button>
        </td>
      </tr>
    </tfoot>
  </table>
  <script src="ui.js"></script>

  <style>
    #input {
      tab-size: 12;
      flex: 1;
    }
    div {
      display: flex;
    }
    .error {
      color: red;
    }

    html {
      font-family: sans-serif;
    }
    table {
      width: 100%;
    }

    table td:first-child {
      width: min-content;
    }

    textarea:read-only {
      box-sizing: border-box;
      width: 100%;
    }
  </style>
</html>

stv.js

// @ts-check

// based on https://github.com/alizain/stv

const STV = (function () {
  /**
   * Calculate the Droop Quota: the number of votes anyone needs to win
   *
   * This will decrease as votes are invalidated.
   *
   * @param {number} vacancies
   * @param {number} numVotes
   * @returns {number}
   */
  function droopQuota(vacancies, numVotes) {
    return new Fraction(numVotes, 1 + vacancies).add(1).floor();
  }

  /** @param {Candidate[]} prefs */
  function Vote(prefs) {
    if (!(this instanceof Vote)) return new Vote(prefs);
    this.prefs = prefs;
  }

  function WeightedVote(/** @type {Vote} */ vote) {
    if (!(this instanceof WeightedVote)) return new WeightedVote(vote);
    this.vote = vote;
    /** @type {Fraction} */ this.value = new Fraction(1);
  }

  /**
   * @param {Candidate[]} candidates
   * @returns {Candidate | null}
   */
  WeightedVote.prototype.mostPreferred = function (candidates) {
    const ronLeft = candidates.some((c) => c.isFreeRon());
    const prefCandidate = this.vote.prefs.find((c) =>
      c.isRon() ? ronLeft : candidates.includes(c)
    );
    if (!prefCandidate) return null;
    return prefCandidate.indirect();
  };
  WeightedVote.prototype.updateValueWithSurplusRatio = function (
    /** @type {Fraction} */ surplusRatio
  ) {
    this.value = this.value.multiply(surplusRatio);
  };
  WeightedVote.prototype.toString = function () {
    return (
      'Vote(' + this.vote.prefs.join(', ') + ', weight = ' + this.value + ')'
    );
  };

  function CandidateResult(/** @type {Candidate} */ candidate) {
    if (!(this instanceof CandidateResult))
      return new CandidateResult(candidate);
    this.candidate = candidate;
    /** @type {WeightedVote[]} */ this.cachedVotes = [];
    /** @type {Fraction} */ this.cachedValue = Fraction(0);
    this.hasWon = false;
    /** @type {Fraction[]} */ this.valueHistory = [];
  }
  CandidateResult.prototype.saveWeightedVote = function (
    /** @type {WeightedVote} */ vote
  ) {
    this.cachedValue = this.cachedValue.add(vote.value);
    this.cachedVotes.push(vote);
  };
  CandidateResult.prototype.isWinner = function (/** @type {number} */ quota) {
    return this.cachedValue.compare(quota) >= 0;
  };
  CandidateResult.prototype.isVoteSurplus = function (
    /** @type {number} */ quota
  ) {
    return this.cachedValue.compare(quota) > 0;
  };
  CandidateResult.prototype.declareVoteSurplus = function (
    /** @type {number} */ quota
  ) {
    if (this.cachedValue.compare(quota) <= 0) {
      throw new Error();
    }
    const surplusRatio = this.calculateSurplusRatio(quota);
    this.hasWon = true;
    this.cachedVotes.forEach((rv) =>
      rv.updateValueWithSurplusRatio(surplusRatio)
    );
    this.cachedValue = Fraction(quota);
    return this.cachedVotes;
  };
  CandidateResult.prototype.calculateSurplusRatio = function (
    /** @type {number} */ quota
  ) {
    if (this.cachedValue.compare(quota) <= 0) {
      throw new Error();
    }
    return this.cachedValue.subtract(quota).divide(this.cachedValue);
  };

  /** @typedef {{type: 'snapshot', snapshot: CandidateResultSnapshot[]} | {type: 'ties', ties: string[]}}
   *            LogEntry */
  /** @typedef {{ value: Fraction, votes: WeightedVote[], hasWon: boolean, candidate: Candidate, toString(): String }}
   *            CandidateResultSnapshot */
  /** @returns {CandidateResultSnapshot} */
  CandidateResult.prototype.snapshot = function () {
    return {
      value: this.cachedValue,
      votes: [...this.cachedVotes],
      candidate: this.candidate,
      hasWon: this.hasWon,
      toString: function () {
        return (
          '(' +
          this.candidate +
          ': ' +
          (this.hasWon ? 'elected, ' : '') +
          this.value +
          // ' (' +
          // this.votes.length +
          // ' votes)' +
          ')'
        );
      },
    };
  };

  /**
   * @param {CandidateResult} a
   * @param {CandidateResult} b
   * @param {Map<Candidate, string[]>} ties
   * @returns {number}
   */
  CandidateResult.sortHighest = function (a, b, ties) {
    // higher is "better", i.e. occurs first in array, so b - a
    const byValue = b.cachedValue.subtract(a.cachedValue);
    if (byValue.compare(0) !== 0) return byValue.valueOf();

    // the one that’s been around the longest (favouring non-RON, as a result of 5.2.3/5.2.5)
    const byRoundAge = b.valueHistory.length - a.valueHistory.length;
    if (byRoundAge !== 0) return byRoundAge;

    // the one that started with the most votes (5.2.3/5.2.5)
    for (let i = 0; i < a.valueHistory.length; i++) {
      const byPreviousVote = b.valueHistory[i].subtract(a.valueHistory[i]);
      if (!byPreviousVote.equals(0)) {
        const signum = byPreviousVote.signum();
        const [winner, loser] = signum > 0 ? [b, a] : [a, b];
        const tieMessage = `Candidate ${winner.candidate.name} favoured over ${loser.candidate.name} based on positions in previous rounds.`
        mapGetOrDefault(ties, a.candidate, []).push(tieMessage);
        mapGetOrDefault(ties, b.candidate, []).push(tieMessage);
        return signum;
      }
    }
    // This should be resolved by the returning officer.
    // We solve this manually by taking the positions of candidates in the list (lower is better)
    const indexDiff = a.candidate.index - b.candidate.index;
    const [winner, loser] = indexDiff > 0 ? [b, a] : [a, b];
    const tieMessage = `Candidate ${winner.candidate.name} favoured over ${loser.candidate.name} using tie break.`;
    mapGetOrDefault(ties, a.candidate, []).push(tieMessage);
    mapGetOrDefault(ties, b.candidate, []).push(tieMessage);
    return indexDiff;
  };

  function ResultMap() {
    if (!(this instanceof ResultMap)) return new ResultMap();
    /** @type {Map<Candidate, CandidateResult>} */ this.map = new Map();
  }
  ResultMap.fromCandidates = function (/** @type {Candidate[]} */ candidates) {
    const resultMap = new ResultMap();
    candidates.forEach((c) => resultMap.map.set(c, new CandidateResult(c)));
    return resultMap;
  };
  /**
   * @param {WeightedVote[]} votes
   * @param {Candidate[]} validCandidates
   * @returns {number}
   */
  ResultMap.prototype.saveWeightedVotes = function (votes, validCandidates) {
    let nonTransferables = 0;
    votes.forEach((vote) => {
      const prefCandidate = vote.mostPreferred(
        validCandidates
      );
      // handle an exhausted vote
      if (prefCandidate === null) nonTransferables++;
      else {
        const prefCandidateResult = this.map.get(prefCandidate);
        prefCandidateResult.saveWeightedVote(vote);
      }
    });
    // used for tie-breaking
    for (const candidateResult of this.map.values())
      candidateResult.valueHistory.push(candidateResult.cachedValue);
    return nonTransferables;
  };
  /**
   * @param {Candidate} candidate
   */
  ResultMap.prototype.addRon = function (candidate) {
    this.map.set(candidate, new CandidateResult(candidate));
  };
  ResultMap.prototype.getSortedResults = function (/** @type {Map<Candidate, string[]>} */ ties) {
    return Array.from(this.map.values()).sort((a,b) => CandidateResult.sortHighest(a, b, ties));
  };
  /** @returns {CandidateResultSnapshot[]} */
  ResultMap.prototype.snapshot = function () {
    return this.getSortedResults(new Map()).map((result) => result.snapshot());
  };

  function Candidate(/** @type {string} */ name, /** @type {number} */ index) {
    if (!(this instanceof Candidate)) return new Candidate();
    this.name = name;
    this.index = index === -1 ? Infinity : index;
    this.ronIndex = 0;
    this.child = null;
  }
  /** @returns {Candidate} */
  Candidate.ron = function (/** @type {number} */ index) {
    const ronIndex = 1;
    const ron = new Candidate('RON', index);
    ron.child = null;
    ron.ronIndex = ronIndex;
    return ron;
  };
  Candidate.prototype.duplicate = function () {
    if (!this.isRon()) throw new Error();
    const ronIndex = this.ronIndex + 1;
    const ron = new Candidate('RON ' + ronIndex, this.index);
    this.child = ron;
    ron.child = null;
    ron.ronIndex = ronIndex;
    return ron;
  };
  /** @returns {Candidate} */
  Candidate.prototype.indirect = function () {
    if (!this.isRon()) return this;
    else if (this.child === null) return this;
    else return this.child.indirect();
  };
  Candidate.prototype.isRon = function () {
    return this.ronIndex != 0;
  };
  Candidate.prototype.isFreeRon = function () {
    return this.isRon() && this.child === null;
  };
  /**
   * @param {Candidate[]} candidates
   * @param {Candidate} candidateToRemove
   */
  Candidate.filterCandidateFromList = function (candidates, candidateToRemove) {
    return candidates.filter((c) => c !== candidateToRemove);
  };
  Candidate.prototype.toString = function () {
    return this.name;
  };

  /**
   * Get a value from a map, setting it if not set
   *
   * @param {Map<K, V>} map
   * @param {K} key
   * @param {V} value
   * @template K
   * @template V
   */
  function mapGetOrDefault(map, key, value) {
    if (!map.has(key)) {
      map.set(key, value);
    }
    return map.get(key);
  }

  /**
   * @param {number} quota
   * @param {number} votesLeft
   * @param {Candidate[]} candidates
   * @param {ResultMap} resultMap
   * @param {LogEntry[]=} log
   * @returns {{ candidates: Candidate[], votesLeft: number }}
   */
  function calculateStableVoteResult(
    quota,
    votesLeft,
    candidates,
    resultMap,
    log
  ) {
    while (true) {
      /** @type {Map<Candidate, string[]>} */
      const ties = new Map();

      if (log !== undefined) log.push({type:'snapshot', snapshot:resultMap.snapshot()});

      const surplusCandidate = determineSurplusCandidate(quota, resultMap, ties);

      if (surplusCandidate === false) {
        for (const winner of determineExactWinnerCandidates(quota, resultMap, ties)) {
          resultMap.map.get(winner).hasWon = true;
          candidates = Candidate.filterCandidateFromList(candidates, winner);
        }

        return { candidates, votesLeft };
      }

      if (log !== undefined && ties.get(surplusCandidate)) {
        log.push({type:'ties', ties: ties.get(surplusCandidate)});
      }

      candidates = Candidate.filterCandidateFromList(
        candidates,
        surplusCandidate
      );
      if (surplusCandidate.isRon() && !surplusCandidate.child) {
        const newRon = surplusCandidate.duplicate();
        resultMap.addRon(newRon);
        candidates.push(newRon);
      }
      const nonTransferables = updateResultWithSurplusVotes(
        quota,
        candidates,
        resultMap,
        surplusCandidate
      );
      votesLeft -= nonTransferables;
    }
  }

  /**
   * Initialise the vote counts
   * @param {WeightedVote[]} votes
   * @param {Candidate[]} candidates
   * @returns {ResultMap}
   */
  function calculateInitialVoteResult(votes, candidates) {
    // Create a blank mapping from candidate to result
    const resultMap = ResultMap.fromCandidates(candidates);
    // Add the initial votes 5.1.2 - 5.1.5
    const nonTransferables = resultMap.saveWeightedVotes(votes, candidates);
    // Throw an error if there are papers without initial votes (bad sorting previously)
    if (nonTransferables > 0) throw new Error('Papers without initial votes');
    return resultMap;
  }

  /**
   * @param {number} quota
   * @param {ResultMap} resultMap
   * @param {Map<Candidate, string[]>} ties
   * @returns {Candidate | false}
   */
  function determineSurplusCandidate(quota, resultMap, ties) {
    const sortedResults = resultMap.getSortedResults(ties);
    const highestSurplus = sortedResults.find((result) =>
      result.isVoteSurplus(quota)
    );
    return highestSurplus === undefined ? false : highestSurplus.candidate;
  }

  /**
   * @param {number} quota
   * @param {ResultMap} resultMap
   * @param {Map<Candidate, string[]>} ties
   * @returns {Candidate[]}
   */
  function determineExactWinnerCandidates(quota, resultMap, ties) {
    const sortedResults = resultMap.getSortedResults(ties);
    return sortedResults
      .filter((result) => /* !result.hasWon && */ result.isWinner(quota))
      .map((result) => result.candidate);
  }

  /**
   * @param {number} quota
   * @param {Candidate[]} remainingCandidates
   * @param {ResultMap} resultMap
   * @param {Candidate} surplusCandidate
   * @returns {number} number of non-transferable votes
   */
  function updateResultWithSurplusVotes(
    quota,
    remainingCandidates,
    resultMap,
    surplusCandidate
  ) {
    const candidateResult = resultMap.map.get(surplusCandidate);
    const surplusVotes = candidateResult.declareVoteSurplus(quota);
    return resultMap.saveWeightedVotes(surplusVotes, remainingCandidates);
  }

  /**
   * @param {number} quota
   * @param {ResultMap} stableResultMap
   * @returns {Candidate[]}
   */
  function determineWinners(quota, stableResultMap) {
    return stableResultMap
      .getSortedResults(new Map())
      .filter((result) => result.isWinner(quota))
      .map((result) => result.candidate);
  }

  /**
   * @param {ResultMap} stableResultMap
   * @param {Map<Candidate, string[]>} ties
   * @returns {CandidateResult}
   */
  function determineExcludedCandidateResult(stableResultMap, ties) {
    return stableResultMap.getSortedResults(ties).reverse()[0];
  }

  /**
   * @param {Candidate[]} remainingCandidates
   * @param {ResultMap} resultMap
   * @param {CandidateResult} excludedCandidateResult
   * @returns {number} number of non-transferable votes
   */
  function updateResultWithExcludedVotes(
    remainingCandidates,
    resultMap,
    excludedCandidateResult
  ) {
    return resultMap.saveWeightedVotes(
      excludedCandidateResult.cachedVotes,
      remainingCandidates
    );
  }

  /**
   * @param {ResultMap} resultMap
   * @param {Candidate[]} candidates
   * @param {LogEntry[]=} log
   * @returns {{ nonTransferables: number, remainingCandidates: Candidate[] }}
   */
  function calculateExcludedVoteResult(resultMap, candidates, log) {
    /** @type {Map<Candidate, string[]>} */
    const ties = new Map();
    const excludedCandidateResult = determineExcludedCandidateResult(resultMap, ties);
    if (log !== undefined && ties.get(excludedCandidateResult.candidate)) {
      log.push({type:'ties', ties: ties.get(excludedCandidateResult.candidate)});
    }

    resultMap.map.delete(excludedCandidateResult.candidate);
    const remainingCandidates = Candidate.filterCandidateFromList(
      candidates,
      excludedCandidateResult.candidate
    );
    const nonTransferables = updateResultWithExcludedVotes(
      remainingCandidates,
      resultMap,
      excludedCandidateResult
    );

    return { nonTransferables, remainingCandidates };
  }

  /**
   * Calculate the winner of STV, writing to a log as we go.
   *
   * @param {number} vacancies
   * @param {Vote[]} votes
   * @param {Candidate[]} candidates
   * @param {LogEntry[]=} log
   * @returns {Candidate[]}
   */
  function determineWinnersIteratively(vacancies, votes, candidates, log) {
    while (candidates.length < vacancies) candidates.push(Candidate.ron(Infinity));

    const weightedVotes = votes.map((vote) => WeightedVote(vote));

    // 5.1.1 count number of votes cast (invalid votes are filtered out previously)
    let votesLeft = weightedVotes.length;

    // 5.1.2 - 5.1.5 sort by first preferences
    const resultMap = calculateInitialVoteResult(weightedVotes, candidates);
    while (true) {
      // 5.1.6 quota
      const quota = droopQuota(vacancies, votesLeft);

      // 5.1.7 - 5.2.4
      ({ votesLeft, candidates } = calculateStableVoteResult(
        quota,
        votesLeft,
        candidates,
        resultMap,
        log
      ));
      const winningCandidates = determineWinners(quota, resultMap);
      if (winningCandidates.length == vacancies) {
        return winningCandidates;
      } else if (winningCandidates.length > vacancies) {
        throw new Error(
          'this shouldn’t be possible: there cannot be more than ' +
          '`vacancies` positions with a weight of `quota`, because ' +
          'quota = (numVotes / (1+vacancies)) + 1, so ' +
          'vacancies*((numVotes / (1+vacancies)) + 1) ' +
          '= vacancies*((numVotes / (1+vacancies)) + vacancies' +
          '> vacancies*((numVotes / vacancies) + vacancies' +
          '= numVotes + vacancies, which is greater than the number of votes'
        );
      }
      const {
        nonTransferables,
        remainingCandidates,
      } = calculateExcludedVoteResult(resultMap, candidates, log);
      votesLeft -= nonTransferables;
      candidates = remainingCandidates;

      // If we have eliminated enough candidates, take the remaining candidates
      if (winningCandidates.length + candidates.length == vacancies) {
        return winningCandidates.concat(candidates);
      }
    }
  }

  return {
    Vote,
    Candidate,
    CandidateResult,
    ResultMap,
    determineWinnersIteratively,
  };
})();

ui.js

const textarea = document.getElementById('input');
    textarea.addEventListener('paste', async () => {
      await tick();
      printErrors(handleTextArea);
    });
    textarea.addEventListener('keypress', e => {
      if (e.key === 'Enter' && !e.shiftKey) {
        e.preventDefault();
        printErrors(handleTextArea);
      }
    });
    const calculateButton = document.getElementById('submit');
    calculateButton.addEventListener('click', () => {
      printErrors(handleTextArea);
    });
    const reloadButton = document.getElementById('reload');
    reloadButton.addEventListener('click', () => {
      location.reload();
    });
    const saveButton = document.getElementById('save');
    saveButton.addEventListener('click', () => {
      let history = [];
      try {
        history = JSON.parse(localStorage.history);
      } catch (e) {}
      if (!Array.isArray(history)) history = [];
      history.push({time: +new Date, input: textarea.value, output: resultPre.textContent});
      localStorage.history = JSON.stringify(history);
      saveButton.hidden = true;
      showHistory(false);
    });

    const historyButton = document.getElementById('showHistory');
    const table = document.querySelector('table');
    const tbody = document.querySelector('tbody');
    historyButton.addEventListener('click', () => {
      showHistory(true);
    });

    const clearHistory = document.getElementById('clearHistory');
    clearHistory.addEventListener('click',() => {
      if (confirm("Are you sure you want to remove all history entries?")) {
        localStorage.clear();
        location.reload();
      }
    })

    const resultPre = document.getElementById('output');

    function printErrors(f, ...args) {
      try {
        f(...args);
      } catch (e) {
        console.error(e);
        resultPre.classList.add('error')
        resultPre.textContent = e.message;
      }
    }

    function handleTextArea() {
      textarea.scrollTop = 0;
      reloadButton.hidden = false;
      const string = textarea.value;
      resultPre.textContent = '';
      resultPre.classList.remove('error');
      const parsed = parsePaste(string);
      const { title, positions, candidates, ron, votes } = parsed;
      console.log(parsed);
      const result = executeSTV(votes.map(vote => vote.rankings), ron, positions, candidates);
      const { winners, log } = result;
      console.log(result);
      const stringResult = [
        "Winners: " + winners.map(x => x.name).join(', '),
        "Title: " + title,
        "",
        "Votes: " + votes.length,
        "Log:", printLog(log).join('\n')
      ];
      resultPre.textContent = stringResult.join('\n');
      saveButton.hidden = false;
    }

    /** @typedef {{type: 'snapshot', snapshot: CandidateResultSnapshot[]} | {type: 'ties', ties: string[]}}
     *            LogEntry */
    /** @typedef {{ value: Fraction, votes: WeightedVote[], hasWon: boolean, candidate: Candidate, toString(): String }}
     *            CandidateResultSnapshot */
    function printLog(/** @type {LogEntry[]} */ log) {
      /** @typedef {string[]} */
      const lines = [];
      for (const logLine of log) {
        if (logLine.type === 'snapshot') {
          lines.push(logLine.snapshot.join(','));
        } else {
          lines.push(logLine.ties.join(' '));
        }
      }
      return lines;
    }

    function showHistory(force = true) {
      if (force) historyButton.hidden = true;
      let history = [];
      tbody.innerHTML = '';
      try {
        history = JSON.parse(localStorage.history);
      } catch (e) {}
      if (!Array.isArray(history)) history = [];
      for (const row of history) {
        const newRow = document.createElement('tr');
        const dateCell = document.createElement('td');
        dateCell.textContent = new Intl.DateTimeFormat('en-GB', { dateStyle: 'short', timeStyle: 'long' }).format(new Date(row.time));
        newRow.appendChild(dateCell);
        const input = document.createElement('td');
        const inputTextarea = document.createElement('textarea');
        inputTextarea.readOnly = true;
        inputTextarea.rows = 4;
        inputTextarea.textContent = row.input;
        input.appendChild(inputTextarea);
        newRow.appendChild(input);
        const output = document.createElement('td');
        const outputTextarea = document.createElement('textarea');
        outputTextarea.readOnly = true;
        outputTextarea.rows = 4;
        outputTextarea.textContent = row.output;
        output.appendChild(outputTextarea);
        newRow.appendChild(output);
        tbody.appendChild(newRow);
      }
      if (force) table.hidden = false;
    }

    /**
     * @param {string} string
     */
    function parsePaste(string) {
      const lines = string.split('\n');
      if (lines.length < 6) {
        throw new Error('Too few lines, please copy the entire sheet.');
      }
      const [titleLine, _statsLine, candidatesLine, _numbersLine, _headersLine, ...voteLines] = string.split('\n');
      const title = titleLine.split('\t')[1];
      const positions = +titleLine.split('\t')[6] || 1;
      const candidatesCells = candidatesLine.split('\t');
      const ron = candidatesCells.shift() ?? null;
      const candidates = candidatesCells.filter(Boolean);
      const votes = voteLines.map(parseVoteRow).filter(Boolean);
      return {
        title,
        positions,
        candidates,
        ron,
        votes,
      }
    }

    /**
     * @return {Promise<void>}
     */
    function tick() {
      return new Promise(resolve => setTimeout(resolve));
    }

    /**
     * @param {string} vote
     */
    function parseVoteRow(vote) {
      const trimmed = vote.trimEnd();
      if (!trimmed) return null;
      const [id,...rankings] = trimmed.split('\t');
      return { id, rankings };
    }