• James Blachly (33/33) Aug 22 2020 I am happy to share our interval tree library we built for some internal...

James Blachly <james.blachly gmail.com> writes:

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


https://github.com/blachlylab/intervaltree
https://code.dlang.org/packages/intervaltree


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.


 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()`


Genesis: https://forum.dlang.org/post/qxaqonnyezgtwxjqwopl forum.dlang.org