BUG: BptreeMap range return wrong result

[Erigara]

Here is minimal example:

    #[test]
    fn test_bptree2_map_rangeiter_2() {
        let map = BptreeMap::from_iter([("ca", ()), ("cb", ()), ("a", ())]);

        let r = map.read();
        assert!(r.range("b"..="bb").count() == 0); // return 2
    }

[Erigara]

I can work on this one

[Firstyear]

Sorry I didn't get to look at this yet. I was planning to investigate this week but if you have a look first that would be great. Thanks!

[Erigara]

So unfortunately my previous fix was not enough, there is more edge cases like:

#[test]
fn test_bptree2_map_rangeiter_3() {
    let map = BptreeMap::from_iter([0, 1, 2, 3, 4, 5, 6, 8].map(|v| (v, ())));

    let r = map.read();
    assert!(r.range((Bound::Excluded(6), Bound::Included(7))).count() == 0);
    assert!(r.range((Bound::Excluded(6), Bound::Excluded(8))).count() == 0);
}

From what i debugged so far it happens when two values are on the edges of adjacent leaves and when we are adjusting leaf iterators to the bounds left itrator became ahead of right iterator.

Case 1:

range: (6, 8)

         leaf 1        leaf 2
[0, 1, 2, 3, 4, 5, 6] [8, ...]
                   ^   ^
before:            L   R
after:             R   L

Case 2:

range: (6, 7]

         leaf 1        leaf 2
[0, 1, 2, 3, 4, 5, 6] [8, ...]
                   ^   ^
before:            LR  |
after:             R   L

I will try to figure out how to check this condition.

[nxsaken]

Has this been resolved/published? @Erigara

[Firstyear]

I believe it is resolved, I need to publish a new update.