Module bio::data_structures::smallints
source · Expand description
A data structure for a sequence of small integers with a few big integers.
Small ints are stored in type S (e.g. a byte), big ints are stored separately (in type B
) in a BTree.
The implementation provides vector-like operations on the data structure (e.g. retrieve a position,
add an integer, etc.). Getting and setting (by position) time complexity is O(1)
for small ints,
and O(b)
for big ints, where b
is the number of big ints stored.
§Space usage
SmallInts pay the cost of slower retrieval of big integers with smaller overall memory usage;
O(size_of(S) * (s+b) + size_of(B) * b)
where S
and B
are the small and large int types, and
s
and b
are the number of those stored respectively.
§Example
use bio::data_structures::smallints::SmallInts;
let mut smallints: SmallInts<u8, usize> = SmallInts::new();
smallints.push(3);
smallints.push(4);
smallints.push(255);
smallints.push(305093);
assert_eq!(smallints.get(0).unwrap(), 3);
smallints.set(0, 50000);
let values: Vec<usize> = smallints.iter().collect();
assert_eq!(values, [50000, 4, 255, 305093]);
Structs§
- Iterator over the elements of a
SmallInts
sequence. - Data structure for storing a sequence of small integers with few big ones space efficiently while supporting classical vector operations.