radix_immutable 0.1.0

use quickcheck::quickcheck;
use radix_immutable::StringTrie;
use std::collections::HashMap;

/// Insert all keys, verify every key is retrievable and len matches.
fn prop_insert_then_get(entries: Vec<(String, u32)>) -> bool {
    let mut trie = StringTrie::<String, u32>::new();
    let mut reference = HashMap::new();

    for (k, v) in &entries {
        trie = trie.insert(k.clone(), *v);
        reference.insert(k.clone(), *v);
    }

    if trie.len() != reference.len() {
        return false;
    }

    for (k, v) in &reference {
        if trie.get(k) != Some(v) {
            return false;
        }
    }

    true
}

/// Insert then remove all keys; trie should be empty.
fn prop_insert_remove_all(keys: Vec<String>) -> bool {
    let mut trie = StringTrie::<String, u32>::new();
    for (i, k) in keys.iter().enumerate() {
        trie = trie.insert(k.clone(), i as u32);
    }

    // Deduplicate keys for removal
    let unique: Vec<_> = keys.iter().collect::<std::collections::HashSet<_>>()
        .into_iter().collect();

    for k in &unique {
        let (new_trie, removed) = trie.remove(k);
        if removed.is_none() {
            return false;
        }
        trie = new_trie;
    }

    trie.is_empty() && trie.len() == 0
}

/// Two tries built from the same set of entries (possibly in different order)
/// should be equal.
fn prop_insertion_order_independent(entries: Vec<(String, u32)>) -> bool {
    // Deduplicate: keep last value for each key (like HashMap)
    let mut deduped = HashMap::new();
    for (k, v) in &entries {
        deduped.insert(k.clone(), *v);
    }

    let mut trie_forward = StringTrie::<String, u32>::new();
    for (k, v) in &deduped {
        trie_forward = trie_forward.insert(k.clone(), *v);
    }

    // Insert in reverse-sorted order
    let mut sorted: Vec<_> = deduped.iter().collect();
    sorted.sort_by(|a, b| b.0.cmp(a.0));
    let mut trie_reverse = StringTrie::<String, u32>::new();
    for (k, v) in sorted {
        trie_reverse = trie_reverse.insert(k.clone(), *v);
    }

    trie_forward == trie_reverse
}

/// Iteration should yield exactly the entries in the trie.
fn prop_iter_matches_entries(entries: Vec<(String, u32)>) -> bool {
    let mut reference = HashMap::new();
    let mut trie = StringTrie::<String, u32>::new();

    for (k, v) in &entries {
        trie = trie.insert(k.clone(), *v);
        reference.insert(k.clone(), *v);
    }

    let iter_entries: HashMap<String, u32> = trie.iter().collect();
    iter_entries == reference
}

/// Subtree size should match len and iter count.
fn prop_subtree_size_consistent(entries: Vec<(String, u32)>) -> bool {
    let mut trie = StringTrie::<String, u32>::new();
    let mut reference = HashMap::new();

    for (k, v) in &entries {
        trie = trie.insert(k.clone(), *v);
        reference.insert(k.clone(), *v);
    }

    let len = trie.len();
    let iter_count = trie.iter().count();

    len == reference.len() && iter_count == len
}

/// Removing a key that was inserted should return Some, and the
/// resulting trie should not contain it.
fn prop_remove_returns_value(entries: Vec<(String, u32)>) -> bool {
    if entries.is_empty() {
        return true;
    }

    let mut trie = StringTrie::<String, u32>::new();
    let mut reference = HashMap::new();
    for (k, v) in &entries {
        trie = trie.insert(k.clone(), *v);
        reference.insert(k.clone(), *v);
    }

    // Remove the first unique key
    let key_to_remove = reference.keys().next().unwrap().clone();
    let expected_value = reference[&key_to_remove];
    let (new_trie, removed) = trie.remove(&key_to_remove);

    removed == Some(expected_value)
        && new_trie.get(&key_to_remove).is_none()
        && new_trie.len() == trie.len() - 1
}

/// After insert+remove, structural hash should match a directly-built trie.
fn prop_canonical_after_remove(entries: Vec<(String, u32)>) -> bool {
    if entries.len() < 2 {
        return true;
    }

    let mut reference = HashMap::new();
    for (k, v) in &entries {
        reference.insert(k.clone(), *v);
    }

    if reference.len() < 2 {
        return true;
    }

    // Build trie with all entries
    let mut trie_full = StringTrie::<String, u32>::new();
    for (k, v) in &reference {
        trie_full = trie_full.insert(k.clone(), *v);
    }

    // Remove the first key
    let key_to_remove = reference.keys().next().unwrap().clone();
    let (trie_after_remove, _) = trie_full.remove(&key_to_remove);

    // Build trie directly without that key
    let mut trie_direct = StringTrie::<String, u32>::new();
    for (k, v) in &reference {
        if *k != key_to_remove {
            trie_direct = trie_direct.insert(k.clone(), *v);
        }
    }

    trie_after_remove == trie_direct
}

quickcheck! {
    fn qc_insert_then_get(entries: Vec<(String, u32)>) -> bool {
        prop_insert_then_get(entries)
    }

    fn qc_insert_remove_all(keys: Vec<String>) -> bool {
        prop_insert_remove_all(keys)
    }

    fn qc_insertion_order_independent(entries: Vec<(String, u32)>) -> bool {
        prop_insertion_order_independent(entries)
    }

    fn qc_iter_matches_entries(entries: Vec<(String, u32)>) -> bool {
        prop_iter_matches_entries(entries)
    }

    fn qc_subtree_size_consistent(entries: Vec<(String, u32)>) -> bool {
        prop_subtree_size_consistent(entries)
    }

    fn qc_remove_returns_value(entries: Vec<(String, u32)>) -> bool {
        prop_remove_returns_value(entries)
    }

    fn qc_canonical_after_remove(entries: Vec<(String, u32)>) -> bool {
        prop_canonical_after_remove(entries)
    }
}