use std::collections::BTreeSet;
use smallvec::SmallVec;
use crate::core::index::impact::Impact;
pub struct CompetitiveImpactAccumulator {
max_freqs: [i32; 256],
other_freq_norm_pairs: BTreeSet<Impact>,
}
impl Default for CompetitiveImpactAccumulator {
fn default() -> Self {
Self::new()
}
}
impl CompetitiveImpactAccumulator {
pub fn new() -> Self {
CompetitiveImpactAccumulator {
max_freqs: [0; 256],
other_freq_norm_pairs: BTreeSet::new(),
}
}
pub fn clear(&mut self) {
self.max_freqs = [0; 256];
if !self.other_freq_norm_pairs.is_empty() {
self.other_freq_norm_pairs.clear();
}
debug_assert!(self.assert_consistent());
}
pub fn add(&mut self, freq: i32, norm: i64) {
if (i8::MIN as i64..=i8::MAX as i64).contains(&norm) {
let idx = (norm as i8) as u8 as usize;
self.max_freqs[idx] = self.max_freqs[idx].max(freq);
} else {
let entry = Impact::new(freq, norm);
Self::add_entry(entry, &mut self.other_freq_norm_pairs);
}
debug_assert!(self.assert_consistent());
}
pub fn add_all(&mut self, acc: &Self) {
for i in 0..256 {
self.max_freqs[i] = self.max_freqs[i].max(acc.max_freqs[i]);
}
for entry in &acc.other_freq_norm_pairs {
Self::add_entry(entry.clone(), &mut self.other_freq_norm_pairs);
}
debug_assert!(self.assert_consistent());
}
pub fn copy_from(&mut self, acc: &Self) {
self.max_freqs.copy_from_slice(&acc.max_freqs);
self.other_freq_norm_pairs = acc.other_freq_norm_pairs.clone();
debug_assert!(self.assert_consistent());
}
pub fn get_competitive_freq_norm_pairs(&self) -> SmallVec<[Impact; 8]> {
let mut impacts = SmallVec::new();
let mut max_freq_for_lower_norms = 0;
for (block_index, block) in self.max_freqs.as_chunks::<16>().0.iter().enumerate() {
if block.iter().copied().max().unwrap_or(0) <= max_freq_for_lower_norms {
continue;
}
for (offset, &freq) in block.iter().enumerate() {
if freq > max_freq_for_lower_norms {
let norm_index = block_index * 16 + offset;
impacts.push(Impact::new(freq, norm_index as i8 as i64));
max_freq_for_lower_norms = freq;
}
}
}
if self.other_freq_norm_pairs.is_empty() {
return impacts;
}
if impacts.is_empty() {
return self.other_freq_norm_pairs.iter().cloned().collect();
}
let mut byte_impacts = impacts.into_iter().rev().peekable();
let mut custom_impacts = self.other_freq_norm_pairs.iter().rev().peekable();
let mut impacts = smallvec::SmallVec::<[Impact; 8]>::new();
let mut lowest_norm = None;
loop {
let next = if let Some(custom) = custom_impacts.peek()
&& byte_impacts.peek().is_none_or(|byte| *custom > byte)
{
custom_impacts.next().cloned()
} else {
byte_impacts.next()
};
let Some(impact) = next else {
break;
};
let norm = impact.norm as u64;
if lowest_norm.is_none_or(|previous| norm < previous) {
lowest_norm = Some(norm);
impacts.push(impact);
}
}
impacts.reverse();
impacts
}
fn add_entry(new_entry: Impact, freq_norm_pairs: &mut BTreeSet<Impact>) {
if let Some(next) = freq_norm_pairs.range(&new_entry..).next()
&& (next.norm as u64) <= (new_entry.norm as u64)
{
return;
}
freq_norm_pairs.insert(new_entry.clone());
let mut first_to_remove = None;
for e in freq_norm_pairs.range(..&new_entry).rev() {
if (e.norm as u64) >= (new_entry.norm as u64) {
first_to_remove = Some(e.clone());
} else {
break;
}
}
if let Some(first) = first_to_remove {
for _ in freq_norm_pairs.extract_if(first..new_entry, |_| true) {}
}
}
fn assert_consistent(&self) -> bool {
let mut prev_freq = 0;
let mut prev_norm = 0u64;
for impact in &self.other_freq_norm_pairs {
debug_assert!(impact.norm < i8::MIN as i64 || impact.norm > i8::MAX as i64);
debug_assert!(prev_freq < impact.freq);
debug_assert!(prev_norm < impact.norm as u64);
prev_freq = impact.freq;
prev_norm = impact.norm as u64;
}
true
}
}
impl std::fmt::Display for CompetitiveImpactAccumulator {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "[")?;
for (index, impact) in self
.get_competitive_freq_norm_pairs()
.into_iter()
.enumerate()
{
if index > 0 {
write!(f, ", ")?;
}
write!(f, "{impact}")?;
}
write!(f, "]")
}
}