bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful

[Andreas Politz]

My implementation seems to work. The correctness of the algorithm would follow 
from 

1. The Rb tree algorithm produces a tree with left <= root <= right,
2. the algorithm you’ve posted, and I’ve  adapted, produces an in–order of the 
tree and
3. the conditions guiding the traversal are correct, i.e. they don’t exclude 
matching intervals.

Since I believe these statements are true, I believe the algorithm is correct.

Andreas



> Am 03.10.2022 um 06:35 schrieb Gerd Möllmann <gerd.moellmann@gmail.com>:
> 
> Andreas Politz <mail@andreas-politz.de> writes:
> 
>> It seems to work, at least buffer-tests are passing.
> 
> "seems to work" is a bit weak.  Can we prove it?
> 
> I don't mean mathematically, but by reasoning like I tried in the
> comments in successor function I posted,