Overwrite is legal because write lags read
Updated
w ≤ i, so a[w] was already read, or is the current i. Overwriting a dropped slot cannot destroy unread data.
What to focus on
If w ever passed i, a write would clobber a value i has not read. The lag is what makes in-place compact safe.
Worked examples
overwrite a zero
a = [0, 1, 0, 9], i=1 w=0- a[0] already scanned as 0
- write 1 onto it
Result: safe, a = [1, 1, 0, 9]
overwrite a dropped 1
a = [4, 1, 9, 1], i=2 w=1- a[1] was the dropped 1
- write 9 onto it
Result: safe, a = [4, 9, 9, 1]
w==i keep
a = [4, 1, 9], i=1 w=1- write a[1] onto a[1]
- no unread slot lost
Result: self-assign, still w ≤ i
Try it
Write compact(a). a is an array of integers. i is the read index. w is the write index. w ≤ i at every write. Assert w ≤ i before every write. Return the compacted array. On [0, 1, 0, 9] and on [4, 1, 9, 1].
a is nonempty. w ≤ i at every write.