use std::cell::Cell;
use crate::reference::{MergeEntry, MergeTable};
use crate::{PairKey, Rank, TokenId};
const ABSENT_MERGED_ID: TokenId = TokenId(0);
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct MergeState {
seq: Vec<TokenId>,
pair_rank: Vec<Rank>,
pair_merged: Vec<TokenId>,
lookups: u64,
merges: u64,
}
impl MergeState {
#[must_use]
pub const fn new() -> Self {
Self {
seq: Vec::new(),
pair_rank: Vec::new(),
pair_merged: Vec::new(),
lookups: 0,
merges: 0,
}
}
pub fn load(&mut self, tokens: &[TokenId], table: &impl MergeTable) {
self.seq.clear();
self.seq.extend_from_slice(tokens);
let slots = self.seq.len().saturating_sub(1);
self.pair_rank.clear();
self.pair_rank.resize(slots, Rank::ABSENT);
self.pair_merged.clear();
self.pair_merged.resize(slots, ABSENT_MERGED_ID);
for slot in 0..slots {
self.refresh(slot, table);
}
}
#[must_use]
pub fn select(&self) -> Option<usize> {
let mut best_slot = 0usize;
let mut best_rank = Rank::ABSENT;
for slot in 0..self.pair_rank.len() {
let rank = self.pair_rank[slot];
if rank < best_rank {
best_rank = rank;
best_slot = slot;
}
}
if best_rank.is_present() {
Some(best_slot)
} else {
None
}
}
pub fn apply(&mut self, slot: usize, table: &impl MergeTable) {
if slot >= self.pair_rank.len() || slot + 1 >= self.seq.len() {
return;
}
if !self.pair_rank[slot].is_present() {
return;
}
let merged = self.pair_merged[slot];
self.seq[slot] = merged;
self.seq.remove(slot + 1);
self.pair_rank.remove(slot);
self.pair_merged.remove(slot);
self.merges += 1;
if slot > 0 {
self.refresh(slot - 1, table);
}
if slot < self.pair_rank.len() {
self.refresh(slot, table);
}
}
pub fn run(&mut self, table: &impl MergeTable) {
while let Some(slot) = self.select() {
self.apply(slot, table);
}
}
fn refresh(&mut self, slot: usize, table: &impl MergeTable) {
let (Some(&left), Some(&right)) = (self.seq.get(slot), self.seq.get(slot + 1)) else {
return;
};
self.lookups += 1;
match table.lookup(PairKey::new(left, right)) {
Some(entry) => {
self.pair_rank[slot] = entry.rank;
self.pair_merged[slot] = entry.id;
}
None => {
self.pair_rank[slot] = Rank::ABSENT;
self.pair_merged[slot] = ABSENT_MERGED_ID;
}
}
}
#[must_use]
pub fn tokens(&self) -> &[TokenId] {
&self.seq
}
#[must_use]
pub fn pair_ranks(&self) -> &[Rank] {
&self.pair_rank
}
#[must_use]
pub fn pair_merges(&self) -> &[TokenId] {
&self.pair_merged
}
#[must_use]
pub const fn lookups(&self) -> u64 {
self.lookups
}
#[must_use]
pub const fn merges(&self) -> u64 {
self.merges
}
pub const fn clear_counters(&mut self) {
self.lookups = 0;
self.merges = 0;
}
}
#[must_use]
pub fn encode_pretoken(tokens: &[TokenId], table: &impl MergeTable) -> Vec<TokenId> {
let mut state = MergeState::new();
state.load(tokens, table);
state.run(table);
state.seq
}
#[must_use]
pub fn encode<S: AsRef<[TokenId]>>(pretokens: &[S], table: &impl MergeTable) -> Vec<TokenId> {
let mut ids = Vec::new();
let mut state = MergeState::new();
for pretoken in pretokens {
state.load(pretoken.as_ref(), table);
state.run(table);
ids.extend_from_slice(&state.seq);
}
ids
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Measurement {
pub ids: Vec<TokenId>,
pub lookups: u64,
pub merges: u64,
}
#[must_use]
pub fn measure_pretoken(tokens: &[TokenId], table: &impl MergeTable) -> Measurement {
let mut state = MergeState::new();
state.load(tokens, table);
state.run(table);
Measurement {
lookups: state.lookups,
merges: state.merges,
ids: state.seq,
}
}
#[must_use]
pub fn measure<S: AsRef<[TokenId]>>(pretokens: &[S], table: &impl MergeTable) -> Measurement {
let mut ids = Vec::new();
let mut state = MergeState::new();
for pretoken in pretokens {
state.load(pretoken.as_ref(), table);
state.run(table);
ids.extend_from_slice(&state.seq);
}
Measurement {
ids,
lookups: state.lookups,
merges: state.merges,
}
}
#[derive(Debug, Default)]
pub struct CountingTable<T> {
inner: T,
lookups: Cell<u64>,
}
impl<T: MergeTable> CountingTable<T> {
#[must_use]
pub const fn new(inner: T) -> Self {
Self {
inner,
lookups: Cell::new(0),
}
}
#[must_use]
pub fn lookups(&self) -> u64 {
self.lookups.get()
}
pub fn clear(&self) {
self.lookups.set(0);
}
}
impl<T: MergeTable> MergeTable for CountingTable<T> {
fn lookup(&self, pair: PairKey) -> Option<MergeEntry> {
self.lookups.set(self.lookups.get().saturating_add(1));
self.inner.lookup(pair)
}
}
#[must_use]
pub fn naive_lookups(tokens: &[TokenId], table: &impl MergeTable) -> u64 {
let counting = CountingTable::new(table);
let _ = crate::reference::encode_pretoken(tokens, &counting);
counting.lookups()
}
#[must_use]
pub fn incremental_lookups(tokens: &[TokenId], table: &impl MergeTable) -> u64 {
let counting = CountingTable::new(table);
let _ = encode_pretoken(tokens, &counting);
counting.lookups()
}