//! Insertion sort: neighbours compared, and swapped while the left is larger. //! //! 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. const anim = @import("anim"); const canim = @import("canim"); const recordings = @import("recordings"); pub const background = canim.background; pub const scene = anim.Live(frame, struct {}); fn frame(s: *anim.Frame) void { const rec = canim.open(recordings.sort); 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; while (rec.next(.over, rec.next(.over, start)) < rec.call("swap", 0).enter) start = rec.next(.over, start); 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. 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 }); 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); } }.step; 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))); // 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.close(s); }