add ability to remove item #36
Conversation
src/kdtree.rs
Outdated
| self.left.as_mut().unwrap().remove(point, data)?; | ||
| } | ||
| } | ||
| self.size -= 1; |
There was a problem hiding this comment.
this always decreases the size, what if there's no match?
There was a problem hiding this comment.
good point, I'll move the decrement to here "if let (Some(points), Some(bucket)) = (self.points.take(), self.bucket.take())"
src/kdtree.rs
Outdated
| @@ -288,6 +288,25 @@ impl<A: Float + Zero + One, T, U: AsRef<[A]>> KdTree<A, T, U> { | |||
| } | |||
| } | |||
|
|
|||
| pub fn remove(&mut self, point: &U, data: &T) -> Result<(), ErrorKind> { | |||
There was a problem hiding this comment.
what's the targeted use case for removing a node?
- by value(
data) - by coordinates(
point) - OR or BOTH relationship when both value and coordinates are provided
There was a problem hiding this comment.
I assumed since you need the coordinate and value to create the tree, it would be reasonable to require them both to remove an item. It looked like since the values are stored separately that it would be difficult to remove them without having both.
There was a problem hiding this comment.
it seems 1 & 2 are also quite common use case
- e.g. add/remove/update entity's location when
datarepresents entity id/uuid - e.g. when location(
point) is actually the primary key for the use case
it's okay if we just want to implement 3's BOTH(AND) relationship but we have to make sure nodes are removed only when both point and data match the parameters
src/kdtree.rs
Outdated
| self.points = Some(points.into_iter().filter(|x| x != point).collect()); | ||
| self.bucket = Some(bucket.into_iter().filter(|x| x != data).collect()); | ||
| } else { | ||
| if self.right.is_some() { |
There was a problem hiding this comment.
can we leverage split dimension and value similar to binary search?
src/kdtree.rs
Outdated
| return Err(err); | ||
| } | ||
| if let (Some(points), Some(bucket)) = (self.points.take(), self.bucket.take()) { | ||
| self.points = Some(points.into_iter().filter(|x| x != point).collect()); |
There was a problem hiding this comment.
trying to understand the safety of this implementation, what if point matches node A but data matches node B?
There was a problem hiding this comment.
If the incorrect point/data pair are passed in, there aren't any checks that they match. I didn't think there was a way to validate that. If they indices match we could use that, but I didn't think that was always true.
There was a problem hiding this comment.
related to the use case comment - iirc the points and buckets match by index; then we should be able to iterate by index to ensure both point and data match the input
|
should have fixed most of the issues you brought up now, except binary search. Would you prefer if a point that isn't in the tree is passed to remove that it return an error? Right now it just doesn't remove anything. |
tests/kdtree.rs
Outdated
| kdtree.add(&item3.0, item3.1).unwrap(); | ||
| kdtree.add(&item4.0, item4.1).unwrap(); | ||
|
|
||
| kdtree.remove(&&[1f64], &2).unwrap(); |
There was a problem hiding this comment.
if we're targeting use case 3(AND), maybe kdtree.remove(&item1.0, item2.1) would cover more scenarios?
|
thanks for the update - followed up on comments re: return value - it'd be better if to indicate whether there're matches(possible to have duplicates) or not
|
src/kdtree.rs
Outdated
| return Err(err); | ||
| } | ||
| if let (Some(mut points), Some(mut bucket)) = (self.points.take(), self.bucket.take()) { | ||
| let point_pos = points.iter().position(|x| x == point); |
There was a problem hiding this comment.
we could iterate by index to verify both point and data match
also current implementation short-circuits(position), which doesn't seem to handle the scenario with more than one match
|
I updated to match multiple values and return the number of items removed. If you'd like I can also add options to remove by data or point, instead of both. |
|
Thanks for the PR! If you'd like to, feel free to iterate on binary-search(efficiency) and remove by data or point(functionality). |
From limited testing this seems to work well. Had to add a partialeq constraint to filter data and points. I don't rebalance the tree, just remove the items, not sure if that would be helpful.
Fixes #30