use alloc::{vec, vec::Vec};

/// Generate a list of possible fallback positions for the needle, called a `longest suffix-prefix` table.
/// This can also be used if multiple haystacks are to be searched with the same needle,
/// reducing the amount of table generation to one. Functions using this table all end with
/// `_with_lsp_table`.
#[allow(clippy::indexing_slicing)]
pub fn kmp_table<N>(needle: &[N]) -> Vec<usize>
where
    N: PartialEq,
{
    if needle.is_empty() {
        return vec![];
    }

    let mut lsp = Vec::with_capacity(needle.len());
    lsp.push(0);

    for needle_char in &needle[1..] {
        #[allow(clippy::option_unwrap_used)]
        let mut distance: usize = *lsp.last().unwrap();

        #[allow(clippy::integer_arithmetic)]
        while distance > 0 && *needle_char != needle[distance] {
            distance = lsp[distance - 1];
        }

        if *needle_char == needle[distance] {
            distance += 1;
        }

        lsp.push(distance);
    }

    lsp
}

#[cfg(test)]
mod tests {
    use alloc::vec;

    use proptest::prelude::*;

    use crate::kmp_table;

    #[test]
    fn generation() {
        let empty_needle: &[char; 0] = &[];
        assert!(kmp_table(empty_needle).is_empty());
    }

    #[test]
    fn repeating() {
        assert_eq!(vec![0, 1, 2, 3, 4], kmp_table(&['a', 'a', 'a', 'a', 'a']));
    }

    #[test]
    fn boolean() {
        assert_eq!(
            vec![0, 0, 1, 1, 2, 0, 1],
            kmp_table(&[true, false, true, true, false, false, true])
        );
    }

    #[test]
    fn multiple_chars() {
        assert_eq!(
            vec![0, 0, 1, 0, 1, 2, 3, 2],
            kmp_table(&['a', 'b', 'a', 'c', 'a', 'b', 'a', 'b'])
        );
    }

    #[test]
    fn two_chars_with_repetitions() {
        assert_eq!(
            vec![0, 1, 2, 0, 1, 2, 3, 3, 3, 4],
            kmp_table(&['a', 'a', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b'])
        );
    }

    proptest! {
        #[ignore]
        #[test]
        fn fuzz_input(characters in prop::collection::vec(".*", 0..100)) {
            kmp_table(&characters);
        }
    }
}