acacia
acacia copied to clipboard
milibopp
Geometric bounds of tree partition are not checked
The current tree constructors fail, when they are supplied with a set of points not contained within their partition.
- [ ] First of all, the construction of a (minimal) partition that contains a set of given points must be implemented. This could be wrapped in a subtrait of
Partition. - [ ] The tree needs to be equipped with constructors making use of the above. Examine, in how far the type system can be used to guarantee such a property.
If I understand you correctly, you would like to resolve this by constructing the minimal domain, instead of being able to specify the domain yourself?
I can imagine that this might be an issue for some use cases, where you want to use a specific domain, although I don't have a good example atm, besides maybe directly comparing your implementation to other codes.
Or do you think this would be a nonissue?
In the meantime an explicit check when inserting a point would be a workable alternative imo, but would be associated with a certain runtime cost. Do you think a safe and unsafe version of the constructor would be a good idea?
Btw, the same is true for checking for duplicates, but I'm not sure if this would not be better handled by supporting multiple leafs.
OK, I've benched the creation of a PureTree with explicit testing wheter the object is inside the tree domain, i.e.
pub fn new<I: Iterator<Item=O>>(iter: I, partition: P) -> PureTree<P, O> {
let mut tree = PureTree::empty(partition);
for object in iter {
if tree.partition.contains(&object.position()) {
tree.insert(object)
} else {
panic!("WAHHH")
}
}
tree
}
Without testing:
test pure_tree::test::pure_tree_quad_new_1000 ... bench: 217,655 ns/iter (+/- 14,512)
With testing:
test pure_tree::test::pure_tree_quad_new_1000 ... bench: 220,087 ns/iter (+/- 56,874)
The difference doesn't seem to be significant, but it might be worthwhile to test other cases.
Looks like the performance penalty is negligible. No need to introduce an unsafe API for one percent performance gain imho. The check you are proposing is more about improving error reporting. And yes, that's worthwhile doing, I didn't even consider that at the beginning.
If you want to merge that, I would suggest changing new to return something like a Result<PureTree<P, O>, ConstructionError>, because that can be caught & handled if necessary.
Regarding your question about the minimal domain: the current API takes the list of objects and the partition. This may be inconvenient, as it can cause a runtime error, when you don't care about the partition being a particular fixed value or simply don't know what it is.
To avoid that, constructing a partition that forms an outer hull around the list of objects (for a given type of partition supporting this → subtrait) allows a safe tree construction for arbitrary data known only at runtime. And that function could return a PureTree directly, no Result required.
The error type is still a bit barebones, i.e. it isn't a real Error yet... But besides that you could already review the rest.
On that note, would you reexport error types?
Why would it have to be anything more than a barebones enum? And what precisely do you mean by re-export?