Crate coitrees

Source
Expand description

§COITrees

coitrees implements a fast static interval tree data structure with genomic data in mind.

The data structure used a fairly standard interval tree, but with nodes stored in van Emde Boas layout, which improves average cache locality, and thus query performance. The downside is that building the tree is more expensive so a relatively large number of queries needs to made for it to break even.

The data structure COITree is constructed with an array of IntervalNode structs which store integer, end-inclusive intervals along with associated metadata. The tree can be queried directly for coverage or overlaps, or through the intermediary SortedQuerenty which keeps track of some state to accelerate overlaping queries.

Structs§

BasicCOITree
COITree data structure. A representation of a static set of intervals with associated metadata, enabling fast overlap and coverage queries.
BasicCOITreeIterator
Iterate through nodes in a tree in sorted order by interval start position.
BasicSortedQuerent
An alternative query strategy that can be much faster when queries are performed in sorted order and overlap.
Interval
An interval with associated metadata.
IntervalNode
Internal interval node representation used by BasicCOITree

Traits§

GenericInterval
IntWithMax
A trait facilitating COITree index types.
IntervalTree
Basic interval tree interface supported by each COITree implementation.
SortedQuerent

Type Aliases§

COITree
COITreeSortedQuerent