HasNext() advances iterators position

[MadsRC]

Writing integration testing for a code-base that uses this wonderful project, I ran across behavior that runs counter to what the documentation says. I am unsure if this is "working as intended" (in which case the docs most likely wrong) or if it is bug.

The documentation for the Iterator interfaces clearly states that calling Next() advances the iterators position. While the HasNext() documentation states that one should be careful to call HasNext() before calling Next(), I would still argue that the wording of the docs for Next() indicates that one should not expect HasNext() to advance the position of the iterator - otherwise you'd advance the iterator twice when calling HasNext() followed by Next().

The following piece of code reproduces the issue:

package main

import (
	"fmt"

	art "github.com/plar/go-adaptive-radix-tree/v2"
)

func main() {
	// Initialize a new Adaptive Radix Tree
	tree := art.New()

	// Insert key-value pairs into the tree
	tree.Insert(art.Key("apple"), "A sweet red fruit")
	tree.Insert(art.Key("banana"), "A long yellow fruit")
	tree.Insert(art.Key("cherry"), "A small red fruit")
	tree.Insert(art.Key("date"), "A sweet brown fruit")

	iter := tree.Iterator()
	_ = iter.HasNext()
	_ = iter.HasNext()
	_ = iter.HasNext()
	_ = iter.HasNext()
	n, _ := iter.Next()
	fmt.Printf("%+v\n", string(n.Key()))
}

The output of the above is date.

Furthermore, calling Next() does not seem to actually advance the pointer as evident by the following piece of code:

package main

import (
	"fmt"

	art "github.com/plar/go-adaptive-radix-tree/v2"
)

func main() {
	// Initialize a new Adaptive Radix Tree
	tree := art.New()

	// Insert key-value pairs into the tree
	tree.Insert(art.Key("apple"), "A sweet red fruit")
	tree.Insert(art.Key("banana"), "A long yellow fruit")
	tree.Insert(art.Key("cherry"), "A small red fruit")
	tree.Insert(art.Key("date"), "A sweet brown fruit")

	iter := tree.Iterator()
	n, _ := iter.Next()
	fmt.Printf("%+v\n", n)
	n, _ = iter.Next()
	fmt.Printf("%+v\n", n)
	_ = iter.HasNext()
	n, _ = iter.Next()
	fmt.Printf("%+v\n", string(n.Key()))
	n, _ = iter.Next()
	fmt.Printf("%+v\n", string(n.Key()))
}

The output of this block is:

<nil>
<nil>
apple
apple

[plar]

Hmm, do you mind to check it with v1? Just remove v2 from the import. It looks like a regression, I can't check it right now but I will do it when I have access to my computer.

[plar]

@MadsRC Thanks for catching this! You’re right: HasNext() shouldn’t advance the iterator, and I agree it was misleading.

The code works fine if you use it like this:

it := tree.Iterator()
for it.HasNext() {
    leaf, _ := it.Next()
    // do something
}

But relying on that behavior isn’t clean, and HasNext() SHOULD BE idempotent without side effects.
I’ve fixed it to align with the docs, and now calling HasNext() multiple times won’t advanced the iterator. See #47.

I also added tests to make sure this won’t break again.

Appreciate the detailed report! Let me know if you hit anything else.

[plar]

@MadsRC v2.0.3 has been released.

[MadsRC]

@plar thank you, that was a quick turnaround ;)