digitalmars.D.announce - Interval Trees library intervaltree
- James Blachly (33/33) Aug 22 I am happy to share our interval tree library we built for some internal...
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