Skip to content

Releases: blachlylab/intervaltree

Harmonized API: insert, @nogc, speed impr

10 Jan 06:33
Compare
Choose a tag to compare

Major but API breaking updates:
Harmonized API: AVLtree and splaytree insert both now take IntervalType
AVLTree and splaytree both use malloc backed arena allocation and insert() is @nogc
UnrolledList removed from AVLTree findOVerlapsWith which should speed search (and eliminate a dep)

Splay Tree Improvements

06 Jan 02:03
Compare
Choose a tag to compare

Splay tree insert function which takes Node, now performs non-GC memory allocation (function not yet annotated @nogc) using an arena/region strategy with enough room initially reserved for 65536 nodes, backed by malloc.

Splay tree now probabalistically splays , which increases speed up to 10-20% on certain serial query workloads. To do, we will parameterize this (including, off course, 100% probability).

API unchanged

Toward a common API

16 Nov 21:19
Compare
Choose a tag to compare

Now AVL Trees and Splay Trees have a (near) common API; simply import intervaltree. and the code to work with the trees should be the same -- in both packages, Interval<Whichever>Tree has been aliased to IntervalTree.

There are still some differences that need to be version()ed in however, most notably insert. AVLTree still takes a pointer to a node (IntervalTreeNode) while SplayTree takes an interval type by value (and internally creates the node).

Example:

                    foreach(link; c.links)
                    {
                        version(avl)    { uint cnt; (*tree).insert( new IntervalTreeNode!ChainLink(*link), cnt ); }
                        version(splay)  (*tree).insert(*link);
                    }

Splaytree Speed Boost

21 Mar 02:29
Compare
Choose a tag to compare
v0.9.5

10-20% speed boost in splay tree lookup

v0.9.0

21 Mar 00:21
Compare
Choose a tag to compare

Fully implemented AVL interval tree and Splay tree intervaltree ; the API differs between the two, as the AVL tree takes Node* , while splay tree takes an interval type. This will be unified by 1.0.