summaryrefslogtreecommitdiff
path: root/anim/scenes/sort.zig
blob: 81d55ddfc0961021da9f102e286e2369fd6dab3d (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
66
67
68
69
70
71
72
73
74
75
76
//! 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, "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");

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 graph = canim.graph;
    const t = canim.theme.time;
    // The `while`, about to compare 31 with 12: the stop before the one that calls swap.
    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);
    at.levels = .{ .fire = .disasm, .source_rows = 20 };
    const last = rec.call("swap", 9);
    // 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 = .{};
    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);
        }
    }.walk;

    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);

    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);
}