diff options
Diffstat (limited to 'anim/scenes/sort.zig')
| -rw-r--r-- | anim/scenes/sort.zig | 100 |
1 files changed, 55 insertions, 45 deletions
diff --git a/anim/scenes/sort.zig b/anim/scenes/sort.zig index 82a99e1..81d55dd 100644 --- a/anim/scenes/sort.zig +++ b/anim/scenes/sort.zig @@ -1,11 +1,17 @@ -//! Insertion sort: neighbours compared, and swapped while the left is larger. +//! Insertion sort as its blocks: the graph of `sort` in the band (the +//! `blocks` lens), the disassembly its view over the state column, the +//! source alone in the program column; on the map the same graph with its +//! rows. //! -//! How it moves (design/motion.md): it opens where `i` has reached 12, the -//! first value out of order; the compare is walked (its two cells framed: -//! the swap's anticipation), the caption about the swap stands two -//! seconds before it, and the swap is two flights on arcs, the second a -//! little behind the first, each cell struck as its value lands. The next -//! trips are a run, the long middle a sprint, and the last swap is walked. +//! How it moves (design/motion.md, "A block left"): it opens where `i` has +//! reached 12, the first value out of order. One trip round the inner +//! loop is walked a block at a time: each block's instructions a cascade +//! onto its last row, then `leave` along the edge that row takes (the +//! compare's chips framed, the edge drawn gold, the mark along it, the +//! target's count struck), and `turn` up the inner loop's lane. The next +//! trip is a run; the long middle is a sprint on the map (`surface`, the +//! gold going block to block, `dive`); the last value's trip is walked +//! again, and the way out run. const anim = @import("anim"); const canim = @import("canim"); const recordings = @import("recordings"); @@ -15,52 +21,56 @@ pub const scene = anim.Live(frame, struct {}); fn frame(s: *anim.Frame) void { const rec = canim.open(recordings.sort); + const graph = canim.graph; const t = canim.theme.time; - const sort = rec.call("sort", 0); // The `while`, about to compare 31 with 12: the stop before the one that calls swap. - var start = sort.enter; + var start = rec.call("sort", 0).enter; while (rec.next(.over, rec.next(.over, start)) < rec.call("swap", 0).enter) start = rec.next(.over, start); + // The inner loop's test (`j > 0`): where each of its trips begins. + const test_pc = rec.register(start, "rip"); var at = canim.cursor(s, rec, start); - // The array is the idea; `i` and `j` are memory, and strike a beat before their tags slide. - at.levels = .{ .idea = .data, .follow = t.quick, .source_rows = 10 }; - // Its last compare: nothing larger is left of 20. + at.levels = .{ .fire = .disasm, .source_rows = 20 }; const last = rec.call("swap", 9); - const end = rec.next(.over, rec.next(.over, last.exit.?)); - at.journey(.over, end); - // The context is the instrumented program's: its registers are unmarked. - const split = canim.layout.split.subject; - const ctx = canim.context(s, at, .{ .split = split }); - // The lens: the array as cells, and the two indices that walk it. - const cells = canim.array(s, .{ .cursor = at, .stage = ctx.stage, .variable = "a", .indices = &.{ "i", "j" }, .focus = true }); - ctx.map.add(s, canim.Array{ .cursor = at, .stage = ctx.map.stage, .variable = "a", .indices = &.{ "i", "j" } }); + // The last value's trip: from its test, before the compare that leads to the last swap. + var last_trip = last.enter; + while (rec.register(last_trip, "rip") != test_pc) last_trip -= 1; + at.journey(.over, rec.call("sort", 0).exit.? - 1); + const ctx = canim.context(s, at, .{ .split = canim.layout.split.blocks, .graph = true }); + const blocks = canim.add(s, graph.Blocks{ .cursor = at, .stage = ctx.stage, .focus = true }); var says: canim.Narrator = .{}; - // A swap, start to finish, as one step of sort(): over the call. - const swap = struct { - fn step(c: canim.Cursor, frame_: *anim.Frame, r: *canim.Recording) void { - c.step(frame_, r.next(.over, c.moment(frame_)), canim.Array.swap, canim.Array.swap.total); + const joins = ctx.ties(s); + // A block at a time: its rows a cascade onto its last, then the edge it takes. + const block = struct { + fn walk(c: canim.Cursor, f: *anim.Frame) void { + graph.toEnd(c, f); + graph.leave(c, f); } - }.step; + }.walk; - const joins = ctx.ties(s); - // The cells come in beside their bytes, one by one. - ctx.establish(s, .{ ctx.clock, ctx.registers, ctx.stack, ctx.source, ctx.disasm, cells, joins }, 8); - says.line(s, "`i` walks right. Everything left of it is in order,\nand 12 is not yet in its place."); - // The compare: both cells framed. It is the swap's anticipation. - at.walk(s, .over, rec.next(.over, start)); - says.line(s, "While the one on the left is larger, they trade places,\nand `j` follows the smaller value down."); - // Arcs: the two values fly past each other, one over, one under. The - // whole context stays: the swap is bytes changing, then cards moving. - swap(at, s, rec); - at.walk(s, .over, rec.next(.over, at.moment(s))); + canim.establish(s, .{ ctx.clock, ctx.registers, ctx.stack, ctx.source, ctx.disasm, blocks, joins }); + says.line(s, "`sort` as its blocks: two loops. `j > 0`, so its `jle`\nis not taken, and the inner loop goes on to its compare."); + block(at, s); + says.line(s, "31 > 12: `setg` leaves 1, and `jne` takes the swap."); + block(at, s); + block(at, s); + says.line(s, "The swap and `j--`; then the inner loop turns,\nback up to `j > 0`."); + block(at, s); + + // Pacing: the next trip at a run; then the long middle on the map, at a sprint. + says.line(s, "Once more at a run: 17 > 12, a second swap."); + at.hurry(s, .over, rec.lineMoment(12, rec.call("swap", 1).exit.?), .{ .settle = false }); + says.line(s, "The rest on the map: the gold goes block to block,\nand the counts grow with every trip."); + ctx.map.surface(s); + at.hurry(s, .over, last_trip, .{ .pace = t.sprint, .from = t.run }); + ctx.map.dive(s); - // Pacing: the same again, so at a run; then the long way 5 has to go, - // at a sprint; slowing for the last swap. - says.line(s, "And so on: each value is carried left\nuntil the one before it is not larger."); - at.hurry(s, .over, rec.call("swap", 3).enter - 1, .{ .to = t.run, .settle = false }); - at.hurry(s, .over, last.enter - 1, .{ .pace = t.sprint, .from = t.run }); - says.line(s, "The last swap: 20 goes one place left, past 26."); - swap(at, s, rec); - at.walk(s, .over, end); - says.line(s, "Nothing larger is left of 20. The array is sorted."); + says.line(s, "The last value, 20: 26 > 20, so `jne` takes the swap."); + block(at, s); + block(at, s); + block(at, s); + says.line(s, "The swap, and the inner loop turns once more."); + block(at, s); + says.line(s, "17 > 20 is false: the inner loop is done, and with `i` at 8\nso is the outer. The array is sorted."); + at.hurry(s, .over, rec.call("sort", 0).exit.? - 1, .{}); says.close(s); } |
