applejack 0.2.1

Simple implementation of Radix tree
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

use applejack::Rax;

#[test]
pub fn basic_test() {
    let mut root = Rax::<()>::default();
    assert!(!root.exists(&[]));
    root.insert(&[], ());
    assert!(root.exists(&[]));
}

#[test]
pub fn basic_insert_stuff() {
    let a = b"hello alice";
    let b = b"hello kyle";
    let mut root = Rax::default();
    root.insert(a, ());
    root.insert(b, ());
    assert!(root.exists(a));
    assert!(root.exists(b));
    assert!(!root.exists(b"h"));
    assert!(!root.exists(b"hello"));
    assert!(!root.exists(b"alice"));
    assert!(!root.exists(&[]));
}

#[test]
pub fn insert_1_element() {
    let a = b"hello alice";
    let mut root = Rax::default();
    root.insert(a, 10);
    assert!(root.exists(a));
}

#[test]
pub fn basic_insert_and_remove_stuff() {
    let a = b"hello alice";
    let b = b"hello kyle";
    let mut root = Rax::default();
    root.insert(a, 10);
    root.insert(b, 20);
    assert!(root.exists(a));
    assert!(root.exists(b));
    assert_eq!(root.remove(a), Some(10));
    assert!(!root.exists(a));
    assert_eq!(root.remove(b), Some(20));
    assert!(!root.exists(b));
}

#[test]
pub fn basic_insert_and_get_stuff() {
    let a = b"hello alice";
    let b = b"hello kyle";
    let mut root = Rax::default();
    root.insert(a, 10);
    root.insert(b, 20);
    assert_eq!(root.get(a), Some(&10));
    assert_eq!(root.get(b), Some(&20));
    assert_eq!(root.get(&[]), None);
    assert_eq!(root.get(b"hello"), None);
    assert_eq!(root.get(b"alice"), None);
}

#[test]
pub fn insert_and_remove_random_values() {
    let a = b"hello alice";
    let b = b"hello kyle";
    let mut root = Rax::default();
    root.insert(a, 10);
    root.insert(b, 20);
    assert_eq!(root.get(a), Some(&10));
    assert_eq!(root.get(b), Some(&20));
    assert_eq!(root.get(&[]), None);
    assert_eq!(root.get(b"hello"), None);
    assert_eq!(root.get(b"alice"), None);
}

#[test]
pub fn test_remove_remove_remove() {
    let a = b"hello kye";
    let mut root = Rax::default();
    root.remove(a);
    assert!(!root.exists(a));
    root.insert(a, ());
    assert!(root.exists(a));
    root.remove(a);
    root.remove(a);
    assert!(!root.exists(a));
}

#[test]
pub fn test_get_empty() {
    let root = Rax::<()>::default();
    assert!(!root.exists(&[]));
}

#[test]
pub fn test_insert_empty() {
    let mut root = Rax::default();
    root.insert(&[], ());
    root.insert(&[], ());
    root.insert(b"hello", ());
    root.remove(b"hello");
    assert!(root.exists(&[]));
}

#[derive(Debug)]
enum Operation {
    Insert(&'static [u8], u8),
    Remove(&'static [u8]),
}

/// See https://github.com/hbina/applejack/pull/9
#[test]
pub fn test_only_delete_node_if_no_branches() {
    let data = [
        Operation::Insert(&[101, 212, 101, 101, 40, 83, 101, 101], 101),
        Operation::Insert(&[101, 101, 101, 83, 83], 0),
        Operation::Insert(&[101, 101], 233),
        Operation::Insert(&[101, 101, 101, 101, 101], 212),
        Operation::Remove(&[101, 101]),
        Operation::Remove(&[101, 101, 101, 101, 101]),
    ];
    let mut table = std::collections::HashMap::new();
    let mut rax = Rax::default();
    for operation in &data {
        match operation {
            Operation::Insert(key, value) => {
                rax.insert(key, *value);
                table.insert(key, *value);
            }
            Operation::Remove(key) => {
                assert_eq!(rax.remove(key), table.remove(key));
            }
        };
    }
}