Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
ナイーブなdouble array trieの実装
use std::collections::HashMap;
fn validate(
base: &Vec<Option<usize>>,
check: &Vec<Option<usize>>,
wdict: &HashMap<char, usize>,
s: &String,
) -> bool {
let ci = s.chars();
// initial offset is 0
let mut offset = 0;
for c in ci {
eprintln!("input: {}, of: {}", c, offset);
match wdict.get(&c) {
Some(j) => {
match base[offset] {
Some(next_offset) => {
// parent sanity check
if next_offset + j >= check.len() { return false }; // まだusizeなのでoffsetが負になることはありえない(修正必要)
let ck = check[next_offset + j];
eprintln!(
"sanity check: next offset {} + jump {} = {}, check[{}] = {:?} == {} ?",
next_offset,
j,
next_offset + j,
next_offset + j,
ck,
offset
);
if ck == None || ck == Some(offset) {
// None stands for initial state
// sanity check complete. set offset
offset = next_offset + j;
} else {
return false; // 遷移失敗
}
}
None => match c {
END_FLAG_CHAR => return true,
_otherwise => return false,
}, // ジャンプ先が無いのでここで終了 現在の文字が$でなければ失敗
}
}
None => panic!("undefined character in dict"),
}
}
// 終端に到着せずに入力が終了した場合ここに来る
return false;
}
const END_FLAG_CHAR: char = '$';
fn main() {
let base: Vec<Option<usize>> = vec![Some(0), Some(0), Some(1), Some(4), None];
let check: Vec<Option<usize>> = vec![None, Some(0), Some(1), Some(2), Some(3)];
let mut wdict: HashMap<char, usize> = HashMap::new();
wdict.insert('T', 0);
wdict.insert('W', 1);
wdict.insert('E', 2);
wdict.insert(END_FLAG_CHAR, 3);
// validate "TWEET"
let result = validate(&base, &check, &wdict, &"TWEET".to_string());
println!("validate? => {}", result);
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_validate() {
let base: Vec<Option<usize>> = vec![Some(0), Some(0), Some(1), Some(4), None];
let check: Vec<Option<usize>> = vec![None, Some(0), Some(1), Some(2), Some(3)];
let mut wdict: HashMap<char, usize> = HashMap::new();
wdict.insert('T', 0);
wdict.insert('W', 1);
wdict.insert('E', 2);
wdict.insert(END_FLAG_CHAR, 3);
let result = validate(&base, &check, &wdict, &"TWEET".to_string());
assert_eq!(result, true);
}
#[test]
fn test_invalid_transition() {
let base: Vec<Option<usize>> = vec![Some(0), Some(0), Some(1), Some(4), None];
let check: Vec<Option<usize>> = vec![None, Some(0), Some(1), Some(2), Some(3)];
let mut wdict: HashMap<char, usize> = HashMap::new();
wdict.insert('T', 0);
wdict.insert('W', 1);
wdict.insert('E', 2);
wdict.insert(END_FLAG_CHAR, 3);
let result = validate(&base, &check, &wdict, &"TWEEET".to_string());
assert_eq!(result, false);
}
#[test]
fn test_incomplete_transition() {
let base: Vec<Option<usize>> = vec![Some(0), Some(0), Some(1), Some(4), None];
let check: Vec<Option<usize>> = vec![None, Some(0), Some(1), Some(2), Some(3)];
let mut wdict: HashMap<char, usize> = HashMap::new();
wdict.insert('T', 0);
wdict.insert('W', 1);
wdict.insert('E', 2);
wdict.insert(END_FLAG_CHAR, 3);
let result = validate(&base, &check, &wdict, &"TWE".to_string());
assert_eq!(result, false);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment