// -*- Mode: c++; c-basic-offset: 4; -*- // hrmph, no javaspit mode in emacs ...
/* Code to implement "life" in ECMAScript.
 * $Id: weblife.js,v 1.50 2010-07-19 08:13:06 eddy Exp $
 */
/* Mental model
 *
 * The universe comprises a rectangular lattice of actual cells.  Just over the
 * edge of the universe is a border of indirect cells.  These are either
 * references to a void (permanently dead) cell or references to cells elsewhere
 * (generally on the border).
 *
 * The display comprises a window on the universe.  It is a table of indirect
 * cells, each referencing an actual cell of the universe.  If the table is
 * bigger than the universe, and the edge of the universe uses non-void cells,
 * some actual cells shall be represented by more than one table cell.  The
 * display may flip either or both axes relative to their directions in the
 * underlying universe; and it may swap vertical with horizontal relative to the
 * underlying universe.  The display may move across the universe without
 * reference to the nominal origin thereof: if it straddles a boundary, the
 * extension is inferred from the universe's cycling.  If it moves completely
 * across a boundary, the result may amount to a flip or swap of axes, possibly
 * combined with a translation.
 *
 * Indirect cells can be implicitly implemented by simply having the grid object
 * handle de-reference gracefully past edges.
 */
/* Geometry and Topology
 *
 * Label edges { 1: left, 2: top, 3: right, 4: bottom } and let 0 serve as a
 * token for void.  We can then encode our grid's boundary handling by a list of
 * pairs: each pair's first entry is an edge label, second entry is an
 * optionally negated edge label; negation indicates reversal; each edge label
 * must appear (possibly negated) in exactly one pair; pairing with 0 indicates
 * void, pairing with self mirrors (or spin-mirrors if negated).  An edge
 * appearing in no pair is deemed paired with 0.  Of course, a list of pairs can
 * be encoded as a list, read two by two.  For internal use, it is worth
 * re-coding as a self-consistent list with 4 entries, at indices 1 to 4
 * (instead of 0 to 3), mapping each edge label to its possibly negated partner.

Oasis		= [,  0,  0,  0,  0]; // <= []
Cylinder	= [,  3,  0,  1,  0]; // <= [1,3]
Moebius		= [, -3,  0, -1,  0]; // <= [1,-3]
mOasis		= [,  1,  2,  3,  4]; // <= [1,1,2,2,3,3,4,4]
mCylinder	= [,  3,  2,  1,  4]; // <= [1,3,2,2,4,4]
mMoebius	= [, -3,  2, -1,  4]; // <= [1,-3,2,2,4,4]
Torus		= [,  3,  4,  1,  2]; // <= [1,3,2,4]
Klein		= [, -3,  4, -1,  2]; // <= [1,-3,2,4]
Projective	= [, -3, -4, -1, -2]; // <= [1,-3,2,-4]
Sphere		= [,  2,  1,  4,  3]; // <= [1,2,3,4]

 */
/* TODO: mirror would be better (albeit spin can't do this) if it
 * supported using the centre-line of the boundary row or column as the
 * mirror, instead of using the edge; e.g. putting Long line along the
 * axis of symmetry.
 */
/* Event handling: onchange is triggered onblur when the value has changed.
 */
/* TODO: be more dynamic ?
 *
 * May be worth using Element.scrollIntoView() to display grid when
 * starting run.  May be nice to make each illustration a link to a
 * paste-and-go run for it.
 */
/* TODO: implement time-machine
 *
 * Each cell already rembers its last 32 time-steps; so it should be
 * possible to implement re-winding back through those.
 */
/* TODO: Object Refactoring
 *
 * Should be broken up into (roughly) one object per form in present
 * controls for page, here regarding the status display as another form.
 * Should also probably have an object to manage Paste menu: initialized
 * with a bunch of id values; each so-id'd object should be a table and
 * should have a title attribute to be used by the Paste menu as
 * user-visible text.
 *
 * Each form's associated object is then initialized by being given the
 * form object; the paste form also gets the Paste menu object.  Each
 * object binds its methods to the relevant form controls.  Display size
 * object gets Grid object at init, so it can (default to +2 in each
 * direction around the outside and) bind display cells to grid cells.
 * Display size object also gets Display offset/orientation table at
 * init (doesn't need cell size; independent).  Grid form should have
 * two objects: size and topology.
 */
/* TODO: Grid Optimisation
 *
 * Represent grid by a linked list of tiles, each of which remembers: the states
 * of the cells within it and; its position in the grid's global co-ordinates.
 * A tile may contain live cells anywhere inside it; its sphere of influence
 * includes the cells immediately outside it; and it must co-operate (or merge)
 * with any tile that includes any cell immediately outside that perimeter.
 * When time-stepping a tile, track its projections onto left and top edges so
 * as to detect any vertical or horizontal dead-trench of width two through it;
 * split on any such.
 *
 * Use a binary tree of sqrt(2):1 rectangles as index.  Each parent splits as
 * two children, to: each tile is associated with the smallest tree-node: whose
 * rectangle contains the tile and each cell immediately outside it.  To find
 * which tiles a tile may need to co-ordinate with, it suffices to check tiles
 * associated with the descendants and ancestors of its tree node.
 *
 * Tiles may come in many flavours: some may be bit-racks computing their
 * evolution as per the definition; others may be references to known cycling
 * patterns, recording which frame in that patter's cycle they currently hold
 * and in which orientation.  The abstract API of a tile addresses it purely in
 * terms of the global grid: get boundary box; get, toggle and set a cell;
 * prepare next time-step and update to it.  Both preparation and update may
 * lead to the tile changing its boundary box and hence needing to re-attach
 * itself within the index tree.  A tile with empty boundary box has died.
 */
/* TODO: Display Optimisation
 *
 * The display only needs to attend to the tiles that over-lap it; for each, it
 * needs to keep track of potentially several avatars; but, on show(), it only
 * needs to query one avatar to discover which cells have changed (hence need
 * className changed).
 */

var pstatus;

function cellClass () {
    function Cell(down, right) {
	this.down = down;
	this.right = right;
	this.neighbour = [ null, null, null, null, null, null, null, null ];
	this.avatar = [];
	this.state = this.next = false;
	this.count = this.recent = 0;
    }

    Cell.prototype = {
	'update': function (show) {
	    this.state = this.next;
	    var state = this.className(false);
	    if (show && this.avatar.length > 0 && this.avatar[0].getState() != state)
		for (var i in this.avatar)
		    this.avatar[i].show(state);

	    this.recent <<= 1;
	    if (this.state) {
		this.recent |= 1;
		this.count++;
	    }

	    return this.state;
	},
	'prepare': function (show, count) {
	    if (count < 0) {
		count = 0;
		for (var i in this.neighbour)
		    if (this.neighbour[i] && this.neighbour[i].state) count++;
	    } else if (this.state) count--;

	    this.next = count == 3 || (count == 2 && this.state);

	    if (show && this.avatar.length > 0) {
		var state = this.className(true);
		if (this.avatar[0].getState() != state)
		    for (var i in this.avatar)
			this.avatar[i].show(state);
	    }
	},

	'period': function () {
	    var best = 0, len = 0, gap = 1;
	    var span = 0, mask = 1; // mask is (1 << (span+1))-1
	    while (span + len < 32)
		if (gap & mask) {
		    /* Compute a bit-mask indicating how this.recent
		     * fails to be periodic with period len.
		     *
		     * This bit-mask is obtained by x-or-ing this.recent
		     * with a 32-bit int that would equal it if it were
		     * periodic.  (Less significant bits are termed
		     * recent.)  The built value's most recent 32-len
		     * bits are obtained simply by shifting bits right
		     * by len; the len bits that lost are split and
		     * shunted so as to ensure each block is shifted a
		     * multiple of len bits, to fill the least recent
		     * len bits.
		     *
		     * Every clear bit at gap's recent end indicates a
		     * time tick in an earlier cycle that is indeed
		     * repeated a cycle later.
		     */
		    var off = 32 % ++len, bits = this.recent;
		    gap = bits ^
			((bits >> len) |
			 (bits << (32 - off)) |
			 ((bits >> off) << (32 - len)));

		} else if (gap) {
		    best = len;
		    span += 1;
		    mask <<= 1;
		    mask |= 1;

		} else {
		    this.span = 32;
		    return len;
		}

	    this.span = best ? span + best : 0;
	    return best;
	},

	'toggle': function (future) {
	    if (future)
		this.next = !this.next;
	    else
		this.state = !this.state;

	    var state = this.className(future);
	    for (var i in this.avatar)
		this.avatar[i].show(state);

	    if (this.state)
		this.recent |= 1;
	    else
		this.recent &= ~1;
	},
	'setState': function (state, preview) {
	    var change = (preview
			  ? (((state & 2) != 0) != this.next)
			  : (((state & 1) != 0) != this.state));
	    // bit-wise binary operators bind *less* tightly than comparison !
	    this.state = (state & 1) != 0;
	    this.next = (state & 2) != 0;
	    var klaz = this.className(preview);
	    if (this.avatar.length > 0 && this.avatar[0].getState() != klaz)
		for (var i in this.avatar)
		    this.avatar[i].show(klaz);

	    if (this.state)
		this.recent |= 1;
	    else
		this.recent &= ~1;

	    return change;
	},
	'clear': function () {
	    this.setState(0, false);
	    this.count = 0;
	},

	'dropAvatar': function (which) {
	    var i = this.avatar.length;
	    while (i-- > 0 && this.avatar[i] != which)
		/* skip */ ;
	    if (i < 0)
		alert("Dropping non-avatar ! " + which + " at [" + this.down + "," + this.right + "]");
	    else {
		var end = this.avatar.length - 1;
		while (i++ < end)
		    this.avatar[i-1] = this.avatar[i];
		/* That ends by leaving two copies of the last element at the end,
		 * unless i == end initially. */
		delete this.avatar[end];
		this.avatar.length = end;
	    }
	},
	'addAvatar': function (whom, preview) {
	    var i = 0;
	    while (i < this.avatar.length)
		if (this.avatar[i] == whom) {
		    alert("Duplicating avatar[" + i + "] ! " + whom + " at [" + this.down + "," + this.right + "]");
		    break;
		} else
		    i++;

	    this.avatar[i] = whom;
	    whom.show(this.className(preview));
	}
    };

    // Anchor to neighbours:
    var offsets = [[-1,-1], [1,1], [-1,1], [1,-1], [-1,0], [1,0], [0,-1], [0,1]];
    Cell.prototype.gridBind = function (grid) {
	for (var i in offsets) {
	    var off = offsets[i];
	    var down = off[0] + this.down;
	    var right = off[1] + this.right;
	    var cell = this.neighbour[i];
	    if (!cell || cell.down != down || cell.right != right)
		this.neighbour[i] = grid.findCell(down, right);
	}
    }

    // [state, next] -> class mappings:
    var transitions = [ "dead", "dies", "born", "live" ];
    Cell.prototype.className = function (preview) {
	return transitions[preview
			   ? ((this.state ? 1 : 0) | (this.next ? 2 : 0))
			   : this.state ? 3 : 0];
    }

    var busyness = [ "zero", "one", "two", "three", "four", "five",
		     "six", "seven", "eight", "nine", "ten" ];
    Cell.prototype.hasLived = function () {
	var bit = 1;
	for (var i = this.count; i > 0 && bit < busyness.length; i >>= 1)
	    bit++;
	var name = busyness[bit - 1];
	for (var i in this.avatar)
	    this.avatar[i].show(name);
    }

    return Cell;
}

function gridClass() {
    var Cell = cellClass();
    var cycle = [[, 1, 2, 3, 4],
		 [, 4, 1, 2, 3], // left -> bottom, top -> left, ...
		 [, 3, 4, 1, 2],
		 [, 2, 3, 4, 1]];

    function Grid() {
	this.height = this.nextHeight;
	this.width = this.nextWidth;

	this.kick = 0; // time of last user intervention
	this.frobs = 0; // how many user interventions
	this.delay = -1;
	this.edges = [, 0, 0, 0, 0];
	this.countdown = this.cycle = null;
	this.waiting = this.pending = false;

	// opera.postError("Setting up " + this.height + " by " + this.width + " lattice of cells"); // kinda slow
	var slab = this.lattice = [];
	for (var i = 0; i < this.height; i++) {
	    var row = slab[i] = [];
	    for (var j = 0; j < this.width; j++)
		row[j] = new Cell(i, j);
	}
	// opera.postError("Lattice complete.");

	for (var i = this.height; i-- > 1;)
	    for (var j = this.width; j-- > 1;) {
		slab[i][j].neighbour[0] = slab[i-1][j-1];
		slab[i-1][j-1].neighbour[1] = slab[i][j];
		slab[i][j-1].neighbour[2] = slab[i-1][j];
		slab[i-1][j].neighbour[3] = slab[i][j-1];
		slab[i][j].neighbour[4] = slab[i-1][j];
		slab[i-1][j].neighbour[5] = slab[i][j];
		slab[i][j].neighbour[6] = slab[i][j-1];
		slab[i][j-1].neighbour[7] = slab[i][j];
	    }
	this.bindBoundary();
	// opera.postError("Lattice boundary bound");
    }
    Grid.prototype = {
	'display': null,
	'nodull': false,
	'nextWidth': 1,
	'nextHeight': 1,
	'togglePos': [,], // two inputs recording last position toggled

	'stepTime': function () {
	    this.waiting = false;

	    if (this.display.preview) {
		if (this.pending) this.update(false);
		this.prepare(true);
	    } else {
		if (!this.pending) this.prepare(false);
		this.update(true);
	    }

	    this.tickDone();
	},
	'singleStep': function () {
	    if ((this.mayStep() && null == this.cycle) || this.waiting) return;
	    this.stepTime();
	},
	'mayStep': function () {
	    return (this.delay >= 0 &&
		    (this.countdown == null || this.countdown > 0));
	},
	'tickDone': function () {
	    if (this.cycle != null) {
		pstatus.data = ('Last ' + this.cycle[1] + ' steps indicate ' +
				this.cycle[0] + '-cycle.');
	    } else if (this.mayStep() && !this.waiting) {
		setTimeout(stepTime, this.delay);
		this.waiting = true;
	    }
	},
	'setDelay': function (num) {
	    var stopped = this.delay < 0;
	    this.delay = num;
	    if (stopped) this.tickDone();
	},

	'bindBoundary': function () {
	    var slab = this.lattice;
	    var width = this.width - 1;
	    for (var i = this.height; i-- > 0;) {
		slab[i][0].gridBind(this);
		slab[i][width].gridBind(this);
	    }
	    var height = this.height - 1;
	    for (var j = width; j-- > 1;) {
		slab[0][j].gridBind(this);
		slab[height][j].gridBind(this);
	    }
	},
	'setTopology': function (topology) {
	    edges = [, 0, 0, 0, 0];
	    if (topology.length % 2)
		alert("Odd length topology description: " + topology);
	    var i;
	    for (i = 0; i < topology.length; i += 2) {
		var a = topology[i];
		var b = topology[i+1];
		if (edges[a] || edges[b])
		    alert("Inconsistent topology: " + topology);
		if (a < 0) {
		    a = -a;
		    b = -b;
		}
		if (b < 0) {
		    edges[-b] = -a;
		    edges[a] = b;
		} else {
		    edges[b] = a;
		    edges[a] = b;
		}
	    }
	    if (i != topology.length)
		alert("Loop parity error: " + i + " != " + topology.length);
	    for (var i = 4; i > 0; i--) {
		var k = edges[i];
		if (k) {
		    k = edges[k < 0 ? -k : k];
		    if (i != (k < 0 ? -k : k))
			alert("Mis-bound edge: " + i +
			      " -> " + edges[i] + " -> " + k);
		}
		if (this.width != this.height)
		    if (edges[i] && (edges[i] - i) % 2)
			alert("Bound edges of different lengths: " + i +
			      " -> " + edges[i]);
	    }

	    this.edges = edges;
	    this.pending = false; // invalidate any pending Cells' .next values
	    this.bindBoundary();

	    if (this.display)
		this.display.gridBind(this);
	},
	'setOutside': function (out) {
	    switch (out) {
	    case -1:
	    for (var i = 4; i > 0; i--)
		if (this.edges[i] == i || this.edges[i] == 0)
		    this.edges[i] = -i;
	    break;
	    case 0:
	    for (var i = 4; i > 0; i--)
		if (this.edges[i] == i || this.edges[i] == -i)
		    this.edges[i] = 0;
	    break;
	    case 1:
	    for (var i = 4; i > 0; i--)
		if (this.edges[i] == 0 || this.edges[i] == -i)
		    this.edges[i] = i;
	    break;
	    }
	    this.pending = false;
	    this.bindBoundary();

	    if (this.display)
		this.display.gridBind(this);
	},

	'crossEdge': function (e, left) {
	    // e is the edge you're crossing;
	    // left is nominal left edge of tile you're moving from, -ve if flipped;
	    // returns nominal left edge of tile moved to, -ve if flipped.
	    var flip = left < 0;
	    if (flip) left = -left;

	    var f = this.edges[e]; // e's partner
	    if (!f) return 0;
	    else if (f == -e) left = cycle[2][left];
	    else if (f == cycle[2][e]) ; // nothing to do
	    else if (-f == cycle[2][e]) {
		if (cycle[1][left] == e || cycle[3][left] == e)
		    left = cycle[2][left];
		flip = !flip;
	    } else if (f == e) {
		if (left == e || left == cycle[2][e])
		    left = cycle[2][left];
		flip = !flip;
	    } else {
		// Adjacent edges:
		var chiral = ((e & 2) == (f & 2)); // true if both in [2,3] or both in [1,4]
		// chiral is true iff e and f go the same way round the square
		if ((chiral && f > 0) || (!chiral && f < 0)) {
		    flip = !flip;
		    if (chiral) left = 1 + ((left - 1) ^ 1);
		    else left = 5 - left;
		} else {
		    // no flip
		    if (f < 0) f = -f;
		    if (e == cycle[1][f]) left = cycle[1][left];
		    else {
			if (e != cycle[3][f]) alert("Unhandled edge crossing: " + e + " -> " + f);
			left = cycle[3][left];
		    }
		}
		/* e->f: { left -> new left, ... }, flip if appropriate:

		 * 1<->4:  [, 2, 1, 4, 3], flip
		 * 2<->3:  [, 2, 1, 4, 3], flip

		 * 1<->-2: [, 4, 3, 2, 1], flip
		 * 3<->-4: [, 4, 3, 2, 1], flip

		 * 1->-4: [, 2, 3, 4, 1]
		 * 2->1:  [, 2, 3, 4, 1]
		 * 3->-2: [, 2, 3, 4, 1]
		 * 4->3:  [, 2, 3, 4, 1]

		 * 4->-1: [, 4, 1, 2, 3]
		 * 1->2:  [, 4, 1, 2, 3]
		 * 2->-3: [, 4, 1, 2, 3]
		 * 3->4:  [, 4, 1, 2, 3]
		 */
	    }
	    return flip ? -left : left;
	},
	'getPos': function (i, j) {
	    var down = i;
	    var across = j;
	    if (this.height < 2) i = 0;
	    else i = i < 0 ? i % this.height + this.height : i % this.height;
	    if (this.width < 2) j = 0;
	    else j = j < 0 ? j % this.width  + this.width  : j % this.width;
	    // Which tile is that within ?
	    var n = (down   - i) / this.height;
	    var m = (across - j) / this.width;

	    // Compute orientation of tile:
	    var left = 1;
	    var flip = false;
	    while (true) {
		var edge; // chose an edge to cross, if necessary
		if (m < 0) {
		    edge = left;
		    m++;
		} else if (m > 0) {
		    m--;
		    edge = cycle[2][left]; // right
		} else if (n < 0) {
		    n++;
		    edge = cycle[flip ? 1 : 3][left]; // top;
		} else if (n > 0) {
		    n--;
		    edge = cycle[flip ? 3 : 1][left]; // bottom
		} else
		    break; // not necessary :-)

		left = this.crossEdge(edge, flip ? -left : left);
		if (!left) {
		    if (down >= 0 && down < this.height && across >= 0 && across < this.width)
			alert("Fell off edge of unbounded topology:  " + this.edges);
		    return null; // void edge
		}
		flip = left < 0;
		if (flip) left = -left;
	    }

	    // Now set down and across to duly adjusted i and j:
	    switch (left) {
	    case 1:
	    down = flip ? this.height - 1 - i : i;
	    across = j;
	    break;
	    case 3:
	    down = flip ? i : (this.height - 1 - i);
	    across = this.width - 1 - j;
	    break;
	    case 2:
	    down = flip ? this.width - 1 - j : j;
	    across = i;
	    break;
	    case 4:
	    down = flip ? j : (this.width - 1 - j);
	    across = this.height - 1 - i;
	    break;
	    default: alert("Bad edge: " + left);
	    }

	    return [down, across];
	},
	'findCell': function (i, j) {
	    var ij = this.getPos(i, j);
	    if (ij == null) return null;
	    return this.lattice[ij[0]][ij[1]];
	},

	'prepare': function (show) {
	    pstatus.data = "Computing next time-step's values.";
	    var i = this.height - 1;
	    var j;
	    var below = this.lattice[i--];
	    var level = this.lattice[i];
	    while (i-- > 0) {
		j = this.width - 1;
		var above = this.lattice[i];
		var last = (below[j].state ? 1 : 0) + (level[j].state ? 1 : 0) + (above[j].state ? 1 : 0);
		var here = (below[j-1].state ? 1 : 0) + (level[j-1].state ? 1 : 0) + (above[j-1].state ? 1 : 0);
		while (j-- > 1) {
		    var next = (below[j-1].state ? 1 : 0) + (level[j-1].state ? 1 : 0) + (above[j-1].state ? 1 : 0);
		    level[j].prepare(show, last + here + next);
		    last = here;
		    here = next;
		}
		below = level;
		level = above;
	    }

	    j = this.width - 1;
	    for (i = this.height; i-- > 0;) {
		this.lattice[i][0].prepare(show, -1);
		this.lattice[i][j].prepare(show, -1);
	    }

	    i = this.height - 1;
	    while (j-- > 1) {
		this.lattice[0][j].prepare(show, -1);
		this.lattice[i][j].prepare(show, -1);
	    }

	    this.pending = true;
	    pstatus.data += "  Done.";
	},
	'update': function (show) {
	    pstatus.data = "Updating grid state to new time-step.";
	    var tick = Number(this.timer.data);
	    if (tick == 0)
		// First time: adjust wording of timeOut's accompanying text
		this.atStart.className = "";

	    this.timer.data = String(1 + tick);
	    if (this.countdown != null)
		this.torun.value = String(--this.countdown);


	    /* Revise live data to use pending data.
	     *
	     * In the process, determine how many cells are active and,
	     * if stop-on-boring is enabled, detect boredom.  For the
	     * latter, period is the lowest common multiple and slow is
	     * the maximum of of all cells' .period()s; span is the
	     * length of recent history that matches all cell's
	     * periodicities. */
	    var count = 0; // Number of active cells
	    var period = 1, slow = 0, span = tick - this.kick;
	    for (var i = this.height; i-- > 0;)
		for (var j = this.width; j-- > 0;) {
		    var cell = this.lattice[i][j];
		    cell.update(show);
		    if (cell.state) count++;
		    if (this.nodull && period && span >= slow) {
			var p = cell.period(); // sets cell.span
			if (p > slow) slow = p;
			if (cell.span < span) span = cell.span;
			var g = period > p ? period : p;
			var d = period > p ? p : period;
			while (d > 0) {
			    var r = g % d;
			    g = d;
			    d = r;
			} // g is greatest common divisor of p and period.
			period = period * p / g; // lowest common multiple
		    }
		}
	    this.active.data = count + " / " + (this.height * this.width);

	    this.cycle = (this.nodull && period && span >= slow
			  ? [ period, span ]
			  : null);

	    this.pending = false;
	    pstatus.data += "  Done.";
	},
	'hasLived': function () {
	    pstatus.data = "Showing how often each cell has lived.";
	    for (var i = this.height; i-- > 0;)
		for (var j = this.width; j-- > 0;)
		    this.lattice[i][j].hasLived();
	    pstatus.data += "  Done.";
	},

	'showStat': function (node, see) {
	    node.parentNode.className = see ? "" : "irrelevant";
	},
	'tamper': function (toggle) {
	    this.showStat(this.toggleSense, toggle);
	    this.kick = Number(this.timer.data);
	    this.cycle = null;
	},
	'frobbed': function (count, see) {
	    this.tamper(see);
	    this.frobs += count;
	    this.toggleCount.data = String(this.frobs);
	    this.showStat(this.toggleCount, this.frobs > 0);
	},
	'clear': function () {
	    pstatus.data = "Clearing grid.";
	    for (var i = this.height; i-- > 0;)
		for (var j = this.width; j-- > 0;)
		    this.lattice[i][j].clear();

	    this.timer.data = "0";
	    this.frobbed(-this.frobs, false);
	    this.atStart.className = "irrelevant";
	    this.pending = false;
	    this.active.data = "0 / " + (this.height * this.width);
	    pstatus.data += "  Done.";
	},
	'random': function () {
	    // 0 <= Math.random() < 1.
	    var n = 0, count = 0;
	    for (var i = this.height; i-- > 0;)
		for (var j = this.width; j-- > 0;) {
		    if (Math.random() < .17) {
			this.lattice[i][j].toggle(this.pending);
			n++;
		    }
		    if (this.lattice[i][j].state)
			count++;
		}
	    /* Assorted runs in standard grid (total area 4895)
	     * [threshold vs Math.random()]: @[time], [count]
	     * .5: @1189, 166
	     * .2: @1253, 143
	     * .17:@2693, c. mid 100s (but Opera crashed while I was transcribing !)
	     * .17:@ 721:  96; @1308: 170, @1328: 118, @1423: 127, @354: 153, @1240: 154
	     * .16:@1203, 133
	     * .14:@ 695, 158
	     * .1: @ 972, 128
	     * .1: @ 720, 139
	     */

	    this.active.data = count + " / " + (this.height * this.width);
	    var stopped = !this.mayStep();
	    this.frobbed(n, false)
	    if (stopped && this.mayStep())
		this.tickDone();
	},
	'toggle': function (ij) {
	    var ij = this.getPos(ij[0], ij[1]);
	    if (ij == null)
		alert("Can't toggle a barren cell.");
	    else {
		this.togglePos[0].data = String(ij[0]);
		this.togglePos[1].data = String(ij[1]);
		var cell = this.lattice[ij[0]][ij[1]];
		cell.toggle(this.pending);
		// No need to reset pending.
		// TODO: record time of toggling as well.
		this.toggleSense.data = cell.state ? "on" : "off";
	    }
	    this.frobbed(1, true);
	},

	/** Fill a (usually new) Grid from a (usually old) one.
	 *
	 * Sets .state of each cell of this from that of the cell at the
	 * matching co-ordinates (suitably wrapped, if appropriate) in a
	 * given other Grid.
	 */
	'setFrom': function (other) {
	    var offi = other.display.i;
	    var offj = other.display.j;
	    // Fill a new grid from an old one:
	    for (var i = this.height; i-- > 0;)
		for (var j = this.width; j-- > 0;) {
		    var oi = i + offi, oj = j + offj;
		    var cell = other.findCell(oi, oj);
		    oi = oi % this.height;
		    while (oi < 0) oi += this.height;
		    oj = oj % this.width;
		    while (oj < 0) oj += this.width;
		    this.lattice[oi][oj].state = cell == null ? false : cell.state;
		}

	    this.delay = other.delay;
	    this.edges = other.edges;
	    this.pending = false;
	    this.tamper(false);
	    this.bindBoundary();
	}
    };
    return Grid;
}

/** Box object packages a TD element which displays a Cell.
 *
 * A Box object keeps a table cell's CSS class (and, hence, how the
 * relevant TD element is displayed) in sync with the state of an
 * internal Cell object of a Grid.
 *
 * Many Box objects may represent one Cell, if a dimension of the
 * Display exceeds the matching dimension of the Grid.  A Cell need not
 * be displayed in any Box, if a dimension of the Grid exceeds the
 * matching dimension of the Display.
 */
function boxClass() {
    function Box(display, td, d, a, bind) {
	this.down = d;
	this.across = a;
	this.ent = td;
	td.onclick = function () { display.toggle(d, a); }
	this.cell = null;
	if (bind)
	    this.cellBind(liveGrid.findCell(d, a));
    }
    Box.prototype = {

	'forget': function () {
	    delete this.ent.onclick;
	    this.ent.parentNode.removeChild(this.ent);
	    delete this.ent;
	    if (this.cell) {
		this.cell.dropAvatar(this);
		this.cell = null;
	    }
	},
	'cellBind': function (cell, preview) {
	    if (this.cell)
		this.cell.dropAvatar(this);
	    this.cell = cell;
	    if (cell)
		cell.addAvatar(this, preview);
	    else
		this.show("void");
	},

	'show': function (state) { this.ent.className = state; },
	'getState': function () { return this.ent.className; }
    }
    return Box;
}

function displayClass() {
    var Box = boxClass();

    function Display(table) {
	this.table = table; // actually the tbody ...
	this.preview = false;
	this.orient = 1; // left edge of top-left td as described by grid
	this.orientor = null; // form control with id="Orient"

	// Origin: top left td's position in liveGrid:
	this.i = this.j = 0;
	// Insertion point:
	this.yIns = this.xIns = 0;
	// Work out our size:
	this.tall = table.childNodes.length;
	this.broad = this.tall > 0 ? table.firstChild.childNodes.length : 0;
	this.nextTall = this.tall;
	this.nextBroad = this.broad;

	// Set up grid of Box()es
	this.boxes = [];
	var d = 0;
	for (var row = this.table.firstChild; d < this.tall; row = row.nextSibling) {
	    var a = 0;
	    this.boxes[d] = [];
	    for (var cell = row.firstChild; a < this.broad; cell = cell.nextSibling) {
		if (cell != table.childNodes[d].childNodes[a])
		    alert("Mangled table[" + d + "][" + a + "]: " + cell + " != " + table.childNodes[d].childNodes[a]);
		this.boxes[d][a] = new Box(this, cell, d, a, false);
		a++;
	    }
	    d++;
	}
    }

    Display.prototype = {
	'offset': [,], // form controls with ids right, down
	'togglePos': [,], // form controls with ids ddTog, adTog

	'reviseSize': function (bind) {
	    // Insist on leaving at least one cell in our table:
	    if (this.nextTall  < 1) this.nextTall  = 1;
	    if (this.nextBroad < 1) this.nextBroad = 1;
	    // set tall = nextTall, broad = nextBroad
	    /* Involves frobbing the table: which is horribly slow if we're
	     * displaying it, so taking it out of sight for the duration
	     * might speed matters. */

	    if (this.tall > this.nextTall) {
		var row = this.table.childNodes[this.nextTall - 1];
		while (this.tall > this.nextTall) {
		    row.parentNode.removeChild(row.nextSibling);
		    var i = --this.tall;
		    for (var j in this.boxes[i])
			this.boxes[i][j].forget();
		    delete this.boxes[i];
		}
		this.boxes.length = this.tall;
	    }

	    if (this.broad > this.nextBroad) {
		for (var d = this.tall; d-- > 0;) {
		    var row = this.boxes[d];
		    for (var a = this.broad; a-- > this.nextBroad;) {
			row[a].forget();
			delete row[a];
		    }
		    row.length = this.nextBroad;
		}

		/* Reflow bug, 2005/Nov/1: bodge-around.
		 * Tarquin says it'll persuade the table to notice when it narrows !
		 document.body.className += '';
		*/
	    } else if (this.nextBroad > this.broad)
		for (var d = this.tall; d-- > 0;) {
		    var row = this.table.childNodes[d];
		    for (var a = this.broad; a < this.nextBroad; a++) {
			var ent = row.firstChild.cloneNode(true);
			row.appendChild(ent);
			this.boxes[d][a] = new Box(this, ent, d, a, bind);
		    }
		}

	    this.broad = this.nextBroad;

	    for (; this.tall < this.nextTall; this.tall++) {
		var row = this.table.firstChild.cloneNode(true);
		this.table.appendChild(row);

		var ent = row.firstChild;
		this.boxes[this.tall] = []
		    for (var a = 0; a < this.broad; a++) {
			this.boxes[this.tall][a] = new Box(this, ent, this.tall, a, bind);
			ent = ent.nextSibling;
		    }
		if (ent)
		    alert("More cells in row[" + this.tall + "] = " + row + " than expected: " + ent);
	    }

	    this.gridBind(liveGrid);
	},
	'gridBind': function (grid) {
	    var preview = this.preview && grid.pending;
	    for (var i = this.tall; i-- > 0;)
		for (var j = this.broad; j-- > 0;) {
		    var ij = this.transform(i, j);
		    this.boxes[i][j].cellBind(grid.findCell(ij[0], ij[1]), preview);
		}
	    /* It should be possible to evade all but one .findCell() call: do it
	     * for corner, then use cell.neighbour[5] for down and cell.neighbour[7]
	     * for right to find all the rest.  But would fail for topologies with
	     * void edges. */
	},

	'transform': function (down, across) {
	    // Transforms down, across to grid co-ordinates without trying to normalise tile
	    if (this.orient == 1)
		return [ this.i + down, this.j + across ];
	    if (this.orient == -1)
		return [ this.i - down, this.j + across ];
	    if (this.orient == 2)
		return [ this.i - across, this.j + down ];
	    if (this.orient == -2)
		return [ this.i + across, this.j + down ];
	    if (this.orient == 3)
		return [ this.i - down, this.j - across ];
	    if (this.orient == -3)
		return [ this.i + down, this.j - across ];
	    if (this.orient == 4)
		return [ this.i + across, this.j - down ];
	    if (this.orient == -4)
		return [ this.i - across, this.j - down ];

	    alert(this + " lost track of orientation.");
	    return [];
	},
	'toGrid': function (down, across) {
	    // Returns the grid co-ordinates of the grid cell to which down, across map
	    var ij = this.transform(down, across);
	    return liveGrid.getPos(ij[0], ij[1]);
	},

	'Paste': function () {
	    var orient = Number(document.getElementById("orientPaste").value);
	    switch (this.Paster.value) {
		// Special cases:
	    case "empty": liveGrid.clear(); return;
	    case "random": liveGrid.random(); return;
	    case "linear": this.Linear(orient); return;
	    }
	    pstatus.data = "Locating pattern: " + this.Paster.value;
	    var table = document.getElementById(this.Paster.value);
	    if (table) {
		// parseTable actually wants the table section element rather than the table itself ...
		var tBody = table.firstChild;
		while (tBody && tBody.nodeType == tBody.TEXT_NODE)
		    tBody = tBody.nextSibling;

		if (tBody)
		    return this.parseTable(tBody, orient, this.yIns, this.xIns);
		else
		    alert("Failed to find non-text node in " + table + "(" + table.id + ")");
	    } else
		alert("Unable to locate template: " + this.Paster.value);
	    pstatus.data += " ... failed.";
	},
	'Linear': function (orient) {
	    var horiz = liveGrid.width > liveGrid.height;
	    if (orient % 2 == 0) horiz = !horiz;
	    var len = horiz ? liveGrid.width : liveGrid.height;
	    var ij = this.transform(this.yIns, this.xIns);
	    var cell = liveGrid.findCell(ij[0], ij[1]);
	    var count = 0;
	    while (cell && len-- > 0) {
		cell.toggle();
		count++;
		cell = cell.neighbour[horiz ? 7 : 5];
	    }
	    liveGrid.frobbed(count, false);
	},
	'parseTable': function (table, orient, down, across) {
	    /* The table must be oriented according to orient, positioned so that the
	     * corner this puts in the top left is at [down, across] then transcribed
	     * according to our table's orientation.
	     */
	    pstatus.data = "Parsing pattern-table.";

	    var cells = [];
	    var wide = 0, tall = 0;
	    for (var tr = table.firstChild; tr; tr = tr.nextSibling)
		if (tr.nodeType != tr.TEXT_NODE) {
		    var j = 0;
		    cells[tall] = [];
		    for (var td = tr.firstChild; td; td = td.nextSibling)
			if (td.nodeType != td.TEXT_NODE) {
			    var type;
			    switch (td.className) {
			    case "live": type = 3; break;
			    case "born": type = 2; break;
			    case "dies": type = 1; break;
			    case "dead": type = 0; break;
				/* Ignore anything else, e.g. void, so we have the
				 * option of masking off areas we don't want our
				 * template to set. */
			    default: type = -1; break;
			    }
			    cells[tall][j++] = type;
			}

		    if (j > wide) wide = j;
		    tall++;
		}

	    // Apply orient:
	    pstatus.data += "  Orienting " + wide + " by " + tall + " data.";
	    switch (orient) {
	    case 1: break; // Identity
	    case -1: // Horizon: horizontal mirror
		var rack = [];
		for (var i = tall; i-- > 0;)
		    rack[rack.length] = cells[i];
		cells = rack;
		break;
	    case 3: // Half: half-turn
		var rack = [];
		for (var i = tall; i-- > 0;) {
		    var row = rack[rack.length] = [];
		    for (var j = wide; j-- > 0;)
			row[row.length] = cells[i][j];
		}
		cells = rack;
		break;
	    case -3: // Vertical: vertical mirror
		for (var i = tall; i-- > 0;) {
		    var row = [];
		    for (var j = wide; j-- > 0;)
			row[row.length] = cells[i][j];
		    cells[i] = row;
		}
		break;
	    case 2: // Clock: clockwise quarter turn
		var rack = [];
		for (var j = 0; j < wide; j++) {
		    var row = rack[rack.length] = [];
		    for (var i = tall; i-- > 0;)
			row[row.length] = cells[i][j];
		}
		cells = rack;
		break;
	    case -2: // TL-BR: reflect in across = down diagonal mirror
		var rack = [];
		for (var j = 0; j < wide; j++) {
		    var row = rack[rack.length] = [];
		    for (var i = 0; i < tall; i++)
			row[row.length] = cells[i][j];
		}
		cells = rack;
		break;
	    case 4: // Anti: anti-clockwise quarter turn
		var rack = [];
		for (var j = wide; j-- > 0;) {
		    var row = rack[rack.length] = [];
		    for (var i = 0; i < tall; i++)
			row[row.length] = cells[i][j];
		}
		cells = rack;
		break;
	    case -4: // BL-TR: reflect in constant across + down mirror:
		var rack = [];
		for (var j = wide; j-- > 0;) {
		    var row = rack[rack.length] = [];
		    for (var i = tall; i-- > 0;)
			row[row.length] = cells[i][j];
		}
		cells = rack;
		break;
	    }
	    switch (orient) {
	    case 2: case 4: case -2: case -4:
	    var tmp = wide;
	    wide = tall;
	    tall = tmp;
	    break;
	    }
	    if (wide != cells[0].length)
		alert("Transformed tile width is wrong (" + cells[0].length + " != " + wide + ")");
	    if (tall != cells.length)
		alert("Transformed tile height is wrong (" + cells.length + " != " + tall + ")");

	    // Finally, transcribe our data ...
	    pstatus.data += "  Transcribing.";
	    var fallout = false, count = 0;
	    for (var i = tall; i-- > 0;)
		for (var j = wide; j-- > 0;)
		    if (cells[i][j] >= 0) {
			var ij = this.transform(down + i, across + j);
			var cell = liveGrid.findCell(ij[0], ij[1]);
			if (cell == null) fallout = cells[i][j] >= 0;
			else if (cell.setState(cells[i][j], liveGrid.pending))
			    count++;
		    }
	    if (fallout)
		alert("Warning: pattern pasted was not entirely inside grid; parts may have been missed.");

	    liveGrid.frobbed(count, false);
	    pstatus.data += "  Done.";
	},

	'toggle': function (down, across) {
	    this.togglePos[0].data = String(down);
	    this.togglePos[1].data = String(across);
	    liveGrid.toggle(this.transform(down, across));
	},

	'normalise': function (keep) {
	    pstatus.data = "(Presentation form's submit action is vacuous, for now.)";
	    // TODO: Adjust i, j, orient to put i, j inside canonical rectangle
	    // Involves frobbing the form controls to show revised values
	    // Keep is (-1 or) the form control we're least eager to frob.
	    // this.orientor, this.offset
	    // shouldn't need to call gridBind afterwards ... but may be worth checking !
	},
	'setOrigin': function () {
	    pstatus.data = "Adjusting display origin.";
	    this.i = this.j = 0;
	    var ij = this.transform(Number(this.offset[0].value),
				    Number(this.offset[1].value));
	    this.i = ij[0];
	    this.j = ij[1];
	    this.gridBind(liveGrid);
	    pstatus.data += "  Done.";
	}
    };
    return Display;
}

var Grid = gridClass();
var liveGrid = new Grid(); // fake grid that we can throw away cheaply
liveGrid.findCell = function (i, j) { return this.lattice[0][0]; } // cheap short-cut

function stepTime() { liveGrid.stepTime(); }

function SetGrid() {
    if (liveGrid.nextWidth != liveGrid.width ||
	liveGrid.nextHeight != liveGrid.height)
    {
	pstatus.data = "Constructing new grid.";
	var newGrid = new Grid();
	newGrid.setFrom(liveGrid);
	liveGrid = newGrid;
	if (liveGrid.display)
	    liveGrid.display.gridBind(liveGrid);

	pstatus.data += "  Done.";
    }
    liveGrid.tickDone();
}
function SetDisplay() {
    if (liveGrid.display.nextTall != liveGrid.display.tall ||
	liveGrid.display.nextBroad != liveGrid.display.broad)
    {
	pstatus.data = "Revising display size (this takes a while).";
	liveGrid.display.reviseSize(true);
	liveGrid.tickDone();
	pstatus.data += "  Done.";
    }
}

// Utilities:
function stripString(text) {
    if (text == null)
	return "";

    if (text.trim != null)
	return text.trim();

    return text.replace(/^\s+|\s+$/g,''); // thanks Tarquin ;-)
}
function readNumber(desc, text) {
    var num = Number(text);
    text = stripString(text);
    if (String(num) != text)
	alert(desc + " must be a number (" + String(num) + " != '" + text + "')");
    else
	return num;

    return null;
}
function readPosInt(desc, text) {
    var num = readNumber(desc, text);
    if (num != null) {
	if (num > 0)
	    return num;
	else
	    alert(desc + " must be positive (" + num + " < 1)");
    }
    return -1;
}

function InitGrid(display) {
    // Initialize the grid:
    var proto = Grid.prototype;
    proto.display = display;
    proto.timer = document.getElementById("Time").nextSibling;
    proto.active = document.getElementById("Active").nextSibling;
    proto.toggleCount = document.getElementById("nTog").nextSibling;
    proto.toggleSense  = document.getElementById("ooTog").nextSibling;
    proto.togglePos[1] = document.getElementById("agTog").nextSibling;
    proto.togglePos[0] = document.getElementById("dgTog").nextSibling;
    proto.atStart = document.getElementById("atStart");

    var c = document.getElementById("timeOut");
    proto.torun = c;
    c.onchange = function () {
	var stopped = liveGrid.countdown <= 0;
	if (this.value) {
	    var num = readNumber("Count-down to stop time", this.value);
	    if (num == null) {
		this.focus();
		this.select();
	    } else
		liveGrid.countdown = num < 0 ? 0 : num;
	} else
	    liveGrid.countdown = null;

	if (stopped && liveGrid.mayStep())
	    liveGrid.tickDone();
    }
    c.size = 6;

    c = document.getElementById("width");
    c.size = 5;
    c.onchange = function () {
	var num = readPosInt("Grid width", this.value);
	if (num > 0)
	    proto.nextWidth = num;
	else {
	    this.focus();
	    this.select();
	}
    }
    c.onchange();

    c = document.getElementById("height");
    c.size = 5;
    c.onchange = function () {
	var num = readPosInt("Grid height", this.value);
	if (num > 0)
	    proto.nextHeight = num;
	else {
	    this.focus();
	    this.select();
	}
    }
    c.onchange();

    c = document.getElementById("noCycle");
    c.onchange = function () {
	if (this.checked) {
	    proto.nodull = true;
	    pstatus.data = "Enabled stop-on-dull.";
	} else {
	    var stopped = liveGrid.cycle != null;
	    proto.nodull = false;
	    liveGrid.cycle = null;
	    if (stopped && liveGrid.mayStep())
		liveGrid.tickDone();
	    pstatus.data = "Disabled stop-on-dull.";
	}
    }
    c.onchange();

    pstatus.data = "Setting up initial grid.";
    display.i = -((liveGrid.nextHeight - liveGrid.height) >> 1);
    display.j = -((liveGrid.nextWidth  - liveGrid.width)  >> 1);
    // we'll blot those out in a moment ...
    SetGrid(); // before topology

    pstatus.data = "Configuring initial grid topology.";
    c = document.getElementById("Topology");
    c.onchange = function () {
	var out = document.getElementById("Outside");
	var open = false;
	switch (this.value) {
	case "Torus": liveGrid.setTopology([1,3,2,4]); break;
	case "Klein": liveGrid.setTopology([1,-3,2,4]); break;
	case "Projective": liveGrid.setTopology([1,-3,2,-4]); break;
	case "Sphere": liveGrid.setTopology([1,2,3,4]); break;
	default:
	    var outside = Number(out.value);
	    open = true;
	    switch (this.value) {
	    case "Oasis":    liveGrid.setTopology(!outside ? []     : outside < 0 ? [1,-1,2,-2,3,-3,4,-4] : [1,1,2,2,3,3,4,4]); break;
	    case "Cylinder": liveGrid.setTopology(!outside ? [1,3]  : outside < 0 ? [1,3,2,-2,4,-4]	  : [1,3,2,2,4,4]); break;
	    case "Moebius":  liveGrid.setTopology(!outside ? [1,-3] : outside < 0 ? [1,-3,2,-2,4,-4]	  : [1,-3,2,2,4,4]); break;
	    default:
		alert("Unrecognised topology: " + this.value);
		this.focus();
	    }
	}
	if (open) out.parentNode.className = "";
	else out.parentNode.className = "irrelevant";
    }
    c.onchange();

    c = document.getElementById("Outside");
    c.onchange = function () { liveGrid.setOutside(Number(this.value)); }
    // don't need to onchange(), since Topology took account of it

    c = document.getElementById("Speed");
    c.onchange = function () {
	var num = Number(this.value);
	if (String(num) != this.value) {
	    alert("Speed must be specified as a numeric time-step (" +
		  this.value + " != " + String(num) + ")");
	    this.focus();
	} else
	    liveGrid.setDelay(num);
    }
    c.onchange();

    pstatus.data = "Adjusting display size.";
    display.reviseSize(false);
    display.setOrigin();
}

function makeDisplay(table) {
    var Display = displayClass();
    view = new Display(table.firstChild);
    pstatus.data = "Binding form elements to internal data structures";
    view.Paster = document.getElementById("Paste");

    view.orientor = document.getElementById("Orient");
    view.orientor.onchange = function () { view.orient = Number(this.value); }
    view.orientor.onchange();

    view.togglePos[0] = document.getElementById("ddTog").nextSibling;
    view.togglePos[1] = document.getElementById("adTog").nextSibling;

    view.offset[0] = document.getElementById("down");
    view.offset[1] = document.getElementById("right");
    view.offset[0].size = view.offset[1].size = 3;

    view.offset[1].onchange = function () {
	var num = readNumber("Display offset to right", this.value);
	if (num == null) {
	    this.focus();
	    this.select();
	} else
	    view.setOrigin();
    }

    view.offset[0].onchange = function () {
	var num = readNumber("Display offset downwards", this.value);
	if (num == null) {
	    this.focus();
	    this.select();
	} else
	    view.setOrigin();
    }

    var c = document.getElementById("xIns");
    c.size = 3;
    c.onchange = function () {
	var num = readNumber("Insertion position horizontal co-ordinate",
			     this.value);
	if (num == null) {
	    this.focus();
	    this.select();
	} else
	    view.xIns = num;
    }
    c.onchange();

    c = document.getElementById("yIns");
    c.size = 3;
    c.onchange = function () {
	var num = readNumber("Insertion position vertical co-ordinate",
			     this.value);
	if (num == null) {
	    this.focus();
	    this.select();
	} else
	    view.yIns = num;
    }
    c.onchange();

    c = document.getElementById("Preview");
    c.onchange = function () {
	if (this.checked) view.preview = true;
	else view.preview = false;
    }
    c.onchange();

    c = document.getElementById("wide");
    c.size = 3;
    c.onchange = function () {
	var num = readPosInt("Display width", this.value);
	if (num > 0)
	    view.nextBroad = num;
	else {
	    this.focus();
	    this.select();
	}
    }
    c.onchange();

    c = document.getElementById("tall");
    c.size = 3;
    c.onchange = function () {
	var num = readPosInt("Display height", this.value);
	if (num > 0)
	    view.nextTall = num;
	else {
	    this.focus();
	    this.select();
	}
    }
    c.onchange();

    c = document.getElementById("scale");
    c.onchange = function () { table.className = "size" + this.value; }
    c.onchange();

    return view;
}

function Initialize() {
    // Handles onload for weblife.html
    pstatus = document.getElementById("status").nextSibling;
    pstatus.data = "Initialize()ing";

    var table = document.getElementById("portal").firstChild;
    /* That's the table itself; its .firstChild is a table section whose
     * children are the actual rows. */

    // Turn off unscript on elements that are useless without this script:
    table.className = "";
    document.getElementById("funcSpec").className = "";
    document.getElementById("config").className = "";
    document.getElementById("Reflector").className = "";
    document.getElementById("gunsmith").className = "";

    // Create display and set up grid:
    InitGrid(makeDisplay(table));
    pstatus.data = "Ready";
}