summaryrefslogtreecommitdiff
path: root/anim/scenes/sort.zig
diff options
context:
space:
mode:
Diffstat (limited to 'anim/scenes/sort.zig')
-rw-r--r--anim/scenes/sort.zig63
1 files changed, 63 insertions, 0 deletions
diff --git a/anim/scenes/sort.zig b/anim/scenes/sort.zig
new file mode 100644
index 0000000..0f14269
--- /dev/null
+++ b/anim/scenes/sort.zig
@@ -0,0 +1,63 @@
+//! 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 = .{ .cpu = false, .idea = .data, .follow = t.quick, .source_rows = 8 };
+ // 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.beside;
+ const ctx = canim.context(s, at, .{ .split = split, .quiet = true });
+ // The lens: the array as cells, and the two indices that walk it.
+ const cells = canim.array(s, .{ .cursor = at, .box = split.lens, .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 = canim.ties(s, .{ .cursor = at });
+ canim.establish(s, .{ ctx.clock, ctx.source, ctx.disasm, ctx.registers, ctx.stack, ctx.backtrace, cells, joins });
+ 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.");
+ // The caption of the step the scene is about stands a second longer.
+ s.wait(t.caption_lead);
+ // Arcs: the two values fly past each other, one over, one under.
+ 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.
+ 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 });
+ swap(at, s, rec);
+ at.walk(s, .over, end);
+ says.line(s, "Nothing larger is left of 20. The array is sorted.");
+ s.wait(t.before_cut - t.caption_lead);
+}