Terminate backwards search if a symbol isn't found.
* Terminate backwards search if a symbol isn't found.
This stops LF-mapping when a symbol in the pattern couldn't be mapped to
an interval in 'F'.
* Add test case for backwards search which terminates early.
@@ -123,6 +123,12 @@ pub trait FMIndexable {
let less = self.less(a);
l = less + if l > 0 { self.occ(l - 1, a) } else { 0 };
r = less + self.occ(r, a) - 1;
+
+ // The symbol was not found if we end up with an empty interval.
+ // Terminate the LF-mapping process.
+ if l == r {
+ break;
+ }
}
Interval {
@@ -432,6 +438,24 @@ mod tests {
assert_eq!(positions, [3, 12, 9]);
}
+ #[test]
+ fn test_fmindex_not_found() {
+ let text = b"GCCTTAACATTATTACGCCTA$";
+ let alphabet = dna::n_alphabet();
+ let sa = suffix_array(text);
+ let bwt = bwt(text, &sa);
+ let less = less(&bwt, &alphabet);
+ let occ = Occ::new(&bwt, 3, &alphabet);
+ let fm = FMIndex::new(&bwt, &less, &occ);
+
+ let pattern = b"TTT";
+ let sai = fm.backward_search(pattern.iter());
+
+ let positions = sai.occ(&sa);
+
+ assert_eq!(positions, []);
+ }
+
#[test]
fn test_smems() {
let orig_text = b"GCCTTAACAT";
