georust / rstar

R*-tree spatial index for the Rust ecosystem
https://docs.rs/rstar
Apache License 2.0
410 stars 68 forks source link

Provide `retain` function for mutable selection iterators #76

Closed lehmanju closed 3 years ago

lehmanju commented 3 years ago

Iterating over a subset of RTree elements, modifying some elements and potentially removing some is not possible efficiently at the moment.

A retain function as for Vec for an RTree would simplify this dramatically. Basically, after applying a selection function, i.e. selecting all elements in an envelope, that contains a mutable reference to its elements, applying a modification function afterwards would allow efficient tree modifications without additional cloning.

Currently, one would first select all elements in an envelope, then iterate over them, modifiying some and cloning those that need to be deleted. After the iterator has finished, the elements marked for deletion are removed one by one.

lehmanju commented 3 years ago

An alternative would be to provide a remove_in_envelope function that returns all elements, then modify and afterwards insert the remaining elements. But because algorithm and the iterator types are private one would need to write a custom SelectionIterator and remove all elements one by one via remove_with_selection_function.

Stoeoef commented 3 years ago

I agree, a retain function seems like a useful and idiomatic addition.

rmanoka commented 3 years ago

Closed by #77