Fix OrdMap removal/range logic #154
Conversation
Pulling predecessor/successor must be ruled out before merge can be done
src/ord/map.rs
Outdated
| #[test] | ||
| fn range_iter_big() { | ||
| use std::ops::Bound::Included; | ||
| let n = 25_000; // enough for a sizeable 3 level tree |
There was a problem hiding this comment.
Could you have this number depend on crate::nodes::btree::NODE_SIZE?
Something like NODE_SIZE * NODE_SIZE * 6?
There was a problem hiding this comment.
Yes, I hesitated because it was not public. But it can be solved with a pub(crate)
|
@bodil friendly ping. The crates.io version of OrdMap is significantly impaired without these fixes. |
It must pull the highest or lowest item in the subtree and not just from the next level
| } | ||
| } | ||
| path | ||
| } |
There was a problem hiding this comment.
This fix seems to be needed in lookup_prev and lookup_next as well. Currently, OrdMap::get_prev and OrdMap::get_next may return None when they are not supposed to.
There was a problem hiding this comment.
The problem I described above can be demonstrated using a test case similar to the one in the below:
assert_eq!(omap.range(..=i).next_back(), omap.get_prev(&i));
assert_eq!(omap.range(i..).next(), omap.get_next(&i));There was a problem hiding this comment.
Indeed. Good observation.
There was a problem hiding this comment.
@arthurprs Any chance to update this PR to address it?
There was a problem hiding this comment.
Not right now.
The author seemingly abandoned this project so eventually I switched to https://github.com/orium/rpds instead. It has an arguably worse API but at least it's correct/maintained.
|
@bodil Any chance to review this PR and possible publish a new release of |
|
Ah, I should have taken a closer look at this PR yesterday... I redid a chunk of it in my fork, but this PR is mostly nicer, so I'll cherry-pick it and add the missing bits in |
|
Merged. Sorry it took a while. I'll tag a bugfix release shortly. |
Pulling predecessor/successor must be ruled out before merge can be done.
btree::Node::path_{next/prev} weren't considering going up to find next/prev.
Might fix #124
Fix #152
Fix #143