Keep a write pointer behind the read
Updated
i reads every index. w sits at the next slot that should receive a kept value. After each step w ≤ i.
What to focus on
[0, w) is kept. [w, i) is dropped junk. [i, n) is unread. w never runs ahead of i.
Worked examples
skip then write
a = [0, 1, 0, 9], keep nonzero, i=0 w=0- i=0 drop 0, w stays 0
- i=1 keep 1, write a[0], w=1
Result: w=1 behind i=1, a = [1, 1, 0, 9]
keep all
a = [4, 1, 9], keep all, i=0 w=0- i=0 write 4 at 0, w=1
- i=1 write 1 at 1, w=2
- i=2 write 9 at 2, w=3
Result: w tracks i+1, never lags
drop 1s
a = [4, 1, 9, 1], keep ≠ 1, i=0 w=0- i=0 write 4, w=1
- i=1 skip 1, w stays 1
- i=2 write 9 at 1, w=2
Result: w=2, i=2, lag is the skipped 1
Try it
Write compact(a). a is an array of integers. i is the read index. w is the write index. Keep-nonzero (or keep ≠ 1) is the rule: a function from a value to true or false is given. Walk i from 0. Assert w ≤ i always. Return the compacted prefix. Keep nonzeros on [0, 1, 0, 9]. Repeat keep ≠ 1 on [4, 1, 9, 1].
a is nonempty. The keep rule is a function from a value to true or false.