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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
// We want to make sure we are getting the shortest match possible
// without getting tripped up by pathological cases.
pub mod minspan {
pub fn span<A>(query: &Vec<A>, history: &Vec<A>) -> Option<(usize, usize)>
where
A: PartialEq,
{
// If history is empty, we cannot find any span with valid indices.
if history.is_empty() {
return None;
}
// If query is empty, it's a subsequence starting at index 0.
// The current implementation returns (0, 0), representing history[0..=0].
// This is valid since history is non-empty here.
if query.is_empty() {
return Some((0, 0));
}
// Initialize state for the main algorithm
let mut starting_at: Vec<Option<(usize, usize)>> = query.iter().map(|_| None).collect();
let mut best_complete_solution: Option<(usize, usize)> = None;
// Main loop: requires non-empty query and history
for (bodyindex, bodychr) in history.iter().enumerate() {
for (keyindex, keychr) in query.iter().enumerate().rev() {
if keychr == bodychr {
// we have a match, therefore record it: it ends at bodyindex,
// and by construction, starts at starting_at[0]
starting_at[keyindex] = if keyindex == 0 {
// we got nothing yet! set to beginning
Some((bodyindex, bodyindex))
} else {
starting_at[keyindex - 1].map(|(start, _end)| (start, bodyindex))
};
// are we finished?
if (keyindex + 1) == query.len() {
if let Some((from, to)) = starting_at[keyindex] {
best_complete_solution = match best_complete_solution {
None => Some((from, to)), // 1+to - from),
Some((currfrom, currto)) => {
Some(if to - from < currto - currfrom {
(from, to)
} else {
(currfrom, currto)
})
}
}
}
}
}
}
}
best_complete_solution
}
}
// Add proptest imports for property-based testing
#[cfg(test)]
extern crate proptest;
#[cfg(test)]
use proptest::prelude::*;
#[cfg(test)]
mod tests {
use super::*;
// Keep existing tests
#[test]
fn test_minimal_match() {
// Helper to convert string slices to Vec<char> and call span
let run_span = |needle: &str, haystack: &str| {
let query: Vec<char> = needle.chars().collect();
let history: Vec<char> = haystack.chars().collect();
minspan::span(&query, &history)
};
// Helper to get span length or None
let get_span_len = |needle: &str, haystack: &str| {
run_span(needle, haystack).map(|(from, to)| 1 + to - from)
};
assert_eq!(get_span_len("ab", "ab"), Some(2));
assert_eq!(get_span_len("a", "ab"), Some(1));
assert_eq!(get_span_len("ab", "abc"), Some(2));
assert_eq!(get_span_len("abc", "abcd"), Some(3));
assert_eq!(get_span_len("curl", "curly"), Some(4));
assert_eq!(get_span_len("curl", "acccccurlycurrelly"), Some(4));
assert_eq!(get_span_len("z", "acccccurlycurrelly"), None);
assert_eq!(get_span_len("ssh", "testssh"), Some(3));
assert_eq!(get_span_len("aba", "abababa"), Some(3));
assert_eq!(run_span("", "abc"), Some((0, 0))); // Empty query
assert_eq!(run_span("a", ""), None); // Empty history
assert_eq!(run_span("", ""), None); // Both empty
}
#[test]
fn test_is_subsequence_consumes_main_seq() {
let sub: Vec<char> = vec!['a', 'a', 'a'];
let main_seq: Vec<char> = vec!['a', 'a'];
assert!(!is_subsequence(&sub, &main_seq), "is_subsequence should return false when main_seq is consumed before sub is fully matched");
let sub_ok: Vec<char> = vec!['a', 'a'];
let main_seq_ok: Vec<char> = vec!['a', 'a', 'a'];
assert!(
is_subsequence(&sub_ok, &main_seq_ok),
"is_subsequence should return true when sub is shorter or equal and matches"
);
let sub_diff: Vec<char> = vec!['a', 'b'];
let main_seq_diff: Vec<char> = vec!['a', 'a'];
assert!(
!is_subsequence(&sub_diff, &main_seq_diff),
"is_subsequence should return false for non-matching elements"
);
}
// Helper function to check if `sub` is a subsequence of `main_seq`
fn is_subsequence<A: PartialEq>(sub: &[A], main_seq: &[A]) -> bool {
let mut main_iter = main_seq.iter();
sub.iter()
.all(|sub_item| main_iter.any(|main_item| main_item == sub_item))
}
// Use proptest! with a custom config and closure syntax
proptest! {
#![proptest_config(ProptestConfig::with_cases(10000))]
#[test]
fn prop_span_finds_valid_subsequence(
// Query uses chars 'a'..'c' via regex strategy, length 0..10
query in proptest::collection::vec("[a-c]", 0..10),
// History uses chars 'a'..'d' via regex strategy, length 0..50
history in proptest::collection::vec("[a-d]", 0..50)
) {
if let Some((from, to)) = minspan::span(&query, &history) {
// 1. Indices must be valid
prop_assert!(from <= to, "from index {} > to index {}", from, to);
prop_assert!(to < history.len(), "to index {} is out of bounds for history len {}", to, history.len());
// 2. The slice history[from..=to] must contain query as a subsequence
let history_slice = &history[from..=to];
prop_assert!(
is_subsequence(&query, history_slice),
"query {:?} is not a subsequence of history slice {:?} (from={}, to={})",
query, history_slice, from, to
);
// 3. Check if a shorter span exists *before* the found one (minimality check part 1)
// This is tricky to fully verify without re-implementing the logic.
// We can check that no shorter valid subsequence exists ending at or before `to`.
// A simpler check: ensure the first element of query matches history[from]
// if query is not empty. This isn't always true for the *minimal* span,
// e.g., query="ab", history="axb", span=(1,2) 'xb', not (0,2) 'axb'.
// 3. Minimality Check: Ensure no shorter span contains the query.
// Iterate through all possible start (f) and end (t) indices.
for f in 0..history.len() {
for t in f..history.len() {
// Check only spans that are strictly shorter than the found span (to - from).
if t - f < to - from {
let shorter_slice = &history[f..=t];
prop_assert!(
!is_subsequence(&query, shorter_slice),
"Found shorter span history[{}:{}] ({:?}) that contains query {:?}, but span returned ({}, {}) len {}",
f, t, shorter_slice, query, from, to, to - from + 1
);
}
}
}
} else {
// If span returns None, then query should not be a subsequence of history,
// unless the query itself is empty (as empty query is always a subsequence).
prop_assert!(
!is_subsequence(&query, &history) || query.is_empty(),
"span returned None, but query {:?} IS a subsequence of history {:?}",
query, history
);
}
}
}
}