artsy 0.1.1

ART Tree data structure library.
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

use std::mem;

use super::{
    Child,
    NodeImpl,
};

use crate::node256::Node256;

pub(crate) struct Node48<'a, T> {
    child_indices: [u8; 256],
    children: [Option<Box<Child<'a, T>>>; 48],
    nb_children: u8,
}

impl<'a, T> Node48<'a, T> {
    #[cfg(any(feature = "node4", feature = "node16"))]
    pub fn new(child_indices: [u8; 256], children: [Option<Box<Child<'a, T>>>; 48], nb_children: u8) -> Self {
        Node48 { child_indices, children, nb_children }
    }

    fn upgrade_to_node256(mut self: Box<Self>) -> Box<Node256<'a, T>> {
        let mut children: [Option<Box<Child<'a, T>>>; 256] = [
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
            None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None,
        ];

        for i in 0..self.child_indices.len() {
            let key = self.child_indices[i] as usize;
            mem::swap(&mut children[key], &mut self.children[self.child_indices[key] as usize]);
        }

        Box::new(Node256::new(children))
    }
}

impl<'a, T> Default for Node48<'a, T> {
    fn default() -> Self {
        Node48 {
            child_indices: [48; 256],
            children: [
                None, None, None, None, None, None,
                None, None, None, None, None, None,
                None, None, None, None, None, None,
                None, None, None, None, None, None,
                None, None, None, None, None, None,
                None, None, None, None, None, None,
                None, None, None, None, None, None,
                None, None, None, None, None, None,
            ],
            nb_children: 0,
        }
    }
}

impl<'a, T> NodeImpl<'a, T> for Node48<'a, T> {
    fn update_child(&mut self, key: u8, child: Child<'a, T>) -> Result<(), Child<'a, T>> {
        let ref mut index = self.child_indices[key as usize];
        if *index >= 48 {
            // If we're adding a new entry, there should be less than 48 entries.
                if self.nb_children < 48 {
                    *index = self.nb_children;
                    self.children[*index as usize] = Some(Box::new(child));
                    self.nb_children += 1;
                    return Ok(());
                }
            } else {
                return Ok(());
            }

            Err(child)
        }

        fn insert_child(&mut self, key: u8, mut child: Child<'a, T>) -> Result<Option<Child<'a, T>>, Child<'a, T>> {
            let ref mut index = self.child_indices[key as usize];
            if *index >= 48 {
                // If we're adding a new entry, there should be less than 48 entries.
                if self.nb_children < 48 {
                    *index = self.nb_children;
                    self.children[*index as usize] = Some(Box::new(child));
                    self.nb_children += 1;
                return Ok(None);
            }
        } else {
            mem::swap(&mut child, self.children[*index as usize].as_mut().unwrap());
            return Ok(Some(child));
        }

        Err(child)
    }

    fn upgrade(self: Box<Self>) -> Box<dyn NodeImpl<'a, T> + 'a> {
        self.upgrade_to_node256()
    }

    fn find_child(&self, key: u8) -> Option<&Child<'a, T>> {
        let index = self.child_indices[key as usize];
        if index < 48 {
            self.children[index as usize].as_ref().map(|x| &**x)
        } else {
            None
        }
    }
}