Demo
Adds 30 numbers with the weighted fold, each weighing its magnitude, and draws every move. A value sits on the stack where the run two below it outweighs it; otherwise the two runs beneath it merge first, so a heavy value is never merged on arrival and equal values carry like a binary counter.
Each line is one state, the runs over the values they cover: underscores join the two runs about to merge, a line ending in | is a push complete, lines ending in . are the fold at the end, and the last line is the sum.
Input:
11 25 18 19 16 20 23 27 13 9 21 17 3 5 1 24 26 29 22 28 7 12 6 14 10 2 4 8 30 15
Merge tree:
11 |
11 25 |
11_25 18
36 18 |
36 18 19 |
36 18 19 16 |
36 18 19_16 20
36 18___35 20
36 53 20 |
36 53 20 23 |
36 53 20_23 27
36_____53 43 27
89 43 27 |
89 43 27 13 |
89 43 27 13 9 |
89 43 27 13__9 21
89 43 27 22 21 |
89 43 27 22 21 17 |
89 43 27 22 21 17 3 |
89 43 27 22 21 17 3 5 |
89 43 27 22 21 17 3 5 1 |
89 43 27 22 21 17 3 5__1 24
89 43 27 22 21 17 3___6 24
89 43 27 22 21 17_____9 24
89 43 27 22__21 26 24
89 43__27 43 26 24
89 70 43 26 24 |
89 70 43 26_____24 26
89 70 43 50 26 |
89 70 43 50 26 29 |
89 70 43 50 26 29 22 |
89 70 43 50 26 29 22 28 |
89 70 43 50 26 29 22 28 7 |
89 70 43 50 26 29 22 28 7 12 |
89 70 43 50 26 29 22 28 7 12 6 |
89 70 43 50 26 29 22 28 7 12__6 14
89 70 43 50 26 29 22 28 7___18 14
89 70 43 50 26 29 22_28 25 14
89 70 43 50 26_29 50 25 14
89 70 43__________50 55 50 25 14
89__________70 93 55 50 25 14
159 93 55 50 25 14 |
159 93 55 50 25 14 10 |
159 93 55 50 25 14 10 2 |
159 93 55 50 25 14 10 2 4 |
159 93 55 50 25 14 10 2__4 8
159 93 55 50 25 14 10 6 8 |
159 93 55 50 25 14 10 6____8 30
159 93 55 50 25 14_10 14 30
159 93 55 50 25 24_____14 30
159 93 55 50 25__________38 30
159 93 55____50 63 30
159 93 105 63 30 |
159 93 105 63 30 15 |
159 93 105 63 30_15 .
159 93 105 63_____________45 .
159 93_______________105 108 .
159 198______________________________108 .
159__________________________________________306 .
465