milibopp/acacia

A spatial partitioning and tree library in Rust.

acacia's Issues

Update to Rust 2018 edition

Make the demo example more readable

There's a lot of physics and complex syntax. This ought to be made a bit simpler to focus mainly on acacia's interface.

Builds fail at the moment, because nealgebra had a version bump

The dev-dependency on nalgebra has no version, so the new 0.3.0 crate is used. This creates a conflict. See pull request #72 for a fix.

Stack overflow when object is outside domain

Currently acacia causes a stack overflow, when particles outside of the domain are inserted into the tree, though I'm not 100% during which step it happens.

Checking objects whether they are inside the domain during construction is associated with a certain cost. Should there be additional "safe" functions, that do the check, or should this happen by default?

Merge associated data with tree implementation

Currently the associated data tree is generated from a bare tree. It might be sensible to generate an tree that only contains spatial information for things like neighbour search, thus it still makes sense to maintain this separation to some degree. However, it might also work to use () as the associated data type for this use case, probably providing some specialized constructors that do not require dummy closures to compute the associated data.

Merging these two types also has the advantage that the structure does not have to be copied. A interface specification should be drafted before implementing this.

Opinion on repartitioning

In-place updates of the tree structure when e.g. only some of the data has been changed, can be much faster (according to the GADGET paper atleast, haven't done benchmarks myself, but it seems plausible). The same should be true, when only some data is removed or later inserted.

Do you think that the current framework could be adapted to support such mutable operations?

Make the container for branch nodes an output type

Semantically the container is an output type of Node, as it makes little sense for users to require a specific kind of container. However, associated types need to be more stable first.

Use unboxed closures for queries

Currently the closure for recursion and callback passed to the query methods have to be wrapped inside another closure for each level of recursion. This is most likely a very inefficient implementation, see here for reference.

Unboxed closures are a bit experimental at the moment and the interface may become a little weird for the time being.

Integrate with Travis CI and Rust CI

Should be done.

Allow for separate tree and node structs

It may be useful to have separate tree and node structs in some implementations. The current trait infrastructure does not allow this.

Queries as iterators

Having the Node abstraction it should be possible to design the query methods in a slightly different way:

trait DataQuery<D> {
    fn query_data<'a>(&'a self, recurse: |&Self| -> bool) -> SomeIterator<&'a D>;
}

This is nicer as the current interface, as it allows the user to chain this with iterator adaptors instead of using a mutable state captured from the environment.

However, the implementation is certainly somewhat trickier. For instance, it is a bit awkward to generalize over SomeIterator<_> without higher-kinded types (which Rust 1.0 will not include). This is also mentioned under limitations in the associated types RFC rust-lang/rfcs#195. A workaround could look like this:

trait QueryableOwned<A> {
    type I: Iterator<A>;
    fn query_owned(self) -> I;
}

trait DataQuery<D> {
    fn query_data<'a>(&'a self, recurse: |&Self| -> bool) -> <&'a Self>::I
        where &'a Self: QueryableOwned<&'a D>
    {
        QueryableOwned::query_owned(self)
    }
}

Now one would have to implement QueryableOwned<&'a D> for &'a T, so that T can implement DataQuery<D>. This is a bit complicated, so I am not sure whether it is worth the effort.

On the other hand it may be possible that DataQuery<D> can be implemented generically for all T: AssociatedData<D> + Node<..>. In this case it would almost be reduced to an implementation detail.

RFC1214 warnings when compiling on nightly

These will soon turn into hard errors. You should insert a few : Sized bounds (to Subdivide and Node).

src/partition/mod.rs:15:5: 15:38 warning: the trait `core::marker::Sized` is not implemented for the type `Self` [E0277]
src/partition/mod.rs:15     fn subdivide(&self) -> Vec<Self>;
                            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/partition/mod.rs:15:5: 15:38 help: run `rustc --explain E0277` to see a detailed explanation
src/partition/mod.rs:15:5: 15:38 note: `Self` does not have a constant size known at compile-time
src/partition/mod.rs:15:5: 15:38 note: this warning results from recent bug fixes and clarifications; it will become a HARD ERROR in the next release. See RFC 1214 for details.
src/partition/mod.rs:15     fn subdivide(&self) -> Vec<Self>;
                            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/partition/mod.rs:15:5: 15:38 note: required by `collections::vec::Vec`
src/traits.rs:80:5: 81:36 warning: the trait `core::marker::Sized` is not implemented for the type `Self` [E0277]
src/traits.rs:80     fn query_objects<'a, R>(&'a self, recurse: R) -> RecurseObjects<'a, Self, R>
src/traits.rs:81         where R: Fn(&Self) -> bool;
src/traits.rs:80:5: 81:36 help: run `rustc --explain E0277` to see a detailed explanation
src/traits.rs:80:5: 81:36 note: `Self` does not have a constant size known at compile-time
src/traits.rs:80:5: 81:36 note: this warning results from recent bug fixes and clarifications; it will become a HARD ERROR in the next release. See RFC 1214 for details.
src/traits.rs:80     fn query_objects<'a, R>(&'a self, recurse: R) -> RecurseObjects<'a, Self, R>
src/traits.rs:81         where R: Fn(&Self) -> bool;
src/traits.rs:80:5: 81:36 note: required by `iter::RecurseObjects`
src/traits.rs:124:5: 125:36 warning: the trait `core::marker::Sized` is not implemented for the type `Self` [E0277]
src/traits.rs:124     fn query_data<'a, R>(&'a self, recurse: R) -> RecurseData<'a, Self, R>
src/traits.rs:125         where R: Fn(&Self) -> bool;
src/traits.rs:124:5: 125:36 help: run `rustc --explain E0277` to see a detailed explanation
src/traits.rs:124:5: 125:36 note: `Self` does not have a constant size known at compile-time
src/traits.rs:124:5: 125:36 note: this warning results from recent bug fixes and clarifications; it will become a HARD ERROR in the next release. See RFC 1214 for details.
src/traits.rs:124     fn query_data<'a, R>(&'a self, recurse: R) -> RecurseData<'a, Self, R>
src/traits.rs:125         where R: Fn(&Self) -> bool;
src/traits.rs:124:5: 125:36 note: required by `iter::RecurseData`

Relicense as MPL 2.0

Similar to how I proceeded with carboxyl, this library will be available under LGPL 3.0+, too. I just have to copy & paste the license stuff.

Doc hosting site not online anymore

rust-ci.com now redirects to crates.io, so the doc link is not working anymore. An alternative seems to be either using github pages hosting (which needs an updated GH_TOKEN, as you can see in the latest travis build log), or docs.rs.

The later only supports docs for crate releases though, so maybe it'd be a good idea to use that for the crates.io link, but have the development on github.io, too. Also link them both in the README.md.

Create a Tree trait and implement it for all trees

There will probably be at least four different implementations: one that does not now its dimension at compile-time and can be used generically, and specialized binary tree, quadtree and octree impls with hard-coded dimension. Therefore a trait is required to unify their interfaces.

Stabilize benchmarking

The benchmarks don't work on stable Rust yet. Either simply wait or feature-gate them, so that testing on stable Rust is possible.

Abstract over the NodeState

Currently NodeState is coupled tightly to its particular kind of memory layout:

pub enum NodeState<O, N> {
    Empty,
    Leaf(O),
    Branch(Vec<N>),
}

As the Node trait requires this exact type, it would not be possible for an implementation to use a different internal representation, e.g. [N, ..8] instead of Vec<N> for a dimension-specific octree.

Another problem is, that the queries are currently not implemented generically, which would be possible, if the state was generic, too. In principle, we could have impls like:

impl<T, P, N, O> ObjectQuery<O> for T
    where T: Node<P, N, O>
{ /* ... */ }

impl<T, P, N, O, D> DataQuery<D> for T
    where T: Node<P, N, O> + AssociatedData<D>
{ /* ... */ }

This would remove part of the code duplication between PureNTree and NTree.

Allow free type of partition subdivisions

Consider the Partition trait:

pub trait Partition<T>: Sized {
    fn subdivide(&self) -> Vec<Self>;
    /* ... */
}

One could imagine impls of Partition that subdivide into another implementation of Partition. Currently this would have to be worked around by wrapping such partitions in an enum that comprises both. However the following does not compile:

pub trait Partition<T>: Sized {
    type Subdivision: Partition<T>;
    fn subdivide(&self) -> Vec<Subdivision>;
    /* ... */
}

For this to work rust-lang/rust#20551 needs to be fixed (only if such recursion is intended to be allowed, of course).

Implement dimension-specific trees

Hard-coding the dimension of a tree probably allows it to be quite a bit faster. Macros should be used to avoid code duplication similar to how nalgebra works.

Abstract over Vec as the sole container type

Both the Partition trait and the structs Tree and PureTree could benefit from not being specialized to Vec as a container type for subdivision/branching. Some obvious types to use are [T; 2], [T; 4] and [T; 8]. The cube map partition could use a specialized hybrid container type that can hold either six (dividing the top-level sphere) or four elements (the per-side quad trees). This would also enable using lazy structures such as iterators or any kind of lazily initialized container/sequence.

Hide nalgebra away from public interface

It would be good to avoid breaking acacia on each nalgebra release, and also to be less tied to any particular library.
Instead, types from https://github.com/kvark/mint could be used.

Expose methods for mutable trees

Currently, methods such as insert are private, since (1) they cannot guarantee the internal invariants of a tree completely, and (2) their signature is inconsistent between Tree and PureTree.

However, it may well be sensible to access the tree mutably after its construction. Therefore, it is necessary to provide a public interface that fulfills the missing properties mentioned above.

Furthermore, there may be more methods than insert to consider, e.g.

• remove(filter) removes objects based on some filter.
• collapse(filter) collapses nodes to empty nodes based on some filter.
• extend(iterator) inserts all elements from the iterator into the tree. (stdlib trait Extend)
• …

Move to crates.io for dependencies

Targets the alpha version of the compiler. Requires nalgebra and quickcheck to upload a version.

Error boilerplating

Ugh, writing good error types seems painful.

Do you think, @aepsil0n, that https://github.com/tailhook/quick-error looks worthwhile?

Version bump?

with incompatibilities with nalgebra < 0.9 due to name changes, should there be a minor version bump for acacia?

Use more abstract scalar types

Currently the subdivision algorithms pretty much restrict this library to be applied to flat vector spaces (Vec2<T>, Vec3<T>…). However, there are certainly more general spaces, where subdivision can be reasonably defined in terms of some form of interpolation. An example would be the curved surface of a sphere (e.g. using cube maps).

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.

Overthink public item hierarchy

The crate could benefit ergonomically from some reexports. The internal module structure could also be better factored and rearranged to reflect recent changes type name and semantics.

Last crate publishing attempt failed on travis

https://travis-ci.org/aepsil0n/acacia/jobs/79702209#L621