///|
/// A single regression tree stored in the flat array layout used by XGBoost.
///
/// Node `i` is a leaf when `left[i] == -1`. For a leaf, `value[i]` is the leaf
/// weight. For a split node, `value[i]` is the split threshold and the sample
/// goes left when `x[feature[i]] < value[i]`. Missing values (NaN) follow
/// `default_left[i]`.
///
/// A node may instead be a categorical split: `categories[i]` holds the sorted
/// category codes that go right; every other non-missing code goes left.
///
/// All arithmetic is done in 32-bit floats, matching XGBoost's `bst_float`,
/// so that comparisons against thresholds behave bit-for-bit the same.
pub struct Tree {
left : Array[Int32]
right : Array[Int32]
feature : Array[Int32]
value : Array[Float]
default_left : Array[Bool]
categories : Array[Array[Int32]?]
priv compiled : Compiled
}
///|
pub fn Tree::new(
left~ : Array[Int32],
right~ : Array[Int32],
feature~ : Array[Int32],
value~ : Array[Float],
default_left~ : Array[Bool],
categories~ : Array[Array[Int32]?] = [],
) -> Tree raise ModelError {
let n = left.length()
if n == 0 {
raise InvalidModel("tree has no nodes")
}
if right.length() != n ||
feature.length() != n ||
value.length() != n ||
default_left.length() != n {
raise InvalidModel("tree arrays have inconsistent lengths")
}
let categories = if categories.length() == 0 {
Array::make(n, None)
} else if categories.length() != n {
raise InvalidModel("categories length \{categories.length()} != \{n}")
} else {
categories.map(c => {
c.map(set => {
let sorted = set.copy()
sorted.sort()
sorted
})
})
}
for i in 0..= n || r >= n {
raise InvalidModel("node \{i} has invalid children (\{l}, \{r})")
}
if feature[i] < 0 {
raise InvalidModel("node \{i} splits on negative feature \{feature[i]}")
}
}
let t = {
left,
right,
feature,
value,
default_left,
categories,
compiled: empty_compiled(),
}
let compiled = compile([t], t.max_feature() + 1)
{ ..t, compiled, }
}
///|
/// Number of nodes in the tree.
pub fn Tree::num_nodes(self : Tree) -> Int32 {
self.left.length()
}
///|
/// Largest feature index used by any split, or -1 for a single-leaf tree.
pub fn Tree::max_feature(self : Tree) -> Int32 {
let mut m = -1
for i in 0.. m {
m = self.feature[i]
}
}
m
}
///|
/// Index of the leaf reached by `row`. Features beyond the end of `row` are
/// treated as missing.
pub fn Tree::leaf_index(self : Tree, row : ArrayView[Float]) -> Int32 {
self.compiled.leaf(0, self.compiled.keys(row))
}
///|
/// Leaf weight reached by `row`.
pub fn Tree::predict(self : Tree, row : ArrayView[Float]) -> Float {
self.value[self.leaf_index(row)]
}