Let’s code it: Compact tree (part 2)
In the previous post we defined the tree itself and the methods to add and delete a child. This post covers the pack and re-index functionality, this allows the removal of unused space and makes the tree more compact. The pack could be very useful to make the tree easier to load in the cpu cache.
Note that the first post was updated due to the introduction of the new method.
Before starting writing some code let’s see what is the goal of the new method on an example. Let’s say that we a tree with a root and three nodes. We called delete on index 2 child, and pack after:
As you can see from above the node index 2 is moved to index 3 and the node at index 1 is updated with the new index, moreover the last value is dropped from the memory chunk because is not needed anymore.
Note that the allocated space is not dropped, if we want to add a new node we will not pay the allocation cost associated to the memory chunk allocation.
The pack method will move all the deleted nodes at the end of the memory chunk and pack all the valid nodes near the start. Before introducing the method itself, however, we want to write some helpers to:
- retrieve the first deleted node starting from the head of the memory chunk;
/// Returns the next deleted node starting from start
fn find_next_deleted(&self, start: usize) -> Option<usize> {
for i in start..self.nodes.len() {
let n = &self.nodes[i];
// The node is deleted if there is no parent and the next node is pointing to itself
if n.parent.is_none() && n.next_node == Some(i) {
return Some(i);
}
}
None
}- retrieve the first non deleted node starting from the end;
/// Returns the next non deleted node starting from start
fn find_next_not_deleted(&self, start: usize) -> Option<usize> {
for i in (start..self.nodes.len()).rev() {
let n = &self.nodes[i];
// The node is not deleted if is not pointing to itself
if n.next_node != Some(i) {
return Some(i);
}
}
None
}- update two swapped nodes.
fn update_links(&mut self, old_index: usize, new_index: usize) {
// Checks if there is a parent, if not the root is deleted and there is not
// a link to update
if let Some(p) = self[new_index].parent {
// Gets the first child
let first_child = self.nodes[p].first_child;
// Checks if the first child is the node that needs to be moved
if first_child == Some(old_index) {
// Connects the child with the node moved node
self.nodes[p].first_child = Some(new_index);
} else {
// Takes the first sibling
let mut node = first_child;
// Until there is a sibling
while let Some(n) = node {
// If the next node of this sibling is the swapped node,
if self.nodes[n].next_node == Some(old_index) {
// Updates the index with the new one
self.nodes[n].next_node = Some(new_index);
// There should be only one instance of the node in the list
break;
}
// Moves to the next sibling
node = self.nodes[n].next_node;
}
}
// Updates all the children with the new parent
let mut child = self.nodes[new_index].first_child;
// Until there is a child
while let Some(c) = child {
// Updates the child parent with the new index of the moved node
self.nodes[c].parent = Some(new_index);
// Moves to the next child
child = self.nodes[c].next_node;
}
}
// Sets the old_index node to itself, this node is the deleted moved
self.nodes[old_index].next_node = Some(old_index);
}Using the previous methods we can write the pack one, as you can see the implementation is fairly simple compared to the add and delete child:
pub fn pack_nodes_and_reindex(&mut self) -> Vec<(usize, usize)> {
// This contains the pair (old index, new index)
let mut result = Vec::new();
// Checks if there is a deleted node
if let Some(first_delete) = self.node_deleted {
// Starts from the first node, the delete node is not the one closer to the start of the vec
for i in first_delete..self.nodes.len() - 1 {
// Searches for the first deleted node from the start
let deleted = self.find_next_deleted(i);
// Searches for the first non deleted node from the end
let not_deleted = self.find_next_not_deleted(i + 1);
// Checks if there is a deleted node
if let Some(d) = deleted {
// Checks if there is a node to move
if let Some(nd) = not_deleted {
// Swaps only if the indices are in the right position.
// If delete is higher than not delete the pack is completed
if d < nd {
// Swaps the nodes
self.nodes.swap(d, nd);
// Updates the links in the tree
self.update_links(nd, d);
// Pushes the changed index into the list
result.push((nd, d));
} else {
// Nodes found but already in the correct positions
break;
}
} else {
// No node to swap found
break;
}
} else {
// No delete node to swap found
break;
}
}
// Finds the first delete node
if let Some(deleted) = self.find_next_deleted(0) {
// Drop all the values from that index to the end
self.nodes.drain(deleted..self.nodes.len());
}
// Removes the delete node, all the deleted nodes now are removed
self.node_deleted = None;
}
result
}Note that we need to save and return all the new indices because we physically moved some nodes. If the result is empty the tree was already packed.
See you next time!