1 //! Node. 2 3 #[cfg(not(feature = "std"))] 4 use core::fmt; 5 6 #[cfg(feature = "deser")] 7 use serde::{Deserialize, Serialize}; 8 9 #[cfg(feature = "std")] 10 use std::fmt; 11 12 use crate::{id::NodeStamp, NodeId}; 13 14 #[derive(PartialEq, Eq, Clone, Debug)] 15 #[cfg_attr(feature = "deser", derive(Deserialize, Serialize))] 16 pub(crate) enum NodeData<T> { 17 /// The actual data store 18 Data(T), 19 /// The next free node position. 20 NextFree(Option<usize>), 21 } 22 23 #[derive(PartialEq, Eq, Clone, Debug)] 24 #[cfg_attr(feature = "deser", derive(Deserialize, Serialize))] 25 /// A node within a particular `Arena`. 26 pub struct Node<T> { 27 // Keep these private (with read-only accessors) so that we can keep them 28 // consistent. E.g. the parent of a node’s child is that node. 29 pub(crate) parent: Option<NodeId>, 30 pub(crate) previous_sibling: Option<NodeId>, 31 pub(crate) next_sibling: Option<NodeId>, 32 pub(crate) first_child: Option<NodeId>, 33 pub(crate) last_child: Option<NodeId>, 34 pub(crate) stamp: NodeStamp, 35 /// The actual data which will be stored within the tree. 36 pub(crate) data: NodeData<T>, 37 } 38 39 impl<T> Node<T> { 40 /// Returns a reference to the node data. get(&self) -> &T41 pub fn get(&self) -> &T { 42 if let NodeData::Data(ref data) = self.data { 43 data 44 } else { 45 unreachable!("Try to access a freed node") 46 } 47 } 48 49 /// Returns a mutable reference to the node data. get_mut(&mut self) -> &mut T50 pub fn get_mut(&mut self) -> &mut T { 51 if let NodeData::Data(ref mut data) = self.data { 52 data 53 } else { 54 unreachable!("Try to access a freed node") 55 } 56 } 57 58 /// Creates a new `Node` with the default state and the given data. new(data: T) -> Self59 pub(crate) fn new(data: T) -> Self { 60 Self { 61 parent: None, 62 previous_sibling: None, 63 next_sibling: None, 64 first_child: None, 65 last_child: None, 66 stamp: NodeStamp::default(), 67 data: NodeData::Data(data), 68 } 69 } 70 71 /// Convert a removed `Node` to normal with default state and given data. reuse(&mut self, data: T)72 pub(crate) fn reuse(&mut self, data: T) { 73 debug_assert!(matches!(self.data, NodeData::NextFree(_))); 74 debug_assert!(self.stamp.is_removed()); 75 self.stamp.reuse(); 76 self.parent = None; 77 self.previous_sibling = None; 78 self.next_sibling = None; 79 self.first_child = None; 80 self.last_child = None; 81 self.data = NodeData::Data(data); 82 } 83 84 /// Returns the ID of the parent node, unless this node is the root of the 85 /// tree. 86 /// 87 /// # Examples 88 /// 89 /// ``` 90 /// # use indextree::Arena; 91 /// # let mut arena = Arena::new(); 92 /// # let n1 = arena.new_node("1"); 93 /// # let n1_1 = arena.new_node("1_1"); 94 /// # let n1_2 = arena.new_node("1_2"); 95 /// # n1.append(n1_2, &mut arena); 96 /// # let n1_3 = arena.new_node("1_3"); 97 /// # n1.append(n1_3, &mut arena); 98 /// # n1.append(n1_1, &mut arena); 99 /// // arena 100 /// // `-- 1 101 /// // |-- 1_1 102 /// // |-- 1_2 103 /// // `-- 1_3 104 /// assert_eq!(arena[n1].parent(), None); 105 /// assert_eq!(arena[n1_1].parent(), Some(n1)); 106 /// assert_eq!(arena[n1_2].parent(), Some(n1)); 107 /// assert_eq!(arena[n1_3].parent(), Some(n1)); 108 /// ``` parent(&self) -> Option<NodeId>109 pub fn parent(&self) -> Option<NodeId> { 110 self.parent 111 } 112 113 /// Returns the ID of the first child of this node, unless it has no child. 114 /// 115 /// # Examples 116 /// 117 /// ``` 118 /// # use indextree::Arena; 119 /// # let mut arena = Arena::new(); 120 /// # let n1 = arena.new_node("1"); 121 /// # let n1_1 = arena.new_node("1_1"); 122 /// # n1.append(n1_1, &mut arena); 123 /// # let n1_2 = arena.new_node("1_2"); 124 /// # n1.append(n1_2, &mut arena); 125 /// # let n1_3 = arena.new_node("1_3"); 126 /// # n1.append(n1_3, &mut arena); 127 /// // arena 128 /// // `-- 1 129 /// // |-- 1_1 130 /// // |-- 1_2 131 /// // `-- 1_3 132 /// assert_eq!(arena[n1].first_child(), Some(n1_1)); 133 /// assert_eq!(arena[n1_1].first_child(), None); 134 /// assert_eq!(arena[n1_2].first_child(), None); 135 /// assert_eq!(arena[n1_3].first_child(), None); 136 /// ``` first_child(&self) -> Option<NodeId>137 pub fn first_child(&self) -> Option<NodeId> { 138 self.first_child 139 } 140 141 /// Returns the ID of the last child of this node, unless it has no child. 142 /// 143 /// # Examples 144 /// 145 /// ``` 146 /// # use indextree::Arena; 147 /// # let mut arena = Arena::new(); 148 /// # let n1 = arena.new_node("1"); 149 /// # let n1_1 = arena.new_node("1_1"); 150 /// # n1.append(n1_1, &mut arena); 151 /// # let n1_2 = arena.new_node("1_2"); 152 /// # n1.append(n1_2, &mut arena); 153 /// # let n1_3 = arena.new_node("1_3"); 154 /// # n1.append(n1_3, &mut arena); 155 /// // arena 156 /// // `-- 1 157 /// // |-- 1_1 158 /// // |-- 1_2 159 /// // `-- 1_3 160 /// assert_eq!(arena[n1].last_child(), Some(n1_3)); 161 /// assert_eq!(arena[n1_1].last_child(), None); 162 /// assert_eq!(arena[n1_2].last_child(), None); 163 /// assert_eq!(arena[n1_3].last_child(), None); 164 /// ``` last_child(&self) -> Option<NodeId>165 pub fn last_child(&self) -> Option<NodeId> { 166 self.last_child 167 } 168 169 /// Returns the ID of the previous sibling of this node, unless it is a 170 /// first child. 171 /// 172 /// # Examples 173 /// 174 /// ``` 175 /// # use indextree::Arena; 176 /// # let mut arena = Arena::new(); 177 /// # let n1 = arena.new_node("1"); 178 /// # let n1_1 = arena.new_node("1_1"); 179 /// # n1.append(n1_1, &mut arena); 180 /// # let n1_2 = arena.new_node("1_2"); 181 /// # n1.append(n1_2, &mut arena); 182 /// # let n1_3 = arena.new_node("1_3"); 183 /// # n1.append(n1_3, &mut arena); 184 /// // arena 185 /// // `-- 1 186 /// // |-- 1_1 187 /// // |-- 1_2 188 /// // `-- 1_3 189 /// assert_eq!(arena[n1].previous_sibling(), None); 190 /// assert_eq!(arena[n1_1].previous_sibling(), None); 191 /// assert_eq!(arena[n1_2].previous_sibling(), Some(n1_1)); 192 /// assert_eq!(arena[n1_3].previous_sibling(), Some(n1_2)); 193 /// ``` 194 /// 195 /// Note that newly created nodes are independent toplevel nodes, and they 196 /// are not siblings by default. 197 /// 198 /// ``` 199 /// # use indextree::Arena; 200 /// let mut arena = Arena::new(); 201 /// let n1 = arena.new_node("1"); 202 /// let n2 = arena.new_node("2"); 203 /// // arena 204 /// // |-- (implicit) 205 /// // | `-- 1 206 /// // `-- (implicit) 207 /// // `-- 2 208 /// assert_eq!(arena[n1].previous_sibling(), None); 209 /// assert_eq!(arena[n2].previous_sibling(), None); 210 /// 211 /// n1.insert_after(n2, &mut arena); 212 /// // arena 213 /// // `-- (implicit) 214 /// // |-- 1 215 /// // `-- 2 216 /// assert_eq!(arena[n1].previous_sibling(), None); 217 /// assert_eq!(arena[n2].previous_sibling(), Some(n1)); 218 /// ``` previous_sibling(&self) -> Option<NodeId>219 pub fn previous_sibling(&self) -> Option<NodeId> { 220 self.previous_sibling 221 } 222 223 /// Returns the ID of the next sibling of this node, unless it is a 224 /// last child. 225 /// 226 /// # Examples 227 /// 228 /// ``` 229 /// # use indextree::Arena; 230 /// # let mut arena = Arena::new(); 231 /// # let n1 = arena.new_node("1"); 232 /// # let n1_1 = arena.new_node("1_1"); 233 /// # n1.append(n1_1, &mut arena); 234 /// # let n1_2 = arena.new_node("1_2"); 235 /// # n1.append(n1_2, &mut arena); 236 /// # let n1_3 = arena.new_node("1_3"); 237 /// # n1.append(n1_3, &mut arena); 238 /// // arena 239 /// // `-- 1 240 /// // |-- 1_1 241 /// // |-- 1_2 242 /// // `-- 1_3 243 /// assert_eq!(arena[n1].next_sibling(), None); 244 /// assert_eq!(arena[n1_1].next_sibling(), Some(n1_2)); 245 /// assert_eq!(arena[n1_2].next_sibling(), Some(n1_3)); 246 /// assert_eq!(arena[n1_3].next_sibling(), None); 247 /// ``` 248 /// 249 /// Note that newly created nodes are independent toplevel nodes, and they 250 /// are not siblings by default. 251 /// 252 /// ``` 253 /// # use indextree::Arena; 254 /// let mut arena = Arena::new(); 255 /// let n1 = arena.new_node("1"); 256 /// let n2 = arena.new_node("2"); 257 /// // arena 258 /// // |-- (implicit) 259 /// // | `-- 1 260 /// // `-- (implicit) 261 /// // `-- 2 262 /// assert_eq!(arena[n1].next_sibling(), None); 263 /// assert_eq!(arena[n2].next_sibling(), None); 264 /// 265 /// n1.insert_after(n2, &mut arena); 266 /// // arena 267 /// // `-- (implicit) 268 /// // |-- 1 269 /// // `-- 2 270 /// assert_eq!(arena[n1].next_sibling(), Some(n2)); 271 /// assert_eq!(arena[n2].next_sibling(), None); 272 /// ``` next_sibling(&self) -> Option<NodeId>273 pub fn next_sibling(&self) -> Option<NodeId> { 274 self.next_sibling 275 } 276 277 /// Checks if the node is marked as removed. 278 /// 279 /// # Examples 280 /// 281 /// ``` 282 /// # use indextree::Arena; 283 /// # let mut arena = Arena::new(); 284 /// # let n1 = arena.new_node("1"); 285 /// # let n1_1 = arena.new_node("1_1"); 286 /// # n1.append(n1_1, &mut arena); 287 /// # let n1_2 = arena.new_node("1_2"); 288 /// # n1.append(n1_2, &mut arena); 289 /// # let n1_3 = arena.new_node("1_3"); 290 /// # n1.append(n1_3, &mut arena); 291 /// // arena 292 /// // `-- 1 293 /// // |-- 1_1 294 /// // |-- 1_2 * 295 /// // `-- 1_3 296 /// assert_eq!(arena[n1_1].next_sibling(), Some(n1_2)); 297 /// assert_eq!(arena[n1_2].parent(), Some(n1)); 298 /// assert!(!arena[n1_2].is_removed()); 299 /// assert_eq!(arena[n1_3].previous_sibling(), Some(n1_2)); 300 /// 301 /// n1_2.remove(&mut arena); 302 /// // arena 303 /// // `-- 1 304 /// // |-- 1_1 305 /// // `-- 1_3 306 /// assert_eq!(arena[n1_1].next_sibling(), Some(n1_3)); 307 /// assert_eq!(arena[n1_2].parent(), None); 308 /// assert!(arena[n1_2].is_removed()); 309 /// assert_eq!(arena[n1_3].previous_sibling(), Some(n1_1)); 310 /// ``` is_removed(&self) -> bool311 pub fn is_removed(&self) -> bool { 312 self.stamp.is_removed() 313 } 314 315 /// Checks if the node is detached. is_detached(&self) -> bool316 pub(crate) fn is_detached(&self) -> bool { 317 self.parent.is_none() && self.previous_sibling.is_none() && self.next_sibling.is_none() 318 } 319 } 320 321 impl<T> fmt::Display for Node<T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result322 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 323 if let Some(parent) = self.parent { 324 write!(f, "parent: {}; ", parent)?; 325 } else { 326 write!(f, "no parent; ")?; 327 } 328 if let Some(previous_sibling) = self.previous_sibling { 329 write!(f, "previous sibling: {}; ", previous_sibling)?; 330 } else { 331 write!(f, "no previous sibling; ")?; 332 } 333 if let Some(next_sibling) = self.next_sibling { 334 write!(f, "next sibling: {}; ", next_sibling)?; 335 } else { 336 write!(f, "no next sibling; ")?; 337 } 338 if let Some(first_child) = self.first_child { 339 write!(f, "first child: {}; ", first_child)?; 340 } else { 341 write!(f, "no first child; ")?; 342 } 343 if let Some(last_child) = self.last_child { 344 write!(f, "last child: {}; ", last_child)?; 345 } else { 346 write!(f, "no last child; ")?; 347 } 348 Ok(()) 349 } 350 } 351