Split lib.ts into layout.ts and util.ts

1 files changed, 778 insertions, 0 deletions

diff --git a/src/layout.ts b/src/layout.ts
new file mode 100644
index 0000000..711f20a
--- /dev/null
+++ b/src/layout.ts
@@ -0,0 +1,778 @@
+/*
+ * Contains classes used for representing tile-based layouts of tree-of-life data.
+ *
+ * Generally, given a TolNode tree T,initLayoutTree() produces a tree structure representing a subtree of T,
+ * which is passed to tryLayout(), which alters data fields to represent a tile-based layout.
+ * The tree structure consists of LayoutNode objects, each of which holds placement info for a linked TolNode.
+ */
+
+import {TolNode} from './tol';
+import {range, arraySum, limitVals, updateAscSeq} from './util';
+
+// Represents a node/tree, and holds layout data for a TolNode node/tree
+export class LayoutNode {
+	tolNode: TolNode;
+	children: LayoutNode[];
+	parent: LayoutNode | null;
+	// Used for rendering a corresponding tile
+	pos: [number, number];
+	dims: [number, number];
+	showHeader: boolean;
+	sepSweptArea: SepSweptArea | null;
+	hidden: boolean;
+	hasFocus: boolean;
+	collapseFailFlag: boolean; // Used to trigger failure animations
+	expandFailFlag: boolean; // Used to trigger failure animations
+	// Used for layout heuristics and info display
+	dCount: number; // Number of descendant leaf nodes
+	depth: number; // Number of ancestor nodes
+	empSpc: number; // Amount of unused space (in pixels)
+	// Creates object with given fields ('parent' are 'depth' are generally initialised later, 'dCount' is computed)
+	constructor(tolNode: TolNode, children: LayoutNode[]){
+		this.tolNode = tolNode;
+		this.children = children;
+		this.parent = null;
+		this.pos = [0,0];
+		this.dims = [0,0];
+		this.showHeader = false;
+		this.sepSweptArea = null;
+		this.hidden = false;
+		this.hasFocus = false;
+		this.collapseFailFlag = false;
+		this.expandFailFlag = false;
+		this.dCount = children.length == 0 ? 1 : arraySum(children.map(n => n.dCount));
+		this.depth = 0;
+		this.empSpc = 0;
+	}
+	// Creates new node tree with the same structure (fields like 'pos' are set to defaults)
+	// 'chg' is usable to apply a change to the resultant tree
+	cloneNodeTree(chg?: LayoutTreeChg){
+		let newNode: LayoutNode;
+		if (chg != null && this == chg.node){
+			switch (chg.type){
+				case 'expand':
+					let children = this.tolNode.children.map((n: TolNode) => new LayoutNode(n, []));
+					newNode = new LayoutNode(this.tolNode, children);
+					newNode.children.forEach(n => {
+						n.parent = newNode;
+						n.depth = this.depth + 1;
+					});
+					break;
+				case 'collapse':
+					newNode = new LayoutNode(this.tolNode, []);
+					break;
+			}
+		} else {
+			let children = this.children.map(n => n.cloneNodeTree(chg));
+			newNode = new LayoutNode(this.tolNode, children);
+			children.forEach(n => {n.parent = newNode});
+		}
+		newNode.depth = this.depth;
+		return newNode;
+	}
+	// Copies render-relevant data to a given LayoutNode tree
+	// If a target node has more/less children, removes/gives own children
+	copyTreeForRender(target: LayoutNode, map?: LayoutMap): void {
+		target.pos = this.pos;
+		target.dims = this.dims;
+		target.showHeader = this.showHeader;
+		target.sepSweptArea = this.sepSweptArea;
+		target.dCount = this.dCount; // Copied for structural-consistency
+		target.empSpc = this.empSpc; // Currently redundant, but maintains data-consistency
+		// Handle children
+		if (this.children.length == target.children.length){
+			this.children.forEach((n,i) => n.copyTreeForRender(target.children[i], map));
+		} else if (this.children.length < target.children.length){
+			if (map != null){
+				target.children.forEach(child => removeFromLayoutMap(child, map));
+			}
+			target.children = [];
+		} else {
+			target.children = this.children;
+			target.children.forEach(n => {n.parent = target});
+			if (map != null){
+				target.children.forEach(child => {addToLayoutMap(child, map)});
+			}
+		}
+	}
+	// Assigns render-relevant data to this single node
+	assignLayoutData(pos=[0,0] as [number,number], dims=[0,0] as [number,number],
+		{showHeader=false, sepSweptArea=null as SepSweptArea|null, empSpc=0} = {}){
+		this.pos = [...pos];
+		this.dims = [...dims];
+		this.showHeader = showHeader;
+		this.sepSweptArea = sepSweptArea;
+		this.empSpc = empSpc;
+	}
+	// Used to update a LayoutNode tree's dCount fields after adding/removing a node's children
+	static updateDCounts(node: LayoutNode | null, diff: number): void {
+		while (node != null){
+			node.dCount += diff;
+			node = node.parent;
+		}
+	}
+	// Used to hide/show parent nodes upon expand-to-view
+	static hideUpward(node: LayoutNode){
+		if (node.parent != null){
+			node.parent.hidden = true;
+			node.parent.children.filter(n => n != node).forEach(n => LayoutNode.hideDownward(n));
+			LayoutNode.hideUpward(node.parent);
+		}
+	}
+	static hideDownward(node: LayoutNode){
+		node.hidden = true;
+		node.children.forEach(n => LayoutNode.hideDownward(n));
+	}
+	static showDownward(node: LayoutNode){
+		if (node.hidden){
+			node.hidden = false;
+			node.children.forEach(n => LayoutNode.showDownward(n));
+		}
+	}
+}
+// Contains settings that affect how layout is done
+export type LayoutOptions = {
+	tileSpacing: number; // Spacing between tiles, in pixels (ignoring borders)
+	headerSz: number;
+	minTileSz: number; // Minimum size of a tile edge, in pixels (ignoring borders)
+	maxTileSz: number;
+	layoutType: 'sqr' | 'rect' | 'sweep'; // The LayoutFn function to use
+	rectMode: 'horz' | 'vert' | 'linear' | 'auto' | 'auto first-row';
+		// Layout in 1 row, 1 column, 1 row or column, or multiple rows (with/without first-row-heuristic)
+	sweepMode: 'left' | 'top' | 'shorter' | 'auto'; // Sweep to left, top, shorter-side, or to minimise empty space
+	sweptNodesPrio: 'linear' | 'sqrt' | 'pow-2/3'; // Specifies allocation of space to swept-vs-remaining nodes
+	sweepingToParent: boolean; // Allow swept nodes to occupy empty space in a parent's swept-leaves area
+};
+export type LayoutTreeChg = {
+	type: 'expand' | 'collapse';
+	node: LayoutNode;
+}
+// Used with layout option 'sweepingToParent', and represents, for a LayoutNode, a parent area to place leaf nodes in
+export class SepSweptArea {
+	pos: [number, number];
+	dims: [number, number];
+	sweptLeft: boolean; // True if the parent's leaves were swept left
+	constructor(pos: [number, number], dims: [number, number], sweptLeft: boolean){
+		this.pos = pos;
+		this.dims = dims;
+		this.sweptLeft = sweptLeft;
+	}
+	clone(): SepSweptArea {
+		return new SepSweptArea([...this.pos], [...this.dims], this.sweptLeft);
+	}
+}
+//
+export type LayoutMap = Map<string, LayoutNode>;
+
+// Creates a LayoutNode representing a TolNode tree, up to a given depth (0 means just the root)
+export function initLayoutTree(tol: TolNode, depth: number): LayoutNode {
+	function initHelper(tolNode: TolNode, depthLeft: number, atDepth: number = 0): LayoutNode {
+		if (depthLeft == 0){
+			let node = new LayoutNode(tolNode, []);
+			node.depth = atDepth;
+			return node;
+		} else {
+			let children = tolNode.children.map((n: TolNode) => initHelper(n, depthLeft-1, atDepth+1));
+			let node = new LayoutNode(tolNode, children);
+			children.forEach(n => n.parent = node);
+			return node;
+		}
+	}
+	return initHelper(tol, depth);
+}
+export function initLayoutMap(node: LayoutNode): LayoutMap {
+	function helper(node: LayoutNode, map: LayoutMap){
+		map.set(node.tolNode.name, node);
+		node.children.forEach(n => helper(n, map));
+	}
+	let map = new Map();
+	helper(node, map);
+	return map;
+}
+function removeFromLayoutMap(node: LayoutNode, map: LayoutMap){
+	map.delete(node.tolNode.name);
+	node.children.forEach(n => removeFromLayoutMap(n, map));
+}
+function addToLayoutMap(node: LayoutNode, map: LayoutMap){
+	map.set(node.tolNode.name, node);
+	node.children.forEach(n => addToLayoutMap(n, map));
+}
+// Attempts layout on a LayoutNode's corresponding TolNode tree, for an area with given xy-position and width+height
+// 'allowCollapse' allows the layout algorithm to collapse nodes to avoid layout failure
+// 'chg' allows for performing layout after expanding/collapsing a node
+export function tryLayout(layoutTree: LayoutNode, layoutMap: LayoutMap, pos: [number,number], dims: [number,number],
+	options: LayoutOptions, allowCollapse: boolean = false, chg?: LayoutTreeChg){
+	// Create a new LayoutNode tree, in case of layout failure
+	let tempTree = layoutTree.cloneNodeTree(chg);
+	let success: boolean;
+	switch (options.layoutType){
+		case 'sqr':   success =   sqrLayout(tempTree, pos, dims, true, allowCollapse, options); break;
+		case 'rect':  success =  rectLayout(tempTree, pos, dims, true, allowCollapse, options); break;
+		case 'sweep': success = sweepLayout(tempTree, pos, dims, true, allowCollapse, options); break;
+	}
+	if (success){
+		// Center in layout area
+		tempTree.pos[0] += (dims[0] - tempTree.dims[0]) / 2;
+		tempTree.pos[1] += (dims[1] - tempTree.dims[1]) / 2;
+		// Apply to active LayoutNode tree
+		tempTree.copyTreeForRender(layoutTree, layoutMap);
+	}
+	return success;
+}
+
+// Type for functions called by tryLayout() to perform layout
+// Given a LayoutNode tree, determines and records a new layout by setting fields of nodes in the tree
+// Returns a boolean indicating success
+type LayoutFn = (
+	node: LayoutNode,
+	pos: [number, number],
+	dims: [number, number],
+	showHeader: boolean,
+	allowCollapse: boolean,
+	opts: LayoutOptions,
+	ownOpts?: any,
+) => boolean;
+// Lays out node as one square, ignoring child nodes (used for base cases)
+let oneSqrLayout: LayoutFn = function (node, pos, dims, showHeader, allowCollapse, opts){
+	let tileSz = Math.min(dims[0], dims[1], opts.maxTileSz);
+	if (tileSz < opts.minTileSz){
+		return false;
+	}
+	node.assignLayoutData(pos, [tileSz,tileSz], {showHeader, empSpc: dims[0]*dims[1] - tileSz**2});
+	return true;
+}
+// Lays out nodes as squares within a grid with intervening+surrounding spacing
+let sqrLayout: LayoutFn = function (node, pos, dims, showHeader, allowCollapse, opts){
+	if (node.children.length == 0){
+		return oneSqrLayout(node, pos, dims, false, false, opts);
+	}
+	// Consider area excluding header and top/left spacing
+	let headerSz = showHeader ? opts.headerSz : 0;
+	let newPos = [opts.tileSpacing, opts.tileSpacing + headerSz];
+	let newDims = [dims[0] - opts.tileSpacing, dims[1] - opts.tileSpacing - headerSz];
+	if (newDims[0] * newDims[1] <= 0){
+		return false;
+	}
+	// Find number of rows/columns with least empty space
+	let numChildren = node.children.length;
+	let areaAR = newDims[0] / newDims[1]; // Aspect ratio
+	let lowestEmpSpc = Number.POSITIVE_INFINITY, usedNumCols = 0, usedNumRows = 0, usedTileSz = 0;
+	for (let numCols = 1; numCols <= numChildren; numCols++){
+		let numRows = Math.ceil(numChildren / numCols);
+		let gridAR = numCols / numRows;
+		let usedFrac = // Fraction of area occupied by maximally-fitting grid
+			areaAR > gridAR ? gridAR / areaAR : areaAR / gridAR;
+		// Get tile edge length
+		let tileSz = (areaAR > gridAR ? newDims[1] / numRows : newDims[0] / numCols) - opts.tileSpacing;
+		if (tileSz < opts.minTileSz){
+			continue;
+		} else if (tileSz > opts.maxTileSz){
+			tileSz = opts.maxTileSz;
+		}
+		// Get empty space
+		let empSpc = (1 - usedFrac) * (newDims[0] * newDims[1]) + // Area outside grid plus ...
+			(numCols * numRows - numChildren) * (tileSz - opts.tileSpacing)**2; // empty cells within grid
+		// Compare with best-so-far
+		if (empSpc < lowestEmpSpc){
+			lowestEmpSpc = empSpc;
+			usedNumCols = numCols;
+			usedNumRows = numRows;
+			usedTileSz = tileSz;
+		}
+	}
+	if (lowestEmpSpc == Number.POSITIVE_INFINITY){
+		if (allowCollapse){
+			node.children = [];
+			LayoutNode.updateDCounts(node, 1 - node.dCount);
+			return oneSqrLayout(node, pos, dims, false, false, opts);
+		}
+		return false;
+	}
+	// Layout children
+	for (let i = 0; i < numChildren; i++){
+		let child = node.children[i];
+		let childX = newPos[0] + (i % usedNumCols) * (usedTileSz + opts.tileSpacing);
+		let childY = newPos[1] + Math.floor(i / usedNumCols) * (usedTileSz + opts.tileSpacing);
+		let success: boolean;
+		if (child.children.length == 0){
+			success = oneSqrLayout(child, [childX,childY], [usedTileSz,usedTileSz], false, false, opts);
+		} else {
+			success = sqrLayout(child, [childX,childY], [usedTileSz,usedTileSz], true, allowCollapse, opts);
+		}
+		if (!success){
+			if (allowCollapse){
+				node.children = [];
+				LayoutNode.updateDCounts(node, 1 - node.dCount);
+				return oneSqrLayout(node, pos, dims, false, false, opts);
+			}
+			return false;
+		}
+	}
+	// Create layout
+	let usedDims: [number, number] = [
+		usedNumCols * (usedTileSz + opts.tileSpacing) + opts.tileSpacing,
+		usedNumRows * (usedTileSz + opts.tileSpacing) + opts.tileSpacing + headerSz,
+	];
+	let empSpc = // Empty space within usedDims area
+		(usedNumCols * usedNumRows - numChildren) * (usedTileSz - opts.tileSpacing)**2 +
+		arraySum(node.children.map(child => child.empSpc));
+	node.assignLayoutData(pos, usedDims, {showHeader, empSpc});
+	return true;
+}
+// Lays out nodes as rows of rectangles, deferring to sqrLayout() or oneSqrLayout() for simpler cases
+//'subLayoutFn' allows other LayoutFns to use this layout, but transfer control back to themselves on recursion
+let rectLayout: LayoutFn = function (node, pos, dims, showHeader, allowCollapse, opts,
+	ownOpts?: {subLayoutFn?: LayoutFn}){
+	// Check for simpler cases
+	if (node.children.length == 0){
+		return oneSqrLayout(node, pos, dims, false, false, opts);
+	} else if (node.children.every(n => n.children.length == 0)){
+		return sqrLayout(node, pos, dims, showHeader, allowCollapse, opts);
+	}
+	// Consider area excluding header and top/left spacing
+	let headerSz = showHeader ? opts.headerSz : 0;
+	let newPos = [opts.tileSpacing, opts.tileSpacing + headerSz];
+	let newDims = [dims[0] - opts.tileSpacing, dims[1] - opts.tileSpacing - headerSz];
+	if (newDims[0] * newDims[1] <= 0){
+		return false;
+	}
+	// Try finding arrangement with low empty space
+	// Done by searching possible rows groupings, allocating within rows using dCounts, and trimming empty space
+	let numChildren = node.children.length;
+	let rowBrks: number[] = []; // Will hold indices for nodes at which each row starts
+	let lowestEmpSpc = Number.POSITIVE_INFINITY;
+	let usedTree: LayoutNode | null = null, usedEmpRight = 0, usedEmpBottom = 0;
+	const minCellDims = [ // Can situationally assume non-leaf children
+		opts.minTileSz + opts.tileSpacing +
+			(opts.layoutType == 'sweep' ? opts.tileSpacing*2 : 0),
+		opts.minTileSz + opts.tileSpacing +
+			(opts.layoutType == 'sweep' ? opts.tileSpacing*2 + opts.headerSz : 0)
+	];
+	rowBrksLoop:
+	while (true){
+		// Update rowBrks or exit loop
+		switch (opts.rectMode){
+			case 'horz':
+				if (rowBrks.length == 0){
+					rowBrks = [0];
+				} else {
+					break rowBrksLoop;
+				}
+				break;
+			case 'vert':
+				if (rowBrks.length == 0){
+					rowBrks = range(numChildren);
+				} else {
+					break rowBrksLoop;
+				}
+				break;
+			case 'linear':
+				if (rowBrks.length == 0){
+					rowBrks = [0];
+				} else if (rowBrks.length == numChildren){
+					rowBrks = range(numChildren);
+				} else {
+					break rowBrksLoop;
+				}
+				break;
+			case 'auto':
+				if (rowBrks.length == 0){
+					rowBrks = [0];
+				} else {
+					let updated = updateAscSeq(rowBrks, numChildren);
+					if (!updated){
+						break rowBrksLoop;
+					}
+				}
+				break;
+			case 'auto first-row': // Like auto, but only iterates over first-rows, determining the rest with dCounts
+				if (rowBrks.length == 0){
+					rowBrks = [0];
+				} else {
+					// Get next possible first row
+					let idxFirstRowLastEl = (rowBrks.length == 1 ? numChildren : rowBrks[1]) - 1;
+					if (idxFirstRowLastEl == 0){
+						break rowBrksLoop;
+					}
+					rowBrks = [0];
+					rowBrks.push(idxFirstRowLastEl);
+					// Allocate remaining rows
+					let firstRowDCount = arraySum(range(rowBrks[1]).map(idx => node.children[idx].dCount));
+					let dCountTotal = node.children[idxFirstRowLastEl].dCount;
+					let nextRowIdx = idxFirstRowLastEl + 1;
+					while (nextRowIdx < numChildren){ // Over potential next row breaks
+						let nextDCountTotal = dCountTotal + node.children[nextRowIdx].dCount;
+						if (nextDCountTotal <= firstRowDCount){ // If acceptable within current row
+							dCountTotal = nextDCountTotal;
+						} else {
+							rowBrks.push(nextRowIdx);
+							dCountTotal = node.children[nextRowIdx].dCount;
+						}
+						nextRowIdx++;
+					}
+				}
+				break;
+		}
+		// Create array-of-arrays representing each rows' cells' dCounts
+		let rowsOfCnts: number[][] = new Array(rowBrks.length);
+		for (let rowIdx = 0; rowIdx < rowBrks.length; rowIdx++){
+			let numNodes = (rowIdx < rowBrks.length - 1) ?
+				rowBrks[rowIdx + 1] - rowBrks[rowIdx] :
+				numChildren - rowBrks[rowIdx];
+			let rowNodeIdxs = range(numNodes).map(i => i + rowBrks![rowIdx]);
+			rowsOfCnts[rowIdx] = rowNodeIdxs.map(idx => node.children[idx].dCount);
+		}
+		// Get initial cell dims
+		let cellWs: number[][] = new Array(rowsOfCnts.length);
+		for (let rowIdx = 0; rowIdx < rowsOfCnts.length; rowIdx++){
+			let rowCount = arraySum(rowsOfCnts[rowIdx]);
+			cellWs[rowIdx] = range(rowsOfCnts[rowIdx].length).map(
+				colIdx => rowsOfCnts[rowIdx][colIdx] / rowCount * newDims[0]);
+		}
+		let totalDCount = arraySum(node.children.map(n => n.dCount));
+		let cellHs = rowsOfCnts.map(rowOfCnts => arraySum(rowOfCnts) / totalDCount * newDims[1]);
+		// Check min-tile-size, attempting to reallocate space if needed
+		for (let rowIdx = 0; rowIdx < rowsOfCnts.length; rowIdx++){
+			let newWs = limitVals(cellWs[rowIdx], minCellDims[0], Number.POSITIVE_INFINITY);
+			if (newWs == null){
+				continue rowBrksLoop;
+			}
+			cellWs[rowIdx] = newWs;
+		}
+		cellHs = limitVals(cellHs, minCellDims[1], Number.POSITIVE_INFINITY)!;
+		if (cellHs == null){
+			continue rowBrksLoop;
+		}
+		// Get cell xy-coordinates
+		let cellXs: number[][] = new Array(rowsOfCnts.length);
+		for (let rowIdx = 0; rowIdx < rowBrks.length; rowIdx++){
+			cellXs[rowIdx] = [0];
+			for (let colIdx = 1; colIdx < rowsOfCnts[rowIdx].length; colIdx++){
+				cellXs[rowIdx].push(cellXs[rowIdx][colIdx - 1] + cellWs[rowIdx][colIdx - 1]);
+			}
+		}
+		let cellYs: number[] = new Array(rowsOfCnts.length).fill(0);
+		for (let rowIdx = 1; rowIdx < rowBrks.length; rowIdx++){
+			cellYs[rowIdx] = cellYs[rowIdx - 1] + cellHs[rowIdx - 1];
+		}
+		// Determine child layouts, resizing cells to reduce empty space
+		let tempTree: LayoutNode = node.cloneNodeTree();
+		let empRight = Number.POSITIVE_INFINITY, empBottom = 0;
+		for (let rowIdx = 0; rowIdx < rowBrks.length; rowIdx++){
+			for (let colIdx = 0; colIdx < rowsOfCnts[rowIdx].length; colIdx++){
+				let nodeIdx = rowBrks[rowIdx] + colIdx;
+				let child: LayoutNode = tempTree.children[nodeIdx];
+				let childPos: [number, number] = [newPos[0] + cellXs[rowIdx][colIdx], newPos[1] + cellYs[rowIdx]];
+				let childDims: [number, number] = [
+					cellWs[rowIdx][colIdx] - opts.tileSpacing,
+					cellHs[rowIdx] - opts.tileSpacing
+				];
+				let success: boolean;
+				if (child.children.length == 0){
+					success = oneSqrLayout(child, childPos, childDims, false, false, opts);
+				} else if (child.children.every(n => n.children.length == 0)){
+					success = sqrLayout(child, childPos, childDims, true, allowCollapse, opts);
+				}  else {
+					let layoutFn = (ownOpts && ownOpts.subLayoutFn) || rectLayout;
+					success = layoutFn(child, childPos, childDims, true, allowCollapse, opts);
+				}
+				if (!success){
+					continue rowBrksLoop;
+				}
+				// Remove horizontal empty space by trimming cell and moving/expanding any next cell
+				let horzEmp = childDims[0] - child.dims[0];
+				cellWs[rowIdx][colIdx] -= horzEmp;
+				if (colIdx < rowsOfCnts[rowIdx].length - 1){
+					cellXs[rowIdx][colIdx + 1] -= horzEmp;
+					cellWs[rowIdx][colIdx + 1] += horzEmp;
+				} else {
+					empRight = Math.min(empRight, horzEmp);
+				}
+			}
+			// Remove vertical empty space by trimming row and moving/expanding any next row
+			let childUsedHs = range(rowsOfCnts[rowIdx].length).map(
+				colIdx => tempTree.children[rowBrks[rowIdx] + colIdx].dims[1]);
+			let vertEmp = cellHs[rowIdx] - opts.tileSpacing - Math.max(...childUsedHs);
+			cellHs[rowIdx] -= vertEmp;
+			if (rowIdx < rowBrks.length - 1){
+				cellYs[rowIdx + 1] -= vertEmp;
+				cellHs[rowIdx + 1] += vertEmp;
+			} else {
+				empBottom = vertEmp;
+			}
+		}
+		// Get empty space
+		let usedSpc = arraySum(tempTree.children.map(
+			child => (child.dims[0] + opts.tileSpacing) * (child.dims[1] + opts.tileSpacing) - child.empSpc));
+		let empSpc = newDims[0] * newDims[1] - usedSpc;
+		// Check with best-so-far
+		if (empSpc < lowestEmpSpc){
+			lowestEmpSpc = empSpc;
+			usedTree = tempTree;
+			usedEmpRight = empRight;
+			usedEmpBottom = empBottom;
+		}
+	}
+	if (usedTree == null){ // If no found layout
+		if (allowCollapse){
+			node.children = [];
+			LayoutNode.updateDCounts(node, 1 - node.dCount);
+			return oneSqrLayout(node, pos, dims, false, false, opts);
+		}
+		return false;
+	}
+	// Create layout
+	usedTree.copyTreeForRender(node);
+	let usedDims: [number, number] = [dims[0] - usedEmpRight, dims[1] - usedEmpBottom];
+	node.assignLayoutData(pos, usedDims, {showHeader, empSpc: lowestEmpSpc});
+	return true;
+}
+// Lays out nodes by pushing leaves to one side, and using rectLayout() for the non-leaves
+// With layout option 'sweepingToParent', leaves from child nodes may occupy a parent's leaf-section
+//'sepArea' represents a usable leaf-section area from a direct parent,
+	//and is altered to represent the area used, which the parent can use for reducing empty space
+let sweepLayout: LayoutFn = function (node, pos, dims, showHeader, allowCollapse, opts,
+	ownOpts?: {sepArea?: SepSweptArea}){
+	// Separate leaf and non-leaf nodes
+	let leaves: LayoutNode[] = [], nonLeaves: LayoutNode[] = [];
+	node.children.forEach(child => (child.children.length == 0 ? leaves : nonLeaves).push(child));
+	// Check for simpler cases
+	if (node.children.length == 0){
+		return oneSqrLayout(node, pos, dims, false, false, opts);
+	} else if (nonLeaves.length == 0){
+		return sqrLayout(node, pos, dims, showHeader, allowCollapse, opts);
+	} else if (leaves.length == 0){
+		return rectLayout(node, pos, dims, showHeader, allowCollapse, opts, {subLayoutFn: sweepLayout});
+	}
+	// Some variables
+	let headerSz = showHeader ? opts.headerSz : 0;
+	let leavesLyt: LayoutNode | null = null, nonLeavesLyt: LayoutNode | null = null, sweptLeft = false;
+	let sepArea: SepSweptArea | null = null, sepAreaUsed = false; // Represents leaf-section area provided for a child
+	// Try using parent-provided area
+	let parentArea = (opts.sweepingToParent && ownOpts) ? ownOpts.sepArea : null; // Represents area provided by parent
+	let usingParentArea = false;
+	if (parentArea != null){
+		// Attempt leaves layout
+		sweptLeft = parentArea.sweptLeft;
+		leavesLyt = new LayoutNode(new TolNode('SWEEP_' + node.tolNode.name), leaves);
+			// Not updating child nodes to point to tempTree as a parent seems acceptable here
+		let leavesSuccess = sqrLayout(leavesLyt, [0,0], parentArea.dims, !sweptLeft, false, opts);
+		if (leavesSuccess){
+			// Move leaves to parent area
+			leavesLyt.children.map(lyt => {
+				lyt.pos[0] += parentArea!.pos[0];
+				lyt.pos[1] += parentArea!.pos[1];
+			});
+			// Attempt non-leaves layout
+			let newDims: [number,number] = [dims[0], dims[1] - (sweptLeft ? headerSz : 0)];
+			nonLeavesLyt = new LayoutNode(new TolNode('SWEEP_REM_' + node.tolNode.name), nonLeaves);
+			let tempTree: LayoutNode = nonLeavesLyt.cloneNodeTree();
+			let sepAreaLen = 0;
+			let nonLeavesSuccess: boolean;
+			if (nonLeaves.length > 1){
+				nonLeavesSuccess = rectLayout(tempTree, [0,0], newDims, false, false, opts, {subLayoutFn:
+					((n,p,d,h,a,o) => sweepLayout(n,p,d,h,allowCollapse,o,{sepArea:sepArea})) as LayoutFn});
+			} else {
+				// Get leftover area usable by non-leaf child
+				if (sweptLeft){
+					sepArea = new SepSweptArea(
+						[parentArea.pos[0], parentArea.pos[1] + leavesLyt.dims[1] - (opts.tileSpacing + headerSz)],
+							// The y-coord subtraction is to make the position relative to a direct non-leaf child
+						[parentArea.dims[0], parentArea.dims[1] - leavesLyt.dims[1] - opts.tileSpacing*2],
+						sweptLeft
+					);
+					sepAreaLen = sepArea.dims[1];
+				} else {
+					sepArea = new SepSweptArea(
+						[parentArea.pos[0] + leavesLyt.dims[0] - opts.tileSpacing, parentArea.pos[1] + headerSz],
+						[parentArea.dims[0] - leavesLyt.dims[0] - opts.tileSpacing*2, parentArea.dims[1] - headerSz],
+						sweptLeft
+					);
+					sepAreaLen = sepArea.dims[0];
+				}
+				// Attempt layout
+				nonLeavesSuccess = rectLayout(tempTree, [0,0], newDims, false, false, opts, {subLayoutFn:
+					((n,p,d,h,a,o) => sweepLayout(n,p,d,h,allowCollapse,o,{sepArea:sepArea})) as LayoutFn});
+			}
+			if (nonLeavesSuccess){
+				usingParentArea = true;
+				tempTree.copyTreeForRender(nonLeavesLyt);
+				// Adjust child positions
+				if (sweptLeft){
+					nonLeavesLyt.children.forEach(lyt => {lyt.pos[1] += headerSz});
+				}
+				// Update parentArea to represent space used
+				if (sweptLeft){
+					parentArea.dims[1] = leavesLyt.dims[1];
+					if (sepArea != null && sepAreaLen > sepArea.dims[1]){ // If space used by child
+						parentArea.dims[1] += sepArea.dims[1] + opts.tileSpacing;
+					}
+				} else {
+					parentArea.dims[0] = leavesLyt.dims[0];
+					if (sepArea != null && sepAreaLen > sepArea.dims[0]){
+						parentArea.dims[0] += sepArea.dims[0] + opts.tileSpacing;
+					}
+				}
+				// Align parentArea size with non-leaves area
+				if (sweptLeft){
+					if (parentArea.pos[1] + parentArea.dims[1] > nonLeavesLyt.dims[1] + headerSz){
+						nonLeavesLyt.dims[1] = parentArea.pos[1] + parentArea.dims[1] - headerSz;
+					} else {
+						parentArea.dims[1] = nonLeavesLyt.dims[1] + headerSz - parentArea.pos[1];
+					}
+				} else {
+					if (parentArea.pos[0] + parentArea.dims[0] > nonLeavesLyt.dims[0]){
+						nonLeavesLyt.dims[0] = parentArea.pos[0] + parentArea.dims[0];
+					} else {
+						parentArea.dims[0] = nonLeavesLyt.dims[0] - parentArea.pos[0];
+					}
+				}
+				// Adjust area to avoid overlap with non-leaves
+				if (sweptLeft){
+					parentArea.dims[0] -= opts.tileSpacing;
+				} else {
+					parentArea.dims[1] -= opts.tileSpacing;
+				}
+			}
+		}
+	}
+	// Try using own area
+	if (!usingParentArea){
+		// Choose proportion of area to use for leaves
+		let ratio: number; // area-for-leaves / area-for-non-leaves
+		let nonLeavesTiles = arraySum(nonLeaves.map(n => n.dCount));
+		switch (opts.sweptNodesPrio){
+			case 'linear':
+				ratio = leaves.length / (leaves.length + nonLeavesTiles);
+				break;
+			case 'sqrt':
+				ratio = Math.sqrt(leaves.length) / (Math.sqrt(leaves.length) + Math.sqrt(nonLeavesTiles));
+				break;
+			case 'pow-2/3':
+				ratio = Math.pow(leaves.length, 2/3) /
+					(Math.pow(leaves.length, 2/3) + Math.pow(nonLeavesTiles, 2/3));
+				break;
+		}
+		// Attempt leaves layout
+		let newPos = [0, headerSz];
+		let newDims: [number,number] = [dims[0], dims[1] - headerSz];
+		leavesLyt = new LayoutNode(new TolNode('SWEEP_' + node.tolNode.name), leaves);
+		let minSz = opts.minTileSz + opts.tileSpacing*2;
+		let sweptW = Math.max(minSz, newDims[0] * ratio), sweptH = Math.max(minSz, newDims[1] * ratio);
+		let leavesSuccess: boolean;
+		switch (opts.sweepMode){
+			case 'left':
+				leavesSuccess = sqrLayout(leavesLyt, [0,0], [sweptW, newDims[1]], false, false, opts);
+				sweptLeft = true;
+				break;
+			case 'top':
+				leavesSuccess = sqrLayout(leavesLyt, [0,0], [newDims[0], sweptH], false, false, opts);
+				sweptLeft = false;
+				break;
+			case 'shorter':
+				let documentAR = document.documentElement.clientWidth / document.documentElement.clientHeight;
+				if (documentAR >= 1){
+					leavesSuccess = sqrLayout(leavesLyt, [0,0], [sweptW, newDims[1]], false, false, opts);
+					sweptLeft = true;
+				} else {
+					leavesSuccess = sqrLayout(leavesLyt, [0,0], [newDims[0], sweptH], false, false, opts);
+					sweptLeft = false;
+				}
+				break;
+			case 'auto':
+				// Attempt left-sweep, then top-sweep on a copy, and copy over if better
+				leavesSuccess = sqrLayout(leavesLyt, [0,0], [sweptW, newDims[1]], false, false, opts);
+				sweptLeft = true;
+				let tempTree = leavesLyt.cloneNodeTree();
+				let sweptTopSuccess = sqrLayout(tempTree, [0,0], [newDims[0], sweptH], false, false, opts);;
+				if (sweptTopSuccess && (!leavesSuccess || tempTree.empSpc < leavesLyt.empSpc)){
+					tempTree.copyTreeForRender(leavesLyt);
+					sweptLeft = false;
+					leavesSuccess = true;
+				}
+				break;
+		}
+		if (!leavesSuccess){
+			if (allowCollapse){
+				node.children = [];
+				LayoutNode.updateDCounts(node, 1 - node.dCount);
+				return oneSqrLayout(node, pos, dims, false, false, opts);
+			}
+			return false;
+		}
+		leavesLyt.children.forEach(lyt => {lyt.pos[1] += headerSz});
+		// Attempt non-leaves layout
+		if (sweptLeft){
+			newPos[0] += leavesLyt.dims[0] - opts.tileSpacing;
+			newDims[0] += -leavesLyt.dims[0] + opts.tileSpacing;
+		} else {
+			newPos[1] += leavesLyt.dims[1] - opts.tileSpacing;
+			newDims[1] += -leavesLyt.dims[1] + opts.tileSpacing
+		}
+		nonLeavesLyt = new LayoutNode(new TolNode('SWEEP_REM_' + node.tolNode.name), nonLeaves);
+		let nonLeavesSuccess: boolean;
+		if (nonLeaves.length > 1){
+			nonLeavesSuccess = rectLayout(nonLeavesLyt, [0,0], newDims, false, false, opts, {subLayoutFn:
+				((n,p,d,h,a,o) => sweepLayout(n,p,d,h,allowCollapse,o,{sepArea:sepArea})) as LayoutFn});
+		} else {
+			// Get leftover area usable by non-leaf child
+			let sepAreaLen;
+			if (sweptLeft){
+				sepAreaLen = newDims[1] - leavesLyt.dims[1] - opts.tileSpacing;
+				sepArea = new SepSweptArea(
+					[-leavesLyt.dims[0] + opts.tileSpacing, leavesLyt.dims[1] - opts.tileSpacing], //Relative to child
+					[leavesLyt.dims[0], sepAreaLen],
+					sweptLeft
+				);
+			} else {
+				sepAreaLen = newDims[0] - leavesLyt.dims[0] - opts.tileSpacing;
+				sepArea = new SepSweptArea(
+					[leavesLyt.dims[0] - opts.tileSpacing, -leavesLyt.dims[1] + opts.tileSpacing],
+					[sepAreaLen, leavesLyt.dims[1]],
+					sweptLeft
+				);
+			}
+			// Attempt layout
+			nonLeavesSuccess = rectLayout(nonLeavesLyt, [0,0], newDims, false, false, opts, {subLayoutFn:
+				((n,p,d,h,a,o) => sweepLayout(n,p,d,h,allowCollapse,o,{sepArea:sepArea})) as LayoutFn});
+			if ((sweptLeft && sepAreaLen > sepArea.dims[1]) || (!sweptLeft && sepAreaLen > sepArea.dims[0])){
+				sepAreaUsed = true;
+			}
+		}
+		if (!nonLeavesSuccess){
+			if (allowCollapse){
+				node.children = [];
+				LayoutNode.updateDCounts(node, 1 - node.dCount);
+				return oneSqrLayout(node, pos, dims, false, false, opts);
+			}
+			return false;
+		}
+		nonLeavesLyt.children.forEach(lyt => {
+			lyt.pos[0] += newPos[0];
+			lyt.pos[1] += newPos[1];
+		});
+	}
+	// Combine layouts
+	if (leavesLyt == null || nonLeavesLyt == null){ //hint for typescript
+		return false;
+	}
+	let usedDims: [number, number];
+	if (usingParentArea){
+		usedDims = [nonLeavesLyt.dims[0], nonLeavesLyt.dims[1] + (sweptLeft ? headerSz : 0)];
+	} else {
+		if (sweptLeft){
+			usedDims = [
+				leavesLyt.dims[0] + nonLeavesLyt.dims[0] - opts.tileSpacing,
+				Math.max(leavesLyt.dims[1] + (sepAreaUsed ? sepArea!.dims[1] : 0), nonLeavesLyt.dims[1]) + headerSz
+			];
+		} else {
+			usedDims = [
+				Math.max(leavesLyt.dims[0] + (sepAreaUsed ? sepArea!.dims[0] : 0), nonLeavesLyt.dims[0]),
+				leavesLyt.dims[1] + nonLeavesLyt.dims[1] - opts.tileSpacing + headerSz
+			];
+		}
+	}
+	let empSpc = (!usingParentArea ? leavesLyt.empSpc : 0) + nonLeavesLyt.empSpc;
+	node.assignLayoutData(pos, usedDims, {showHeader, empSpc, sepSweptArea: usingParentArea ? parentArea! : null});
+	return true;
+}