aboutsummaryrefslogtreecommitdiff
path: root/src/layout.js
diff options
context:
space:
mode:
Diffstat (limited to 'src/layout.js')
-rw-r--r--src/layout.js368
1 files changed, 167 insertions, 201 deletions
diff --git a/src/layout.js b/src/layout.js
index b713e29..1fa1f2d 100644
--- a/src/layout.js
+++ b/src/layout.js
@@ -1,45 +1,50 @@
-export {defaultLayout, initTree};
+export {staticSqrLayout, staticRectLayout, sweepToSideLayout};
-const DEFAULT_TILE_SPACING = 5;
-const DEFAULT_HEADER_SZ = 20;
+const TILE_SPACING = 5;
+const HEADER_SZ = 20;
-const staticSqrLayout = { //determines layout for squares in a specified rectangle, with spacing
- TILE_SPACING: DEFAULT_TILE_SPACING,
- HEADER_SZ: DEFAULT_HEADER_SZ,
- genLayout(nodes, x0, y0, w, h, hideHeader){
- //get number-of-columns with highest occupied-fraction of rectangles with aspect-ratio w/h
- //account for tile-spacing?, account for parent-box-border?, cache results?,
- let hOffset = (hideHeader ? 0 : this.HEADER_SZ);
- let availW = w - this.TILE_SPACING, availH = h - hOffset - this.TILE_SPACING;
- let numTiles = nodes.length, ar = availW/availH;
- let numCols, numRows, bestFrac = 0, tileSz, empSpc;
- for (let nc = 1; nc <= numTiles; nc++){
- let nr = Math.ceil(numTiles/nc);
+const staticSqrLayout = { //lays out nodes as squares in a rectangle, with spacing
+ genLayout(node, x, y, w, h, hideHeader){
+ //get number-of-columns with lowest leftover empty space
+ let headerSz = (hideHeader ? 0 : HEADER_SZ);
+ let availW = w - TILE_SPACING, availH = h - headerSz - TILE_SPACING;
+ let numChildren = node.children.length, ar = availW/availH;
+ let lowestEmp = Number.POSITIVE_INFINITY, numCols, numRows, tileSize;
+ for (let nc = 1; nc <= numChildren; nc++){
+ let nr = Math.ceil(numChildren/nc);
let ar2 = nc/nr;
let frac = ar > ar2 ? ar2/ar : ar/ar2;
- if (frac > bestFrac){
- bestFrac = frac;
+ let tileSz = ar > ar2 ? availH/nr-TILE_SPACING : availW/nc-TILE_SPACING;
+ let empSpc = (1-frac)*availW*availH + (nc*nr-numChildren)*(tileSz - TILE_SPACING)**2;
+ if (empSpc < lowestEmp){
+ lowestEmp = empSpc;
numCols = nc;
numRows = nr;
- tileSz = ar > ar2 ? availH/numRows-this.TILE_SPACING : availW/numCols-this.TILE_SPACING;
- empSpc = (1 - frac) * availW * availH;
- empSpc += (nc*nr - numTiles) * tileSz**2;
+ tileSize = tileSz;
+ }
+ }
+ let childLayouts = Array(numChildren).fill();
+ for (let i = 0; i < numChildren; i++){
+ let childX = TILE_SPACING + (i % numCols)*(tileSize + TILE_SPACING);
+ let childY = TILE_SPACING + headerSz + Math.floor(i / numCols)*(tileSize + TILE_SPACING);
+ if (node.children[i].children.length == 0){
+ childLayouts[i] = {
+ x: childX, y: childY, w: tileSize, h: tileSize, headerSz: 0,
+ children: [],
+ contentW: tileSize, contentH: tileSize, empSpc: 0,
+ }
+ } else {
+ childLayouts[i] = this.genLayout(node.children[i], childX, childY, tileSize, tileSize, false);
+ lowestEmp += childLayouts[i].empSpc;
}
}
- //determine layout
return {
- coords: Object.fromEntries(
- nodes.map((el, idx) => [el.tolNode.name, {
- x: x0 + this.TILE_SPACING + (idx % numCols)*(tileSz + this.TILE_SPACING),
- y: y0 + this.TILE_SPACING + hOffset + Math.floor(idx / numCols)*(tileSz + this.TILE_SPACING),
- w: tileSz,
- h: tileSz
- }])
- ),
- contentW: numCols * (tileSz + this.TILE_SPACING) + this.TILE_SPACING,
- contentH: numRows * (tileSz + this.TILE_SPACING) + this.TILE_SPACING + hOffset,
- empSpc: empSpc
- };
+ x: x, y: y, w: w, h: h, headerSz: headerSz,
+ children: childLayouts,
+ contentW: numCols * (tileSize + TILE_SPACING) + TILE_SPACING,
+ contentH: numRows * (tileSize + TILE_SPACING) + TILE_SPACING + headerSz,
+ empSpc: lowestEmp,
+ }
},
initLayoutInfo(tree){
return;
@@ -52,28 +57,47 @@ const staticSqrLayout = { //determines layout for squares in a specified rectang
}
};
const staticRectLayout = {
- TILE_SPACING: DEFAULT_TILE_SPACING,
- HEADER_SZ: DEFAULT_HEADER_SZ,
- genLayout(nodes, x0, y0, w, h, hideHeader){
- if (nodes.every(e => e.children.length == 0)){
- return staticSqrLayout.genLayout(nodes, x0, y0, w, h, hideHeader);
- }
- //if a node has children, find 'best' grid-arrangement
- let hOffset = (hideHeader ? 0 : this.HEADER_SZ);
- let availW = w - this.TILE_SPACING, availH = h - this.TILE_SPACING - hOffset;
- let numChildren = nodes.length;
- let rowBrks = [0]; //holds node indices at which each row starts
- let rowBreaks, lowestEmp = Number.POSITIVE_INFINITY, rowsOfCounts, cellWidths, cellHeights, nodeDims;
+ genLayout(node, x, y, w, h, hideHeader, subLayout = staticRectLayout){
+ if (node.children.every(n => n.children.length == 0))
+ return staticSqrLayout.genLayout(node, x, y, w, h, hideHeader);
+ //find grid-arrangement with lowest leftover empty space
+ let headerSz = (hideHeader ? 0 : HEADER_SZ);
+ let availW = w - TILE_SPACING, availH = h - TILE_SPACING - headerSz;
+ let numChildren = node.children.length;
+ let rowBrks = null; //will holds node indices at which each row starts
+ let lowestEmp = Number.POSITIVE_INFINITY, rowBreaks, rowsOfCounts, childLayouts;
+ rowBrksLoop:
while (true){
+ //update rowBrks or exit loop
+ if (rowBrks == null){
+ rowBrks = [0];
+ } else {
+ let i = rowBrks.length-1;
+ while (true){
+ if (i > 0 && rowBrks[i] < numChildren-1 - (rowBrks.length-1 - i)){
+ rowBrks[i]++;
+ break;
+ } else if (i > 0){
+ i--;
+ } else {
+ if (rowBrks.length < numChildren){
+ rowBrks = Array.from({length: rowBrks.length+1}, (x,i) => i);
+ } else {
+ break rowBrksLoop;
+ }
+ break;
+ }
+ }
+ }
//create list-of-lists representing each row's cells' tileCounts
let rowsOfCnts = Array(rowBrks.length).fill();
for (let r = 0; r < rowBrks.length; r++){
let numNodes = (r == rowBrks.length-1) ? numChildren-rowBrks[r] : rowBrks[r+1]-rowBrks[r];
let rowNodeIdxs = Array.from({length: numNodes}, (x,i) => i+rowBrks[r]);
- rowsOfCnts[r] = rowNodeIdxs.map(idx => nodes[idx].tileCount);
+ rowsOfCnts[r] = rowNodeIdxs.map(idx => node.children[idx].tileCount);
}
//get cell dims
- let totalTileCount = nodes.map(e => e.tileCount).reduce((x,y) => x+y);
+ let totalTileCount = node.children.map(n => n.tileCount).reduce((x,y) => x+y);
let cellHs = rowsOfCnts.map(row => row.reduce((x, y) => x+y) / totalTileCount * availH);
let cellWs = Array(numChildren).fill();
for (let r = 0; r < rowsOfCnts.length; r++){
@@ -82,56 +106,61 @@ const staticRectLayout = {
cellWs[rowBrks[r]+c] = rowsOfCnts[r][c] / rowCount * availW;
}
}
- //get node dims and empty-space
- let emptySpace = 0;
- let nodeDs = Array(numChildren).fill();
+ //get cell x/y coords
+ let cellXs = Array(cellWs.length).fill(0);
for (let r = 0; r < rowBrks.length; r++){
- for (let c = 0; c < rowsOfCnts[r].length; c++){
+ for (let c = 1; c < rowsOfCnts[r].length; c++){
let nodeIdx = rowBrks[r]+c;
- let res = nodes[nodeIdx].layoutRes(cellWs[nodeIdx], cellHs[r]);
- emptySpace += res.empSpc;
- nodeDs[nodeIdx] = [res.contentW, res.contentH];
+ cellXs[nodeIdx] = cellXs[nodeIdx-1] + cellWs[nodeIdx-1];
}
}
- if (emptySpace < lowestEmp){
- lowestEmp = emptySpace;
- rowBreaks = [...rowBrks];
- rowsOfCounts = rowsOfCnts;
- cellWidths = cellWs;
- cellHeights = cellHs;
- nodeDims = nodeDs;
+ let cellYs = Array(cellHs.length).fill(0);
+ for (let r = 1; r < rowBrks.length; r++){
+ cellYs[r] = cellYs[r-1] + cellHs[r-1];
}
- //update rowBrks or exit loop
- let i = rowBrks.length-1, exitLoop = false;
- while (true){
- if (i > 0 && rowBrks[i] < numChildren-1 - (rowBrks.length-1 - i)){
- rowBrks[i]++;
- break;
- } else if (i > 0){
- i--;
- } else {
- if (rowBrks.length < numChildren){
- rowBrks = Array.from({length: rowBrks.length+1}, (x,i) => i);
+ //get child layouts and empty-space
+ let childLyts = Array(numChildren).fill(), empSpc = 0;
+ for (let r = 0; r < rowBrks.length; r++){
+ for (let c = 0; c < rowsOfCnts[r].length; c++){
+ let nodeIdx = rowBrks[r]+c;
+ let child = node.children[nodeIdx];
+ let childX = cellXs[nodeIdx] + TILE_SPACING, childY = cellYs[r] + TILE_SPACING + headerSz,
+ childW = cellWs[nodeIdx] - TILE_SPACING, childH = cellHs[r] - TILE_SPACING;
+ if (child.children.length == 0){
+ let contentSz = Math.min(childW, childH);
+ childLyts[nodeIdx] = {
+ x: childX, y: childY, w: contentSz, h: contentSz, headerSz: 0,
+ children: [],
+ contentW: contentSz, contentH: contentSz, empSpc: childW*childH - contentSz**2,
+ };
+ } else if (child.children.every(n => n.children.length == 0)){
+ childLyts[nodeIdx] = staticSqrLayout.genLayout(child, childX, childY, childW, childH, false);
} else {
- exitLoop = true;
+ childLyts[nodeIdx] = subLayout.genLayout(child, childX, childY, childW, childH, false);
}
- break;
+ empSpc += childLyts[nodeIdx].empSpc;
}
}
- if (exitLoop)
- break;
+ //check with best-so-far
+ if (empSpc < lowestEmp){
+ lowestEmp = empSpc;
+ rowBreaks = [...rowBrks];
+ rowsOfCounts = rowsOfCnts;
+ childLayouts = childLyts;
+ }
}
//for each row, shift empty right-space to rightmost cell
let minEmpHorzTotal = Number.POSITIVE_INFINITY;
for (let r = 0; r < rowBreaks.length; r++){
- let empHorzTotal = 0;
+ let empHorzTotal = 0, leftShiftTotal = 0;
for (let c = 0; c < rowsOfCounts[r].length - 1; c++){
let nodeIdx = rowBreaks[r] + c;
- let empHorz = cellWidths[nodeIdx] - nodeDims[nodeIdx][0];
- cellWidths[nodeIdx] -= empHorz;
+ let empHorz = childLayouts[nodeIdx].w - childLayouts[nodeIdx].contentW;
+ childLayouts[nodeIdx].w -= empHorz;
empHorzTotal += empHorz;
+ childLayouts[nodeIdx+1].x -= empHorzTotal;
}
- cellWidths[rowBreaks[r] + rowsOfCounts[r].length - 1] += empHorzTotal;
+ childLayouts[rowBreaks[r] + rowsOfCounts[r].length - 1].w += empHorzTotal;
if (empHorzTotal < minEmpHorzTotal)
minEmpHorzTotal = empHorzTotal;
}
@@ -139,43 +168,24 @@ const staticRectLayout = {
let empVertTotal = 0;
for (let r = 0; r < rowBreaks.length - 1; r++){
let nodeIdxs = Array.from({length: rowsOfCounts[r].length}, (x,i) => rowBreaks[r] + i);
- let empVerts = nodeIdxs.map(idx => cellHeights[r] - nodeDims[idx][1]);
+ nodeIdxs.forEach(idx => childLayouts[idx].y -= empVertTotal);
+ let empVerts = nodeIdxs.map(idx => childLayouts[idx].h - childLayouts[idx].contentH);
let minEmpVert = Math.min(...empVerts);
- cellHeights[r] -= minEmpVert;
+ nodeIdxs.forEach(idx => childLayouts[idx].h -= minEmpVert);
empVertTotal += minEmpVert;
}
- cellHeights[rowBreaks.length - 1] += empVertTotal;
+ let lastRowIdx = rowBreaks.length-1;
+ let lastNodeIdxs = Array.from({length: rowsOfCounts[lastRowIdx].length}, (x,i) => rowBreaks[lastRowIdx] + i);
+ lastNodeIdxs.forEach(idx => childLayouts[idx].y -= empVertTotal);
+ lastNodeIdxs.map(idx => childLayouts[idx].h += empVertTotal);
//determine layout
- let cellHorzPoints = Array(cellWidths.length).fill(0);
- for (let r = 0; r < rowBreaks.length; r++){
- for (let c = 1; c < rowsOfCounts[r].length; c++){
- let nodeIdx = rowBreaks[r]+c;
- cellHorzPoints[nodeIdx] = cellHorzPoints[nodeIdx-1] + cellWidths[nodeIdx-1];
- }
- }
- let cellVertPoints = Array(cellHeights.length).fill(0);
- for (let r = 1; r < rowBreaks.length; r++){
- cellVertPoints[r] = cellVertPoints[r-1] + cellHeights[r-1];
- }
return {
- coords: Object.fromEntries(
- nodes.map((el, idx) => {
- let cellW = cellWidths[idx];
- let rowIdx = rowBreaks.findIndex((e,i) => i==rowBreaks.length-1 || rowBreaks[i+1] > idx);
- let cellH = cellHeights[rowIdx];
- let cellAR = cellW / cellH;
- return [el.tolNode.name, {
- x: x0 + this.TILE_SPACING + cellHorzPoints[idx],
- y: y0 + this.TILE_SPACING + cellVertPoints[rowIdx] + hOffset,
- w: (el.children.length == 0 ? (cellAR>1 ? cellW * 1/cellAR : cellW) : cellW) - this.TILE_SPACING,
- h: (el.children.length == 0 ? (cellAR>1 ? cellH : cellH * cellAR) : cellH) - this.TILE_SPACING
- }];
- })
- ),
+ x: x, y: y, w: w, h: h, headerSz: headerSz,
+ children: childLayouts,
contentW: w - minEmpHorzTotal,
contentH: h - empVertTotal,
- empSpc: lowestEmp
- };
+ empSpc: lowestEmp,
+ }
},
initLayoutInfo(tree){
if (tree.children.length > 0){
@@ -197,75 +207,65 @@ const staticRectLayout = {
updateLayoutInfo(tree){
if (tree.children.length == 0){
tree.tileCount = 1;
- tree.layoutRes = (w, h) => {
- let ar = w / h;
- let ar2 = 1;
- let frac = ar > ar2 ? ar2/ar : ar/ar2;
- return {
- empSpc: (1 - frac) * w * h,
- contentW: ar > ar2 ? frac * w : w,
- contentH: ar > ar2 ? h : frac * h
- };
- };
} else {
tree.tileCount = tree.children.map(e => e.tileCount).reduce((x,y) => x+y);
- if (tree.children.every(e => e.children.length == 0)){
- tree.layoutRes = (w, h) => {
- let layout = staticSqrLayout.genLayout(tree.children, 0, 0, w, h, tree.hideHeader);
- return {empSpc: layout.empSpc, contentW: layout.contentW, contentH: layout.contentH};
- };
- } else {
- tree.layoutRes = (w, h) => {
- let layout = staticRectLayout.genLayout(tree.children, 0, 0, w, h, tree.hideHeader);
- return {empSpc: layout.empSpc, contentW: layout.contentW, contentH: layout.contentH};
- };
- }
}
}
};
const sweepToSideLayout = {
- TILE_SPACING: DEFAULT_TILE_SPACING,
- HEADER_SZ: DEFAULT_HEADER_SZ,
- genLayout(nodes, x0, y0, w, h, hideHeader){
+ genLayout(node, x, y, w, h, hideHeader){
//separate leaf and non-leaf nodes
let leaves = [], nonLeaves = [];
- nodes.forEach(e => (e.children.length == 0 ? leaves : nonLeaves).push(e));
+ node.children.forEach(n => (n.children.length == 0 ? leaves : nonLeaves).push(n));
//determine layout
+ let tempTree;
if (nonLeaves.length == 0){ //if all leaves, use squares-layout
- return staticSqrLayout.genLayout(nodes, x0, y0, w, h, hideHeader);
- } else { //if some non-leaves, use rect-layout
- if (leaves.length == 0){
- return staticRectLayout.genLayout(nonLeaves, x0, y0, w, h, hideHeader);
+ return staticSqrLayout.genLayout(node, x, y, w, h, hideHeader);
+ } else if (leaves.length == 0){
+ tempTree = {tolNode: null, children: nonLeaves};
+ return staticRectLayout.genLayout(tempTree, x, y, w, h, hideHeader);
+ } else {
+ let ratio = leaves.length / (leaves.length + nonLeaves.map(e => e.tileCount).reduce((x,y) => x+y));
+ let headerSz = (hideHeader ? 0 : HEADER_SZ);
+ //get swept-area layout
+ let area = {x: x, y: y+headerSz, w: w, h: h-headerSz};
+ tempTree = {tolNode: null, children: leaves};
+ let leftLayout = staticSqrLayout.genLayout(tempTree, area.x, area.y, area.w*ratio, area.h, true);
+ let topLayout = staticSqrLayout.genLayout(tempTree, area.x, area.y, area.w, area.h*ratio, true);
+ //let sweptLayout = leftLayout;
+ let sweptLayout = (leftLayout.empSpc < topLayout.empSpc) ? leftLayout : topLayout;
+ sweptLayout.children.forEach(layout => {layout.y += headerSz});
+ //get remaining-area layout
+ let xyChg;
+ if (sweptLayout == leftLayout){
+ xyChg = [sweptLayout.contentW - TILE_SPACING, 0];
+ area.w += -sweptLayout.contentW + TILE_SPACING;
} else {
- let ratio = leaves.length / (leaves.length + nonLeaves.map(e => e.tileCount).reduce((x,y) => x+y));
- let hOffset = (hideHeader ? 0 : this.HEADER_SZ);
- //get swept-area layout
- let area = {x: x0, y: y0+hOffset, w: w, h: h-hOffset};
- let leftLayout = staticSqrLayout.genLayout(leaves, area.x, area.y, area.w*ratio, area.h, true);
- let topLayout = staticSqrLayout.genLayout(leaves, area.x, area.y, area.w, area.h*ratio, true);
- //let sweptLayout = leftLayout;
- let sweptLayout = (leftLayout.empSpc < topLayout.empSpc) ? leftLayout : topLayout;
- //get remaining-area layout
- if (sweptLayout == leftLayout){
- area.x += sweptLayout.contentW - this.TILE_SPACING;
- area.w += -sweptLayout.contentW + this.TILE_SPACING;
- } else {
- area.y += sweptLayout.contentH - this.TILE_SPACING;
- area.h += -sweptLayout.contentH + this.TILE_SPACING;
- }
- let nonLeavesLayout = staticRectLayout.genLayout(nonLeaves, area.x, area.y, area.w, area.h, true);
- //return combined layout
- return {
- coords: {...sweptLayout.coords, ...nonLeavesLayout.coords},
- contentW: (sweptLayout == leftLayout) ?
- sweptLayout.contentW + nonLeavesLayout.contentW - this.TILE_SPACING :
- Math.max(sweptLayout.contentW, nonLeavesLayout.contentW),
- contentH: (sweptLayout == leftLayout) ?
- Math.max(sweptLayout.contentH, nonLeavesLayout.contentH) :
- sweptLayout.contentH + nonLeavesLayout.contentH - this.TILE_SPACING,
- empSpc: sweptLayout.empSpc + nonLeavesLayout.empSpc
- };
+ xyChg = [0, sweptLayout.contentH - TILE_SPACING];
+ area.h += -sweptLayout.contentH + TILE_SPACING;
}
+ tempTree = {tolNode: null, children: nonLeaves}
+ let nonLeavesLayout = staticRectLayout.genLayout(
+ tempTree, area.x, area.y, area.w, area.h, true, sweepToSideLayout);
+ nonLeavesLayout.children.forEach(layout => {layout.x += xyChg[0]; layout.y += xyChg[1] + headerSz;});
+ //return combined layouts
+ let children = leaves.concat(nonLeaves);
+ let layouts = sweptLayout.children.concat(nonLeavesLayout.children);
+ let layoutsInOldOrder = [...Array(node.children.length).keys()]
+ .map(i => children.findIndex(n => n == node.children[i]))
+ .map(i => layouts[i]);
+ return {
+ x: x, y: y, w: w, h: h, headerSz: headerSz,
+ //children: [...sweptLayout.children, ...nonLeavesLayout.children],
+ children: layoutsInOldOrder,
+ contentW: (sweptLayout == leftLayout) ?
+ sweptLayout.contentW + nonLeavesLayout.contentW - TILE_SPACING :
+ Math.max(sweptLayout.contentW, nonLeavesLayout.contentW),
+ contentH: (sweptLayout == leftLayout) ?
+ Math.max(sweptLayout.contentH, nonLeavesLayout.contentH) :
+ sweptLayout.contentH + nonLeavesLayout.contentH - TILE_SPACING,
+ empSpc: sweptLayout.empSpc + nonLeavesLayout.empSpc
+ };
}
},
initLayoutInfo(tree){
@@ -288,43 +288,9 @@ const sweepToSideLayout = {
updateLayoutInfo(tree){
if (tree.children.length == 0){
tree.tileCount = 1;
- tree.layoutRes = (w, h) => {
- let ar = w / h;
- let ar2 = 1;
- let frac = ar > ar2 ? ar2/ar : ar/ar2;
- return {
- empSpc: (1 - frac) * w * h,
- contentW: ar > ar2 ? frac * w : w,
- contentH: ar > ar2 ? h : frac * h
- };
- };
} else {
tree.tileCount = tree.children.map(e => e.tileCount).reduce((x,y) => x+y);
- if (tree.children.every(e => e.children.length == 0)){
- tree.layoutRes = (w, h) => {
- let layout = staticSqrLayout.genLayout(tree.children, 0, 0, w, h, tree.hideHeader);
- return {empSpc: layout.empSpc, contentW: layout.contentW, contentH: layout.contentH};
- }
- } else {
- tree.layoutRes = (w, h) => {
- let layout = sweepToSideLayout.genLayout(tree.children, 0, 0, w, h, tree.hideHeader);
- return {empSpc: layout.empSpc, contentW: layout.contentW, contentH: layout.contentH};
- }
- }
}
}
};
-let defaultLayout = sweepToSideLayout;
-function initTree(tol, lvl, layout = defaultLayout){
- let tree = {tolNode: tol, children: []};
- initTreeRec(tree, lvl);
- layout.initLayoutInfo(tree)
- return tree;
-}
-function initTreeRec(tree, lvl){
- if (lvl > 0){
- tree.children = tree.tolNode.children.map(e => initTreeRec({tolNode: e, children: []}, lvl-1));
- }
- return tree;
-}
generated by cgit v1.2.3 (git 2.39.1) at 2026-04-25 15:16:40 +0000