sublime_fuzzy/
matching.rs

1use std::{cmp::Ordering, slice::Iter};
2
3use crate::Scoring;
4
5/// A (possible partial) match of query within the target string. Matched chars
6/// are stored as indices into the target string.
7///
8/// The score is not clamped to any range and can be negative.
9#[derive(Clone, Debug)]
10#[cfg_attr(feature = "serde_support", derive(Serialize, Deserialize))]
11pub struct Match {
12    /// Accumulative score
13    score: isize,
14    /// Count of current consecutive matched chars
15    consecutive: usize,
16    /// Matched char indices
17    matched: Vec<usize>,
18}
19
20impl Match {
21    /// Creates a new match with the given scoring and matched indices.
22    pub(crate) fn with_matched(score: isize, consecutive: usize, matched: Vec<usize>) -> Self {
23        Match {
24            score,
25            consecutive,
26            matched,
27        }
28    }
29
30    /// Returns the accumulative score for this match.
31    pub fn score(&self) -> isize {
32        self.score
33    }
34
35    /// Returns an iterator over the matched char indices.
36    pub fn matched_indices(&self) -> Iter<usize> {
37        self.matched.iter()
38    }
39
40    /// Returns an iterator that groups the individual char matches into groups.
41    pub fn continuous_matches(&self) -> ContinuousMatches {
42        ContinuousMatches {
43            matched: &self.matched,
44            current: 0,
45        }
46    }
47
48    /// Extends this match with `other`.
49    pub fn extend_with(&mut self, other: &Match, scoring: &Scoring) {
50        self.score += other.score;
51        self.consecutive += other.consecutive;
52
53        if let (Some(last), Some(first)) = (self.matched.last(), other.matched.first()) {
54            let distance = first - last;
55
56            match distance {
57                0 => {}
58                1 => {
59                    self.consecutive += 1;
60                    self.score += self.consecutive as isize * scoring.bonus_consecutive;
61                }
62                _ => {
63                    self.consecutive = 0;
64                    let penalty = (distance as isize - 1) * scoring.penalty_distance;
65                    self.score -= penalty;
66                }
67            }
68        }
69
70        self.matched.extend(&other.matched);
71    }
72}
73
74impl Ord for Match {
75    fn cmp(&self, other: &Match) -> Ordering {
76        self.score.cmp(&other.score)
77    }
78}
79
80impl PartialOrd for Match {
81    fn partial_cmp(&self, other: &Match) -> Option<Ordering> {
82        Some(self.cmp(other))
83    }
84}
85
86impl Eq for Match {}
87
88impl PartialEq for Match {
89    fn eq(&self, other: &Match) -> bool {
90        self.score == other.score
91    }
92}
93
94/// Describes a continuous group of char indices
95#[derive(Debug)]
96pub struct ContinuousMatch {
97    start: usize,
98    len: usize,
99}
100
101impl ContinuousMatch {
102    pub(crate) fn new(start: usize, len: usize) -> Self {
103        ContinuousMatch { start, len }
104    }
105
106    /// Returns the start index of this group.
107    pub fn start(&self) -> usize {
108        self.start
109    }
110
111    /// Returns the length of this group.
112    pub fn len(&self) -> usize {
113        self.len
114    }
115}
116
117impl Eq for ContinuousMatch {}
118
119impl PartialEq for ContinuousMatch {
120    fn eq(&self, other: &ContinuousMatch) -> bool {
121        self.start == other.start && self.len == other.len
122    }
123}
124
125/// Iterator returning [`ContinuousMatch`]es from the matched char indices in a [`Match`]
126pub struct ContinuousMatches<'a> {
127    matched: &'a Vec<usize>,
128    current: usize,
129}
130
131impl<'a> Iterator for ContinuousMatches<'_> {
132    type Item = ContinuousMatch;
133
134    fn next(&mut self) -> Option<ContinuousMatch> {
135        let mut start = None;
136        let mut len = 0;
137
138        let mut last_idx = None;
139
140        for idx in self.matched.iter().cloned().skip(self.current) {
141            start = start.or(Some(idx));
142
143            if last_idx.is_some() && (idx - last_idx.unwrap() != 1) {
144                return Some(ContinuousMatch::new(start.unwrap(), len));
145            }
146
147            self.current += 1;
148            len += 1;
149            last_idx = Some(idx);
150        }
151
152        if last_idx.is_some() {
153            return Some(ContinuousMatch::new(start.unwrap(), len));
154        }
155
156        None
157    }
158}
159
160#[cfg(test)]
161mod tests {
162    use crate::Scoring;
163
164    use super::{ContinuousMatch, Match};
165
166    #[test]
167    fn continuous() {
168        let m = Match::with_matched(0, 0, vec![0, 1, 2, 5, 6, 10]);
169
170        assert_eq!(
171            m.continuous_matches().collect::<Vec<ContinuousMatch>>(),
172            vec![
173                ContinuousMatch { start: 0, len: 3 },
174                ContinuousMatch { start: 5, len: 2 },
175                ContinuousMatch { start: 10, len: 1 },
176            ]
177        )
178    }
179
180    #[test]
181    fn extend_match() {
182        let mut a = Match::with_matched(16, 3, vec![1, 2, 3]);
183        let b = Match::with_matched(8, 3, vec![5, 6, 7]);
184
185        let s = Scoring::default();
186
187        a.extend_with(&b, &s);
188
189        assert_eq!(a.score(), 24 - s.penalty_distance);
190        assert_eq!(a.consecutive, 0);
191        assert_eq!(a.matched_indices().len(), 6);
192    }
193
194    #[test]
195    fn extend_match_cont() {
196        let mut a = Match::with_matched(16, 3, vec![1, 2, 3]);
197        let b = Match::with_matched(8, 3, vec![4, 5, 6]);
198
199        let s = Scoring::default();
200
201        a.extend_with(&b, &s);
202
203        assert_eq!(a.score(), 16 + 8 + (3 + 3 + 1) * s.bonus_consecutive);
204        assert_eq!(a.consecutive, 3 + 3 + 1);
205        assert_eq!(a.matched_indices().len(), 6);
206    }
207}
sublime_fuzzy/matching.rs

sublime_fuzzy/
matching.rs
