Skip to content

Instantly share code, notes, and snippets.

@CoolOppo

CoolOppo/chemical-equation-balancer.js

Created January 12, 2015 18:25
Show Gist options
  • Save CoolOppo/c52d0cef39fcc051c7c7 to your computer and use it in GitHub Desktop.
Save CoolOppo/c52d0cef39fcc051c7c7 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. CoolOppo created this gist Jan 12, 2015.
    881 changes: 881 additions & 0 deletions chemical-equation-balancer.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,881 @@
    /*
    * Chemical equation balancer
    *
    * Copyright (c) 2014 Project Nayuki
    * All rights reserved. Contact Nayuki for licensing.
    * http://www.nayuki.io/page/chemical-equation-balancer-javascript
    */

    "use strict";


    /* Main functions, which are the entry points from the HTML code */

    // Balances the given formula string and sets the HTML output on the page. Returns nothing.
    function balance(formulaStr) {
    // Clear output
    setMessage("");
    var balancedElem = document.getElementById("balanced");
    var codeOutElem = document.getElementById("codeOutput");
    removeAllChildren(balancedElem);
    removeAllChildren(codeOutElem);
    appendText(" ", codeOutElem);

    // Parse equation
    var eqn;
    try {
    eqn = parse(formulaStr);
    } catch (e) {
    if (typeof e == "string") { // Simple error message string
    setMessage("Syntax error: " + e);

    } else if ("start" in e) { // Error message object with start and possibly end character indices
    setMessage("Syntax error: " + e.message);

    var start = e.start;
    var end = "end" in e ? e.end : e.start;
    while (end > start && (formulaStr.charAt(end - 1) == " " || formulaStr.charAt(end - 1) == "\t"))
    end--; // Adjust position to eliminate whitespace
    if (start == end)
    end++;

    appendText(formulaStr.substring(0, start), codeOutElem);
    var highlight = document.createElement("u");
    if (end <= formulaStr.length) {
    appendText(formulaStr.substring(start, end), highlight);
    codeOutElem.appendChild(highlight);
    appendText(formulaStr.substring(end, formulaStr.length), codeOutElem);
    } else {
    appendText(" ", highlight);
    codeOutElem.appendChild(highlight);
    }

    } else {
    setMessage("Assertion error");
    }
    return;
    }

    try {
    var matrix = buildMatrix(eqn); // Set up matrix
    solve(matrix); // Solve linear system
    var coefs = extractCoefficients(matrix); // Get coefficients
    checkAnswer(eqn, coefs); // Self-test, should not fail
    balancedElem.appendChild(eqn.toHtml(coefs)); // Display balanced equation
    } catch (e) {
    setMessage(e.toString());
    }
    }


    // Sets the input box to the given formula string and balances it. Returns nothing.
    function demo(formulaStr) {
    document.getElementById("inputFormula").value = formulaStr;
    balance(formulaStr);
    }


    var RANDOM_DEMOS = [
    "H2 + O2 = H2O",
    "Fe + O2 = Fe2O3",
    "NH3 + O2 = N2 + H2O",
    "C2H2 + O2 = CO2 + H2O",
    "C3H8O + O2 = CO2 + H2O",
    "Na + O2 = Na2O",
    "P4 + O2 = P2O5",
    "Na2O + H2O = NaOH",
    "Mg + HCl = MgCl2 + H2",
    "AgNO3 + LiOH = AgOH + LiNO3",
    "Pb + PbO2 + H^+ + SO4^2- = PbSO4 + H2O",
    "HNO3 + Cu = Cu(NO3)2 + H2O + NO",
    "KNO2 + KNO3 + Cr2O3 = K2CrO4 + NO",
    "AgNO3 + BaCl2 = Ba(NO3)2 + AgCl",
    "Cu(NO3)2 = CuO + NO2 + O2",
    "Al + CuSO4 = Al2(SO4)3 + Cu",
    "Na3PO4 + Zn(NO3)2 = NaNO3 + Zn3(PO4)2",
    "Cl2 + Ca(OH)2 = Ca(ClO)2 + CaCl2 + H2O",
    "CHCl3 + O2 = CO2 + H2O + Cl2",
    "H2C2O4 + MnO4^- = H2O + CO2 + MnO + OH^-",
    "H2O2 + Cr2O7^2- = Cr^3+ + O2 + OH^-",
    "KBr + KMnO4 + H2SO4 = Br2 + MnSO4 + K2SO4 + H2O",
    "K2Cr2O7 + KI + H2SO4 = Cr2(SO4)3 + I2 + H2O + K2SO4",
    "KClO3 + KBr + HCl = KCl + Br2 + H2O",
    "Ag + HNO3 = AgNO3 + NO + H2O",
    "P4 + OH^- + H2O = H2PO2^- + P2H4",
    "Zn + NO3^- + H^+ = Zn^2+ + NH4^+ + H2O",
    "ICl + H2O = Cl^- + IO3^- + I2 + H^+",
    "AB2 + AC3 + AD5 + AE7 + AF11 + AG13 + AH17 + AI19 + AJ23 = A + ABCDEFGHIJ",
    ];

    var lastRandomIndex = -1;

    function random() {
    var index;
    do {
    index = Math.floor(Math.random() * RANDOM_DEMOS.length);
    index = Math.max(Math.min(index, RANDOM_DEMOS.length - 1), 0);
    } while (RANDOM_DEMOS.length >= 2 && index == lastRandomIndex);
    lastRandomIndex = index;
    demo(RANDOM_DEMOS[index]);
    }


    /* Core number-processing fuctions */

    // Returns a matrix based on the given equation object.
    function buildMatrix(eqn) {
    var elems = eqn.getElements();
    var rows = elems.length + 1;
    var cols = eqn.getLeftSide().length + eqn.getRightSide().length + 1;
    var matrix = new Matrix(rows, cols);
    for (var i = 0; i < elems.length; i++) {
    var j = 0;
    for (var k = 0, lhs = eqn.getLeftSide() ; k < lhs.length; j++, k++)
    matrix.set(i, j, lhs[k].countElement(elems[i]));
    for (var k = 0, rhs = eqn.getRightSide(); k < rhs.length; j++, k++)
    matrix.set(i, j, -rhs[k].countElement(elems[i]));
    }
    return matrix;
    }


    function solve(matrix) {
    matrix.gaussJordanEliminate();

    // Find row with more than one non-zero coefficient
    var i;
    for (i = 0; i < matrix.rowCount() - 1; i++) {
    if (countNonzeroCoeffs(matrix, i) > 1)
    break;
    }
    if (i == matrix.rowCount() - 1)
    throw "All-zero solution"; // Unique solution with all coefficients zero

    // Add an inhomogeneous equation
    matrix.set(matrix.rowCount() - 1, i, 1);
    matrix.set(matrix.rowCount() - 1, matrix.columnCount() - 1, 1);

    matrix.gaussJordanEliminate();
    }


    function countNonzeroCoeffs(matrix, row) {
    var count = 0;
    for (var i = 0; i < matrix.columnCount(); i++) {
    if (matrix.get(row, i) != 0)
    count++;
    }
    return count;
    }


    function extractCoefficients(matrix) {
    var rows = matrix.rowCount();
    var cols = matrix.columnCount();

    if (cols - 1 > rows || matrix.get(cols - 2, cols - 2) == 0)
    throw "Multiple independent solutions";

    var lcm = 1;
    for (var i = 0; i < cols - 1; i++)
    lcm = checkedMultiply(lcm / gcd(lcm, matrix.get(i, i)), matrix.get(i, i));

    var coefs = [];
    var allzero = true;
    for (var i = 0; i < cols - 1; i++) {
    var coef = checkedMultiply(lcm / matrix.get(i, i), matrix.get(i, cols - 1));
    coefs.push(coef);
    allzero &= coef == 0;
    }
    if (allzero)
    throw "Assertion error: All-zero solution";
    return coefs;
    }


    // Throws an exception if there's a problem, otherwise returns silently.
    function checkAnswer(eqn, coefs) {
    if (coefs.length != eqn.getLeftSide().length + eqn.getRightSide().length)
    throw "Assertion error: Mismatched length";

    var allzero = true;
    for (var i = 0; i < coefs.length; i++) {
    var coef = coefs[i];
    if (typeof coef != "number" || isNaN(coef) || Math.floor(coef) != coef)
    throw "Assertion error: Not an integer";
    allzero &= coef == 0;
    }
    if (allzero)
    throw "Assertion error: All-zero solution";

    var elems = eqn.getElements();
    for (var i = 0; i < elems.length; i++) {
    var sum = 0;
    var j = 0;
    for (var k = 0, lhs = eqn.getLeftSide() ; k < lhs.length; j++, k++)
    sum = checkedAdd(sum, checkedMultiply(lhs[k].countElement(elems[i]), coefs[j]));
    for (var k = 0, rhs = eqn.getRightSide(); k < rhs.length; j++, k++)
    sum = checkedAdd(sum, checkedMultiply(rhs[k].countElement(elems[i]), -coefs[j]));
    if (sum != 0)
    throw "Assertion error: Incorrect balance";
    }
    }


    /* Chemical equation data types */

    // A complete chemical equation. It has a left-hand side list of terms and a right-hand side list of terms.
    // For example: H2 + O2 -> H2O.
    function Equation(lhs, rhs) {
    // Make defensive copies
    lhs = cloneArray(lhs);
    rhs = cloneArray(rhs);

    this.getLeftSide = function() { return cloneArray(lhs); }
    this.getRightSide = function() { return cloneArray(rhs); }

    // Returns an array of the names all of the elements used in this equation.
    // The array represents a set, so the items are in an arbitrary order and no item is repeated.
    this.getElements = function() {
    var result = new Set();
    for (var i = 0; i < lhs.length; i++)
    lhs[i].getElements(result);
    for (var i = 0; i < rhs.length; i++)
    rhs[i].getElements(result);
    return result.toArray();
    }

    // Returns an HTML element representing this equation.
    // 'coefs' is an optional argument, which is an array of coefficients to match with the terms.
    this.toHtml = function(coefs) {
    if (coefs !== undefined && coefs.length != lhs.length + rhs.length)
    throw "Mismatched number of coefficients";

    // Creates this kind of DOM node: <span class="className">text</span>
    function createSpan(text, className) {
    var span = document.createElement("span");
    appendText(text, span);
    span.className = className;
    return span;
    }

    var node = document.createElement("span");

    var j = 0;
    function termsToHtml(terms) {
    var head = true;
    for (var i = 0; i < terms.length; i++, j++) {
    var coef = coefs !== undefined ? coefs[j] : 1;
    if (coef != 0) {
    if (head) head = false;
    else node.appendChild(createSpan(" + ", "plus"));
    if (coef != 1)
    node.appendChild(createSpan(coef.toString().replace(/-/, MINUS), "coefficient"));
    node.appendChild(terms[i].toHtml());
    }
    }
    }

    termsToHtml(lhs);
    node.appendChild(createSpan(" " + RIGHT_ARROW + " ", "rightarrow"));
    termsToHtml(rhs);

    return node;
    }
    }


    // A term in a chemical equation. It has a list of groups or elements, and a charge.
    // For example: H3O^+, or e^-.
    function Term(items, charge) {
    if (items.length == 0 && charge != -1)
    throw "Invalid term"; // Electron case

    items = cloneArray(items);

    this.getItems = function() { return cloneArray(items); }

    this.getElements = function(resultSet) {
    resultSet.add("e");
    for (var i = 0; i < items.length; i++)
    items[i].getElements(resultSet);
    }

    // Counts the number of times the given element (specified as a string) occurs in this term, taking groups and counts into account, returning an integer.
    this.countElement = function(name) {
    if (name == "e") {
    return -charge;
    } else {
    var sum = 0;
    for (var i = 0; i < items.length; i++)
    sum = checkedAdd(sum, items[i].countElement(name));
    return sum;
    }
    }

    // Returns an HTML element representing this term.
    this.toHtml = function() {
    var node = document.createElement("span");
    if (items.length == 0 && charge == -1) {
    appendText("e", node);
    var sup = document.createElement("sup");
    appendText(MINUS, sup);
    node.appendChild(sup);
    } else {
    for (var i = 0; i < items.length; i++)
    node.appendChild(items[i].toHtml());
    if (charge != 0) {
    var sup = document.createElement("sup");
    var s;
    if (Math.abs(charge) == 1) s = "";
    else s = Math.abs(charge).toString();
    if (charge > 0) s += "+";
    else s += MINUS;
    appendText(s, sup);
    node.appendChild(sup);
    }
    }
    return node;
    }
    }


    // A group in a term. It has a list of groups or elements.
    // For example: (OH)3
    function Group(items, count) {
    if (count < 1)
    throw "Assertion error: Count must be a positive integer";
    items = cloneArray(items);

    this.getItems = function() { return cloneArray(items); }

    this.getCount = function() { return count; }

    this.getElements = function(resultSet) {
    for (var i = 0; i < items.length; i++)
    items[i].getElements(resultSet);
    }

    this.countElement = function(name) {
    var sum = 0;
    for (var i = 0; i < items.length; i++)
    sum = checkedAdd(sum, checkedMultiply(items[i].countElement(name), count));
    return sum;
    }

    // Returns an HTML element representing this group.
    this.toHtml = function() {
    var node = document.createElement("span");
    appendText("(", node);
    for (var i = 0; i < items.length; i++)
    node.appendChild(items[i].toHtml());
    appendText(")", node);
    if (count != 1) {
    var sub = document.createElement("sub");
    appendText(count.toString(), sub);
    node.appendChild(sub);
    }
    return node;
    }
    }


    // A chemical element.
    // For example: Na, F2, Ace, Uuq6
    function Element(name, count) {
    if (count < 1)
    throw "Assertion error: Count must be a positive integer";

    this.getName = function() { return name; }

    this.getCount = function() { return count; }

    this.getElements = function(resultSet) { resultSet.add(name); }

    this.countElement = function(n) { return n == name ? count : 0; }

    // Returns an HTML element representing this element.
    this.toHtml = function() {
    var node = document.createElement("span");
    appendText(name, node);
    if (count != 1) {
    var sub = document.createElement("sub");
    appendText(count.toString(), sub);
    node.appendChild(sub);
    }
    return node;
    }
    }


    /* Parser functions */

    // Parses the given formula string and returns an equation object, or throws an exception.
    function parse(formulaStr) {
    var tokenizer = new Tokenizer(formulaStr);
    return parseEquation(tokenizer);
    }


    // Parses and returns an equation.
    function parseEquation(tok) {
    var lhs = [];
    var rhs = [];

    lhs.push(parseTerm(tok));
    while (true) {
    var next = tok.peek();
    if (next == "=") {
    tok.consume("=");
    break;
    } else if (next == null) {
    throw {message: "Plus or equal sign expected", start: tok.position()};
    } else if (next == "+") {
    tok.consume("+");
    lhs.push(parseTerm(tok));
    } else
    throw {message: "Plus expected", start: tok.position()};
    }

    rhs.push(parseTerm(tok));
    while (true) {
    var next = tok.peek();
    if (next == null)
    break;
    else if (next == "+") {
    tok.consume("+");
    rhs.push(parseTerm(tok));
    } else
    throw {message: "Plus or end expected", start: tok.position()};
    }

    return new Equation(lhs, rhs);
    }


    // Parses and returns a term.
    function parseTerm(tok) {
    var startPosition = tok.position();

    // Parse groups and elements
    var items = [];
    while (true) {
    var next = tok.peek();
    if (next == null)
    break;
    else if (next == "(")
    items.push(parseGroup(tok));
    else if (/^[A-Za-z][a-z]*$/.test(next))
    items.push(parseElement(tok));
    else
    break;
    }

    // Parse optional charge
    var charge = 0;
    var next = tok.peek();
    if (next != null && next == "^") {
    tok.consume("^");
    next = tok.peek();
    if (next == null)
    throw {message: "Number or sign expected", start: tok.position()};
    else
    charge = parseOptionalNumber(tok);

    next = tok.peek();
    if (next == "+")
    charge = +charge; // No-op
    else if (next == "-")
    charge = -charge;
    else
    throw {message: "Sign expected", start: tok.position()};
    tok.take(); // Consume the sign
    }

    // Check if term is valid
    var elems = new Set();
    for (var i = 0; i < items.length; i++)
    items[i].getElements(elems);
    elems = elems.toArray(); // List of all elements used in this term, with no repeats
    if (items.length == 0) {
    throw {message: "Invalid term - empty", start: startPosition, end: tok.position()};
    } else if (indexOf(elems, "e") != -1) { // If it's the special electron element
    if (items.length > 1)
    throw {message: "Invalid term - electron needs to stand alone", start: startPosition, end: tok.position()};
    else if (charge != 0 && charge != -1)
    throw {message: "Invalid term - invalid charge for electron", start: startPosition, end: tok.position()};
    // Tweak data
    items = [];
    charge = -1;
    } else { // Otherwise, a term must not contain an element that starts with lowercase
    for (var i = 0; i < elems.length; i++) {
    if (/^[a-z]+$/.test(elems[i]))
    throw {message: 'Invalid element name "' + elems[i] + '"', start: startPosition, end: tok.position()};
    }
    }

    return new Term(items, charge);
    }


    // Parses and returns a group.
    function parseGroup(tok) {
    var startPosition = tok.position();
    tok.consume("(");
    var items = [];
    while (true) {
    var next = tok.peek();
    if (next == null)
    throw {message: "Element, group, or closing parenthesis expected", start: tok.position()};
    else if (next == "(")
    items.push(parseGroup(tok));
    else if (/^[A-Za-z][a-z]*$/.test(next))
    items.push(parseElement(tok));
    else if (next == ")") {
    tok.consume(")");
    if (items.length == 0)
    throw {message: "Empty group", start: startPosition, end: tok.position()};
    break;
    } else
    throw {message: "Element, group, or closing parenthesis expected", start: tok.position()};
    }

    return new Group(items, parseOptionalNumber(tok));
    }


    // Parses and returns an element.
    function parseElement(tok) {
    var name = tok.take();
    if (!/^[A-Za-z][a-z]*$/.test(name))
    throw "Assertion error";
    return new Element(name, parseOptionalNumber(tok));
    }


    // Parses a number if it's the next token, returning a non-negative integer, with a default of 1.
    function parseOptionalNumber(tok) {
    var next = tok.peek();
    if (next != null && /^[0-9]+$/.test(next))
    return checkedParseInt(tok.take());
    else
    return 1;
    }


    /* Tokenizer object */

    // Tokenizes a formula into a stream of token strings.
    function Tokenizer(str) {
    var i = 0;

    // Returns the index of the next character to tokenize.
    this.position = function() {
    return i;
    }

    // Returns the next token as a string, or null if the end of the token stream is reached.
    this.peek = function() {
    if (i == str.length) // End of stream
    return null;

    var match = /^([A-Za-z][a-z]*|[0-9]+|[+\-^=()])/.exec(str.substring(i));
    if (match == null)
    throw {message: "Invalid symbol", start: i};
    return match[0];
    }

    // Returns the next token as a string and advances this tokenizer past the token.
    this.take = function() {
    var result = this.peek();
    if (result == null)
    throw "Advancing beyond last token"
    i += result.length;
    skipSpaces();
    return result;
    }

    // Takes the next token and checks that it matches the given string, or throws an exception.
    this.consume = function(s) {
    if (this.take() != s)
    throw "Token mismatch";
    }

    function skipSpaces() {
    var match = /^[ \t]*/.exec(str.substring(i));
    i += match[0].length;
    }

    str = str.replace(/\u2212/g, "-");
    skipSpaces();
    }


    /* Matrix object */

    // A matrix of integers.
    function Matrix(rows, cols) {
    if (rows < 0 || cols < 0)
    throw "Illegal argument";

    // Initialize with zeros
    var row = [];
    for (var j = 0; j < cols; j++)
    row.push(0);
    var cells = []; // Main data (the matrix)
    for (var i = 0; i < rows; i++)
    cells.push(cloneArray(row));
    row = null;

    /* Accessor functions */

    this.rowCount = function() { return rows; }
    this.columnCount = function() { return cols; }

    // Returns the value of the given cell in the matrix, where r is the row and c is the column.
    this.get = function(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols)
    throw "Index out of bounds";
    return cells[r][c];
    }

    // Sets the given cell in the matrix to the given value, where r is the row and c is the column.
    this.set = function(r, c, val) {
    if (r < 0 || r >= rows || c < 0 || c >= cols)
    throw "Index out of bounds";
    cells[r][c] = val;
    }

    /* Private helper functions for gaussJordanEliminate() */

    // Swaps the two rows of the given indices in this matrix. The degenerate case of i == j is allowed.
    function swapRows(i, j) {
    if (i < 0 || i >= rows || j < 0 || j >= rows)
    throw "Index out of bounds";
    var temp = cells[i];
    cells[i] = cells[j];
    cells[j] = temp;
    }

    // Returns a new row that is the sum of the two given rows. The rows are not indices. This object's data is unused.
    // For example, addRow([3, 1, 4], [1, 5, 6]) = [4, 6, 10].
    function addRows(x, y) {
    var z = cloneArray(x);
    for (var i = 0; i < z.length; i++)
    z[i] = checkedAdd(x[i], y[i]);
    return z;
    }

    // Returns a new row that is the product of the given row with the given scalar. The row is is not an index. This object's data is unused.
    // For example, multiplyRow([0, 1, 3], 4) = [0, 4, 12].
    function multiplyRow(x, c) {
    var y = cloneArray(x);
    for (var i = 0; i < y.length; i++)
    y[i] = checkedMultiply(x[i], c);
    return y;
    }

    // Returns the GCD of all the numbers in the given row. The row is is not an index. This object's data is unused.
    // For example, gcdRow([3, 6, 9, 12]) = 3.
    function gcdRow(x) {
    var result = 0;
    for (var i = 0; i < x.length; i++)
    result = gcd(x[i], result);
    return result;
    }

    // Returns a new row where the leading non-zero number (if any) is positive, and the GCD of the row is 0 or 1. This object's data is unused.
    // For example, simplifyRow([0, -2, 2, 4]) = [0, 1, -1, -2].
    function simplifyRow(x) {
    var sign = 0;
    for (var i = 0; i < x.length; i++) {
    if (x[i] > 0) {
    sign = 1;
    break;
    } else if (x[i] < 0) {
    sign = -1;
    break;
    }
    }
    var y = cloneArray(x);
    if (sign == 0)
    return y;
    var g = gcdRow(x) * sign;
    for (var i = 0; i < y.length; i++)
    y[i] /= g;
    return y;
    }

    // Changes this matrix to reduced row echelon form (RREF), except that each leading coefficient is not necessarily 1. Each row is simplified.
    this.gaussJordanEliminate = function() {
    // Simplify all rows
    for (var i = 0; i < rows; i++)
    cells[i] = simplifyRow(cells[i]);

    // Compute row echelon form (REF)
    var numPivots = 0;
    for (var i = 0; i < cols; i++) {
    // Find pivot
    var pivotRow = numPivots;
    while (pivotRow < rows && cells[pivotRow][i] == 0)
    pivotRow++;
    if (pivotRow == rows)
    continue;
    var pivot = cells[pivotRow][i];
    swapRows(numPivots, pivotRow);
    numPivots++;

    // Eliminate below
    for (var j = numPivots; j < rows; j++) {
    var g = gcd(pivot, cells[j][i]);
    cells[j] = simplifyRow(addRows(multiplyRow(cells[j], pivot / g), multiplyRow(cells[i], -cells[j][i] / g)));
    }
    }

    // Compute reduced row echelon form (RREF), but the leading coefficient need not be 1
    for (var i = rows - 1; i >= 0; i--) {
    // Find pivot
    var pivotCol = 0;
    while (pivotCol < cols && cells[i][pivotCol] == 0)
    pivotCol++;
    if (pivotCol == cols)
    continue;
    var pivot = cells[i][pivotCol];

    // Eliminate above
    for (var j = i - 1; j >= 0; j--) {
    var g = gcd(pivot, cells[j][pivotCol]);
    cells[j] = simplifyRow(addRows(multiplyRow(cells[j], pivot / g), multiplyRow(cells[i], -cells[j][pivotCol] / g)));
    }
    }
    }

    // Returns a string representation of this matrix, for debugging purposes.
    this.toString = function() {
    var result = "[";
    for (var i = 0; i < rows; i++) {
    if (i != 0) result += "],\n";
    result += "[";
    for (var j = 0; j < cols; j++) {
    if (j != 0) result += ", ";
    result += cells[i][j];
    }
    result += "]";
    }
    return result + "]";
    }
    }


    /* Set object */

    function Set() {
    // Storage for the set
    var items = [];

    // Adds the given object to the set. Returns nothing.
    this.add = function(obj) {
    if (indexOf(items, obj) == -1)
    items.push(obj);
    }

    // Tests if the given object is in the set, returning a Boolean.
    this.contains = function(obj) {
    return items.indexOf(obj) != -1;
    }

    // Returns an array containing the elements of this set in an arbitrary order, with no duplicates.
    this.toArray = function() {
    return cloneArray(items);
    }
    }


    /* Math functions (especially checked integer operations) */

    var INT_MAX = 9007199254740992; // 2^53

    // Returns the given string parsed into a number, or throws an exception if the result is too large.
    function checkedParseInt(str) {
    var result = parseInt(str, 10);
    if (isNaN(result))
    throw "Not a number";
    if (result <= -INT_MAX || result >= INT_MAX)
    throw "Arithmetic overflow";
    return result;
    }

    // Returns the sum of the given integers, or throws an exception if the result is too large.
    function checkedAdd(x, y) {
    var z = x + y;
    if (z <= -INT_MAX || z >= INT_MAX)
    throw "Arithmetic overflow";
    return z;
    }

    // Returns the product of the given integers, or throws an exception if the result is too large.
    function checkedMultiply(x, y) {
    var z = x * y;
    if (z <= -INT_MAX || z >= INT_MAX)
    throw "Arithmetic overflow";
    return z;
    }


    // Returns the greatest common divisor of the given integers.
    function gcd(x, y) {
    if (typeof x != "number" || typeof y != "number" || isNaN(x) || isNaN(y))
    throw "Invalid argument";
    x = Math.abs(x);
    y = Math.abs(y);
    while (y != 0) {
    var z = x % y;
    x = y;
    y = z;
    }
    return x;
    }


    /* Miscellaneous */

    // Unicode character constants (because this script file's character encoding is unspecified)
    var MINUS = "\u2212"; // Minus sign
    var RIGHT_ARROW = "\u2192"; // Right arrow


    // A JavaScript 1.6 function for Array, which every browser has except for Internet Explorer.
    function indexOf(array, item) {
    for (var i = 0; i < array.length; i++) {
    if (array[i] == item)
    return i;
    }
    return -1;
    }


    // Returns a shallow copy of the given array. Usually used for making defensive copies.
    function cloneArray(array) {
    return array.slice(0);
    }


    // Sets the page's message element to the given string. Returns nothing.
    function setMessage(str) {
    var messageElem = document.getElementById("message");
    removeAllChildren(messageElem);
    appendText(str, messageElem);
    }


    // Removes all the children of the given DOM node. Returns nothing.
    function removeAllChildren(node) {
    while (node.childNodes.length > 0)
    node.removeChild(node.firstChild);
    }


    // Creates a new text node with the given text and appends it to the given DOM node. Returns nothing.
    function appendText(text, node) {
    node.appendChild(document.createTextNode(text));
    }