forest_ds/
entry.rs

1use crate::{node::Node, tree::Tree};
2
3#[derive(Debug, Clone, Copy, PartialEq, Eq)]
4pub(crate) enum Entry<T> {
5    Free { next_free: Option<usize> },
6    Occupied(Node<T>),
7}
8
9impl<T> Entry<T> {
10    pub fn replace(&mut self, val: Self) -> Self {
11        std::mem::replace(self, val)
12    }
13
14    pub fn is_node(&self) -> bool {
15        matches!(self, Entry::Occupied(..))
16    }
17
18    pub fn unwrap(self) -> Node<T> {
19        match self {
20            Entry::Free { .. } => panic!("the entry is free"),
21            Entry::Occupied(node) => node,
22        }
23    }
24
25    pub fn unwrap_ref(&self) -> &Node<T> {
26        match self {
27            Entry::Free { .. } => panic!("the entry is free"),
28            Entry::Occupied(node) => node,
29        }
30    }
31
32    pub fn unwrap_mut(&mut self) -> &mut Node<T> {
33        match self {
34            Entry::Free { .. } => panic!("the entry is free"),
35            Entry::Occupied(node) => node,
36        }
37    }
38
39    pub fn unwrap_free(&self) -> Option<usize> {
40        match self {
41            Entry::Free { next_free } => *next_free,
42            Entry::Occupied(_) => panic!("the entry is occupied"),
43        }
44    }
45
46    pub fn map_ref<'a, U, F>(&'a self, f: F) -> Option<U>
47    where
48        F: FnOnce(&'a Node<T>) -> U,
49    {
50        match self {
51            Entry::Free { .. } => None,
52            Entry::Occupied(node) => Some(f(node)),
53        }
54    }
55
56    pub fn map_mut<'a, U, F>(&'a mut self, f: F) -> Option<U>
57    where
58        F: FnOnce(&'a mut Node<T>) -> U,
59    {
60        match self {
61            Entry::Free { .. } => None,
62            Entry::Occupied(node) => Some(f(node)),
63        }
64    }
65}
66
67impl<T> Tree<T> {
68    pub(crate) fn get_first_free(&self) -> usize {
69        self.first_free.unwrap_or(self.nodes.len())
70    }
71
72    pub(crate) fn allocate_node(&mut self, node: Node<T>) -> usize {
73        match self.first_free {
74            Some(index) => {
75                let entry = self.nodes[index].replace(Entry::Occupied(node));
76
77                self.first_free = entry.unwrap_free();
78
79                index
80            }
81            None => {
82                let index = self.nodes.len();
83
84                self.nodes.push(Entry::Occupied(node));
85
86                index
87            }
88        }
89    }
90
91    pub(super) fn free_node(&mut self, index: usize) -> Entry<T> {
92        let next_free = self.first_free.replace(index);
93
94        self.nodes[index].replace(Entry::Free { next_free })
95    }
96}
forest_ds/entry.rs

forest_ds/
entry.rs
