Module bio::data_structures::interval_tree [−] [src]

Interval tree, a data structure for efficiently storing and searching intervals.

This data structure uses an Interval type to define the intervals. It is implemented by wrapping the std::ops::Range in a newtype. An interval must have a positive with and the interval bounds may be specified by any type satisfies both the std::cmp::Ord and Clone trait. Because Interval implements From<Range> you can also uses normal Range arguments in the insert and find functions. This implicit conversion will panic if a negative-width range is supplied.

Upon inserting an interval may be associated with a data value. The intervals are stored in an augmented AVL-tree which allows for efficient inserting and querying.

Example

use bio::data_structures::interval_tree::{IntervalTree};
use bio::utils::Interval;

let mut tree = IntervalTree::new();
tree.insert(11..20, "Range_1");
tree.insert(25..30, "Range_2");
for r in tree.find(15..25) {
    assert_eq!(r.interval().start, 11);
    assert_eq!(r.interval().end, 20);
    assert_eq!(r.interval(), &(Interval::from(11..20)));
    assert_eq!(r.data(), &"Range_1");
}

Structs

Entry	A `find` query on the interval tree does not directly return references to the nodes in the tree, but wraps the fields `interval` and `data` in an `Entry`.
EntryMut	A `find_mut` query on the interval tree does not directly return references to the nodes in the tree, but wraps the fields `interval` and `data` in an `EntryMut`. Only the data part can be mutably accessed using the `data` method
IntervalTree	An interval tree for storing intervals with data
IntervalTreeIterator	An `IntervalTreeIterator` is returned by `Intervaltree::find` and iterates over the entries overlapping the query
IntervalTreeIteratorMut	An `IntervalTreeIteratorMut` is returned by `Intervaltree::find_mut` and iterates over the entries overlapping the query allowing mutable access to the data `D`, not the the `Interval`.