avltext.js

avltext.js

(function () {

	var _bitDepthOf = (function () {
		var _last = 1 + (Number.MAX_SAFE_INTEGER - 1) / 2;
		var _inverter = [Number.MAX_SAFE_INTEGER];

		do _inverter.push((_last - 1)); while ((_last /= 2) >= 1);

		_inverter = _inverter.reverse();

		return function bDepthOf (value) {
			var num = +value || 0;
			var limit = _inverter.length;
			var index = 0;
			while (index < limit && _inverter[index] < num) index++;
			return num < 0 ? -1 : index < limit ? index : -2;
		};
	})();
	/*
	var _bigShiftBy = (function () {
		var _last = 1 + (Number.MAX_SAFE_INTEGER - 1) / 2;
		var _shifts = [_last];

		while (_last > 1) _shifts.push(_last /= 2);

		_shifts = _shifts.reverse();

		return function (bits) {
			var at = 0|bits;
			return at < 0 ? -1 : at < _shifts.length ? _shifts[at] : -2;
		};
	})();

	function _alignBitDepth (alignment, depth) {
		return (1 + ((depth - 1) >> alignment)) << alignment;
	}



	function packCoord (row, column) {
		var rDepth = 0|_bitDepthOf(row);
		var cDepth = 0|_bitDepthOf(column);
		var rAlign = 0|_alignBitDepth(2, rDepth);
		var cAlign = 0|_alignBitDepth(2, cDepth);
		var rBias = 0;
		if (rDepth < 0 || cDepth < 0) return rDepth < cDepth ? rDepth : cDepth;
		else if (rAlign + cAlign < 29) { // 16383 : 16383
			return (7 & (rAlign >> 2)) | (row << 4) | (column << (4 + rAlign));
		} else {
			rAlign = 0|_alignBitDepth(3, rDepth);
			cAlign = 0|_alignBitDepth(3, cDepth);
			if (rAlign + cAlign < 49) { // 16777215 : 16777215
				return (8 | (rAlign >> 3)) + (row * 16) + (column * 16 * _bigShiftBy(rAlign));
			} else return -2;
		}
	}

	function unpackRow (coord) {
		var value = +coord || 0;
		var longform = 8 & value;
		var rBias = 7 & value;
		if (longform) return Math.floor(((value - 8 - rBias) / 16) % (_bigShiftBy(rBias << 3)));
		else return (value >> 4) & ((1 << (rBias << 2)) - 1);
	}

	function unpackColumn (coord) {
		var value = +coord || 0;
		var longform = 8 & value;
		var rBias = 7 & value;
		if (longform) return Math.floor(((value - 8 - rBias) / 16) / (_bigShiftBy(rBias << 3)));
		else return value >> ( 4 + (rBias << 2));
	}
	*/



	function AVLSequenceNode (left, right, added, mutator) {
		this.$total = 0;
		this.$added = 0|added;

		this.$height = 0;

		// WARNING: node may be off balance depending on left/right ...
		this.$left = left || null;
		this.$right = right || null;

		mutator ? this._recalculate(this) : this._recalculate(this).$asPersistent();
	}

	AVLSequenceNode.prototype.indexOfRowColumn = function (row, column) {
		return -1;
	};

	AVLSequenceNode.prototype.sizeOfRow = function (row) {
		var line = 0|row;
		var before = this.indexOfRowColumn(line, 0);
		var after = this.indexOfRowColumn(line + 1, 0);
		return (before < 0 || after < 0) ? -1 : (after - before);
	};



	AVLSequenceNode.prototype.$offset = function () {
		return this.$left ? 0|this.$left.$total : 0;
	};

	AVLSequenceNode.prototype.$onset = function () {
		return this.$right ? 0|this.$right.$total : 0;
	};

	AVLSequenceNode.prototype.seekBelow = function (index) {
		var at = 0|index;
		return (at < 1 || at > this.$total) ? null : this._seekBelow(at, this);
	};

	AVLSequenceNode.prototype._seekBelow = function (index, node) {
		var at = 0|index;
		var size = 0;
		var diff = (0|node.$offset()) - at;
		if (diff < 0) {
			size = 0|node.$added;
			size = size > 0 ? size : 0;
			if (-diff > size) {
				return  node.$right ? this._seekBelow(-diff - size, node.$right) || null : null;
			} else return node;
		} else return node.$left ? this._seekBelow(at, node.$left) || null : null;
	};

	AVLSequenceNode.prototype.seekAbove = function (index) {
		var at = 0|index;
		return (at > -1 && at < this.$total) ? this._seekAbove(at, this) : null;
	};

	AVLSequenceNode.prototype._seekAbove = function (index, node) {
		var at = 0|index;
		var size = 0;
		var diff = (0|node.$offset()) - at;
		if (diff > 0) return this._seekAbove(at, node.$left) || null;
		else {
			size = 0|node.$added;
			size = size > 0 ? size : 0;
			if (-diff < size) return node;
			else return node.$right ? this._seekAbove(-diff - size, node.$right) || null : null;
		}
	};



	AVLSequenceNode.prototype.gatherContent = function (index, take) {
		var at = 0|index;
		var range = 0|take;
		return (range > 0 && at > -1 && at < this.$total) ?
			this._gatherContent(at, range, this, "") : "";
	};

	AVLSequenceNode.prototype._gatherContent = function (index, take, node, content) {
		var at = 0|index;
		var range = 0|take;
		var before = content;
		var after = before;
		var size = 0;
		var diff = (0|node.$offset()) - at;
		if (diff > 0) {
			after = this._gatherContent(at, range, node.$left, before);
			range -= after.length - before.length;
			diff = 0;
			before = after;
		}
		
		if (range > 0) {
			size = 0|node.$added;
			size = size > 0 ? size : 0;
			if (size > 0 && -diff < size) {
				after = node.collect(-diff, range);
				range -= after.length;
				diff = -size;
				after = before + after;
				before = after;
			}
			
			if (range > 0 && node.$right) {
				after = this._gatherContent(-diff - size, range, node.$right, before);
			}
		}

		return after;
	};



	AVLSequenceNode.prototype.insert = function (index, content) {
		var at = 0|index;
		var text = (content === null || content === void 0) ? "" : content.toString();
		var result = this;
		return text.length < 1 ?
			this : (at < 0 || at > this.$total) ?
			null : this._insert(at, text, this, this.$total, this.$height).persist();
	};

	AVLSequenceNode.prototype._insert = function (index, content, node, total, height) {
		var MUTATING = 0|true;
		var at = 0|index;
		var size = 0;
		var mutable = node;
		var diff = (0|node.$offset()) - at;
		if (diff > 0) {
			mutable = this._insert(at, content, node.$left, 0|total, 0|height);
			mutable = node.build(mutable, node.$right, MUTATING) || node;
			return (mutable === node) ? node : this._rebalance(mutable);
		} else {
			size = 0|node.$added;
			size = size > 0 ? size : 0;
			if (-diff < size || !node.$right) {
				return this._insertNode(-diff, content, node, 0|total, 0|height);
			} else {
				mutable = this._insert(-diff - size, content, node.$right, 0|total, 0|height);
				mutable = node.build(node.$left, mutable, MUTATING) || node;
				return (mutable === node) ? node : this._rebalance(mutable);
			}
		}
	};

	AVLSequenceNode.prototype._insertNode = function (index, content, node, total, height) {
		var mutable = node.retrofit(0|index, content, 0|total, 0|height) || node;
		if (mutable == node) return node;
		else {
			// TODO: consider validating/correcting mutable.$left balance
			if (!mutable.$left) mutable.$left = node.$left || null;
			else if (node.$left) mutable.$left = this._insertMax(mutable.$left, node.$left);

			// TODO: consider validating/correcting mutable.$right balance
			if (!mutable.$right) mutable.$right = node.$right || null;
			else if (node.$right) mutable.$right = this._insertMin(mutable.$right, node.$right);

			return this._rebalance(mutable);
		}
	};

	AVLSequenceNode.prototype._insertMax = function (node, parent) {
		var mutable = this._asMutable(parent);
		mutable.$right = mutable.$right ? this._insertMax(node, mutable.$right) : node;
		return this._rebalance(mutable);
	};

	AVLSequenceNode.prototype._insertMin = function (node, parent) {
		var mutable = this._asMutable(parent);
		mutable.$left = mutable.$left ? this._insertMin(node, mutable.$left) : node;
		return this._rebalance(mutable);
	};



	AVLSequenceNode.prototype.fuse = function (node) {
		return node ? this._fuse(node, this).persist() : this;
	};

	AVLSequenceNode.prototype._fuse = function (after, before) {
		if (after.$height * after.$height < before.$height * before.$height) {
			return this._promoteMin(before, after);
		} else return this._promoteMax(after, before);
	};

	AVLSequenceNode.prototype._promoteMax = function (right, promoter) {
		var root = this._asMutable(promoter);
		var temp = root;
		var node = temp;

		while (temp.$right) {
			node = temp;
			temp = this._asMutable(temp.$right);
			node.$right = temp;
		}

		if (node.$right) {
			node.$right = temp.$left ? this._promoteMax(null, temp.$left) : null;
			temp.$left = this._rebalanceMax(root);
		}

		temp.$right = right || null;

		return this._rebalance(temp);
	};

	AVLSequenceNode.prototype._rebalanceMax = function (node) {
		node.$right = node.$right ? this._rebalanceMax(node.$right) : null;
		return this._rebalance(node);
	};

	AVLSequenceNode.prototype._promoteMin = function (left, promoter) {
		var root = this._asMutable(promoter);
		var temp = root;
		var node = temp;

		while (temp.$left) {
			node = temp;
			temp = this._asMutable(temp.$left);
			node.$left = temp;
		}

		if (node.$left) {
			node.$left = temp.$right ? this._promoteMin(null, temp.$right) : null;
			temp.$right = this._rebalanceMin(root);
		}

		temp.$left = left;

		return this._rebalance(temp);
	};

	AVLSequenceNode.prototype._rebalanceMin = function (node) {
		node.$left = node.$left ? this._rebalanceMin(node.$left) : null;
		return this._rebalance(node);
	};



	AVLSequenceNode.prototype.update = function (index, take, content) {
		var text = (content === null || content === void 0) ? "" : content.toString();
		var at = 0|index;
		var range = 0|take;
		var total = 0|this.$total;
		var node = this;
		var SAFE = 0|true;
		if (range < 1 || at < 0 || at > total - 1) return this.insert(at, text) || this;
		else if (text.length < 1) {
			node = this._remove(at, range, this, SAFE) || this;
			return node === this ? null : node.persist();
		} else {
			node = this._remove(at, range, this, SAFE);
			return this._insert(at, text, node, 0|node.$total, 0|node.$height).persist();
		}
	};

	AVLSequenceNode.prototype.subtree = function (index, take) {
		var at = 0|index;
		var range = 0|take;
		var total = 0|this.$total;
		var node = this;
		var SAFE = 0|true;
		if (at < 0 || at > total - 1) return this;
		else if (range < 1) return this.without(0, total, null, null).persist();
		else {
			if (at + range < total) node = this._remove(at + range, total, node, SAFE);
			if (at > 0) node = this._remove(0, at, node, SAFE);
			return node === this ? node : node.persist();
		}
	};

	AVLSequenceNode.prototype.remove = function (index, take) {
		var at = 0|index;
		var range = 0|take;
		var node = this;
		var SAFE = 0|true;
		if (range < 1 || at < 0 || at > this.$total - 1) return this;
		else {
			node = this._remove(at, range, this, SAFE) || this;
			return node === this ? null : node.persist();
		}
	};

	AVLSequenceNode.prototype._remove = function (index, take, node, safe) {
		var MUTATING = 0|true;
		var SAFE = 0|true;
		var at = 0|index;
		var range = 0|take;
		var size = 0;
		var mutable = node;
		var diff = (0|node.$offset()) - at;
		if (diff > 0) {
			if (diff > range) {
				mutable = this._remove(at, range, node.$left, 0|!SAFE);
				mutable = node.build(mutable, node.$right, MUTATING) || node;
				return this._rebalance(mutable);
			} else return this._removeNode(at, range, node, 0|safe);
		} else {
			size = 0|node.$added;
			size = size > 0 ? size : 0;
			if (-diff < size) return this._removeNode(at, range, node, 0|safe);
			else if (!node.$right) return node;
			else {
				mutable = this._remove(-diff - size, range, node.$right, 0|!SAFE);
				mutable = node.build(node.$left, mutable, MUTATING) || node;
				return this._rebalance(mutable);
			}
		}
	};

	AVLSequenceNode.prototype._removeNode = function (index, take, node, safe) {
		var at = 0|index;
		var range = 0|take;
		var mutable = node;
		var left = node;
		var right = node;
		var before = node;
		var after = node;
		var offset = 0|node.$offset();
		var start = at - offset;
		var end = at + range - offset;

		if (start < (0|node.$added)) {
			before = this._removeAbove(at, node) || null;
			if (start < 0) {
				left = this._seekAbove(at, node) || null;
				start = at - (before ? 0|before.$total : 0); // did - want
			}
		} else before = node.$left || null;

		if (end > 0) {
			after = this._removeBelow(at + range + 1, node) || null;
			if (end + 1 > (0|node.$added)) {
				right = this._seekBelow(at + range + 1, node) || null;
				end = (at + range) - (offset + (0|node.$added)); // want
				end -= (0|node.$onset()) - (after ? 0|after.$total : 0) // minus did
				end += (right ? 0|right.$added : 0);
			}
		} else after = node.$right || null;

		if (!left && !right && !safe) return null;
		else if (start > 0 || end < (right ? 0|right.$added : 0) || (!before && !after && safe)) {
			mutable = this._asMutable(node.without(start, end, left, right));
			if (!mutable.$left) mutable.$left = before;
			else if (before) mutable.$left = this._insertMin(before, mutable.$left);
			if (!mutable.$right) mutable.$right = after;
			else if (after) mutable.$right = this._insertMax(after, mutable.$right);
			return this._rebalance(mutable);
		} else if (!after) return before || null;
		else if (!before) return after || null;
		else return this._fuse(after, before);
	};

	AVLSequenceNode.prototype._removeAbove = function (index, node) {
		var MUTATING = 0|true;
		var at = 0|index;
		var size = 0;
		var mutable = node;
		var diff = (0|node.$offset()) - at;
		if (diff > 0) return this._removeAbove(at, node.$left) || null;
		else {
			size = 0|node.$added;
			size = size > 0 ? size : 0;
			if (-diff < size) return node.$left || null;
			else if (at < (0|node.$total)) {
				mutable = this._removeAbove(-diff - size, node.$right) || null;
				return this._rebalance(node.build(node.$left || null, mutable, MUTATING));
			} else return node;
		}
	};

	AVLSequenceNode.prototype._removeBelow = function (index, node) {
		var MUTATING = 0|true;
		var at = 0|index;
		var size = 0;
		var mutable = node;
		var diff = (0|node.$offset()) - at;
		if (diff < 0) {
			size = 0|node.$added;
			size = size > 0 ? size : 0;
			if (-diff > size) {
				return node.$right ? this._removeBelow(-diff - size, node.$right) || null : null;
			} else return node.$right || null;
		} else if (diff > 0) {
			mutable = this._removeBelow(at, node.$left) || null;
			return this._rebalance(node.build(mutable, node.$right || null, MUTATING));
		} else if (at === 0) return node;
		else return this._rebalance(node.build(null, node.$right || null, MUTATING));
	};



	AVLSequenceNode.prototype._imbalance = function (node) {
		var left = (node.$left ? 0|node.$left.$height : 0);
		var right = (node.$right ? 0|node.$right.$height : 0);
		return (right < 0 ? -right : right) - (left < 0 ? -left : left);
	};

	AVLSequenceNode.prototype._correction = function (node) {
		var imbalance = 0|this._imbalance(node);
		if (imbalance > 1) return (node.$right && this._imbalance(node.$right) < 0) ? 2 : 1;
		else if (imbalance < -1) return (node.$left && this._imbalance(node.$left) > 0) ? -2 : -1;
		else return 0;
	};

	AVLSequenceNode.prototype._rebalance = function (parent) {
		var node = this._asMutable(parent);
		var correction = 0|this._correction(this._recalculate(node));
		if (correction < 0) {
			if (correction < -1) node.$left = this._rotateLeft(node.$left);
			node = this._rotateRight(node);
			if (correction < -2) node.$right = this._rebalance(node.$right);
		} else if (correction > 0) {
			if (correction > 1) node.$right = this._rotateRight(node.$right);
			node = this._rotateLeft(node);
			if (correction > 2) node.$left = this._rebalance(node.$left);
		}
		return node;
	};

	AVLSequenceNode.prototype._recalculate = function (node) {
		var left = 0|node.$offset();
		var right = 0|node.$onset();
		var lower = node.$left ? 0|node.$left.$height : 0;
		var upper = node.$right ? 0|node.$right.$height : 0;

		lower = lower < 0 ? -lower : lower;
		upper = upper < 0 ? -upper : upper;

		node.$height = -1 - (lower > upper ? lower : upper);

		node.$total = (0|node.$added) + left + right;

		return node;
	};

	AVLSequenceNode.prototype._rotateLeft = function (node) {
		var parent = node.$right;
		var child = this._asMutable(node);
		parent = this._asMutable(parent);
		child.$right = parent.$left;
		parent.$left = child;
		this._recalculate(child);
		return this._recalculate(parent);
	};

	AVLSequenceNode.prototype._rotateRight = function (node) {
		var parent = node.$left;
		var child = this._asMutable(node);
		parent = this._asMutable(parent);
		child.$left = parent.$right;
		parent.$right = child;
		this._recalculate(child);
		return this._recalculate(parent);
	};

	AVLSequenceNode.prototype._asMutable = function (node) {
		var MUTATING = 0|true;
		return node.$height < 0 ? node : node.build(node.$left, node.$right, MUTATING);
	};



	AVLSequenceNode.prototype.$asPersistent = function () {
		if (this.$height < 0) this.$height = -this.$height;
		return this;
	};

	AVLSequenceNode.prototype.$invalidate = function () {
		this.$height = 0;
		return this;
	}; 

	AVLSequenceNode.prototype.$asLeaf = function () {
		var result = this._asMutable(this);
		result.$left = null;
		result.$right = null;
		return this._recalculate(result);
	};



	AVLSequenceNode.prototype.build = function (left, right, mutator) {
		throw new Error("AVLSequence.build() requires an overridden implementation");
		//return new AVLSequenceNode(left || null, right || null, 0|this.$added, 0|mutator);
	};

	AVLSequenceNode.prototype.collect = function (index, take) {
		return "";
	};

	AVLSequenceNode.prototype.retrofit = function (index, content, total, height) {
		return null;
	};

	AVLSequenceNode.prototype.without = function (start, end, left, right) {
		throw new Error("AVLSequence.without() requires an overridden implementation");
		//return new AVLSequenceNode(null, null, (0|start) + (0|right.$added) - (0|end), 0|true);
	};

	AVLSequenceNode.prototype.persist = function () {
		var parent = this;
		if (parent.$left && parent.$left.$height < 0) parent.$left.persist();
		if (parent.$right && parent.$right.$height < 0) parent.$right.persist();
		return this.$asPersistent();
	};





	function ColumnProvider (content) {
		this._raw = (content === null || content === void 0) ? "" : content.toString();
	}

	ColumnProvider.prototype.getText = function () {
		return this._raw;
	};

	ColumnProvider.prototype.setText = function (content) {
		this._raw = (content === null || content === void 0) ? "" : content.toString();
		return this;
	};



	function ColumnBuffer (content) {
		var raw = (content === null || content === void 0) ? "" : content.toString();
		ColumnProvider.call(this, raw);
	}

	ColumnBuffer.prototype = new ColumnProvider("");

	ColumnBuffer.prototype.indexOfRowColumn = function (row, column) {
		var line = 0|row;
		var point = 0|column;
		var before = 0;
		var after = this._raw.indexOf("\n", before);

		while (line-- > 0 && after > -1) {
			before = after + 1;
			after = this._raw.indexOf("\n", before);
		}

		after = after < 0 ? this._raw.length : after;
		if (line > -1) return -1;
		else if (point > after - before) return -1;
		else return point + before;
	};

	ColumnBuffer.prototype.insert = function (index, content) {
		var at = 0|index;
		var text = (content === null || content === void 0) ? "" : content.toString();

		if (at < 0 || at > this._raw.length) return this;
		else return this.setText(this._raw.slice(0, at) + text + this._raw.slice(at));
	};

	ColumnBuffer.prototype.remove = function (index, take) {
		var at = 0|index;
		var range = 0|take;

		if (range < 1 || at < 0 || at > this._raw.length) return this;
		else if (at + range > this._raw.length - 1) return this.setText(this._raw.slice(0, at));
		else return this.setText(this._raw.slice(0, at) + this._raw.slice(at + range));
	};



	function _accumulateSplits (content, start, list) {
		var index = 0|start;
		do index = content.indexOf("\n", index);
		while (index > -1 && list.push(index++))
		return list;
	}

	function TextNodeData (content) {
		var raw = (content === null || content === void 0) ? "" : content.toString();
		var nextLine = raw.indexOf("\n", 0);
		var laterLine = nextLine < 0 ? -1 : raw.indexOf("\n", nextLine + 1);

		ColumnBuffer.call(this, raw);

		this.$splits = nextLine < 0 ? 0 : 1;
		this.$extra = -1;
		this.$lastSplit = nextLine;
		this._splitIndices = laterLine > -1 ?
			_accumulateSplits(raw, laterLine + 1, [nextLine, laterLine]) : null;

		if (laterLine > -1) {
			this.$splits = this._splitIndices.length;
			this.$lastSplit = 0|this._splitIndices[this.$splits - 1];
		}

		this.$extra = 0|(raw.length - (this.$lastSplit + 1));
	}

	TextNodeData.prototype = new ColumnBuffer("");

	TextNodeData.prototype.setText = function (content) {
		var raw = (content === null || content === void 0) ? "" : content.toString();
		return new TextNodeData(raw);
	};

	TextNodeData.prototype.indexOfRowColumn = function (row, column) {
		var line = 0|row;
		var point = 0|column;
		var splits = 0|this.$splits;
		if (line > splits || line < 0) return -1;
		else if (splits === line) return point > this.$extra ? -1 : (point + this.$lastSplit + 1);
		else if (splits === 1) return point > this.$lastSplit ? -1 : point;
		else if (line === 0) return point > this._splitIndices[0] ? -1 : point;
		else if (point > this._splitIndices[line] - this._splitIndices[line - 1] - 1) return -1;
		else return point + this._splitIndices[line - 1] + 1;
	};



	function TextNodeProvider (content, meta) {
		var raw = (content === null || content === void 0) ? "" : content.toString();
		TextNodeData.call(this, raw);
		this._meta = null;
		this._meta = (meta === null || meta === void 0) ? null : meta;
	}

	TextNodeProvider.prototype = new TextNodeData("");

	TextNodeProvider.prototype.providerOf = function (content, requestingNode) {
		var text = (content === null || content === void 0) ? "" : content.toString();
		var meta = this.meta() || null;
		meta = meta ? meta.metadataFor(text, this) : null;
		if (text === this.raw() && meta === this.meta()) return this; 
		else return new TextNodeProvider(text, meta);
	};

	TextNodeProvider.prototype.meta = function () {
		return this._meta;
	};

	TextNodeProvider.prototype.splits = function () {
		return 0|this.$splits;
	};

	TextNodeProvider.prototype.extra = function () {
		return 0|this.$extra;
	};

	TextNodeProvider.prototype.raw = function () {
		return this.getText();
	};



	function AVLTextNode (left, right, provider, mutator) {
		var added = provider ? 0|provider.raw().length : 0;

		AVLSequenceNode.call(this, left || null, right || null, added, 0|mutator);

		this.$rows = 0;
		this.$columns = 0;

		this._provider = null;
		this._provider = provider || new TextNodeProvider("", null);
	}

	AVLTextNode.prototype = new AVLSequenceNode(null, null, 0, 0|false);



	AVLTextNode.prototype.limitForTotalHeight = function (height, total) {
		return 240;
	};

	AVLTextNode.prototype.makeNode = function (left, right, provider, mutator) {
		return new AVLTextNode(left, right, provider, 0|mutator);
	};

	AVLTextNode.prototype.locateRowColumn = function (line, point) {
		return this._provider.indexOfRowColumn(0|line, 0|point);
	};

	AVLTextNode.prototype.splits = function () {
		return this._provider.splits();
	};

	AVLTextNode.prototype.extra = function () {
		return this._provider.extra();
	};

	AVLTextNode.prototype.raw = function () {
		return this._provider.raw();
	};

	AVLTextNode.prototype.meta = function () {
		return this._provider.meta();
	};



	AVLTextNode.prototype.$providerOf = function (content) {
		var text = (content === null || content === void 0) ? "" : content.toString();
		return this._provider.providerOf(text, this);
	};

	AVLTextNode.prototype.$nodeOf = function (left, right, provider, mutator) {
		var node = this.makeNode(left, right, provider, 0|mutator);
		return (0|mutator) ? node : node.persist();
	};



	AVLTextNode.prototype.$partition = function (pieces, mutator) {
		var fragments = (Array.isArray(pieces) && pieces.length) ? pieces : [""];
		var count = 0|fragments.length;
		var bits = 0|_bitDepthOf(count);
		var shift = bits || 1;
		var layer = 1 << (shift - 1);
		var capacity = (1 << shift) - 1;
		var unused = capacity - count;
		var deep = layer - unused;
		var shallow = count - deep;
		var index = 0;
		var height = 0;
		var amount = 0;
		var offset = 0;
		var list = [this.$providerOf(fragments[0])];

		for (index = 1; index < deep; index++) list.push(this.$providerOf(fragments[2 * index]));

		while (++height < bits) {
			for (index = -1 + (1 << height); index < 2 * deep; index += 1 << (height + 1)) {
				list.push(this.$providerOf(fragments[index])); 
			}
			for (index; index < capacity; index += 1 << (height + 1)) {
				list.push(this.$providerOf(fragments[index - 1 - ((index - 2 * deep) >> 1)])); 
			}
		}

		for (index = 0; index < deep; index++) {
			list[index] = this.$nodeOf(null, null, list[index], 0|mutator);
		}

		if (--height > 0 && unused > 0) {
			height--;
			amount = 1 << height;
			for (index = 0; index < amount; index++) {
				offset = 2 * index;
				list[index + deep] = this.$nodeOf(
					offset < deep ? list[offset] : null,
					offset + 1 < deep ? list[offset + 1] : null,
					list[index + deep],
					0|mutator
				);
			}
		}

		while (height-- > 0) {
			amount = count + 1 - (1 << height);
			for (index = amount - (1 << height); index < amount; index++) {
				offset = index - (1 << height) - (amount - index);
				list[index] = this.$nodeOf(list[offset], list[offset + 1], list[index], 0|mutator);
			}
		}

		return list[list.length - 1];
	};

	AVLTextNode.prototype.chunk = function (limit, content, mutator) {
		var text = (content === null || content === void 0) ? "" : content.toString();
		var size = ((0|limit) >> 1) || 1;
		if (text.length > 3 * size) {
			return this.$partition(text.match(new RegExp("[^]{1,"+size+"}", "g")), 0|mutator);
		} else if (text.length > 2 * size) {
			return this.$nodeOf(
				this.$nodeOf(null, null, this.$providerOf(text.slice(0, size)), 0|mutator),
				this.$nodeOf(null, null, this.$providerOf(text.slice(2 * size)), 0|mutator),
				this.$providerOf(text.slice(size, 2 * size)),
				0|mutator);
		} else return this.$nodeOf(null, null, this.$providerOf(text), 0|mutator);
	};



	AVLTextNode.prototype.indexOfRowColumn = function (row, column) {
		var line = 0|row;
		var point = 0|column;
		if (point < 0 || line < 0 || line > this.$rows) return -1;
		else if (line === this.$rows) {
			return (point > (0|this.$columns)) ?
				-1 : (0|this.$total) - (0|this.$columns) + point;
		} else return 0|this._indexOfRowColumn(line, point, this, 0);
	};

	AVLTextNode.prototype._indexOfRowColumn = function (row, column, node, index) {
		var at = 0|index;
		var line = 0|row;
		var point = 0|column;
		var verticals = 0;
		var horizontals = 0;
		var offset = 0;
		var rDiff = (node.$left ? 0|node.$left.$rows : 0) - line;
		var cDiff = (node.$left ? 0|node.$left.$columns : 0) - point;
		if (rDiff > 0 || (rDiff === 0 && cDiff > 0)) {
			return this._indexOfRowColumn(line, point, node.$left, at);
		} else {
			offset = 0|node.$offset();
			verticals = 0|node.splits();
			verticals = verticals > 0 ? verticals : 0;
			horizontals = 0|node.extra();
			horizontals = horizontals > 0 ? horizontals : 0;
			line = -rDiff;
			point = line ? 0|column : -cDiff;
			if (line < verticals || (line === verticals && point < horizontals + 1)) {
				at += 0|node.locateRowColumn(line, point);
				return (at < (0|index)) ? -1 : (at + offset);
			} else if (node.$right) {
				line -= verticals;
				point = line ? 0|column : (point - horizontals);
				return this._indexOfRowColumn(line, point, node.$right, at + offset + (0|node.$added));
			} else return -1;
		}
	};



	AVLTextNode.prototype.build = function (left, right, mutator) {
		return this.$nodeOf(left || null, right || null, this.$providerOf(this.raw()), 0|mutator);
	};

	AVLTextNode.prototype.collect = function (index, take) {
		var at = 0|index;
		var range = 0|take;
		var text = this.raw();
		return (at === 0 && range === (0|this.$added)) ? text : text.slice(index, index + take);
	};

	AVLTextNode.prototype.retrofit = function (index, content, total, height) {
		var text = (content === null || content === void 0) ? "" : content.toString();
		var at = 0|index;
		var left = this;
		var right = this;
		var raw = this.raw() || "";
		var size = 0|this.limitForTotalHeight(0|total, 0|height);
		var MUTATING = 0|true;
		if (text.length < 1) throw new Error("unexpected insertion of 0 characters"); // return this;
		else if (raw.length < 1) return this.chunk(size, text, MUTATING);
		else if (at < 1) return this.build(this.chunk(size, text, MUTATING), null, MUTATING);
		else if (at < raw.length) return this.chunk(size, raw.slice(0, at) + text + raw.slice(at), MUTATING);
		else return this.build(null, this.chunk(size, text, MUTATING), MUTATING);
	};

	AVLTextNode.prototype.without = function (start, end, left, right) {
		var before = left ? left.raw() || "" : "";
		var after = right ? right.raw() || "" : "";
		var text = before.slice(0, 0|start) + after.slice(0|end);
		var MUTATING = 0|true;
		return this.$nodeOf(null, null, this.$providerOf(text), MUTATING);
	};

	AVLTextNode.prototype.persist = function () {
		var parent = this;
		var left = parent.$left || _invalidTextNode;
		var right = parent.$right || _invalidTextNode;
		var splits = 0|parent.splits();
		var extra = 0|parent.extra();

		if (left.$height < 0) left.persist();
		if (right.$height < 0) right.persist();

		parent.$columns = 0;
		parent.$rows = 0;

		if (parent.$height !== 0) {
			parent.$columns += 0|right.$columns;
			parent.$rows += 0|right.$rows;
			parent.$columns += !parent.$rows ? extra : 0;
			parent.$rows += splits;
			parent.$columns += !parent.$rows ? 0|left.$columns : 0;
			parent.$rows += 0|left.$rows;
		}

		return parent.$asPersistent();
	};

	var _invalidTextNode = new AVLTextNode(null, null, null, 0|false);
	_invalidTextNode.$invalidate().persist();





	function AVLTextLine (left, right, node, features, mutator) {
		var columns = node || new AVLTextNode(null, null, null, 0|mutator).persist();
		var added = 0|columns.$total;
		var text = "";
		var split = columns.indexOfRowColumn(1, 0);
		var prior = left || null;
		var next = right || null;
		var MUTATING = 0|true;

		if (split > -1 && split < added - 1) {
			text = columns.gatherContent(0, added) || "";
			columns = columns.$partition(text.match(/(.*\n|.+$)/g), MUTATING); // always mutate

			if (!prior) prior = columns.$left ? this._mimic(columns.$left, null, null, 0|mutator) : null;
			else if (columns.$left) {
				prior = this._mimic(columns.$left, prior, null, MUTATING);
				prior = (0|mutator) ? prior : prior.persist();
			}

			if (!next) next = columns.$right ? this._mimic(columns.$right, null, null, 0|mutator) : null;
			else if (columns.$right) {
				next = this._mimic(columns.$right, null, next, MUTATING);
				next = (0|mutator) ? next : next.persist();
			}

			columns = columns.$asLeaf();

			added = 0|columns.$added;
		}

		AVLSequenceNode.call(this, prior || null, next || null, added, 0|mutator);

		this.$rows = 0;

		this.$columns = columns.persist();

		this.$features = features || null;
	}

	AVLTextLine.prototype = new AVLSequenceNode(null, null, 0, 0|false);



	AVLTextLine.prototype.makeLine = function (left, right, node, features, mutator) {
		return new AVLTextLine(left, right, node, features, 0|mutator);
	};



	AVLTextLine.prototype.$lineOf = function (left, right, node, features, mutator) {
		var line = this.makeLine(left, right, node, features, 0|mutator);
		return (0|mutator) ? line : line.persist();
	};

	AVLTextLine.prototype.$featuresOf = function () {
		return this.$features ? this.$features.featuresOf() : null;
	};



	AVLTextLine.prototype.divide = function (content, left, right, mutator) {
		var text = (content === null || content === void 0) ? "" : content.toString();
		var node = this.$columns;
		var MUTATING = 0|true;
		if (text.indexOf("\n") < 0) {
			node = node.$nodeOf(null, null, node.$providerOf(text), 0|!MUTATING);
			return this.$lineOf(left || null, right || null, node, this.$featuresOf(), 0|mutator);
		} else {
			node = node.$partition(text.match(/(.*\n|.+$)/g), MUTATING);
			return this._mimic(node, left || null, right || null, 0|mutator);
		}
	};

	AVLTextLine.prototype._mimic = function (mutable, left, right, mutator) {
		var left = mutable.$left ? this._mimic(mutable.$left, left, null, 0|mutator) : left || null;
		var right = mutable.$right ? this._mimic(mutable.$right, null, right, 0|mutator) : right || null;
		var node = mutable.$asLeaf();
		var mime = this.$lineOf(left, right, node, this.$featuresOf(), 0|mutator);
		return (0|mutator) ? mime : mime.persist();
	};



	AVLTextLine.prototype.sizeOfRow = function (row) {
		var line = 0|row;
		return (line > -1 && line < this.$rows) ?
			0|this._sizeOfRow(line, this) : -1;
	};

	AVLTextLine.prototype._sizeOfRow = function (row, node) {
		var at = 0|index;
		var line = 0|row;
		var diff = (node.$left ? 0|node.$left.$rows : 0) - line;
		if (diff < 0) return 0|this._sizeOfRow(-diff - 1, node.$right);
		else if (diff > 0) return 0|this._sizeOfRow(line, node.$left);
		else return (0|node.$added) - (node.$columns.splits() === 0 ? 0 : 1);
	};



	AVLTextLine.prototype.indexOfRowColumn = function (row, column) {
		var node = this;
		var line = 0|row;
		var point = 0|column;
		if (point < 0 || line < 0 || line > this.$rows) return -1;
		else if (line === this.$rows) {
			if (point === 0) while (node.$right) node = node.$right;
			return point === 0 && node.$columns.splits() > 0 ? 0|this.$total : -1;
		} else return 0|this._indexOfRowColumn(line, point, this, 0);
	};

	AVLTextLine.prototype._indexOfRowColumn = function (row, column, node, index) {
		var at = 0|index;
		var line = 0|row;
		var point = 0|column;
		var relative = (0|node.$added) - point;
		var before = (0|node.$offset());
		var after = at + before + (0|node.$added);
		var diff = (node.$left ? 0|node.$left.$rows : 0) - line;
		if (diff < 0) return this._indexOfRowColumn(-diff - 1, point, node.$right, after);
		else if (diff > 0) return this._indexOfRowColumn(line, point, node.$left, at);
		else if (relative > 0) return at + point + before;
		else if (relative === 0 && node.$columns.splits() === 0) return at + point + before;
		else return -1;
	};



	AVLTextLine.prototype.build = function (left, right, mutator) {
		return this.$lineOf(left || null, right || null, this.$columns, this.$featuresOf(), 0|mutator);
	};

	AVLTextLine.prototype.collect = function (index, take) {
		return this.$columns.gatherContent(0|index, 0|take);
	};

	AVLTextLine.prototype.retrofit = function (index, content, total, height) {
		var text = (content === null || content === void 0) ? "" : content.toString();
		var at = 0|index;
		var split = text.indexOf("\n");
		var cut = text.lastIndexOf("\n");
		var fragments;
		var size = 0|this.$added;
		var left = this;
		var right = this;
		var node = this.$columns;
		var prefix = node;
		var suffix = node;
		var MUTATING = 0|true;
		if (size === 0) {
			return this.divide(text, null, null, MUTATING);
		} else if (split < 0) {
			return this.$lineOf(null, null, node.insert(at, text), this.$featuresOf(), MUTATING);
		} else if (at === 0) {
			fragments = text.match(/(.*\n|.+$)/g);
			suffix = (cut === text.length - 1) ? node : node.insert(0, fragments.pop());
			prefix = this.$columns.$partition(fragments, MUTATING);
			left = this._mimic(prefix, null, null, MUTATING);
			return this.$lineOf(left, null, suffix, this.$featuresOf(), MUTATING);
		} else if (at < size) {
			prefix = node.update(at, size, text.slice(0, split + 1));
			suffix = node.update(0, at, text.slice(cut + 1));
			left = this.$lineOf(null, null, prefix, this.$featuresOf(), MUTATING);
			if (split === cut) {
				return this.$lineOf(left, null, suffix, this.$featuresOf(), MUTATING);
			} else {
				right = this.$lineOf(null, null, suffix, this.$featuresOf(), MUTATING);
				return this.divide(text.slice(split + 1, cut + 1), left, right, MUTATING);
			}
		} else if (node.splits() === 0) {
			fragments = text.slice(split + 1).match(/(.*\n|.+$)/g);
			suffix = this.$columns.$partition(fragments, MUTATING);
			prefix = node.insert(size, text.slice(0, split + 1));
			right = this._mimic(suffix, null, null, MUTATING);
			return this.$lineOf(null, right, prefix, this.$featuresOf(), MUTATING);
		} else if (!this.$right) {
			fragments = text.match(/(.*\n|.+$)/g);
			suffix = this.$columns.$partition(fragments, MUTATING);
			right = this._mimic(suffix, null, null, MUTATING);
			return this.$lineOf(null, right, node, this.$featuresOf(), MUTATING);
		} else throw new Error("insert/retrofit expected on the next AVLTextLine"); // return this;
	};

	AVLTextLine.prototype.without = function (start, end, left, right) {
		var before = left && left.$columns ? left.$columns.subtree(0, 0|start) : null;
		var after = right && right.$columns ?
			right.$columns.subtree(0|end, (0|right.$added) - (0|end)) : null;
		var node = !before ?
			after : !after ?
			before : before.fuse(after);
		var MUTATING = 0|true;
		return this.$lineOf(null, null, node, this.$featuresOf(), MUTATING);
	};

	AVLTextLine.prototype.persist = function () {
		var parent = this;
		var left = parent.$left || _invalidTextLine;
		var right = parent.$right || _invalidTextLine;

		if (left.$height < 0) left.persist();
		if (right.$height < 0) right.persist();

		parent.$rows = 0;

		if (parent.$height !== 0) {
			parent.$rows = 1 + (0|left.$rows) + (0|right.$rows);
		}

		return parent.$asPersistent();
	};

	var _invalidTextLine = new AVLTextLine(null, null, null, null, 0|false);
	_invalidTextLine.$invalidate().persist();





	function LineBuffer () {
		this._cachedSizes = [0];
		this._lines = [new ColumnProvider("")];
	}

	LineBuffer.prototype.lineCount = function () {
		return this._lines.length;
	};

	LineBuffer.prototype.lineAt = function (index) {
		var at = 0|index;
		return (at > -1 && at < this._lines.length) ? this._lines[at] : null;
	};

	LineBuffer.prototype.charCount = function () {
		var count = this._lines.length;
		var index = 0;
		var total = 0;

		for (index; index < count; index++) total += this._cachedSizes[index];

		return total;
	};

	LineBuffer.prototype.indexOfRowColumn = function (row, column) {
		var line = 0|row;
		var point = 0|column;
		if (line < 0 || line > this._cachedSizes.length - 1) return -1;
		else if (point > this._cachedSizes[line]) return -1;
		else {
			while (line-- > 0) point += this._cachedSizes[line];
			return (0|point) + (0|!line);
		}
	};

	LineBuffer.prototype.gatherContent = function (index, take) {
		var at = 0|index;
		var range = 0|take;
		var line = 0;
		var point = 0;
		var count = this._cachedSizes.length;
		var full = "";
		var part = full;

		if (at > -1 && range > 0) {
			while (line < count && at > this._cachedSizes[line]) {
				at -= 0|this._cachedSizes[line++];
			}
			if (at > 0 && at === this._cachedSizes[line]) line++; // start
			else point = at;

			if (line < count) do {
				part = this._lines[line++].getText().slice(point, point + range);
				full += part;
				range -= part.length;
				point = 0;
			} while (range > 0)
		}

		return full;
	};

	LineBuffer.prototype.remove = function (index, take) {
		var at = 0|index;
		var range = 0|take;
		var line = 0;
		var point = 0;
		var count = this._cachedSizes.length;
		var text = "";
		var splice = 0;

		if (at > -1 && range > 0) {
			while (line < count && at > this._cachedSizes[line]) { // end
				at -= 0|this._cachedSizes[line++];
			}
			if (at > 0 && at === this._cachedSizes[line]) line++; // start
			else point = at;

			if (line < count) {
				text = this._lines[line].getText();
				text = (point + range < text.length) ?
					text.slice(0, point) + text.slice(point + range) : (point < text.length) ?
					text.slice(0, point) : text;
				range -= this._cachedSizes[line] - text.length;
				this._lines[line].setText(text);
				this._cachedSizes[line] = text.length;
				splice = line++;

				while (line < count && range > this._cachedSizes[line] - 1) {
					range -= 0|this._cachedSizes[line++];
				}

				if (line < count && (range > 0 || point === text.length)) {
					text = this._lines[line++].getText();
					text = this._lines[splice].getText() + text.slice(range);
					this._lines[splice].setText(text);
					this._cachedSizes[splice] = text.length;
				}

				splice += this._cachedSizes[splice] > 0 ?
					1 : line < count ?
					0 : 1;

				if (splice < line) {
					this._lines.splice(splice, line - splice);
					this._cachedSizes.splice(splice, line - splice);
				}
			}
		}

		return this;
	};

	LineBuffer.prototype.insert = function (index, content) {
		var at = 0|index;
		var line = 0;
		var point = 0;
		var count = this._cachedSizes.length;
		var text = (content === null || content === void 0) ? "" : content.toString();
		var before = text;
		var after = text;

		if (at > -1 && text.length > 0) {
			while (line < count && at > this._cachedSizes[line]) { // end
				at -= 0|this._cachedSizes[line++];
			}
			
			if (line === count - 1) point = at;
			else if (at > 0 && at === this._cachedSizes[line]) line++; // start
			else point = at;

			if (line < count) {
				before = this._lines[line].getText().slice(0, point);
				after = this._lines[line].getText().slice(point);

				if (text.indexOf("\n") < 0) {
					text = before + text + after;
					this._lines[line].setText(text);
					this._cachedSizes[line] = text.length;
				} else {
					this._splice(line, before, after, text);
				}
			}
		}

		return this;
	};

	LineBuffer.prototype._splice = function (row, before, after, content) {
		var line = 0|row;
		var bufferSplice = this._lines;
		var sizeSplice = this._cachedSizes;
		var text = content;
		var parts = text.match(/\n$/.test(text) ? /.*(\n|$)/g : /(.*\n|.+$)/g);

		parts[0] = before + parts[0];
		parts[parts.length - 1] += after;

		this._lines[line].setText(parts[0]);
		this._cachedSizes[line] = parts[0].length;

		line += 1;

		this._lines.splice(line, 0, new ColumnProvider(parts[1]));
		this._cachedSizes.splice(line, 0, parts[1].length);

		if (parts.length > 2) {
			line += 1;
			parts[0] = "";
			parts[1] = "";

			bufferSplice = parts.map(_splicingBuffers, this._lines[0]);
			sizeSplice = parts.map(_splicingSizes);

			bufferSplice[0] = line;
			bufferSplice[1] = 0;
			sizeSplice[0] = line;
			sizeSplice[1] = 0;

			this._lines.splice.apply(this._lines, bufferSplice);
			this._cachedSizes.splice.apply(this._cachedSizes, sizeSplice);
		}
	};

	function _splicingBuffers (text, index) {
		return index > 1 ? new ColumnProvider(text) : this;
	}

	function _splicingSizes (text) {
		return text.length;
	}



	var benchmarks = null && (function validate () {
		var fragment = new ColumnBuffer("");
		var buffer = new LineBuffer();
		var node = new AVLTextNode(null, null, null, 0|false).persist();
		var all = new AVLTextLine(null, null, null, null, 0|false).persist();
		var some = new AVLTextLine(null, null, node, null, 0|false).persist();
		var log = [];

		var use = null;

		var steps = 10 + (0|(10000 * Math.random()));
		var chars = ["0", "1", "2", "3", "4", "5", "0", "1", "2", "3", "4", "5", "0", "1", "2", "3", "4", "5", "0", "1", "2", "3", "4", "5", "\n"];
		var data = makeInstruction();

		try {
			do {
				data = use && use.pop(use.length && steps++) || makeInstruction();
				log.unshift(data);
				handleInstruction(data);
			} while (steps-- > 0)
			//debugger;
			return [
				replayFragment,
				replayBuffer,
				replayNode,
				replayAll,
			].map(function (fn) {
				var then = performance.now();
				fn(0);
				return fn.name + ": "+(performance.now() - then);
			}).concat("steps: "+log.length);
		} catch (e) {
			// in the future, keep logs that failed for retesting later (esp. for reimplementations)
			console.log("\n\t\tvar use = "+JSON.stringify(log)+";\n\n");
			//debugger;
			throw e;
		}



		function replayNode (offset) {
			return log.slice(0|offset).reverse().reduce(function (result, command) {
				var nindex = result.indexOfRowColumn(command.row, command.column);
				result = result.remove(nindex, command.erase);
				return result = result.insert(nindex, command.value) || result;
			}, new AVLTextNode(null, null, null, 0|false).persist());
		}

		function replayAll (offset) {
			return log.slice(0|offset).reverse().reduce(function (result, command) {
				var aindex = result.indexOfRowColumn(command.row, command.column);
				result = result.remove(aindex, command.erase);
				return result = result.insert(aindex, command.value) || result;
			}, new AVLTextLine(null, null, null, null, 0|false).persist());
		}

		function replaySome (offset) {
			return log.slice(0|offset).reverse().reduce(function (result, command, onset, list) {
				var aindex = result.indexOfRowColumn(command.row, command.column);
				var reset = list.length - onset;
				result = result.remove(aindex, command.erase);
				result = result.insert(aindex, command.value) || result;
				if (command.init) {
					result = new AVLTextLine(null, null, replayNode(reset), null, 0|false).persist();
				}
				return result;
			}, new AVLTextLine(null, null, null, null, 0|false).persist());
		}

		function replayBuffer (offset) {
			return log.slice(0|offset).reverse().reduce(function (result, command) {
				var bindex = result.indexOfRowColumn(command.row, command.column);
				result = result.remove(bindex, command.erase);
				return result = result.insert(bindex, command.value);
			}, new LineBuffer());
		}

		function replayFragment (offset) {
			return log.slice(0|offset).reverse().reduce(function (result, command) {
				var findex = result.indexOfRowColumn(command.row, command.column);
				result = result.remove(findex, command.erase);
				return result = result.insert(findex, command.value);
			}, new ColumnBuffer());
		}

		function compareImplementations () {
			var fsize = 0|fragment.getText().length;
			var bsize = 0|buffer.charCount();
			var nsize = 0|node.$total;
			var asize = 0|all.$total;
			var ssize = 0|some.$total;

			var ftext = fragment.getText();
			var btext = buffer.gatherContent(0, bsize);
			var ntext = node.gatherContent(0, nsize);
			var atext = all.gatherContent(0, asize);
			var stext = some.gatherContent(0, ssize);

			if (bsize !== nsize || fsize !== nsize || asize !== nsize || ssize !== nsize) {
				//debugger;
				throw new Error("size mismatch");
			}

			if (btext !== ntext || ftext !== ntext || atext !== ntext || stext !== ntext) {
				//debugger;
				throw new Error("text mismatch");
			}
		}

		function handleInstruction (command) {
			var findex = fragment.indexOfRowColumn(command.row, command.column);
			var bindex = buffer.indexOfRowColumn(command.row, command.column);
			var nindex = node.indexOfRowColumn(command.row, command.column);
			var aindex = all.indexOfRowColumn(command.row, command.column);
			var sindex = some.indexOfRowColumn(command.row, command.column);

			if (bindex !== nindex || findex !== nindex || aindex !== nindex || sindex !== nindex) {
				//debugger;
				throw new Error("index mismatch");
			}

			fragment = fragment.remove(findex, command.erase);
			buffer = buffer.remove(bindex, command.erase);
			node = node.remove(nindex, command.erase);
			all = all.remove(aindex, command.erase);
			some = some.remove(sindex, command.erase);
			compareImplementations();

			fragment = fragment.insert(findex, command.value);
			buffer = buffer.insert(bindex, command.value);
			node = node.insert(nindex, command.value) || node;
			all = all.insert(aindex, command.value) || all;
			some = some.insert(sindex, command.value) || some;
			compareImplementations();

			if (command.init) {
				some = new AVLTextLine(null, null, node, null, 0|false).persist();
				compareImplementations();
			}
		}

		function makeInstruction () {
			var maxRow = 0|(buffer.lineCount() + (1 + 0.1 * Math.random()));
			var row = 0|(maxRow * Math.random());
			var maxColumn = row < buffer.lineCount() ?
				0|(buffer.lineAt(row).getText().length * 1 + 0.1 * Math.random()) : 100;
			var column = 0|(maxColumn * Math.random());

			var maxErase = buffer.charCount();
			var erase = 0|(maxErase * 0.1 * Math.random() * Math.random() * Math.random());

			var textSize = 0|(20 * 10 * Math.random());
			var value = makeText(textSize);

			var init = Math.random() < 0.1;

			return {
				row: row,
				column: column,
				erase: erase,
				value: value,
				init: init,
			};
		}

		function makeText (size) {
			var text = "";
			var limit = chars.length;
			var count = 0|size;
			var index = 0;

			for (index; index < count; index++) text += chars[0|(limit * Math.random())];

			return text;
		}

	})();



	return {
		AVL: {
			Line: AVLTextLine,
			Text: AVLTextNode,
			Node: AVLSequenceNode,
		},
		Content: {
			Data: TextNodeData,
			Provider: TextNodeProvider,
		},
		Buffer: {
			Line: LineBuffer,
			Column: ColumnBuffer,
		},
		_: benchmarks || null,
	};

})();