Closed snowmead closed 8 months ago
@cheme
The modification for iterating backward seems straightforward to me.
However, I believe adding this behaviour in a standard iterator is unintuitive for library users.
Additionally, iterating backward with a single cursor might prematurely end the iteration when it reaches the back of the trie.
That's a valid concern. It could potentially be addressed by always including the root node or prefix node in the crumb list. Yet, I am uncertain whether the change justifies the effort.
IMHO I don't think it does. I believe having separate structs for explicit iteration in both directions enhances code clarity. It also provides a better understanding of the behavior of standard iterator structs compared to double ended iterator structs.
I've implemented modifications based on our discussion (the unit test demonstrates this):
increment
to step
.TrieDB
(added functions). I'm unsure if a more elegant or generic solution is desired.fwd
bool parameter.Still need to add a bunch of tests.
Small note (not something that needs change right now), I think that the raw node iter can return on a status At, then if iterating in different direction we may not have the right next node : eg entering a branch backward then state is At then calling iterator forward and then state become AtChild(0) when we should have exit. This is not an issue right now as we don't expose different iteration direction, but at some point I will probably switch to state At(direction: bool) to be able to support this case.
Closes https://github.com/paritytech/trie/issues/164
Enables bidirectional iteration by implementing the
DoubleEndedIterator
for all iterator types.New double ended iterator structs:
TrieDBDoubleEndedIterator
TrieDBNodeDoubleEndedIterator
TrieDBKeyDoubleEndedIterator
FatDBDoubleEndedIterator
Internal iteration methods now accept a
fwd
bool flag to conditionally traverse a trie backwards or forwards (non exhaustive list).TrieDBRawIterator::next_raw_item
TrieDBRawIterator::seek
Crumb::increment
(renamed toCrumb::step
to better convey its behaviour)Modifies
next_raw_item
to return middle node (i.e. a node containing child nodes) in reverse order based on iteration direction. Middle node is returned last when iterating backwards, mirroring forward iteration behaviour.Adds new
AftExiting
status to pop crumb after returning it inExiting
status for backward iteration.Library users can create one of these iterators from a
TrieDB
instance by calling the publicTrieDB::into_*
methods.