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

From: Andreas Politz <[email-masked]>
Date: Tue, 4 Oct 2022 12:50:54 +0200

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 <[email-masked]>:
> 
> Andreas Politz <[email-masked]> 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,