summaryrefslogtreecommitdiff
path: root/anim/scenes/sort.zig
blob: c9b5b07ff8b6de073b825b3e84bd675eb485bb2a (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//! 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);
}