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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

//! Sampled suffix arrays to perform locate queries.
use crate::heap_size::HeapSize;
use crate::util;
use serde::{Deserialize, Serialize};
use std::fmt;
use vers_vecs::BitVec;

/// A suffix array sampled by the _suffix order_ (SO) sampling strategy.
///
/// For instance, if the suffix array is `[0, 1, 2, 3, 4, 5, 6, 7]` and the sampling level is `2`,
/// the sampled suffix array will be `[0, 4]`.
#[derive(Serialize, Deserialize)]
pub struct SOSampledSuffixArray {
    level: usize,
    word_size: usize,
    sa: BitVec,
    len: usize,
}

impl SOSampledSuffixArray {
    pub(crate) fn sample(sa: &[usize], mut level: usize) -> SOSampledSuffixArray {
        if sa.is_empty() {
            return SOSampledSuffixArray::default();
        }

        let n = sa.len();
        let word_size = util::log2_usize(n) + 1;
        if n <= 1 << level {
            // If the sampling level is too high, we don't sample the suffix array at all.
            level = 0;
        }

        let sa_samples_len = ((n - 1) >> level) + 1;
        let mut sa_samples = BitVec::with_capacity(sa_samples_len);
        for i in 0..sa_samples_len {
            sa_samples.append_bits(sa[i << level] as u64, word_size);
        }
        SOSampledSuffixArray {
            level,
            word_size,
            sa: sa_samples,
            len: sa.len(),
        }
    }

    pub(crate) fn get(&self, i: usize) -> Option<usize> {
        if i >= self.len {
            return None;
        }

        if i & ((1 << self.level) - 1) == 0 {
            Some(
                self.sa
                    .get_bits_unchecked((i >> self.level) * self.word_size, self.word_size)
                    as usize,
            )
        } else {
            None
        }
    }
}

impl fmt::Debug for SOSampledSuffixArray {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for i in 0..self.len {
            match self.get(i) {
                Some(sa) => write!(f, "{}", sa)?,
                None => write!(f, "?")?,
            }
        }
        Ok(())
    }
}

impl Default for SOSampledSuffixArray {
    fn default() -> Self {
        SOSampledSuffixArray {
            level: 0,
            word_size: 0,
            sa: BitVec::new(),
            len: 0,
        }
    }
}

impl HeapSize for SOSampledSuffixArray {
    fn heap_size(&self) -> usize {
        self.sa.heap_size()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_empty() {
        let ssa = SOSampledSuffixArray::sample(&[], 2);
        assert_eq!(ssa.get(0), None);
    }

    #[test]
    fn test_regular() {
        let cases = [
            (1, 10),
            (1, 25),
            (2, 8),
            (2, 9),
            (2, 10),
            (2, 25),
            (3, 24),
            (3, 25),
        ];
        for &(level, n) in cases.iter() {
            let sa = (0..n).collect::<Vec<usize>>();
            let ssa = SOSampledSuffixArray::sample(&sa, level);
            for i in 0..n {
                let v = ssa.get(i);
                if i & ((1 << level) - 1) == 0 {
                    assert_eq!(v, Some(i), "ssa[{}] should be Some({})", i, i);
                } else {
                    assert_eq!(v, None, "ssa[{}] should be None", i);
                }
            }
        }
    }

    #[test]
    fn test_not_sampled() {
        let sa = (0..10).collect::<Vec<usize>>();
        let ssa = SOSampledSuffixArray::sample(&sa, 4);
        for i in 0..10 {
            let v = ssa.get(i);
            assert_eq!(v, Some(i), "ssa[{}] should be Some({})", i, i);
        }
    }
}