IterG.Prev returns true after iterating beyond the end of the tree #46
Description
Hi!
Thank you very much for this project!
I stumbled upon what I would consider a minor bug in the IterG type (I've not checked the other iterators).
If the iterator has previously tried to iterate beyond one end by calling Last, followed by Next immediately after populating the tree, and then iterates in reverse by calling Prev beyond the far end of the tree, Prev will begin returning true even though it as reached the start of the tree.
I wrote a test to describe the problem, the test passes running go 1.22.6 on linux/amd64.
Issue is not urgent for me, I had some quite aggressive tests that caught it whilst consuming your library and I can label certain behaviour as undefined without impacting our users. I thought it was worth raising here though as it caused a bit of head-scratching (I assumed my code was responsible at first).
package iterator
import (
"fmt"
"testing"
"github.com/tidwall/btree"
)
func comparator(a, b int) bool {
return a < b
}
func requireTrue(value bool) {
if !value {
panic("expected: true, actual: false")
}
}
func requireFalse(value bool) {
if value {
panic("expected: false, actual: true")
}
}
func requireEqual(expected, actual int) {
if expected != actual {
panic(fmt.Sprintf("expected: %v, actual: %v", expected, actual))
}
}
func TestBTreeBug(t *testing.T) {
tree := btree.NewBTreeG(comparator)
tree.Set(1)
tree.Set(2)
tree.Set(3)
iterator := tree.Iter()
ok := iterator.Last()
requireTrue(ok)
// The presence of this `Next` call causes the bug to surface later
ok = iterator.Next()
requireFalse(ok)
ok = iterator.Prev()
requireTrue(ok)
v := iterator.Item()
requireEqual(2, v)
ok = iterator.Prev()
requireTrue(ok)
v = iterator.Item()
requireEqual(1, v)
ok = iterator.Prev()
requireFalse(ok)
// Bug starts here!
//
// Notes:
// 1. I expected all the `Prev` calls beyond this point to return `false`.
// 2. If you comment out the `Next` call noted towards the top of the function,
// the `Prev` calls all return `false` as I expected.
// 3. The `Item` calls are included for descriptive reasons only, I found them
// interesting, but much less so than the return value from `Prev`.
// 4. The 2, 1, 1; 2, 1, 1; pattern repeats as far as I bothered looking at.
ok = iterator.Prev()
requireTrue(ok)
v = iterator.Item()
requireEqual(2, v)
ok = iterator.Prev()
requireTrue(ok)
v = iterator.Item()
requireEqual(1, v)
ok = iterator.Prev()
requireFalse(ok)
v = iterator.Item()
requireEqual(1, v)
ok = iterator.Prev()
requireTrue(ok)
v = iterator.Item()
requireEqual(2, v)
}