# ArrayTrace

> ArrayTrace holds the steps of an array algorithm.

Page: https://fframes-kit.pages.dev/docs/computer-science/array-trace/
Cargo feature: `cs` (`fframes-kit = { version = "..", features = ["cs"] }`)

`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.

Gallery clip of `ArrayTrace`: https://fframes-kit.pages.dev/media/scenes/ArrayTrace-9e9cff9a.mp4

```rust
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() })
}
```