sigalign_core/reference/pattern_locate/
mod.rs

1use ahash::AHashMap;
2
3use crate::core::{BufferedPatternLocator, PatternLocation};
4use super::Reference;
5use super::pattern_index::PatternIndex;
6use super::sequence_storage::SequenceStorage;
7
8impl<I, S> BufferedPatternLocator for Reference<I, S> where
9    I: PatternIndex,
10    S: SequenceStorage,
11{
12    type Buffer = S::Buffer;
13
14    #[inline]
15    fn locate(&self, pattern: &[u8], sorted_target_indices: &[u32]) -> Vec<PatternLocation> {
16        let sorted_positions = self.pattern_index.get_sorted_positions(pattern);
17        // TODO: Applying cap is valuable?
18        let mut positions_by_target: AHashMap<u32, Vec<u32>> = AHashMap::new();
19
20        let search_range_count = sorted_target_indices.len();
21
22        let mut size;
23        let mut left;
24        let mut right;
25        let mut mid = 0;
26        let mut index;
27
28        for position in sorted_positions {
29            // reset
30            right = search_range_count;
31            left = mid;
32            size = right - left;
33
34            while left < right {
35                mid = left + size / 2;
36                index = sorted_target_indices[mid];
37                
38                let start = self.target_boundaries[index as usize];
39                let end = self.target_boundaries[(index + 1) as usize];
40
41                if position >= end {
42                    left = mid + 1;
43                } else if start > position {
44                    right = mid;
45                } else if position + pattern.len() as u32 <= end {
46                    let ref_pos = position - start;
47                    match positions_by_target.get_mut(&index) {
48                        Some(v) => {
49                            v.push(ref_pos);
50                        },
51                        None => {
52                            positions_by_target.insert(index, vec![ref_pos]);
53                        },
54                    }
55                    break;
56                } else {
57                    break;
58                }
59                
60                size = right - left;
61            }
62        }
63
64        positions_by_target.into_iter().map(|(target_index, positions)| {
65            PatternLocation {
66                target_index,
67                sorted_positions: positions,
68            }
69        }).collect()
70    }
71    fn fill_buffer(&self, target_index: u32, buffer: &mut Self::Buffer) {
72        self.sequence_storage.fill_buffer(target_index, buffer)
73    }
74}
75
76impl<I, S> Reference<I, S> where
77    I: PatternIndex,
78    S: SequenceStorage,
79{
80    #[inline]
81    pub fn locate_pattern(&self, pattern: &[u8], sorted_target_indices: &[u32]) -> Vec<PatternLocation> {
82        self.locate(pattern, sorted_target_indices)
83    }
84    #[inline]
85    pub fn get_sequence_buffer(&self) -> S::Buffer {
86        self.sequence_storage.get_buffer()
87    }
88    #[inline]
89    pub fn fill_sequence_buffer(&self, target_index: u32, buffer: &mut S::Buffer) {
90        self.sequence_storage.fill_buffer(target_index, buffer)
91    }
92}
93
sigalign_core/reference/pattern_locate/mod.rs

sigalign_core/reference/pattern_locate/
mod.rs
