ナイーブなdouble array trieの実装

naive-darr.rs

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);
    }
}