fm-index 0.3.1

FM index and its variant implementations for Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

use crate::character::Character;
use num_traits::Zero;

/// Build a text for tests using a generator function `gen`.
pub fn build_text<C: Zero + Clone, F: FnMut() -> C>(mut gen: F, len: usize) -> Vec<C> {
    let mut text = vec![C::zero(); len];

    let mut prev_zero = true;
    for t in text.iter_mut().take(len - 1) {
        let mut c = gen();
        if prev_zero {
            while c.is_zero() {
                c = gen();
            }
        }
        prev_zero = c.is_zero();
        *t = c;
    }

    while text[len - 2].is_zero() {
        text[len - 2] = gen();
    }

    text
}

/// Compute the suffix array of the given text in naive way for testing purpose.
pub fn build_suffix_array<C>(text: &[C]) -> Vec<usize>
where
    C: Character + Ord,
{
    let n = text.len();
    let suffixes = (0..n).map(|i| &text[i..n]).collect::<Vec<_>>();
    let mut sa = (0..(suffixes.len())).collect::<Vec<_>>();
    sa.sort_by_key(|i| &suffixes[*i]);
    sa
}

/// Build the inverse suffix array from the suffix array.
pub fn build_inv_suffix_array(suffix_array: &[usize]) -> Vec<usize> {
    let mut isa = vec![0; suffix_array.len()];
    for (p, &i) in suffix_array.iter().enumerate() {
        isa[i] = p;
    }
    isa
}