use algorithms::structures::radix_trie::RadixTrie;

#[test]
fn test_radix_trie() {
    let mut radix_trie = RadixTrie::<u32>::new();
    radix_trie.insert("abab", Some(1));
    radix_trie.insert("abab", Some(11));
    radix_trie.insert("abc", Some(2));
    radix_trie.insert("abccc", Some(3));
    radix_trie.insert("ddvbn", Some(4));
    radix_trie.insert("gg", Some(5));
    radix_trie.insert("g", Some(6));

    assert_eq!(radix_trie.find("abab"), Some(&1));
    assert_eq!(radix_trie.find("ababa"), None);
    assert_eq!(radix_trie.find("abccc"), Some(&3));
    assert_eq!(radix_trie.find("abcc"), None);
    assert_eq!(radix_trie.find("abc"), Some(&2));
    assert_eq!(radix_trie.find("ddvbn"), Some(&4));
    assert_eq!(radix_trie.find("ddvbnn"), None);
    assert_eq!(radix_trie.find("gg"), Some(&5));
    assert_eq!(radix_trie.find("g"), Some(&6));
    assert_eq!(radix_trie.find("ggg"), None);

    let mut radix_trie = RadixTrie::<u32>::new();
    radix_trie.insert("dear", Some(1));
    radix_trie.insert("sweetie", Some(2));
    radix_trie.insert("angel", Some(3));
    radix_trie.insert("dream", Some(4));
    radix_trie.insert("baby", Some(5));

    assert_eq!(radix_trie.find("dear"), Some(&1));
    assert_eq!(radix_trie.find("sweetie"), Some(&2));
    assert_eq!(radix_trie.find("angel"), Some(&3));
    assert_eq!(radix_trie.find("dream"), Some(&4));
    assert_eq!(radix_trie.find("baby"), Some(&5));
    assert_eq!(radix_trie.find("avens"), None);


    let mut radix_trie = RadixTrie::<u32>::new();
    radix_trie.insert("abd", Some(1));
    radix_trie.insert("bcd", Some(2));
    radix_trie.insert("d", Some(3));
    assert_eq!(radix_trie.find("bcd"), Some(&2));
    assert_eq!(radix_trie.find("d"), Some(&3));

    let mut radix_trie = RadixTrie::<u32>::new();
    radix_trie.insert("a b", Some(1));
    assert_eq!(radix_trie.find("a b"), Some(&1));

    let mut radix_trie = RadixTrie::<u32>::new();
    radix_trie.insert("a", Some(1));
    radix_trie.insert("aa", Some(2));
    radix_trie.insert("aaa", Some(3));
    radix_trie.insert("aaaa", Some(4));
    assert_eq!(radix_trie.find("aaa"), Some(&3));
    assert_eq!(radix_trie.find(""), None);

    let radix_trie = RadixTrie::<u32>::new();
    assert_eq!(radix_trie.find("aaa"), None);
}

#[test]
fn test_radix_trie_2() {
    let mut radix_trie = RadixTrie::<bool>::new();
    let text = "Daytrip took it to 10
I spent some days in the trap and got my money up (Yeah)
Bust it down, the Rollie, now she tryna fuck (Yeah, ah)
And now she feeding all up on me just like I'm a drug (Yeah)
I remember back when y'all wouldn't show me love (Yeah, ah)
Jaguar truck on the freeway (Woah)
You can catch me ballin' on the replay (Woah, oh)
Saint Laurent jacket, it's 3K (Woah)
I been with the same gang since Pre-K' (Woah, oh)
Get the money, stack it with my niggas
I remember trappin' with my niggas
Now we overseas in a villa
Goin' back, we won't consider
I remember days we was starving
Still finessin', we was juggin', we was robbing
I was coming off the bench, I wasn't starting
Now I'm out here ballin' like I'm Harden
And I make sure my day ones straight, stay with my gang
You ain't fuckin' with me, you can stay out my way
Stay in your lane, fuck your campaign, yeah
Last year, I was sleepin' in a basement
Now the foreign lookin' like a spaceship
Bust down the gang with the bag, yeah
All the money on me, holographic
I spent some days in the trap and got my money up (Yeah)
Bust it down, the Rollie, now she tryna fuck (Yeah, ah)
And now she feeding all up on me just like I'm a drug (Yeah)
I remember back when y'all wouldn't show me love (Yeah, ah)
Jaguar truck on the freeway (Woah)
You can catch me ballin' on the replay (Woah, oh)
Saint Laurent jacket, it's 3K (Woah)
I been with the same gang since Pre-K' (Woah, oh)
We was down and we was out, and bitches looked at us stupid
It was hating ass niggas, so I kept me a Ruger
Sending shots to his body, make him sing like Ozuna
They was running out they mouth, but they respected the shooter
We was down and we was out, and bitches looked at us stupid
It was hating ass niggas, so I kept me a Ruger
Sending shots to his body, make him sing like Ozuna
They was running out they mouth, but they respected the shooter, yeah
Blocked blocks, sent shots
Threw that shit in reverse, then we bending through your block
Blocked blocks, sent shots
Threw that shit in reverse, then we bending through your block
Watch his body Milly Rock, yeah";

    for line in text.split_whitespace() {
        radix_trie.insert(line, Some(true));
    }

    assert_eq!(radix_trie.find("aaa"), None);
    assert_eq!(radix_trie.find("shots"), Some(&true));
    assert_eq!(radix_trie.find("hating"), Some(&true));
    assert_eq!(radix_trie.find("holographic"), Some(&true));
    assert_eq!(radix_trie.find("Laurent"), Some(&true));
    assert_eq!(radix_trie.find("Daytrip"), Some(&true));
    assert_eq!(radix_trie.find("Daytris"), None);
    assert_eq!(radix_trie.find("bitches"), Some(&true));
    assert_eq!(radix_trie.find("yeah"), Some(&true));
    assert_eq!(radix_trie.find("I"), Some(&true));

}

#[test]
fn test_radix_trie_3() {
    let mut radix_trie = RadixTrie::<u32>::new();
    radix_trie.insert("aaaa", Some(1));
    radix_trie.insert("aaa", Some(2));
    radix_trie.insert("aa", Some(3));
    radix_trie.insert("a", Some(4));

    assert_eq!(radix_trie.find("a"), Some(&4));
    assert_eq!(radix_trie.find("aa"), Some(&3));
    assert_eq!(radix_trie.find("aaa"), Some(&2));
    assert_eq!(radix_trie.find("aaaa"), Some(&1));

    let mut radix_trie = RadixTrie::<u32>::new();
    radix_trie.insert("a", Some(1));
    radix_trie.insert("aa", Some(2));
    radix_trie.insert("aaa", Some(3));
    radix_trie.insert("aaaa", Some(4));

    assert_eq!(radix_trie.find("a"), Some(&1));
    assert_eq!(radix_trie.find("aa"), Some(&2));
    assert_eq!(radix_trie.find("aaa"), Some(&3));
    assert_eq!(radix_trie.find("aaaa"), Some(&4));
}

#[test]
fn test_radix_trie_4() {
    let mut radix_trie = RadixTrie::<u32>::new();
    radix_trie.insert("abcd", Some(1));
    radix_trie.insert("bd", Some(2));

    assert_eq!(radix_trie.find("abcd"), Some(&1));
    assert_eq!(radix_trie.find("bd"), Some(&2));
    assert_eq!(radix_trie.find("ab"), None);
    assert_eq!(radix_trie.find("cd"), None);
    assert_eq!(radix_trie.find("bcd"), None);
}

#[test]
fn test_radix_trie_5() {
    let mut radix_trie = RadixTrie::<u32>::new();
    for i in 0..1000 {
        let key = format!("key-{}", i);
        radix_trie.insert(&key, Some(i));
    }
    for i in 0..1000 {
        let key = format!("key-{}", i);
        assert_eq!(radix_trie.find(&key), Some(&i));
    }
    for i in 0..1000 {
        assert_eq!(radix_trie.find(&i.to_string()), None);
    }
}

#[test]
fn test_radix_trie_6() {
    let mut radix_trie = RadixTrie::<u32>::new();
    radix_trie.insert("abcd", Some(1));
    radix_trie.insert("abce", Some(2));
    radix_trie.insert("abt", Some(3));
    radix_trie.insert("ab", Some(4));

    assert_eq!(radix_trie.find("ab"), Some(&4));
}

#[test]
fn test_radix_trie_7() {
    let radix_trie = RadixTrie::<u32>::new();
    assert_eq!(radix_trie.find("ab"), None);
}