bio 0.1.2

A rusty bioinformatics library. This library provides implementations of many algorithms and data structures that are useful for bioinformatics.
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

//! ShiftAnd algorithm for pattern matching.
//! Patterns may contain at most 64 symbols.
//! Complexity: O(n) with text length n.
//!
//! # Example
//!
//! ```rust
//! use bio::pattern_matching::shift_and;
//! let pattern = b"AAAA";
//! let text = b"ACGGCTAGAAAAGGCTAG";
//! let shiftand = shift_and::ShiftAnd::new(pattern);
//! let occ = shiftand.find_all(text.iter()).next().unwrap();
//! assert_eq!(occ, 8);
//! ```

use std::iter::Enumerate;

#[derive(Copy)]
pub struct ShiftAnd {
    m: usize,
    masks: [u64; 256],
    accept: u64
}


impl ShiftAnd {
    /// Create new ShiftAnd instance.
    pub fn new(pattern: &[u8]) -> ShiftAnd {
        assert!(pattern.len() <= 64, "Expecting a pattern of at most 64 symbols.");
        let (masks, accept) = masks(pattern);

        ShiftAnd { m: pattern.len(), masks: masks, accept: accept }

    }

    /// Find all occurences of pattern in the given text.
    pub fn find_all<'a, I: Iterator<Item=&'a u8>>(&'a self, text: I) -> ShiftAndMatches<I> {
        ShiftAndMatches { shiftand: self, active: 0, text: text.enumerate() }
    }
}


pub fn masks(pattern: &[u8]) -> ([u64; 256], u64) {
    let mut masks = [0; 256];

    let mut bit = 1;
    for &c in pattern.iter() {
        masks[c as usize] |= bit;
        bit *= 2;
    }

    (masks, bit / 2)
}


pub struct ShiftAndMatches<'a, I: Iterator<Item=&'a u8>> {
    shiftand: &'a ShiftAnd,
    active: u64,
    text: Enumerate<I>,
}


impl<'a, I: Iterator<Item=&'a u8>> Iterator for ShiftAndMatches<'a, I> {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        for (i, &c) in self.text.by_ref() {
            self.active = ((self.active << 1) | 1) & self.shiftand.masks[c as usize];
            if self.active & self.shiftand.accept > 0 {
                return Some(i - self.shiftand.m + 1);
            }
        }

        None
    }
}