radix_immutable 0.1.0

Generic immutable radix trie data-structure.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

#![cfg(feature = "serde")]

use radix_immutable::StringTrie;

#[test]
fn test_serialize_deserialize_roundtrip() {
    let trie = StringTrie::<String, i32>::new()
        .insert("hello".to_string(), 1)
        .insert("help".to_string(), 2)
        .insert("world".to_string(), 3);

    let json = serde_json::to_string(&trie).unwrap();
    let deserialized: StringTrie<String, i32> = serde_json::from_str(&json).unwrap();

    assert_eq!(deserialized.len(), 3);
    assert_eq!(deserialized.get(&"hello".to_string()), Some(&1));
    assert_eq!(deserialized.get(&"help".to_string()), Some(&2));
    assert_eq!(deserialized.get(&"world".to_string()), Some(&3));
}

#[test]
fn test_serialize_empty_trie() {
    let trie = StringTrie::<String, i32>::new();
    let json = serde_json::to_string(&trie).unwrap();
    assert_eq!(json, "[]");

    let deserialized: StringTrie<String, i32> = serde_json::from_str(&json).unwrap();
    assert!(deserialized.is_empty());
}

#[test]
fn test_serialize_format() {
    let trie = StringTrie::<String, i32>::new()
        .insert("a".to_string(), 1);

    let json = serde_json::to_string(&trie).unwrap();
    // Should serialize as an array of [key, value] pairs
    assert_eq!(json, r#"[["a",1]]"#);
}

#[test]
fn test_deserialize_preserves_all_entries() {
    let original = StringTrie::<String, u32>::new()
        .insert("alpha".to_string(), 1)
        .insert("alphabet".to_string(), 2)
        .insert("beta".to_string(), 3)
        .insert("gamma".to_string(), 4);

    let json = serde_json::to_string(&original).unwrap();
    let restored: StringTrie<String, u32> = serde_json::from_str(&json).unwrap();

    // All entries preserved
    let original_entries: std::collections::HashMap<_, _> = original.iter().collect();
    let restored_entries: std::collections::HashMap<_, _> = restored.iter().collect();
    assert_eq!(original_entries, restored_entries);
}

#[test]
fn test_deserialize_wrong_type_is_error() {
    // Feed it an object instead of an array
    let result = serde_json::from_str::<StringTrie<String, i32>>(r#"{"key": "value"}"#);
    assert!(result.is_err());
}

#[test]
fn test_deserialize_malformed_pairs_is_error() {
    // Array of single values instead of pairs
    let result = serde_json::from_str::<StringTrie<String, i32>>(r#"["hello", "world"]"#);
    assert!(result.is_err());
}

#[test]
fn test_deserialize_wrong_value_type_is_error() {
    // Correct structure but wrong value type (string where int expected)
    let result = serde_json::from_str::<StringTrie<String, i32>>(r#"[["key","not_a_number"]]"#);
    assert!(result.is_err());
}

#[test]
fn test_deserialize_null_is_error() {
    let result = serde_json::from_str::<StringTrie<String, i32>>("null");
    assert!(result.is_err());
}

#[test]
fn test_deserialize_duplicate_keys_last_wins() {
    // Same key appears twice — last value should win (matches FromIterator behavior)
    let json = r#"[["x",1],["x",2]]"#;
    let trie: StringTrie<String, i32> = serde_json::from_str(json).unwrap();
    assert_eq!(trie.len(), 1);
    assert_eq!(trie.get(&"x".to_string()), Some(&2));
}

#[test]
fn test_roundtrip_with_shared_prefixes() {
    // Ensure trie structure (path compression, etc.) survives serialization
    let original = StringTrie::<String, i32>::new()
        .insert("abc".to_string(), 1)
        .insert("abd".to_string(), 2)
        .insert("xyz".to_string(), 3);

    let json = serde_json::to_string(&original).unwrap();
    let restored: StringTrie<String, i32> = serde_json::from_str(&json).unwrap();

    // Structural equality: same entries, same lookup behavior
    assert_eq!(restored.len(), original.len());
    for (k, v) in original.iter() {
        assert_eq!(restored.get(&k), Some(&v));
    }

    // Prefix operations still work on the deserialized trie
    let ab_entries: Vec<_> = restored.iter_prefix("ab".to_string()).collect();
    assert_eq!(ab_entries.len(), 2);
}