Interval Trees library intervaltree
James Blachly
james.blachly at gmail.com
Sat Aug 22 16:16:42 UTC 2020
I am happy to share our interval tree library we built for some internal
computational biology projects. I would also be very happy to have your
feedback on implementation and execution as I am certainly no
professional software engineer.
James
# Sources
https://github.com/blachlylab/intervaltree
https://code.dlang.org/packages/intervaltree
# Discussion
Implemented are AVL trees, Splay trees, and a newer type of packed array
structure being explored in genomics, the Implicit Interval Tree (IIT;
more info in documentation)
The trees are implemented as generic templated containers for whatever
payload you wish to include. Our applications require a payload, but
certainly there are important applications of interval trees that
require none. I haven't thought about whether one could include a
NoneType, empty struct, etc. but would be glad to hear ideas.
# Notes
@nogc status: Currently everything is @nogc except the
`findOverlapsWith` function, which returns a dynamic array of matching
intervals. Since API remains unstable until 1.0 I would also be open to
changing this (e.g. to a preallocated reusable buffer although this
would make the structure non-threadsafe) if @nogc is important to
library users.
GC warning: since we manage our own memory (with stdx.allocator and
arena allocations via Mallocator), placing objects in the tree having
pointers to GC-managed memory (e.g. strings) will bite you hard, unless
you use the IITree, which currently does include code that defaults to
include `GC.addRange()` at `insert`. In the future I will likely make
all treetypes `GC.addRange` over their entire arenas to improve safety
AND speed `insert()`
# References
Genesis: https://forum.dlang.org/post/qxaqonnyezgtwxjqwopl@forum.dlang.org
More information about the Digitalmars-d-announce
mailing list