use crate::core::util::accountable::Accountable;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::ram_usage_estimator::{size_of_slice, size_of_vec};
use std::cmp;
#[cfg(test)]
use std::collections::HashMap;
pub struct FrequencyTrackingRingBuffer {
max_size: usize,
buffer: Box<[i32]>,
position: usize,
frequencies: IntBag,
}
impl FrequencyTrackingRingBuffer {
pub fn new(max_size: usize, sentinel: i32) -> Result<Self> {
if max_size < 2 {
return Err(LuceneError::illegal_argument("max_size must be at least 2"));
}
let buffer = vec![sentinel; max_size];
let mut frequencies = IntBag::new(max_size);
for _ in 0..max_size {
frequencies.add(sentinel);
}
debug_assert_eq!(frequencies.frequency(sentinel) as usize, max_size);
Ok(Self {
max_size,
buffer: buffer.into_boxed_slice(),
position: 0,
frequencies,
})
}
pub fn add(&mut self, i: i32) {
let removed = self.buffer[self.position];
let removed_from_bag = self.frequencies.remove(removed);
debug_assert!(removed_from_bag);
self.buffer[self.position] = i;
self.frequencies.add(i);
self.position += 1;
if self.position == self.max_size {
self.position = 0;
}
}
pub fn frequency(&self, key: i32) -> i32 {
self.frequencies.frequency(key)
}
#[cfg(test)]
pub fn as_frequency_map(&self) -> HashMap<i32, i32> {
self.frequencies.as_map()
}
}
impl Accountable for FrequencyTrackingRingBuffer {
fn ram_bytes_used(&self) -> Result<i64> {
Ok(size_of_slice(&self.buffer).saturating_add(self.frequencies.ram_bytes_used()?))
}
}
pub struct IntBag {
pub keys: Vec<i32>,
pub freqs: Vec<i32>,
pub mask: usize,
}
impl IntBag {
pub fn new(max_size: usize) -> Self {
let mut capacity = cmp::max(2, max_size * 3 / 2);
capacity = capacity.next_power_of_two();
debug_assert!(capacity > max_size);
let keys = vec![0; capacity];
let freqs = vec![0; capacity];
let mask = capacity - 1;
Self { keys, freqs, mask }
}
pub fn frequency(&self, key: i32) -> i32 {
let mut slot = (key as usize) & self.mask;
loop {
if self.keys[slot] == key {
debug_assert!(self.freqs[slot] >= 0);
return self.freqs[slot];
} else if self.freqs[slot] == 0 {
return 0;
}
slot = (slot + 1) & self.mask;
}
}
pub fn add(&mut self, key: i32) -> i32 {
let mut slot = (key as usize) & self.mask;
loop {
if self.freqs[slot] == 0 {
self.keys[slot] = key;
self.freqs[slot] = 1;
return 1;
} else if self.keys[slot] == key {
self.freqs[slot] += 1;
return self.freqs[slot];
}
slot = (slot + 1) & self.mask;
}
}
pub fn remove(&mut self, key: i32) -> bool {
let mut slot = (key as usize) & self.mask;
loop {
if self.freqs[slot] == 0 {
return false;
} else if self.keys[slot] == key {
self.freqs[slot] -= 1;
let new_freq = self.freqs[slot];
if new_freq == 0 {
self.relocate_adjacent_keys(slot);
}
return true;
}
slot = (slot + 1) & self.mask;
}
}
fn relocate_adjacent_keys(&mut self, mut free_slot: usize) {
let mut slot = (free_slot + 1) & self.mask;
loop {
let freq = self.freqs[slot];
if freq == 0 {
break;
}
let key = self.keys[slot];
let expected_slot = (key as usize) & self.mask;
if Self::between(expected_slot, slot, free_slot) {
self.keys[free_slot] = key;
self.freqs[free_slot] = freq;
self.freqs[slot] = 0;
free_slot = slot;
}
slot = (slot + 1) & self.mask;
}
}
fn between(chain_start: usize, chain_end: usize, slot: usize) -> bool {
if chain_start <= chain_end {
chain_start <= slot && slot <= chain_end
} else {
slot >= chain_start || slot <= chain_end
}
}
#[cfg(test)]
pub(crate) fn as_map(&self) -> HashMap<i32, i32> {
let mut map = HashMap::new();
for i in 0..self.keys.len() {
if self.freqs[i] > 0 {
map.insert(self.keys[i], self.freqs[i]);
}
}
map
}
}
impl Accountable for IntBag {
fn ram_bytes_used(&self) -> Result<i64> {
Ok(size_of_vec(&self.keys).saturating_add(size_of_vec(&self.freqs)))
}
}