ArrayTrace

ArrayTrace holds the steps of an array algorithm. Each ArrayStep has the values after the step, the cells it compared, where each cell came from when it moved cells (moved), the cells in their final place, named pointers, the range still in play, a found cell and a short note. Step 0 is the input. The recorders:

• bubble, insertion, merge (bottom up, merged in place, so the array holds every value once at every step) and quick (Lomuto’s partition, the last value of a range as pivot);
• binary_search(sorted, target), with lo, mid and hi pointers.

ArrayTrace::new takes steps of your own. ArrayTrace::record(&values) starts an ArrayRecorder with manim-dsa’s MArray operations at the end of the array: append(value) adds a cell after the last one and pop takes the last one off, one step each with a note; note replaces the last note and finish gives the trace. at(seconds, step_time) samples a trace, totals counts its comparisons and moves, and max_len is the most cells of any step.

Gallery scene: ArrayTrace shows an append followed by two pops.

ArrayTrace 5 sPlayUnmuteCopy render command

use fframes_kit::prelude::*;

let trace = ArrayTrace::bubble(&[3, 1, 2]);
assert_eq!(trace.result(), [1, 2, 3]);
// two comparisons in the first pass, one in the second, and two values moved
assert_eq!(trace.totals(), (3, 2));

let search = ArrayTrace::binary_search(&[2, 5, 8, 12, 16, 23], 12);
assert_eq!(search.steps().last().unwrap().found, Some(3));

let grown = ArrayTrace::record(&[4, 7]).append(2).pop().pop().finish();
assert_eq!(grown.result(), [4]);
assert_eq!((grown.max_len(), grown.steps()[1].note.as_str()), (3, "append 2"));

fn draw<'a>(ui: &mut Ui<'a, '_, '_>, trace: &'a ArrayTrace) -> Svgr<'a> {
    ui.show(ArrayView { trace: Some(trace), step_time: 1.0, ..ui.defaults() })
}