use crate::entropy::Token;
use crate::lossless::kit::emit_forest_bfs;
use crate::ma_tree::{LearnedTree, MaNode};
pub(crate) const SAMPLE_TARGET: usize = 1 << 16;
pub(crate) const BUDGET_DIV: usize = 1024;
pub(crate) const BUDGET_CAP: usize = 256;
pub(crate) fn emit_forest(
trees: &[LearnedTree],
tag_mults: &[u32],
split: usize,
n_dc_slots: usize,
num_dc_groups: usize,
) -> (Vec<Token>, Vec<u32>, Vec<u32>, u32) {
let n_tags = trees.len();
let n_ac_slots = n_tags - split - n_dc_slots;
debug_assert!(split > 0 && (n_ac_slots > 0 || n_dc_slots == 0));
let mut nodes: Vec<MaNode> = Vec::new();
let mut mult_of: Vec<u32> = Vec::new();
let mut tag_base = vec![0u32; n_tags];
let append_tree = |nodes: &mut Vec<MaNode>, mult_of: &mut Vec<u32>, t: usize| -> u32 {
let base = nodes.len() as u32;
for n in &trees[t].nodes {
nodes.push(match *n {
MaNode::Split { prop, val, gt, le } => MaNode::Split {
prop,
val,
gt: gt + base,
le: le + base,
},
leaf @ MaNode::Leaf { .. } => leaf,
});
mult_of.push(tag_mults[t]);
}
base
};
let build_chain = |nodes: &mut Vec<MaNode>,
mult_of: &mut Vec<u32>,
tag_base: &mut [u32],
lo: usize,
n: usize|
-> u32 {
let base0 = append_tree(nodes, mult_of, lo);
tag_base[lo] = base0;
let mut acc = base0;
for k in 1..n {
let sub = append_tree(nodes, mult_of, lo + k);
tag_base[lo + k] = sub;
nodes.push(MaNode::Split {
prop: 0,
val: (k - 1) as i32,
gt: sub,
le: acc,
});
mult_of.push(1);
acc = (nodes.len() - 1) as u32;
}
acc
};
let global_root = build_chain(&mut nodes, &mut mult_of, &mut tag_base, 0, split);
if n_ac_slots == 0 {
return emit_forest_bfs(&nodes, &mult_of, global_root, tag_base);
}
let ac_root = build_chain(
&mut nodes,
&mut mult_of,
&mut tag_base,
split + n_dc_slots,
n_ac_slots,
);
let low_root = if n_dc_slots > 0 {
let dc_root = build_chain(&mut nodes, &mut mult_of, &mut tag_base, split, n_dc_slots);
nodes.push(MaNode::Split {
prop: 1,
val: 0,
gt: dc_root,
le: global_root,
});
mult_of.push(1);
(nodes.len() - 1) as u32
} else {
global_root
};
nodes.push(MaNode::Split {
prop: 1,
val: (2 * num_dc_groups) as i32,
gt: ac_root,
le: low_root,
});
mult_of.push(1);
let root = (nodes.len() - 1) as u32;
emit_forest_bfs(&nodes, &mult_of, root, tag_base)
}