use std::vec;
use std::vec::Vec;
use super::bitwriter::BitWriter;
pub const MAX_CODE_LEN: u8 = 17;
const _: () = assert!(MAX_CODE_LEN >= 1 && MAX_CODE_LEN <= 20);
pub const GROUP_SIZE: usize = 50;
const N_ITERS: usize = 4;
pub struct Coding {
pub n_groups: usize,
pub selectors: Vec<u8>,
pub lens: Vec<Vec<u8>>,
pub codes: Vec<Vec<u32>>,
}
fn group_count(n_syms: usize) -> usize { match n_syms { 0..=199 => 2, 200..=599 => 3, 600..=1199 => 4, 1200..=2399 => 5, _ => 6 } }
pub fn build(syms: &[u16], alpha_size: usize) -> Coding {
assert!(!syms.is_empty(), "empty symbol stream");
assert!(alpha_size >= 3);
let n_groups = group_count(syms.len());
let mut lens = initial_lengths(syms, alpha_size, n_groups);
for _ in 0..N_ITERS {
let mut rfreq = vec![vec![0u32; alpha_size]; n_groups];
let selectors = assign_selectors(syms, &lens);
for (g, &t) in selectors.iter().enumerate() {
let start = g * GROUP_SIZE;
let end = (start + GROUP_SIZE).min(syms.len());
for &s in &syms[start..end] { rfreq[t as usize][s as usize] += 1; }
}
for (t, len) in lens.iter_mut().enumerate() {
let weights: Vec<u64> = rfreq[t].iter().map(|&f| f.max(1) as u64).collect();
*len = package_merge(&weights, MAX_CODE_LEN);
}
}
let selectors = assign_selectors(syms, &lens);
let codes = lens.iter().map(|l| canonical_codes(l)).collect();
Coding { n_groups, selectors, lens, codes }
}
fn assign_selectors(syms: &[u16], lens: &[Vec<u8>]) -> Vec<u8> {
let mut selectors = Vec::with_capacity(syms.len() / GROUP_SIZE + 1);
let mut start = 0usize;
while start < syms.len() {
let end = (start + GROUP_SIZE).min(syms.len());
let mut best = 0usize;
let mut best_cost = u64::MAX;
for (t, len) in lens.iter().enumerate() {
let cost: u64 = syms[start..end].iter().map(|&s| len[s as usize] as u64).sum();
if cost < best_cost {
best_cost = cost;
best = t;
}
}
selectors.push(best as u8);
start = end;
}
selectors
}
fn initial_lengths(syms: &[u16], alpha_size: usize, n_groups: usize) -> Vec<Vec<u8>> {
let mut freq = vec![0u32; alpha_size];
for &s in syms { freq[s as usize] += 1; }
let mut lens = vec![vec![0u8; alpha_size]; n_groups];
let mut remaining: u32 = syms.len() as u32;
let mut gs: usize = 0;
let mut n_part = n_groups;
while n_part > 0 {
let target = remaining / n_part as u32;
let mut ge: isize = gs as isize - 1;
let mut acc: u32 = 0;
while acc < target && ge < alpha_size as isize - 1 {
ge += 1;
acc += freq[ge as usize];
}
if ge > gs as isize && n_part != n_groups && n_part != 1 && (n_groups - n_part) % 2 == 1 {
acc -= freq[ge as usize];
ge -= 1;
}
for (v, slot) in lens[n_part - 1].iter_mut().enumerate() { *slot = if v as isize >= gs as isize && v as isize <= ge { 1 } else { 15 }; }
n_part -= 1;
gs = (ge + 1) as usize;
remaining -= acc;
}
lens
}
pub fn package_merge(weights: &[u64], limit: u8) -> Vec<u8> {
let m = weights.len();
assert!(m >= 2, "package-merge needs at least two symbols");
assert!(limit >= 1 && (limit >= 32 || (1u64 << limit) >= m as u64), "code-length limit too small for the alphabet");
const NONE: u32 = u32::MAX;
let mut weight: Vec<u64> = Vec::with_capacity(m * 2);
let mut left: Vec<u32> = Vec::with_capacity(m * 2);
let mut right: Vec<u32> = Vec::with_capacity(m * 2);
let mut order: Vec<usize> = (0..m).collect();
order.sort_by_key(|&i| (weights[i], i));
let mut leaves: Vec<u32> = Vec::with_capacity(m);
for &sym in &order {
weight.push(weights[sym]);
left.push(NONE);
right.push(sym as u32);
leaves.push((weight.len() - 1) as u32);
}
let mut level = leaves.clone();
for _ in 1..limit {
let mut packaged: Vec<u32> = Vec::with_capacity(level.len() / 2);
let mut i = 0;
while i + 1 < level.len() {
let (a, b) = (level[i], level[i + 1]);
weight.push(weight[a as usize] + weight[b as usize]);
left.push(a);
right.push(b);
packaged.push((weight.len() - 1) as u32);
i += 2;
}
let mut merged = Vec::with_capacity(leaves.len() + packaged.len());
let (mut x, mut y) = (0usize, 0usize);
while x < leaves.len() || y < packaged.len() {
let take_leaf = y >= packaged.len() || (x < leaves.len() && weight[leaves[x] as usize] <= weight[packaged[y] as usize]);
if take_leaf {
merged.push(leaves[x]);
x += 1;
} else {
merged.push(packaged[y]);
y += 1;
}
}
level = merged;
}
let mut lens = vec![0u8; m];
let mut stack: Vec<u32> = Vec::new();
for &node in level.iter().take(2 * m - 2) {
stack.push(node);
while let Some(nd) = stack.pop() {
if left[nd as usize] == NONE { lens[right[nd as usize] as usize] += 1; } else {
stack.push(left[nd as usize]);
stack.push(right[nd as usize]);
}
}
}
debug_assert!(lens.iter().all(|&l| l >= 1 && l <= limit));
lens
}
pub fn canonical_codes(lens: &[u8]) -> Vec<u32> {
let min = *lens.iter().min().unwrap();
let max = *lens.iter().max().unwrap();
let mut codes = vec![0u32; lens.len()];
let mut next = 0u32;
for l in min..=max {
for (i, &ln) in lens.iter().enumerate() {
if ln == l {
codes[i] = next;
next += 1;
}
}
next <<= 1;
}
codes
}
pub fn write_selectors(w: &mut BitWriter, selectors: &[u8], n_groups: usize) {
let mut pos: Vec<u8> = (0..n_groups as u8).collect();
for &sel in selectors {
let j = pos.iter().position(|&p| p == sel).expect("unknown selector");
for _ in 0..j { w.write_bit(1); }
w.write_bit(0);
let v = pos[j];
pos.copy_within(0..j, 1);
pos[0] = v;
}
}
pub fn write_tables(w: &mut BitWriter, lens: &[Vec<u8>]) {
for table in lens {
let mut curr = table[0] as i32;
w.write_bits(5, curr as u32);
for &len in table {
let target = len as i32;
while curr < target {
w.write_bits(2, 0b10); curr += 1;
}
while curr > target {
w.write_bits(2, 0b11); curr -= 1;
}
w.write_bit(0);
}
}
}