search

sdd / kiddo

Kiddo
Apache License 2.0
79 stars 13 forks source link

Iterate over trees #135

Closed clbarnes closed 5 months ago

clbarnes commented 5 months ago

Resolves #134.

Allows iteration, in arbitrary order, over points and indices in trees.

clbarnes commented 5 months ago

To highlight/ head off a minor quibble: for those trees which allow adding of points, the argument order is (point, index); this iterator yields (index, point). I chose the latter order for the marginal ergonomics gain if someone wants to .collect::<HashMap<T, [A; K]>>.

clbarnes commented 5 months ago

This implementation allocates a vecdeque for each leaf (and, of course, copies all the data). Instead, each leaf could be made iterable so that the TreeIter can re-use the same VecDeque, but that means implementing more things for each tree type.

clbarnes commented 5 months ago

Making the leaves iterable would mean that the iterable trait for trees would also have to be generic over the leaf type, which I think would mean adding the leaf type as an associated type and then possibly rely on GATs. So the method just takes a &mut Vec to write into to avoid those allocations. This changes the iteration order, but it's documented as being arbitrary so that doesn't matter. It was previously leaves left to right, items left to right; now it's leaves left to right, items right to left.

As this buffer is constrained to the bucket size, we could feasibly cut down the remaining allocations with a {small/tiny/array}vec, but that doesn't seem like a worthwhile optimisation at this point.

sdd commented 5 months ago

Hi Chris,

I've been off the grid for a few weeks and only just seen this - thanks a lot, this is a great addition to the library - much appreciated!

sdd commented 5 months ago

Looks like there are some issues that need fixing on master before this can get merged. My train journey was not quite long enough to get all these fixed - I'll carry on with it on the train home later :-)

sdd commented 5 months ago

It seems like the removal of stdsimd in nightly has caused some repercussions in kiddo's dependencies that will need to be resolved before we can merge this, as kiddo is currently broken in master on nightly. This should get resolved in a few days so we can get your changes merged 👍🏼

sdd commented 5 months ago

Closing as these changes were merged in https://github.com/sdd/kiddo/pull/141