use crate::api::ModelError;
use crate::artifact::{ArtifactError, LogicalTreeNode};
pub(crate) const LEAF_FEATURE: u32 = u32::MAX;
pub(crate) const NO_CHILD: u32 = u32::MAX;
pub(crate) const LEFT_IS_LEAF: u32 = 1 << 31;
pub(crate) const RIGHT_IS_LEAF: u32 = 1 << 30;
pub(crate) const FEATURE_MASK: u32 = RIGHT_IS_LEAF - 1;
#[derive(Clone, Copy, Debug, PartialEq)]
#[repr(C)]
pub(crate) struct BuildNode {
pub(crate) feature: u32,
pub(crate) left: u32,
pub(crate) right: u32,
pub(crate) payload: f32,
}
impl BuildNode {
#[inline]
pub(crate) fn is_leaf(&self) -> bool {
self.feature == LEAF_FEATURE
}
#[inline]
pub(crate) fn threshold(&self) -> f32 {
debug_assert!(!self.is_leaf());
self.payload
}
#[inline]
pub(crate) fn value(&self) -> f32 {
debug_assert!(self.is_leaf());
self.payload
}
pub(crate) fn leaf(value: f32) -> Self {
Self {
feature: LEAF_FEATURE,
left: NO_CHILD,
right: NO_CHILD,
payload: value,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq)]
#[repr(C)]
pub(crate) struct PackedNode {
pub(crate) left: u32,
pub(crate) right: u32,
pub(crate) threshold: f32,
pub(crate) feature_and_flags: u32,
}
#[derive(Clone, Debug, PartialEq)]
pub(crate) struct PackedTree {
pub(crate) nodes: Vec<PackedNode>,
pub(crate) root_leaf: Option<f32>,
}
fn pack_topology(
build: &[BuildNode],
n_features: usize,
mut encode_leaf: impl FnMut(usize, BuildNode) -> u32,
) -> Result<Option<Vec<PackedNode>>, ModelError> {
validate_build_topology(build, n_features)?;
if build[0].is_leaf() {
return Ok(None);
}
let mut branch_indices = vec![NO_CHILD; build.len()];
let mut nodes = Vec::new();
for (index, node) in build.iter().enumerate() {
if !node.is_leaf() {
let packed_index = u32::try_from(nodes.len()).map_err(|_| ModelError::TreeTooLarge)?;
nodes.push(PackedNode {
left: 0,
right: 0,
threshold: node.threshold(),
feature_and_flags: node.feature,
});
branch_indices[index] = packed_index;
}
}
for (index, node) in build.iter().enumerate().filter(|(_, node)| !node.is_leaf()) {
let left = build[node.left as usize];
let right = build[node.right as usize];
let packed = &mut nodes[branch_indices[index] as usize];
if left.is_leaf() {
packed.feature_and_flags |= LEFT_IS_LEAF;
packed.left = encode_leaf(node.left as usize, left);
} else {
packed.left = branch_indices[node.left as usize];
}
if right.is_leaf() {
packed.feature_and_flags |= RIGHT_IS_LEAF;
packed.right = encode_leaf(node.right as usize, right);
} else {
packed.right = branch_indices[node.right as usize];
}
}
Ok(Some(nodes))
}
impl PackedTree {
pub(crate) fn from_build_nodes(
build: Vec<BuildNode>,
n_features: usize,
) -> Result<Self, ModelError> {
let Some(nodes) = pack_topology(&build, n_features, |_, node| node.value().to_bits())?
else {
return Ok(Self {
nodes: Vec::new(),
root_leaf: Some(build[0].value()),
});
};
let tree = Self {
nodes,
root_leaf: None,
};
debug_assert!(tree.has_valid_packed_topology(n_features));
Ok(tree)
}
#[inline(always)]
pub(crate) fn predict(&self, row: &[f32]) -> f32 {
if let Some(value) = self.root_leaf {
return value;
}
let mut index = 0usize;
loop {
debug_assert!(
index < self.nodes.len(),
"packed branch token {index} is outside a {}-node tree",
self.nodes.len()
);
let node = unsafe { self.nodes.get_unchecked(index) };
let feature = (node.feature_and_flags & FEATURE_MASK) as usize;
debug_assert!(
feature < row.len(),
"packed feature {feature} is outside a {}-wide row",
row.len()
);
let value = unsafe { *row.get_unchecked(feature) };
if value <= node.threshold {
if node.feature_and_flags & LEFT_IS_LEAF != 0 {
return f32::from_bits(node.left);
}
index = node.left as usize;
} else {
if node.feature_and_flags & RIGHT_IS_LEAF != 0 {
return f32::from_bits(node.right);
}
index = node.right as usize;
}
}
}
fn has_valid_packed_topology(&self, n_features: usize) -> bool {
if self.root_leaf.is_some() {
return self.nodes.is_empty() && self.root_leaf.is_some_and(f32::is_finite);
}
!self.nodes.is_empty()
&& self.nodes.iter().all(|node| {
((node.feature_and_flags & FEATURE_MASK) as usize) < n_features
&& node.threshold.is_finite()
&& child_is_valid(
node.left,
node.feature_and_flags & LEFT_IS_LEAF,
self.nodes.len(),
)
&& child_is_valid(
node.right,
node.feature_and_flags & RIGHT_IS_LEAF,
self.nodes.len(),
)
})
}
}
impl PackedTree {
pub(crate) fn logical_node_count(&self) -> usize {
if self.root_leaf.is_some() {
1
} else {
self.nodes.len() * 2 + 1
}
}
pub(crate) fn max_abs_leaf(&self) -> f32 {
if let Some(value) = self.root_leaf {
return value.abs();
}
self.nodes.iter().fold(0.0_f32, |largest, node| {
let mut largest = largest;
if node.feature_and_flags & LEFT_IS_LEAF != 0 {
largest = largest.max(f32::from_bits(node.left).abs());
}
if node.feature_and_flags & RIGHT_IS_LEAF != 0 {
largest = largest.max(f32::from_bits(node.right).abs());
}
largest
})
}
pub(crate) fn to_logical_nodes(&self) -> Vec<LogicalTreeNode> {
if let Some(value) = self.root_leaf {
return vec![LogicalTreeNode::Leaf { value }];
}
let mut nodes = Vec::with_capacity(self.nodes.len() * 2 + 1);
let mut pending = vec![Emit::Branch(0)];
while let Some(task) = pending.pop() {
match task {
Emit::Leaf(bits) => nodes.push(LogicalTreeNode::Leaf {
value: f32::from_bits(bits),
}),
Emit::AttachRight(parent) => {
let right = u32::try_from(nodes.len()).expect("bounded node count");
match &mut nodes[parent] {
LogicalTreeNode::Branch { right: slot, .. } => *slot = right,
LogicalTreeNode::Leaf { .. } => unreachable!("branch record"),
}
}
Emit::Branch(packed_index) => {
let node = self.nodes[packed_index];
let index = nodes.len();
let left = u32::try_from(index + 1).expect("bounded node count");
nodes.push(LogicalTreeNode::Branch {
feature: node.feature_and_flags & FEATURE_MASK,
threshold: node.threshold,
left,
right: 0,
});
pending.push(child(node.right, node.feature_and_flags & RIGHT_IS_LEAF));
pending.push(Emit::AttachRight(index));
pending.push(child(node.left, node.feature_and_flags & LEFT_IS_LEAF));
}
}
}
nodes
}
pub(crate) fn from_logical_nodes(
nodes: &[LogicalTreeNode],
n_features: usize,
) -> Result<Self, ArtifactError> {
let build = nodes
.iter()
.map(|&node| match node {
LogicalTreeNode::Leaf { value } => BuildNode::leaf(value),
LogicalTreeNode::Branch {
feature,
threshold,
left,
right,
} => BuildNode {
feature,
left,
right,
payload: threshold,
},
})
.collect();
Self::from_build_nodes(build, n_features).map_err(|_| ArtifactError::InvalidPayload)
}
}
#[derive(Clone, Debug, PartialEq)]
pub(crate) struct ClassTree {
nodes: Vec<PackedNode>,
probabilities: Vec<f32>,
classes: usize,
}
impl ClassTree {
pub(crate) fn from_build_nodes(
build: Vec<BuildNode>,
class_weights: &[f64],
weights: &[f64],
classes: usize,
n_features: usize,
) -> Result<Self, ModelError> {
debug_assert_eq!(class_weights.len(), build.len() * classes);
debug_assert_eq!(weights.len(), build.len());
let mut probabilities = Vec::new();
let mut push_leaf = |index: usize| {
let total = weights[index];
for class in 0..classes {
probabilities.push((class_weights[index * classes + class] / total) as f32);
}
};
let mut ordinal = 0_u32;
let nodes = pack_topology(&build, n_features, |index, _| {
push_leaf(index);
let assigned = ordinal;
ordinal += 1;
assigned
})?;
let Some(nodes) = nodes else {
push_leaf(0);
return Ok(Self {
nodes: Vec::new(),
probabilities,
classes,
});
};
let tree = Self {
nodes,
probabilities,
classes,
};
if !tree.has_valid_class_topology(n_features) {
return Err(ModelError::TreeTooLarge);
}
Ok(tree)
}
#[inline]
pub(crate) fn classes(&self) -> usize {
self.classes
}
#[inline(always)]
pub(crate) fn probabilities(&self, row: &[f32]) -> &[f32] {
let ordinal = if self.nodes.is_empty() {
0
} else {
self.leaf_ordinal(row) as usize
};
&self.probabilities[ordinal * self.classes..(ordinal + 1) * self.classes]
}
#[inline(always)]
fn leaf_ordinal(&self, row: &[f32]) -> u32 {
let mut index = 0usize;
loop {
let node = self.nodes[index];
let value = row[(node.feature_and_flags & FEATURE_MASK) as usize];
if value <= node.threshold {
if node.feature_and_flags & LEFT_IS_LEAF != 0 {
return node.left;
}
index = node.left as usize;
} else {
if node.feature_and_flags & RIGHT_IS_LEAF != 0 {
return node.right;
}
index = node.right as usize;
}
}
}
fn has_valid_class_topology(&self, n_features: usize) -> bool {
let leaves = self.nodes.len() + 1;
if self.probabilities.len() != leaves * self.classes || self.classes == 0 {
return false;
}
if !self
.probabilities
.iter()
.all(|value| value.is_finite() && (0.0..=1.0).contains(value))
{
return false;
}
self.nodes.iter().all(|node| {
((node.feature_and_flags & FEATURE_MASK) as usize) < n_features
&& node.threshold.is_finite()
&& class_child_is_valid(
node.left,
node.feature_and_flags & LEFT_IS_LEAF,
self.nodes.len(),
leaves,
)
&& class_child_is_valid(
node.right,
node.feature_and_flags & RIGHT_IS_LEAF,
self.nodes.len(),
leaves,
)
})
}
}
impl ClassTree {
pub(crate) fn logical_node_count(&self) -> usize {
if self.nodes.is_empty() {
1
} else {
self.nodes.len() * 2 + 1
}
}
pub(crate) fn to_logical_nodes(&self) -> (Vec<LogicalTreeNode>, Vec<f32>) {
let leaves = self.nodes.len() + 1;
let mut probabilities = Vec::with_capacity(leaves * self.classes);
if self.nodes.is_empty() {
probabilities.extend_from_slice(&self.probabilities[..self.classes]);
return (vec![LogicalTreeNode::Leaf { value: 0.0 }], probabilities);
}
let mut nodes = Vec::with_capacity(self.nodes.len() * 2 + 1);
let mut pending = vec![Emit::Branch(0)];
while let Some(task) = pending.pop() {
match task {
Emit::Leaf(ordinal) => {
let start = ordinal as usize * self.classes;
probabilities
.extend_from_slice(&self.probabilities[start..start + self.classes]);
nodes.push(LogicalTreeNode::Leaf { value: 0.0 });
}
Emit::AttachRight(parent) => {
let right = u32::try_from(nodes.len()).expect("bounded node count");
match &mut nodes[parent] {
LogicalTreeNode::Branch { right: slot, .. } => *slot = right,
LogicalTreeNode::Leaf { .. } => unreachable!("branch record"),
}
}
Emit::Branch(packed_index) => {
let node = self.nodes[packed_index];
let index = nodes.len();
let left = u32::try_from(index + 1).expect("bounded node count");
nodes.push(LogicalTreeNode::Branch {
feature: node.feature_and_flags & FEATURE_MASK,
threshold: node.threshold,
left,
right: 0,
});
pending.push(child(node.right, node.feature_and_flags & RIGHT_IS_LEAF));
pending.push(Emit::AttachRight(index));
pending.push(child(node.left, node.feature_and_flags & LEFT_IS_LEAF));
}
}
}
(nodes, probabilities)
}
pub(crate) fn from_logical_nodes(
nodes: &[LogicalTreeNode],
leaf_probabilities: &[f32],
classes: usize,
n_features: usize,
) -> Result<Self, ArtifactError> {
if classes == 0 {
return Err(ArtifactError::InvalidPayload);
}
let mut build = Vec::with_capacity(nodes.len());
let mut leaf_rank = vec![0_usize; nodes.len()];
let mut leaves = 0_usize;
for (index, &node) in nodes.iter().enumerate() {
match node {
LogicalTreeNode::Leaf { value } => {
if value.to_bits() != 0 {
return Err(ArtifactError::InvalidPayload);
}
leaf_rank[index] = leaves;
leaves += 1;
build.push(BuildNode::leaf(0.0));
}
LogicalTreeNode::Branch {
feature,
threshold,
left,
right,
} => build.push(BuildNode {
feature,
left,
right,
payload: threshold,
}),
}
}
if leaves
.checked_mul(classes)
.is_none_or(|expected| expected != leaf_probabilities.len())
{
return Err(ArtifactError::InvalidPayload);
}
let mut probabilities = Vec::with_capacity(leaf_probabilities.len());
let mut push_leaf = |index: usize| {
let start = leaf_rank[index] * classes;
probabilities.extend_from_slice(&leaf_probabilities[start..start + classes]);
};
let mut ordinal = 0_u32;
let packed = pack_topology(&build, n_features, |index, _| {
push_leaf(index);
let assigned = ordinal;
ordinal += 1;
assigned
})
.map_err(|_| ArtifactError::InvalidPayload)?;
let tree = match packed {
None => {
push_leaf(0);
Self {
nodes: Vec::new(),
probabilities,
classes,
}
}
Some(nodes) => Self {
nodes,
probabilities,
classes,
},
};
if !tree.has_valid_class_topology(n_features) {
return Err(ArtifactError::InvalidPayload);
}
Ok(tree)
}
}
fn class_child_is_valid(value: u32, leaf_flag: u32, node_count: usize, leaves: usize) -> bool {
if leaf_flag != 0 {
(value as usize) < leaves
} else {
(value as usize) < node_count
}
}
enum Emit {
Branch(usize),
Leaf(u32),
AttachRight(usize),
}
fn child(value: u32, leaf_flag: u32) -> Emit {
if leaf_flag != 0 {
Emit::Leaf(value)
} else {
Emit::Branch(value as usize)
}
}
fn child_is_valid(value: u32, leaf_flag: u32, node_count: usize) -> bool {
if leaf_flag != 0 {
f32::from_bits(value).is_finite()
} else {
(value as usize) < node_count
}
}
fn validate_build_topology(build: &[BuildNode], n_features: usize) -> Result<(), ModelError> {
if build.is_empty() || n_features == 0 {
return Err(ModelError::TreeTooLarge);
}
let mut seen = vec![false; build.len()];
let mut stack = vec![0_usize];
while let Some(index) = stack.pop() {
if index >= build.len() || seen[index] {
return Err(ModelError::TreeTooLarge);
}
seen[index] = true;
let node = build[index];
if !node.payload.is_finite() {
return Err(ModelError::TreeTooLarge);
}
if node.is_leaf() {
if node.left != NO_CHILD || node.right != NO_CHILD {
return Err(ModelError::TreeTooLarge);
}
continue;
}
let left = node.left as usize;
let right = node.right as usize;
if node.feature as usize >= n_features
|| left != index + 1
|| right <= left
|| right >= build.len()
{
return Err(ModelError::TreeTooLarge);
}
stack.push(right);
stack.push(left);
}
if seen.iter().any(|&visited| !visited) {
return Err(ModelError::TreeTooLarge);
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn rejects_invalid_builder_topologies_before_packing() {
assert_eq!(
PackedTree::from_build_nodes(Vec::new(), 1),
Err(ModelError::TreeTooLarge)
);
assert_eq!(
PackedTree::from_build_nodes(vec![BuildNode::leaf(0.0)], 0),
Err(ModelError::TreeTooLarge)
);
let invalid_feature = vec![
BuildNode {
feature: 1,
left: 1,
right: 2,
payload: 0.5,
},
BuildNode::leaf(0.0),
BuildNode::leaf(1.0),
];
assert_eq!(
PackedTree::from_build_nodes(invalid_feature, 1),
Err(ModelError::TreeTooLarge)
);
let cycle = vec![
BuildNode {
feature: 0,
left: 0,
right: 2,
payload: 0.5,
},
BuildNode::leaf(0.0),
BuildNode::leaf(1.0),
];
assert_eq!(
PackedTree::from_build_nodes(cycle, 1),
Err(ModelError::TreeTooLarge)
);
}
fn branch(feature: u32, threshold: f32, left: u32, right: u32) -> BuildNode {
BuildNode {
feature,
left,
right,
payload: threshold,
}
}
fn mixed_depth_build() -> Vec<BuildNode> {
vec![
branch(0, 1.0, 1, 4),
branch(1, 2.0, 2, 3),
BuildNode::leaf(-1.0),
BuildNode::leaf(3.0),
branch(0, 5.0, 5, 6),
BuildNode::leaf(7.0),
branch(1, 0.0, 7, 8),
BuildNode::leaf(11.0),
BuildNode::leaf(13.0),
]
}
#[test]
fn logical_records_synthesize_inline_leaves_and_round_trip_to_the_same_tree() {
let build = mixed_depth_build();
let tree = PackedTree::from_build_nodes(build.clone(), 2).unwrap();
assert_eq!(tree.nodes.len(), 4);
let logical = tree.to_logical_nodes();
assert_eq!(logical.len(), build.len());
assert_eq!(
logical
.iter()
.filter(|node| matches!(node, LogicalTreeNode::Leaf { .. }))
.count(),
5
);
for (index, (&logical_node, build_node)) in logical.iter().zip(&build).enumerate() {
let expected = if build_node.is_leaf() {
LogicalTreeNode::Leaf {
value: build_node.value(),
}
} else {
LogicalTreeNode::Branch {
feature: build_node.feature,
threshold: build_node.threshold(),
left: build_node.left,
right: build_node.right,
}
};
assert_eq!(logical_node, expected, "record {index}");
}
let restored = PackedTree::from_logical_nodes(&logical, 2).unwrap();
assert_eq!(restored, tree);
assert_eq!(restored.to_logical_nodes(), logical);
for row in [[0.0, 0.0], [0.0, 9.0], [3.0, 0.0], [9.0, -1.0], [9.0, 9.0]] {
assert_eq!(restored.predict(&row), tree.predict(&row));
}
}
#[test]
fn a_root_leaf_tree_maps_to_the_one_node_logical_tree() {
let tree = PackedTree::from_build_nodes(vec![BuildNode::leaf(2.5)], 3).unwrap();
assert!(tree.nodes.is_empty());
let logical = tree.to_logical_nodes();
assert_eq!(logical, vec![LogicalTreeNode::Leaf { value: 2.5 }]);
let restored = PackedTree::from_logical_nodes(&logical, 3).unwrap();
assert_eq!(restored.root_leaf, Some(2.5));
assert_eq!(restored, tree);
}
#[test]
fn logical_records_are_revalidated_instead_of_trusted() {
let valid = PackedTree::from_build_nodes(mixed_depth_build(), 2)
.unwrap()
.to_logical_nodes();
assert!(PackedTree::from_logical_nodes(&valid, 2).is_ok());
let cases: [(&str, Vec<LogicalTreeNode>, usize); 5] = [
("empty", Vec::new(), 2),
(
"feature beyond the fitted width",
vec![
LogicalTreeNode::Branch {
feature: 2,
threshold: 1.0,
left: 1,
right: 2,
},
LogicalTreeNode::Leaf { value: 0.0 },
LogicalTreeNode::Leaf { value: 1.0 },
],
2,
),
(
"leaf sentinel smuggled in as a branch feature",
vec![
LogicalTreeNode::Branch {
feature: LEAF_FEATURE,
threshold: 1.0,
left: 1,
right: 2,
},
LogicalTreeNode::Leaf { value: 0.0 },
LogicalTreeNode::Leaf { value: 1.0 },
],
2,
),
(
"non-finite leaf value",
vec![
LogicalTreeNode::Branch {
feature: 0,
threshold: 1.0,
left: 1,
right: 2,
},
LogicalTreeNode::Leaf {
value: f32::INFINITY,
},
LogicalTreeNode::Leaf { value: 1.0 },
],
2,
),
(
"unreachable trailing record",
vec![
LogicalTreeNode::Branch {
feature: 0,
threshold: 1.0,
left: 1,
right: 2,
},
LogicalTreeNode::Leaf { value: 0.0 },
LogicalTreeNode::Leaf { value: 1.0 },
LogicalTreeNode::Leaf { value: 2.0 },
],
2,
),
];
for (name, nodes, n_features) in cases {
assert_eq!(
PackedTree::from_logical_nodes(&nodes, n_features),
Err(ArtifactError::InvalidPayload),
"{name} was accepted"
);
}
assert_eq!(
PackedTree::from_logical_nodes(&valid, 0),
Err(ArtifactError::InvalidPayload)
);
}
fn skewed_class_build() -> Vec<BuildNode> {
vec![
branch(0, 1.0, 1, 4),
branch(1, 2.0, 2, 3),
BuildNode::leaf(0.0),
BuildNode::leaf(0.0),
BuildNode::leaf(0.0),
]
}
const PRE_ORDER_BLOCK: [f32; 6] = [0.25, 0.75, 0.5, 0.5, 0.125, 0.875];
const ROWS_BY_PRE_ORDER_RANK: [[f32; 2]; 3] = [[0.0, 0.0], [0.0, 9.0], [9.0, 0.0]];
fn skewed_class_tree() -> ClassTree {
let mut class_weights = vec![0.0_f64; 5 * 2];
class_weights[2 * 2..2 * 2 + 2].copy_from_slice(&[0.25, 0.75]);
class_weights[3 * 2..3 * 2 + 2].copy_from_slice(&[0.5, 0.5]);
class_weights[4 * 2..4 * 2 + 2].copy_from_slice(&[0.125, 0.875]);
ClassTree::from_build_nodes(skewed_class_build(), &class_weights, &[1.0; 5], 2, 2).unwrap()
}
#[test]
fn the_class_leaf_block_is_ordered_by_pre_order_rank_not_by_runtime_ordinal() {
let tree = skewed_class_tree();
assert_eq!(tree.probabilities, vec![0.125, 0.875, 0.25, 0.75, 0.5, 0.5]);
assert_ne!(tree.probabilities, PRE_ORDER_BLOCK.to_vec());
for (rank, row) in ROWS_BY_PRE_ORDER_RANK.iter().enumerate() {
assert_eq!(
tree.probabilities(row),
&PRE_ORDER_BLOCK[rank * 2..rank * 2 + 2],
"row {row:?} does not reach pre-order leaf {rank}"
);
}
let (records, block) = tree.to_logical_nodes();
assert_eq!(block, PRE_ORDER_BLOCK.to_vec());
assert_eq!(
records
.iter()
.enumerate()
.filter(|(_, node)| matches!(node, LogicalTreeNode::Leaf { .. }))
.map(|(index, _)| index)
.collect::<Vec<_>>(),
vec![2, 3, 4]
);
let decoded = ClassTree::from_logical_nodes(&records, &PRE_ORDER_BLOCK, 2, 2).unwrap();
assert_eq!(decoded, tree);
for (rank, row) in ROWS_BY_PRE_ORDER_RANK.iter().enumerate() {
assert_eq!(
decoded.probabilities(row),
&PRE_ORDER_BLOCK[rank * 2..rank * 2 + 2],
"decoded row {row:?} does not reach pre-order leaf {rank}"
);
}
let as_ordinals: Vec<f32> = tree.probabilities.clone();
let misread = ClassTree::from_logical_nodes(&records, &as_ordinals, 2, 2).unwrap();
assert_ne!(misread, tree);
}
#[test]
fn deep_left_spines_convert_without_recursing() {
let depth = 4_096;
let mut build = Vec::with_capacity(depth * 2 + 1);
for index in 0..depth {
build.push(branch(
0,
0.5,
(index + 1) as u32,
(depth * 2 - index) as u32,
));
}
build.push(BuildNode::leaf(7.0));
build.extend((0..depth).map(|_| BuildNode::leaf(-1.0)));
let tree = PackedTree::from_build_nodes(build, 1).unwrap();
let logical = tree.to_logical_nodes();
assert_eq!(logical.len(), depth * 2 + 1);
assert_eq!(PackedTree::from_logical_nodes(&logical, 1).unwrap(), tree);
}
}