atagen

monolith

public
Star0
Watch0
05668b0d47539e4bfea530f662dd9fa046df74b0
1
ssh://brewery@pls.lobotomise.me:33/atagen/monolith.git
design/planner.htmlHtml712 lines40.5 KB
1
<!doctype html>
2
<html lang="en">
3
<head>
4
<meta charset="utf-8">
5
<title>monolith planner design, draft 1</title>
6
<style>
7
  :root { --bg:#111317; --panel:#181b21; --fg:#d8dbe2; --dim:#8a909c; --accent:#e0774a; --bad:#ff4d5e; }
8
  * { box-sizing:border-box; }
9
  body { margin:0; background:var(--bg); color:var(--fg); font:15px/1.6 system-ui, sans-serif; }
10
  main { max-width:920px; margin:0 auto; padding:32px 20px 120px; }
11
  h1 { font-size:28px; margin:0 0 4px; }
12
  h2 { font-size:20px; margin:48px 0 8px; border-bottom:1px solid #2a2e37; padding-bottom:4px; }
13
  h3 { font-size:16px; margin:24px 0 6px; }
14
  p, li { color:var(--fg); }
15
  .sub { color:var(--dim); margin:0 0 24px; }
16
  code { background:#22262e; padding:1px 5px; border-radius:4px; font-size:13px; }
17
  pre { background:#1a1d23; padding:14px; border-radius:8px; overflow-x:auto; font-size:13px; line-height:1.45; }
18
  table { border-collapse:collapse; width:100%; font-size:14px; margin:12px 0; }
19
  th, td { border:1px solid #2a2e37; padding:6px 8px; text-align:left; vertical-align:top; }
20
  th { background:#1d2027; }
21
  .demo { background:var(--panel); border:1px solid #2a2e37; border-radius:10px; padding:12px; margin:16px 0; }
22
  .demo canvas { display:block; width:100%; height:auto; border-radius:6px; background:#0d0f12; }
23
  .controls { display:flex; flex-wrap:wrap; gap:8px; align-items:center; margin-top:10px; }
24
  button { background:#2a2f39; color:var(--fg); border:1px solid #3a404c; border-radius:6px; padding:5px 12px; cursor:pointer; font:inherit; font-size:14px; }
25
  button:hover { background:#343a46; }
26
  label { color:var(--dim); font-size:14px; display:flex; gap:6px; align-items:center; }
27
  .status { font:13px/1.4 ui-monospace, monospace; color:var(--dim); margin-top:8px; min-height:1.4em; }
28
  .status .bad { color:var(--bad); }
29
  .global { position:sticky; top:0; z-index:5; background:rgba(17,19,23,0.94); backdrop-filter:blur(4px); border-bottom:1px solid #2a2e37; padding:8px 20px; display:flex; gap:20px; justify-content:center; flex-wrap:wrap; }
30
  .q { background:#1d2027; border-left:3px solid var(--accent); padding:8px 12px; margin:10px 0; border-radius:0 6px 6px 0; }
31
  .note { color:var(--dim); font-size:14px; }
32
</style>
33
</head>
34
<body>
35
<div class="global">
36
  <label>phase duration <input id="phaseMs" type="range" min="150" max="1500" step="50" value="450"> <span id="phaseMsOut">450 ms</span></label>
37
  <label>style <select id="style"><option value="direct">direct (diagonal when safe)</option><option value="orthogonal">orthogonal (one axis per window per phase)</option></select></label>
38
</div>
39
<main>
40
<h1>monolith planner, draft 1</h1>
41
<p class="sub">Design for the multiphase layout animation planner (milestone M1). Every demo runs a small JavaScript port of the proposed algorithm, so what you see is what the design does. Red means two windows overlap.</p>
42
43
<h2>1. What the planner does</h2>
44
<p>The layout engine produces a target rectangle for every window. The planner turns "where windows are on screen now" and "where they should be" into a short sequence of keyframe layouts. Each step between two keyframes is a <em>phase</em>. Every window in a phase moves on the same curve and the phase takes exactly <code>t</code>, the configured duration, so a plan lasts <code>phases × t</code>.</p>
45
<p>Rules carried over from wry <code>master</code>.</p>
46
<ul>
47
  <li>Tiled windows never overlap while they move.</li>
48
  <li>Phases are synchronised. Everything in a phase starts and stops together.</li>
49
  <li>An interrupt throws the plan away and replans from what is on screen. Plans never stack.</li>
50
</ul>
51
<p>New requirements wry never met.</p>
52
<ul>
53
  <li>Diagonal moves, moves between outputs, and large groups such as viewing or hiding a tag.</li>
54
  <li>Best-effort velocity continuity when an interrupt lands mid-phase.</li>
55
  <li>A hard bound on plan length, so interrupts can never produce long animations.</li>
56
</ul>
57
58
<h2>2. The problem</h2>
59
<p>Swapping two windows by interpolating straight from start to end drives them through each other. Toggle "naive" to compare.</p>
60
<div class="demo" id="d1"></div>
61
62
<h2>3. The core rule, shared separators</h2>
63
<p>For any two windows there are four ways they can be apart. A is left of B, right of B, above B, or below B. Each is a linear inequality on window edges, for example <code>A.right ≤ B.left</code>. If an inequality holds at both ends of a phase and both windows move on the same curve, it holds for the whole phase, because every edge is the same weighted average of its start and end value.</p>
64
<p>So the planner's entire job reduces to this. <strong>Pick keyframes so that for every pair of windows, every two consecutive keyframes share at least one separating relation.</strong> Diagonal motion is perfectly safe under this rule. wry needed single-axis steps because its solver checked overlap directly. This rule proves it instead.</p>
65
<p>Looking at a single pair gives a lower bound on phases.</p>
66
<table>
67
  <tr><th>pair goes from</th><th>to</th><th>minimum phases</th><th>why</th></tr>
68
  <tr><td>left of</td><td>left of (any sizes)</td><td>1</td><td>relation shared</td></tr>
69
  <tr><td>left of</td><td>above</td><td>2</td><td>needs a middle keyframe where A is both left of and above B</td></tr>
70
  <tr><td>left of</td><td>right of</td><td>3</td><td>left and right can't both hold, so the pair must pass through above or below on the way</td></tr>
71
</table>
72
<p>The plan length is the worst pair, so <strong>every plan is 1, 2 or 3 phases</strong>, with one fallback described in section 10. The rule is sufficient, not necessary. Some overlap-free phases break it, and the Rust validator keeps an exact check for those, but the planner only constructs plans that satisfy it.</p>
73
74
<h2>4. One phase</h2>
75
<p>Anything that keeps the arrangement of windows intact is a single phase, including changes in both axes at once. That covers ratio changes, inserting and removing windows, splitting a column, and viewing or hiding a tag.</p>
76
<p><strong>Seeds.</strong> A window that appears starts as a zero-size rectangle sitting on the edge where space will open. A closing window ends as one. A seed on an edge is already separated from its neighbours, so it obeys the rule from the first frame. wry grew spawns from the centre of their target, which overlaps the neighbours early in the phase while they are still making room.</p>
77
<div class="demo" id="d2"></div>
78
<p>Viewing and hiding a tag is the same thing at a larger scale. The new tag's windows are seeds on the edge where their row will open.</p>
79
<div class="demo" id="d3"></div>
80
81
<h2>5. Two phases, axis order</h2>
82
<p>When a pair turns a corner (left of becomes above), the middle keyframe is built from a <em>mixed</em> rectangle. Each window takes its horizontal extent from one end and its vertical extent from the other. "X first" means the window takes its target horizontal extent in phase 1 and its target vertical extent in phase 2. "Y first" is the reverse. Every window then moves along exactly one axis per phase.</p>
83
<p>Each window's choice is one boolean. Every pair rules out some of the four combinations, and each forbidden combination is a clause over two variables. That makes it a <strong>2-SAT problem, solvable in linear time</strong> with no search. Windows that only change one axis use the same boolean to choose whether they move in phase 1 or phase 2, and the planner prefers phase 1 so nothing waits needlessly.</p>
84
<div class="demo" id="d4a"></div>
85
<p>The style selector at the top matters here. Growing a window in both directions inside a grid is a valid single phase in <em>direct</em> style, because every pair keeps a relation. <em>Orthogonal</em> style forbids moving a window on both axes in one phase, which gives wry's look of making space first and then growing, at the cost of an extra phase.</p>
86
<div class="demo" id="d4b"></div>
87
88
<h2>6. Three phases, lanes</h2>
89
<p>Reversals (left of becomes right of) need two middle keyframes. Windows shrink into <em>lanes</em> across the axis of travel, slide past each other, then expand. Two windows may share a lane only if they never pass each other. Windows stacked on top of each other must keep their stacking order in the lanes, at both ends. Picking lanes is a small constrained colouring problem. For a pure reordering of a row the lane count equals the length of the longest decreasing subsequence of the new order (Dilworth's theorem). Swapping two neighbours or rotating needs 2 lanes, and full reversal of four windows needs 4.</p>
90
<p>Only windows involved in a reversal enter lanes. Everything else moves in whichever phase validates, preferring the slide phase.</p>
91
<div class="demo" id="d5"></div>
92
93
<h2>7. Tags as rigid blocks</h2>
94
<p>Swapping the order of two viewed tags reverses every window of one tag against every window of the other. Planned window by window, that needs one lane per window (5 thin strips in the demo below). Planned with each tag as a <em>rigid block</em>, it needs 2 lanes, and the windows ride inside their block. The block planner is the same algorithm one level up, followed by mapping each window into its block's keyframes.</p>
95
<div class="demo" id="d3b"></div>
96
97
<h2>8. Interrupts and velocity</h2>
98
<p>An interrupt samples the current on-screen rectangles and plans from there to the new target. The new plan has at most 3 phases, however many times you interrupt. Try the storm button, which fires a new target every few hundred milliseconds.</p>
99
<p><strong>Velocity.</strong> The base curve starts and ends at rest, so a window that is moving when interrupted stops dead. Velocity matching measures how fast things were moving and starts the first phase of the new plan at that speed, by setting the first control point of the bezier so the initial slope matches. The slope only applies when the first phase continues in the direction things were already moving. Otherwise the window stops and turns, which reads as deliberate. The control point's height is clamped to 1, which mathematically rules out overshoot, since a cubic bezier never leaves the range of its control points.</p>
100
<p>One curve per <em>motion group</em>, never per window. Windows that share an edge must move that edge on the same curve or the edge tears open or overlaps. So the group gets a single curve, matched to its fastest mover. The graph shows window A's speed, and turning matching off shows the drop to zero at every interrupt.</p>
101
<div class="demo" id="d6"></div>
102
103
<h2>9. Across outputs</h2>
104
<p>Outputs live in one global coordinate space, so a move between outputs is planned like any other move and drawn clipped to each output. The window crosses the bezel and appears on the other side. Moving B over is one phase. Moving A over means A has to pass B, a reversal, so it takes lanes, and the lanes span both outputs.</p>
105
<p class="note">Not shown. Outputs at different scales draw the same window at different sizes. The planner works in logical coordinates and each output scales its part. If two outputs aren't adjacent in the global space, the window would travel through empty space, and the pinch fallback is probably better there.</p>
106
<div class="demo" id="d7"></div>
107
108
<h2>10. Fallback, pinch</h2>
109
<p>If no 1, 2 or 3 phase plan validates, the windows that can't be routed shrink to a point, jump invisibly, and grow at their target. That's two visible phases, never overlaps, and always works. I couldn't find a tiling transition in these demos that needs it, but the bound has to hold for every input, including arbitrary floating-to-tiled transitions and malformed layouts.</p>
110
111
<h2>11. Algorithm</h2>
112
<pre>plan(from, to):
113
  groups = motion groups (windows whose swept areas can touch, transitively)
114
  for each group:
115
    if every pair shares a relation between from and to
116
       and (style is direct or every window changes only one axis):
117
      return [from, to]                                    # 1 phase
118
    if 2-SAT over axis order finds K1:                     # mixed rects
119
      return [from, K1, to]                                # 2 phases
120
    for lane_axis in [y, x]:                               # strips, then columns
121
      for set in [windows in reversals, all movers, all]:
122
        for k in 2..|set|:
123
          if lanes assignable with k lanes and all three phases validate:
124
            return [from, K1, K2, to]                      # 3 phases
125
    return pinch(from, to)                                 # 2 visible phases
126
127
  rigid blocks: run plan() on block rectangles first, then map windows into them
128
  interrupts:   from = rectangles sampled at the current presentation time
129
  velocity:     first-phase curve per group, slope from the fastest mover,
130
                applied only if moving the same way, control point height ≤ 1
131
  validation:   exact pairwise check over the curve actually used</pre>
132
<p>Cost. Pair checks are O(n²) per group. 2-SAT is linear in clauses, so also O(n²). Lane assignment is backtracking over small sets with a greedy cut-off for large ones. Fifty windows is about 1,200 pairs, which is microseconds.</p>
133
<p>Everything here is pure geometry with no smithay dependency, so the <code>planner</code> crate gets property tests. Generate random layouts and random interrupt sequences, then check every frame of every plan for overlap, every plan for ≤ 3 phases, and every interrupt for continuity of position.</p>
134
135
<h2>12. Compared with wry master</h2>
136
<table>
137
  <tr><th>wry master</th><th>this design</th></tr>
138
  <tr><td>SingleAction, MixedSinglePhase</td><td>1 phase, now including diagonal moves in direct style</td></tr>
139
  <tr><td>SpaceThenOrthogonalGrowth, OrientationChange, HierarchyOrderedScales</td><td>2 phases, one 2-SAT problem instead of three strategies</td></tr>
140
  <tr><td>SwapLanes</td><td>3 phases, general lane assignment for any permutation</td></tr>
141
  <tr><td>ReversedForwardPlan</td><td>not needed, the construction is symmetric</td></tr>
142
  <tr><td>Diagonal falls back to overlapping plain interpolation</td><td>diagonal is legal whenever relations are shared, pinch otherwise</td></tr>
143
  <tr><td>Bridged retarget can make plans longer than the original</td><td>every replan is ≤ 3 phases</td></tr>
144
  <tr><td>Per-phase duration, plans grow with strategy</td><td>per-phase duration kept, plan length bounded</td></tr>
145
  <tr><td>Spawns grow from the target centre</td><td>spawns grow from a seed on the opening edge</td></tr>
146
  <tr><td>Exact rational overlap check validates every plan</td><td>plans are correct by construction, the exact check remains as a safety net and for velocity-shaped curves</td></tr>
147
  <tr><td>Cross-output moves skip animation</td><td>planned in global coordinates, clipped per output</td></tr>
148
</table>
149
150
<h2>13. Interspersing tags (new, changes the layout model)</h2>
151
<p>Row stacking answers "what does a combined view look like" but not "what happens when I drag A from tag 1's row in between D and E of tag 2". There are four answers.</p>
152
<table>
153
  <tr><th>option</th><th>meaning</th><th>verdict</th></tr>
154
  <tr><td>Forbid it</td><td>tags stay in their rows</td><td>limiting, as you said</td></tr>
155
  <tr><td>Dragging retags</td><td>moving A into tag 2's row makes A a tag 2 window</td><td>honest and simple, but A then vanishes from tag 1 viewed alone, which is usually not what the drag meant</td></tr>
156
  <tr><td>2D positional merging (L/C/R × T/M/B)</td><td>windows merge into slots by position</td><td>kill it. Users must predict an implicit rule, and every edit in a combined view is ambiguous about which tag's tree it changes</td></tr>
157
  <tr><td>Layout per view combination</td><td>each set of viewed tags gets its own tree, seeded by row stacking</td><td>no surprises between views, but N combinations of trees to keep in sync, and every new window has to be inserted into all of them</td></tr>
158
  <tr><td><strong>One tree per output, tags filter it</strong></td><td>every window of every tag lives in a single tree per output. Viewing tags shows a projection with hidden windows collapsed. Each tag starts as its own row, so row stacking becomes the default arrangement instead of a merge rule</td><td><strong>recommended</strong></td></tr>
159
</table>
160
<p>The last option is dwm's model (one client list, tags as a filter) with a tree in place of the list. Its advantages are one source of truth and no sync problem. Interspersing is just moving a window in the tree. And for the planner, <strong>viewing or hiding any tag is always a single phase</strong>, because hidden windows are zero-weight seeds sitting at their own spot in the same tree. Switching views never rearranges anything.</p>
161
<p>Its cost is action at a distance. Intersperse A into tag 2's row below, then view tag 1 alone. A now sits under B and C, because in the tree it lives in the lower row. You changed tag 1's single view without ever viewing it alone. That's consistent, but some will find it surprising. It also reverses an earlier decision. Layout state moves from per tag-on-output to per output.</p>
162
<div class="demo" id="d8"></div>
163
164
<h2>14. Decisions for you</h2>
165
<div class="q"><strong>1. Direct or orthogonal style?</strong> Direct gives fewer phases and diagonal motion when it's safe. Orthogonal is the wry look, where every window moves along one axis at a time. It could be a config option, but the default shapes how monolith feels.</div>
166
<div class="q"><strong>2. Rigid tag blocks?</strong> Should tags move as blocks when their order changes, and should the same apply to any container whose contents keep their arrangement? Blocks are calmer and need fewer lanes. Per-window planning is more uniform.</div>
167
<div class="q"><strong>3. Lane extent.</strong> Lanes currently span only the band the involved windows occupy. Spanning the whole output gives thicker lanes for small windows, but disturbs more of the screen.</div>
168
<div class="q"><strong>4. Seeds on edges instead of growing from the centre.</strong> Growing from the centre looks friendlier but overlaps the neighbours early on. Edge seeds never overlap. Centre growth drawn on top of everything is the alternative.</div>
169
<div class="q"><strong>5. Pinch as the last resort.</strong> The alternative is a crossfade at the target, which is softer but means two copies of the window are visible at once.</div>
170
<div class="q"><strong>6. One curve per motion group.</strong> This is forced by shared edges, but it means velocity matching follows the group's fastest mover. Slower windows in the group inherit its momentum. Acceptable?</div>
171
<div class="q"><strong>7. One tree per output with tags as a filter</strong>, replacing per-tag layouts and the row-stacking merge rule (section 13)? If yes, what happens to a window's tree position when it is retagged? It can keep its spot, or move into the target tag's own row.</div>
172
<div class="q"><strong>8. Floating windows</strong> are outside the no-overlap rule and move in one phase on top of the tiled layer. Should a floating-to-tiled transition join the plan as a seed, or keep floating above until it lands?</div>
173
</main>
174
175
<script id="planner">
176
const G = 10;
177
const EPS = 0.5;
178
let PHASE_MS = 450;
179
let STYLE = 'direct';
180
181
const R = (x, y, w, h) => ({ x, y, w, h });
182
const clone = L => { const o = {}; for (const k in L) o[k] = { ...L[k] }; return o; };
183
const eq = (a, b) => Math.abs(a - b) < 0.05;
184
const lerp = (a, b, s) => a + (b - a) * s;
185
const lerpRect = (a, b, s) => R(lerp(a.x, b.x, s), lerp(a.y, b.y, s), lerp(a.w, b.w, s), lerp(a.h, b.h, s));
186
187
function splitX(rect, ids, ratios) {
188
  ratios = ratios || ids.map(() => 1);
189
  const tot = ratios.reduce((a, b) => a + b, 0);
190
  const avail = rect.w - G * (ids.length - 1);
191
  let x = rect.x;
192
  const out = {};
193
  ids.forEach((id, i) => { const w = avail * ratios[i] / tot; out[id] = R(x, rect.y, w, rect.h); x += w + G; });
194
  return out;
195
}
196
function splitY(rect, ids, ratios) {
197
  ratios = ratios || ids.map(() => 1);
198
  const tot = ratios.reduce((a, b) => a + b, 0);
199
  const avail = rect.h - G * (ids.length - 1);
200
  let y = rect.y;
201
  const out = {};
202
  ids.forEach((id, i) => { const h = avail * ratios[i] / tot; out[id] = R(rect.x, y, rect.w, h); y += h + G; });
203
  return out;
204
}
205
206
function relBits(a, b) {
207
  let s = 0;
208
  if (a.x + a.w <= b.x + EPS) s |= 1;
209
  if (b.x + b.w <= a.x + EPS) s |= 2;
210
  if (a.y + a.h <= b.y + EPS) s |= 4;
211
  if (b.y + b.h <= a.y + EPS) s |= 8;
212
  return s;
213
}
214
function phaseOk(K1, K2, list) {
215
  for (let i = 0; i < list.length; i++)
216
    for (let j = i + 1; j < list.length; j++) {
217
      const a = list[i], b = list[j];
218
      if ((relBits(K1[a], K1[b]) & relBits(K2[a], K2[b])) === 0) return false;
219
    }
220
  return true;
221
}
222
function chg(a, b) { return { x: !(eq(a.x, b.x) && eq(a.w, b.w)), y: !(eq(a.y, b.y) && eq(a.h, b.h)) }; }
223
224
function plan(from, to, opts = {}) {
225
  const list = Object.keys(to);
226
  const T = PHASE_MS;
227
  if (opts.naive) return { kind: 'naive lerp', keys: [from, to], durs: [T] };
228
  const movers = list.filter(id => { const c = chg(from[id], to[id]); return c.x || c.y; });
229
  if (!movers.length) return { kind: 'no-op', keys: [from, to], durs: [0] };
230
  const pure = movers.every(id => { const c = chg(from[id], to[id]); return !(c.x && c.y); });
231
  if (phaseOk(from, to, list) && (STYLE === 'direct' || pure))
232
    return { kind: '1 phase', keys: [from, to], durs: [T] };
233
  const two = axisOrder(from, to, list, movers);
234
  if (two) return two;
235
  for (const ax of ['y', 'x']) { const l = lanes(from, to, list, movers, ax); if (l) return l; }
236
  return pinch(from, to, movers);
237
}
238
239
function mixed(f, t, xFirst) { return xFirst ? R(t.x, f.y, t.w, f.h) : R(f.x, t.y, f.w, t.h); }
240
241
function axisOrder(from, to, list, movers) {
242
  const n = movers.length;
243
  if (n > 14) return null;
244
  let best = null, bestScore = Infinity;
245
  for (let mask = 0; mask < (1 << n); mask++) {
246
    const K1 = { ...from };
247
    let score = 0;
248
    movers.forEach((id, i) => {
249
      const xf = !!(mask & (1 << i));
250
      const c = chg(from[id], to[id]);
251
      K1[id] = mixed(from[id], to[id], xf);
252
      if (c.x && !c.y && !xf) score++;
253
      if (c.y && !c.x && xf) score++;
254
    });
255
    if (score >= bestScore) continue;
256
    if (phaseOk(from, K1, list) && phaseOk(K1, to, list)) { best = K1; bestScore = score; if (score === 0) break; }
257
  }
258
  return best ? { kind: '2 phases (axis order)', keys: [from, best, to], durs: [PHASE_MS, PHASE_MS] } : null;
259
}
260
261
function lanes(from, to, list, movers, ax) {
262
  const size = ax === 'y' ? 'h' : 'w';
263
  const bitsT = ax === 'y' ? 3 : 12;
264
  const before = ax === 'y' ? 4 : 1, after = ax === 'y' ? 8 : 2;
265
  const conflict = new Set();
266
  for (let i = 0; i < list.length; i++)
267
    for (let j = i + 1; j < list.length; j++) {
268
      const a = list[i], b = list[j];
269
      if ((relBits(from[a], from[b]) & relBits(to[a], to[b])) === 0) { conflict.add(a); conflict.add(b); }
270
    }
271
  const sets = [[...conflict], movers, list];
272
  for (const set of sets) {
273
    const n = set.length;
274
    if (n < 2) continue;
275
    let lo = Infinity, hi = -Infinity;
276
    for (const id of set) for (const r of [from[id], to[id]]) { lo = Math.min(lo, r[ax]); hi = Math.max(hi, r[ax] + r[size]); }
277
    const diff = [], lt = [];
278
    for (let i = 0; i < n; i++) { diff.push(new Array(n).fill(false)); lt.push(new Array(n).fill(false)); }
279
    for (let i = 0; i < n; i++)
280
      for (let j = 0; j < n; j++) {
281
        if (i === j) continue;
282
        const f = relBits(from[set[i]], from[set[j]]), t = relBits(to[set[i]], to[set[j]]);
283
        if (((f & bitsT) & (t & bitsT)) === 0) diff[i][j] = true;
284
        for (const r of [f, t]) if ((r & bitsT) === 0 && (r & before)) lt[i][j] = true;
285
      }
286
    for (let k = 2; k <= n; k++) {
287
      const s = (hi - lo - (k - 1) * G) / k;
288
      if (s < 6) break;
289
      const lane = new Array(n).fill(-1);
290
      const assign = i => {
291
        if (i === n) return true;
292
        for (let l = 0; l < k; l++) {
293
          let ok = true;
294
          for (let j = 0; j < i && ok; j++) {
295
            if (diff[i][j] && lane[j] === l) ok = false;
296
            if (lt[i][j] && !(l < lane[j])) ok = false;
297
            if (lt[j][i] && !(lane[j] < l)) ok = false;
298
          }
299
          if (ok) { lane[i] = l; if (assign(i + 1)) return true; lane[i] = -1; }
300
        }
301
        return false;
302
      };
303
      if (!assign(0)) continue;
304
      const strip = l => lo + l * (s + G);
305
      const inSet = new Set(set);
306
      for (const phase of [2, 1, 3]) {
307
        const K1 = {}, K2 = {};
308
        for (const id of list) {
309
          const f = from[id], t = to[id];
310
          if (inSet.has(id)) {
311
            const l = lane[set.indexOf(id)];
312
            K1[id] = ax === 'y' ? R(f.x, strip(l), f.w, s) : R(strip(l), f.y, s, f.h);
313
            K2[id] = ax === 'y' ? R(t.x, strip(l), t.w, s) : R(strip(l), t.y, s, t.h);
314
          } else if (phase === 1) { K1[id] = t; K2[id] = t; }
315
          else if (phase === 2) { K1[id] = f; K2[id] = t; }
316
          else { K1[id] = f; K2[id] = f; }
317
        }
318
        if (phaseOk(from, K1, list) && phaseOk(K1, K2, list) && phaseOk(K2, to, list))
319
          return { kind: `3 phases (${k} lanes)`, keys: [from, K1, K2, to], durs: [PHASE_MS, PHASE_MS, PHASE_MS] };
320
      }
321
    }
322
  }
323
  return null;
324
}
325
326
function pinch(from, to, movers) {
327
  const K1 = { ...from }, K2 = { ...to };
328
  for (const id of movers) {
329
    const f = from[id], t = to[id];
330
    K1[id] = R(f.x + f.w / 2, f.y + f.h / 2, 0, 0);
331
    K2[id] = R(t.x + t.w / 2, t.y + t.h / 2, 0, 0);
332
  }
333
  return { kind: 'pinch fallback', keys: [from, K1, K2, to], durs: [PHASE_MS, 0, PHASE_MS] };
334
}
335
336
function bbox(rects) {
337
  let x0 = Infinity, y0 = Infinity, x1 = -Infinity, y1 = -Infinity;
338
  for (const r of rects) { x0 = Math.min(x0, r.x); y0 = Math.min(y0, r.y); x1 = Math.max(x1, r.x + r.w); y1 = Math.max(y1, r.y + r.h); }
339
  return R(x0, y0, x1 - x0, y1 - y0);
340
}
341
function planBlocks(from, to, groups) {
342
  const bf = {}, bt = {};
343
  for (const b in groups) { bf[b] = bbox(groups[b].map(id => from[id])); bt[b] = bbox(groups[b].map(id => to[id])); }
344
  const bp = plan(bf, bt);
345
  const last = bp.keys.length - 1;
346
  const keys = bp.keys.map((K, ki) => {
347
    if (ki === 0) return from;
348
    if (ki === last) return to;
349
    const L = { ...from };
350
    for (const b in groups) for (const id of groups[b]) {
351
      const r = from[id], box = bf[b], k = K[b];
352
      const nx = box.w ? (r.x - box.x) / box.w : 0, ny = box.h ? (r.y - box.y) / box.h : 0;
353
      const nw = box.w ? r.w / box.w : 0, nh = box.h ? r.h / box.h : 0;
354
      L[id] = R(k.x + nx * k.w, k.y + ny * k.h, nw * k.w, nh * k.h);
355
    }
356
    return L;
357
  });
358
  return { kind: bp.kind + ' on blocks', keys, durs: bp.durs };
359
}
360
361
function bezier(x1, y1, x2, y2) {
362
  const cx = 3 * x1, bx = 3 * (x2 - x1) - cx, ax = 1 - cx - bx;
363
  const cy = 3 * y1, by = 3 * (y2 - y1) - cy, ay = 1 - cy - by;
364
  const X = u => ((ax * u + bx) * u + cx) * u, Y = u => ((ay * u + by) * u + cy) * u;
365
  const dX = u => (3 * ax * u + 2 * bx) * u + cx;
366
  return t => {
367
    if (t <= 0) return 0;
368
    if (t >= 1) return 1;
369
    let u = t;
370
    for (let i = 0; i < 8; i++) {
371
      const x = X(u) - t;
372
      if (Math.abs(x) < 1e-6) return Y(u);
373
      const d = dX(u);
374
      if (Math.abs(d) < 1e-6) break;
375
      u -= x / d;
376
    }
377
    let lo = 0, hi = 1; u = t;
378
    for (let i = 0; i < 40; i++) { if (X(u) < t) lo = u; else hi = u; u = (lo + hi) / 2; }
379
    return Y(u);
380
  };
381
}
382
const BASE = bezier(0.45, 0, 0.2, 1);
383
const edges = r => [r.x, r.x + r.w, r.y, r.y + r.h];
384
</script>
385
386
<script>
387
const PAL = { A: '#e0774a', B: '#4aa3e0', C: '#7bc96f', D: '#c77be0', E: '#e0c24a', F: '#4ae0c2' };
388
const demos = [];
389
390
class Demo {
391
  constructor(id, W, H, opts = {}) {
392
    this.W = W; this.H = H;
393
    this.outputs = opts.outputs || [R(0, 0, W, H)];
394
    const el = document.getElementById(id);
395
    this.canvas = document.createElement('canvas');
396
    const dpr = window.devicePixelRatio || 1;
397
    this.canvas.width = W * dpr; this.canvas.height = H * dpr;
398
    this.canvas.style.maxWidth = W + 'px';
399
    this.ctx = this.canvas.getContext('2d');
400
    this.ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
401
    el.appendChild(this.canvas);
402
    if (opts.graph) {
403
      this.graph = document.createElement('canvas');
404
      this.graph.width = W * dpr; this.graph.height = 90 * dpr;
405
      this.graph.style.maxWidth = W + 'px'; this.graph.style.marginTop = '8px';
406
      this.gctx = this.graph.getContext('2d');
407
      this.gctx.setTransform(dpr, 0, 0, dpr, 0, 0);
408
      el.appendChild(this.graph);
409
      this.hist = [];
410
    }
411
    this.controls = document.createElement('div'); this.controls.className = 'controls'; el.appendChild(this.controls);
412
    this.status = document.createElement('div'); this.status.className = 'status'; el.appendChild(this.status);
413
    this.anim = null; this.prev = null; this.vel = {}; this.naive = false; this.vmatch = true; this.lastKind = 'idle';
414
    demos.push(this);
415
  }
416
  button(label, fn) { const b = document.createElement('button'); b.textContent = label; b.onclick = fn; this.controls.appendChild(b); return b; }
417
  check(label, init, fn) {
418
    const l = document.createElement('label'); const c = document.createElement('input'); c.type = 'checkbox'; c.checked = init;
419
    c.onchange = () => fn(c.checked); l.appendChild(c); l.appendChild(document.createTextNode(label)); this.controls.appendChild(l); return c;
420
  }
421
  set(L) { this.layout = clone(L); this.anim = null; }
422
  go(target, opts = {}) {
423
    const now = performance.now();
424
    const cur = this.sampleAt(now);
425
    const from = {};
426
    for (const id in target) from[id] = cur[id] || target[id];
427
    const p = opts.blocks ? planBlocks(from, target, opts.blocks) : plan(from, target, { naive: this.naive });
428
    const curves = p.durs.map(() => BASE);
429
    const interrupted = !!this.anim;
430
    let matched = false;
431
    if (this.vmatch && interrupted && p.durs[0] > 0 && p.keys.length > 1) {
432
      const K1 = p.keys[1];
433
      let best = null, bs = 0;
434
      for (const id in K1) {
435
        const v = this.vel[id]; if (!v) continue;
436
        const D = edges(K1[id]).map((e, i) => e - edges(from[id])[i]);
437
        const dd = D.reduce((a, b) => a + b * b, 0); if (dd < 1) continue;
438
        const sp = Math.hypot(...v);
439
        if (sp > bs) { bs = sp; best = { v, D, dd }; }
440
      }
441
      if (best) {
442
        const s = best.v.reduce((a, b, i) => a + b * best.D[i], 0) / best.dd;
443
        const slope = s * p.durs[0];
444
        if (slope > 0.05) { const x1 = 0.3; curves[0] = bezier(x1, Math.min(1, x1 * slope), 0.2, 1); matched = true; }
445
      }
446
    }
447
    this.anim = { keys: p.keys, durs: p.durs, curves, start: now };
448
    this.lastKind = p.kind + (interrupted ? ', replanned' : '') + (matched ? ', velocity matched' : '');
449
    this.overlapSeen = false;
450
  }
451
  sampleAt(t) {
452
    if (!this.anim) return clone(this.layout);
453
    let e = t - this.anim.start;
454
    const { keys, durs, curves } = this.anim;
455
    for (let i = 0; i < durs.length; i++) {
456
      const d = durs[i];
457
      if (e < d) {
458
        this.phase = i;
459
        const s = curves[i](e / d);
460
        const L = {};
461
        for (const id in keys[i + 1]) L[id] = lerpRect(keys[i][id], keys[i + 1][id], s);
462
        return L;
463
      }
464
      e -= d;
465
    }
466
    this.layout = clone(keys[keys.length - 1]);
467
    this.anim = null;
468
    return clone(this.layout);
469
  }
470
  frame(now) {
471
    const L = this.sampleAt(now);
472
    if (this.prev) {
473
      const dt = now - this.prev.t;
474
      if (dt > 0) for (const id in L) if (this.prev.L[id]) {
475
        const a = edges(this.prev.L[id]), b = edges(L[id]);
476
        this.vel[id] = b.map((v, i) => (v - a[i]) / dt);
477
      }
478
    }
479
    this.prev = { t: now, L };
480
    this.draw(L);
481
    const overlaps = this.findOverlaps(L);
482
    if (overlaps.length) this.overlapSeen = true;
483
    const phaseTxt = this.anim ? ` · phase ${this.phase + 1}/${this.anim.durs.length}` : '';
484
    this.status.innerHTML = `${this.lastKind}${phaseTxt}` + (this.overlapSeen ? ' · <span class="bad">overlap</span>' : '');
485
    if (this.graph) this.drawGraph(now);
486
  }
487
  findOverlaps(L) {
488
    const ids = Object.keys(L).filter(id => L[id].w > 0.5 && L[id].h > 0.5);
489
    const out = [];
490
    for (let i = 0; i < ids.length; i++) for (let j = i + 1; j < ids.length; j++) {
491
      const a = L[ids[i]], b = L[ids[j]];
492
      const x0 = Math.max(a.x, b.x), y0 = Math.max(a.y, b.y);
493
      const x1 = Math.min(a.x + a.w, b.x + b.w), y1 = Math.min(a.y + a.h, b.y + b.h);
494
      if (x1 - x0 > 1 && y1 - y0 > 1) out.push(R(x0, y0, x1 - x0, y1 - y0));
495
    }
496
    return out;
497
  }
498
  draw(L) {
499
    const c = this.ctx;
500
    c.clearRect(0, 0, this.W, this.H);
501
    const overlaps = this.findOverlaps(L);
502
    for (const o of this.outputs) {
503
      c.save();
504
      c.fillStyle = '#1b1e25'; c.fillRect(o.x, o.y, o.w, o.h);
505
      c.beginPath(); c.rect(o.x, o.y, o.w, o.h); c.clip();
506
      for (const id in L) {
507
        const r = L[id];
508
        if (r.w < 0.5 || r.h < 0.5) continue;
509
        const rad = Math.min(8, r.w / 2, r.h / 2);
510
        c.beginPath(); c.roundRect(r.x, r.y, r.w, r.h, rad);
511
        c.fillStyle = (PAL[id] || '#888') + 'cc'; c.fill();
512
        c.strokeStyle = PAL[id] || '#888'; c.lineWidth = 1.5; c.stroke();
513
        if (r.w > 22 && r.h > 22) {
514
          c.fillStyle = '#0d0f12'; c.font = '600 16px system-ui'; c.textAlign = 'center'; c.textBaseline = 'middle';
515
          c.fillText(id, r.x + r.w / 2, r.y + r.h / 2);
516
        }
517
      }
518
      for (const o2 of overlaps) { c.fillStyle = 'rgba(255,77,94,0.55)'; c.fillRect(o2.x, o2.y, o2.w, o2.h); c.strokeStyle = '#ff4d5e'; c.lineWidth = 2; c.strokeRect(o2.x, o2.y, o2.w, o2.h); }
519
      c.restore();
520
    }
521
  }
522
  drawGraph(now) {
523
    const v = this.vel.A;
524
    const sp = v ? Math.hypot(v[0] + v[1], v[2] + v[3]) * 1000 / 2 : 0;
525
    this.hist.push([now, sp]);
526
    while (this.hist.length && now - this.hist[0][0] > 4000) this.hist.shift();
527
    const c = this.gctx, W = this.W, H = 90;
528
    c.clearRect(0, 0, W, H);
529
    c.fillStyle = '#0d0f12'; c.fillRect(0, 0, W, H);
530
    const max = Math.max(400, ...this.hist.map(h => h[1]));
531
    c.beginPath();
532
    this.hist.forEach(([t, s], i) => { const x = W - (now - t) / 4000 * W, y = H - 6 - s / max * (H - 16); i ? c.lineTo(x, y) : c.moveTo(x, y); });
533
    c.strokeStyle = PAL.A; c.lineWidth = 2; c.stroke();
534
    c.fillStyle = '#8a909c'; c.font = '12px system-ui'; c.textAlign = 'left'; c.fillText('speed of window A, last 4 s', 8, 14);
535
  }
536
}
537
538
const inner = (W, H, ox = 0) => R(ox + G, G, W - 2 * G, H - 2 * G);
539
540
{ // d1 swap
541
  const W = 640, H = 260, d = new Demo('d1', W, H), I = inner(W, H);
542
  let swapped = false;
543
  const L = () => splitX(I, swapped ? ['B', 'A'] : ['A', 'B']);
544
  d.set(L());
545
  d.button('Swap A and B', () => { swapped = !swapped; d.go(L()); });
546
  d.check('naive', false, v => d.naive = v);
547
}
548
549
{ // d2 one phase
550
  const W = 640, H = 300, d = new Demo('d2', W, H), I = inner(W, H);
551
  const s = { wide: false, d: false, e: false };
552
  const L = () => {
553
    const ids = s.d ? ['A', 'B', 'D', 'C'] : ['A', 'B', 'C'];
554
    const out = splitX(I, ids, ids.map(id => (id === 'A' && s.wide) ? 2 : 1));
555
    if (!s.d) out.D = R((out.B.x + out.B.w + out.C.x) / 2, I.y, 0, I.h);
556
    const b = out.B;
557
    if (s.e) Object.assign(out, splitY(b, ['B', 'E'])); else out.E = R(b.x, b.y + b.h, b.w, 0);
558
    return out;
559
  };
560
  d.set(L());
561
  d.button('Widen A', () => { s.wide = !s.wide; d.go(L()); });
562
  d.button('Insert / remove D', () => { s.d = !s.d; d.go(L()); });
563
  d.button('Split B with E', () => { s.e = !s.e; d.go(L()); });
564
  d.button('All at once', () => { s.wide = !s.wide; s.d = !s.d; s.e = !s.e; d.go(L()); });
565
  d.check('naive', false, v => d.naive = v);
566
}
567
568
function tagLayout(I, view2, order) {
569
  const L = {};
570
  if (view2) {
571
    const rows = splitY(I, order);
572
    Object.assign(L, splitX(rows.t1, ['A', 'B', 'C']), splitX(rows.t2, ['D', 'E']));
573
  } else {
574
    Object.assign(L, splitX(I, ['A', 'B', 'C']));
575
    const y = order[0] === 't2' ? I.y : I.y + I.h;
576
    Object.assign(L, splitX(R(I.x, y, I.w, 0), ['D', 'E']));
577
  }
578
  return L;
579
}
580
581
{ // d3 tag toggle
582
  const W = 640, H = 320, d = new Demo('d3', W, H), I = inner(W, H);
583
  let view2 = false;
584
  d.set(tagLayout(I, view2, ['t1', 't2']));
585
  d.button('View / hide tag 2 (D, E)', () => { view2 = !view2; d.go(tagLayout(I, view2, ['t1', 't2'])); });
586
}
587
588
{ // d3b tag reorder
589
  const W = 640, H = 320, d = new Demo('d3b', W, H), I = inner(W, H);
590
  let order = ['t1', 't2'], blocks = true;
591
  d.set(tagLayout(I, true, order));
592
  d.button('Swap tag order', () => { order = [order[1], order[0]]; d.go(tagLayout(I, true, order), blocks ? { blocks: { t1: ['A', 'B', 'C'], t2: ['D', 'E'] } } : {}); });
593
  d.check('rigid blocks', true, v => blocks = v);
594
}
595
596
{ // d4a orientation flip
597
  const W = 640, H = 300, d = new Demo('d4a', W, H), I = inner(W, H);
598
  let rows = false;
599
  const L = () => rows ? splitY(I, ['A', 'B', 'C']) : splitX(I, ['A', 'B', 'C']);
600
  d.set(L());
601
  d.button('Flip orientation', () => { rows = !rows; d.go(L()); });
602
  d.check('naive', false, v => d.naive = v);
603
}
604
605
{ // d4b grow both axes
606
  const W = 640, H = 300, d = new Demo('d4b', W, H), I = inner(W, H);
607
  let wide = false;
608
  const L = () => {
609
    const r = splitY(I, ['top', 'bot'], wide ? [7, 3] : [1, 1]);
610
    return { ...splitX(r.top, ['A', 'B'], wide ? [7, 3] : [1, 1]), ...splitX(r.bot, ['C', 'D']) };
611
  };
612
  d.set(L());
613
  d.button('Grow A in both directions', () => { wide = !wide; d.go(L()); });
614
}
615
616
{ // d5 lanes
617
  const W = 640, H = 300, d = new Demo('d5', W, H), I = inner(W, H);
618
  let order = ['A', 'B', 'C', 'D'];
619
  const L = () => splitX(I, order);
620
  d.set(L());
621
  d.button('Swap first two', () => { order = [order[1], order[0], ...order.slice(2)]; d.go(L()); });
622
  d.button('Rotate', () => { order = [...order.slice(1), order[0]]; d.go(L()); });
623
  d.button('Reverse', () => { order = [...order].reverse(); d.go(L()); });
624
  d.button('Reset', () => { order = ['A', 'B', 'C', 'D']; d.go(L()); });
625
}
626
627
{ // d6 interrupts
628
  const W = 640, H = 260, d = new Demo('d6', W, H, { graph: true }), I = inner(W, H);
629
  const targets = [
630
    () => splitX(I, ['A', 'B', 'C']),
631
    () => splitX(I, ['C', 'A', 'B']),
632
    () => splitX(I, ['A', 'B', 'C'], [3, 1, 1]),
633
    () => splitX(I, ['B', 'C', 'A']),
634
    () => ({ ...splitX(I, ['A', 'C'], [2, 1]), B: R(I.x + I.w * 0.66, I.y + I.h, I.w * 0.34, 0) }),
635
  ];
636
  const withB = L => { if (!L.B) L.B = R(I.x, I.y, 0, 0); return L; };
637
  let idx = 0;
638
  d.set(withB(targets[0]()));
639
  const next = () => { idx = (idx + 1) % targets.length; d.go(withB(targets[idx]())); };
640
  d.button('Next target', next);
641
  d.button('Storm (8 rapid interrupts)', () => {
642
    let n = 0;
643
    const fire = () => { next(); if (++n < 8) setTimeout(fire, 180 + Math.random() * 300); };
644
    fire();
645
  });
646
  d.check('match velocity', true, v => d.vmatch = v);
647
}
648
649
{ // d7 across outputs
650
  const W = 680, H = 260;
651
  const o1 = R(0, 0, 320, H), o2 = R(360, 0, 320, H);
652
  const d = new Demo('d7', W, H, { outputs: [o1, o2] });
653
  const I1 = inner(320, H, 0), I2 = inner(320, H, 360);
654
  let s1 = ['A', 'B'], s2 = ['C'];
655
  const L = () => ({ ...splitX(I1, s1), ...splitX(I2, s2) });
656
  d.set(L());
657
  d.button('Move B across', () => {
658
    if (s1.includes('B')) { s1 = s1.filter(x => x !== 'B'); s2 = ['B', ...s2]; } else { s2 = s2.filter(x => x !== 'B'); s1 = [...s1, 'B']; }
659
    d.go(L());
660
  });
661
  d.button('Move A across', () => {
662
    if (s1.includes('A')) { s1 = s1.filter(x => x !== 'A'); s2 = ['A', ...s2]; } else { s2 = s2.filter(x => x !== 'A'); s1 = ['A', ...s1]; }
663
    d.go(L());
664
  });
665
  d.button('Reset', () => { s1 = ['A', 'B']; s2 = ['C']; d.go(L()); });
666
}
667
668
function layoutTree(node, rect, visible, out) {
669
  if (typeof node === 'string') { out[node] = visible(node) ? rect : R(rect.x, rect.y, 0, 0); return; }
670
  const horiz = node.dir === 'row';
671
  const shown = node.kids.map(k => anyVisible(k, visible));
672
  const m = shown.filter(Boolean).length;
673
  const len = horiz ? rect.w : rect.h;
674
  const avail = len - G * Math.max(0, m - 1);
675
  let pos = horiz ? rect.x : rect.y, seen = 0;
676
  node.kids.forEach((k, i) => {
677
    if (!shown[i]) {
678
      const p = seen ? pos - G / 2 : pos;
679
      const r = horiz ? R(p, rect.y, 0, rect.h) : R(rect.x, p, rect.w, 0);
680
      layoutTree(k, r, () => false, out);
681
      return;
682
    }
683
    const size = avail / m;
684
    const r = horiz ? R(pos, rect.y, size, rect.h) : R(rect.x, pos, rect.w, size);
685
    layoutTree(k, r, visible, out);
686
    pos += size + G; seen++;
687
  });
688
}
689
function anyVisible(node, visible) { return typeof node === 'string' ? visible(node) : node.kids.some(k => anyVisible(k, visible)); }
690
691
{ // d8 one tree, tags filter
692
  const W = 640, H = 320, d = new Demo('d8', W, H), I = inner(W, H);
693
  const tagOf = { A: 1, B: 1, C: 1, D: 2, E: 2 };
694
  const view = { 1: true, 2: true };
695
  let mixed = false;
696
  const tree = () => mixed
697
    ? { dir: 'col', kids: [{ dir: 'row', kids: ['B', 'C'] }, { dir: 'row', kids: ['D', 'A', 'E'] }] }
698
    : { dir: 'col', kids: [{ dir: 'row', kids: ['A', 'B', 'C'] }, { dir: 'row', kids: ['D', 'E'] }] };
699
  const L = () => { const out = {}; layoutTree(tree(), I, id => view[tagOf[id]], out); return out; };
700
  d.set(L());
701
  d.button('Toggle tag 1 (A, B, C)', () => { view[1] = !view[1]; d.go(L()); });
702
  d.button('Toggle tag 2 (D, E)', () => { view[2] = !view[2]; d.go(L()); });
703
  d.button('Intersperse A between D and E', () => { mixed = !mixed; d.go(L()); });
704
}
705
706
document.getElementById('phaseMs').oninput = e => { PHASE_MS = +e.target.value; document.getElementById('phaseMsOut').textContent = PHASE_MS + ' ms'; };
707
document.getElementById('style').onchange = e => { STYLE = e.target.value; };
708
const loop = now => { for (const d of demos) d.frame(now); requestAnimationFrame(loop); };
709
requestAnimationFrame(loop);
710
</script>
711
</body>
712
</html>