radixt/
lib.rs

1pub(crate) mod node;
2
3pub mod iter;
4pub mod map;
5pub mod set;
6pub use map::RadixMap;
7pub use set::RadixSet;
8
9#[inline]
10fn longest_common_prefix<T>(children: &[node::Node<T>], key: &[u8]) -> (usize, usize) {
11    // If an element exists in the array it returns Ok(index)
12    // If an element does not exist in the array it returns Err(index) where index
13    // is the insert index that maintains the sort order.
14    let byte0 = [key[0]];
15    let idx = match children.binary_search_by_key(&byte0.as_slice(), |k| k.key()) {
16        Ok(idx) => idx,
17        Err(idx) => idx,
18    };
19
20    if (idx >= children.len()) || (children[idx].key()[0] != key[0]) {
21        // Not found
22        return (0, idx);
23    }
24
25    let common_prefix_len = key
26        .iter()
27        .zip(children[idx].key().iter())
28        .take_while(|(a, b)| a == b)
29        .count();
30
31    (common_prefix_len, idx)
32}
33
34#[cfg(test)]
35mod tests {
36    use super::*;
37
38    #[test]
39    fn test_longest_common_prefix() {
40        let mut node: node::Node<()> = node::Node::new("".as_bytes());
41
42        node.push_child(node::Node::new("abb;0".as_bytes()));
43        node.push_child(node::Node::new("cde;1".as_bytes()));
44        node.push_child(node::Node::new("fgh;2".as_bytes()));
45        node.push_child(node::Node::new("ijk;3".as_bytes()));
46
47        assert_eq!(
48            longest_common_prefix(node.children(), "abb;1".as_bytes()),
49            (4, 0)
50        );
51        assert_eq!(
52            longest_common_prefix(node.children(), "abb;0123".as_bytes()),
53            (5, 0)
54        );
55        assert_eq!(
56            longest_common_prefix(node.children(), "fg".as_bytes()),
57            (2, 2)
58        );
59        assert_eq!(
60            longest_common_prefix(node.children(), "ijk;2".as_bytes()),
61            (4, 3)
62        );
63        assert_eq!(
64            longest_common_prefix(node.children(), "ijk;3ab".as_bytes()),
65            (5, 3)
66        );
67        assert_eq!(
68            longest_common_prefix(node.children(), "i".as_bytes()),
69            (1, 3)
70        );
71        assert_eq!(
72            longest_common_prefix(node.children(), "lmo".as_bytes()),
73            (0, 4)
74        );
75        assert_eq!(
76            longest_common_prefix(node.children(), "bar".as_bytes()),
77            (0, 1)
78        );
79    }
80}
radixt/lib.rs

radixt/
lib.rs
