One descent, and the count that falls out of it

One descent, and the count that falls out of it

The walk for "m" in a wavelet tree over 2,048 characters, asked for the first 400 positions. At every level the walk computes one of the two child counts, because that is how it moves to the next level. Where the code says "go right", everything that went left is a smaller symbol — the leaves are in the alphabet's order — and the number of them is the difference between the position and the count already computed. Adding those up gives 240, which is exactly what 21 separate ranks report, and it costs 5 bit-vector operations rather than 105.

Drawn at 700 × 406, wide on the page. Everything above is what compound-walk returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

4 essays call compound-walk. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.