summaryrefslogtreecommitdiff
path: root/plugins/code-modernization/hooks/map/treemap.ts
diff options
context:
space:
mode:
Diffstat (limited to 'plugins/code-modernization/hooks/map/treemap.ts')
-rw-r--r--plugins/code-modernization/hooks/map/treemap.ts156
1 files changed, 156 insertions, 0 deletions
diff --git a/plugins/code-modernization/hooks/map/treemap.ts b/plugins/code-modernization/hooks/map/treemap.ts
new file mode 100644
index 00000000..21042734
--- /dev/null
+++ b/plugins/code-modernization/hooks/map/treemap.ts
@@ -0,0 +1,156 @@
+/**
+ * A squarified treemap over a grid of terminal cells, two levels deep:
+ * groups (domains) first, then each group's items (modules) inside its
+ * rectangle. Pure: sizes in, integer cell rectangles out.
+ *
+ * A terminal cell is about twice as tall as it is wide, so the layout works
+ * in a space where each row counts double and rounds back to whole cells.
+ */
+
+export type Rect = { x: number; y: number; w: number; h: number }
+
+export type Sized<T> = { item: T; size: number }
+
+export type Placed<T> = { item: T; rect: Rect }
+
+/** How much taller than wide one cell is; rows are weighted by it when judging squareness. */
+const CELL_ASPECT = 2
+
+const worst = (row: number[], side: number, scale: number): number => {
+ const sum = row.reduce((a, b) => a + b, 0)
+
+ if (sum === 0 || side === 0) {
+ return Infinity
+ }
+
+ const max = Math.max(...row)
+ const min = Math.min(...row)
+ const s2 = sum * sum
+ const side2 = side * side * scale
+
+ return Math.max((side2 * max) / s2, s2 / (side2 * min))
+}
+
+/**
+ * Squarified layout of `sizes` (already scaled so they sum to the area of
+ * `rect`) into fractional rectangles, in the order given.
+ */
+function squarify(sizes: number[], rect: Rect): Rect[] {
+ const out: Rect[] = []
+ let { x, y, w, h } = rect
+ let index = 0
+
+ while (index < sizes.length) {
+ // Lay rows along the visually shorter side.
+ const isWide = w >= h * CELL_ASPECT
+ const side = isWide ? h : w
+ const scale = isWide ? CELL_ASPECT : 1 / CELL_ASPECT
+ const row: number[] = []
+
+ while (index < sizes.length) {
+ const next = sizes[index] ?? 0
+ const grown = [...row, next]
+
+ if (row.length > 0 && worst(grown, side, scale) > worst(row, side, scale)) {
+ break
+ }
+
+ row.push(next)
+ index += 1
+ }
+
+ const sum = row.reduce((a, b) => a + b, 0)
+ const thick = side > 0 ? sum / side : 0
+ let offset = 0
+
+ for (const size of row) {
+ const length = thick > 0 ? size / thick : 0
+
+ out.push(
+ isWide
+ ? { x, y: y + offset, w: thick, h: length }
+ : { x: x + offset, y, w: length, h: thick },
+ )
+
+ offset += length
+ }
+
+ if (isWide) {
+ x += thick
+ w -= thick
+ } else {
+ y += thick
+ h -= thick
+ }
+
+ if (w <= 0 || h <= 0) {
+ // Out of room: whatever is left collapses onto the last edge.
+ while (index < sizes.length) {
+ out.push({ x: rect.x + rect.w, y: rect.y + rect.h, w: 0, h: 0 })
+ index += 1
+ }
+ }
+ }
+
+ return out
+}
+
+/** Rounds fractional rectangles to whole cells without gaps or overlaps on shared edges. */
+function snap(rects: Rect[], bounds: Rect): Rect[] {
+ const clampX = (v: number) => Math.min(bounds.x + bounds.w, Math.max(bounds.x, Math.round(v)))
+ const clampY = (v: number) => Math.min(bounds.y + bounds.h, Math.max(bounds.y, Math.round(v)))
+
+ return rects.map(rect => {
+ const x0 = clampX(rect.x)
+ const y0 = clampY(rect.y)
+ const x1 = clampX(rect.x + rect.w)
+ const y1 = clampY(rect.y + rect.h)
+
+ return { x: x0, y: y0, w: Math.max(0, x1 - x0), h: Math.max(0, y1 - y0) }
+ })
+}
+
+/** Lays `entries` out in `rect`, largest first, each given at least `floor` of the mean size. */
+export function layout<T>(entries: Sized<T>[], rect: Rect, floor = 0.35): Placed<T>[] {
+ if (entries.length === 0 || rect.w <= 0 || rect.h <= 0) {
+ return []
+ }
+
+ const positive = entries.map(entry => ({ ...entry, size: Math.max(0, entry.size) }))
+ const mean = positive.reduce((sum, entry) => sum + entry.size, 0) / positive.length || 1
+
+ // A tiny item next to a huge one would round to zero cells: lift it to a floor.
+ const lifted = positive
+ .map(entry => ({ ...entry, size: Math.max(entry.size, mean * floor) }))
+ .sort((a, b) => b.size - a.size)
+
+ const total = lifted.reduce((sum, entry) => sum + entry.size, 0)
+ const area = rect.w * rect.h
+ const scaled = lifted.map(entry => (entry.size / total) * area)
+ const snapped = snap(squarify(scaled, rect), rect)
+
+ return lifted.map((entry, index) => ({
+ item: entry.item,
+ rect: snapped[index] ?? { x: rect.x, y: rect.y, w: 0, h: 0 },
+ }))
+}
+
+export type Group<T> = { name: string; items: Sized<T>[] }
+
+export type PlacedGroup<T> = { name: string; rect: Rect; items: Placed<T>[] }
+
+/** Two-level layout: groups by their items' total size, then items within each group. */
+export function layoutGroups<T>(groups: Group<T>[], rect: Rect): PlacedGroup<T>[] {
+ const sized = groups
+ .filter(group => group.items.length > 0)
+ .map(group => ({
+ item: group,
+ size: group.items.reduce((sum, entry) => sum + Math.max(0, entry.size), 0),
+ }))
+
+ return layout(sized, rect, 0.2).map(placed => ({
+ name: placed.item.name,
+ rect: placed.rect,
+ items: layout(placed.item.items, placed.rect),
+ }))
+}