use crate::constants::ALPHABET_SIZE;
pub struct Mtf {
list: [u8; ALPHABET_SIZE],
}
impl Mtf {
pub fn new() -> Self {
let mut list = [0u8; ALPHABET_SIZE];
for i in 0..ALPHABET_SIZE {
list[i] = i as u8;
}
Self { list }
}
pub fn new_with_in_use(in_use: &[bool; ALPHABET_SIZE]) -> (Self, usize) {
let mut list = [0u8; ALPHABET_SIZE];
let mut n = 0;
for i in 0..ALPHABET_SIZE {
if in_use[i] {
list[n] = i as u8;
n += 1;
}
}
(Self { list }, n)
}
#[inline]
pub fn encode(&mut self, byte: u8) -> u8 {
let mut pos = 0;
while pos < ALPHABET_SIZE && self.list[pos] != byte {
pos += 1;
}
if pos > 0 {
let ch = self.list[pos];
let mut i = pos;
while i > 0 {
self.list[i] = self.list[i - 1];
i -= 1;
}
self.list[0] = ch;
}
pos as u8
}
#[inline]
pub fn decode(&mut self, index: u8) -> u8 {
let pos = index as usize;
let ch = self.list[pos];
if pos > 0 {
let mut i = pos;
while i > 0 {
self.list[i] = self.list[i - 1];
i -= 1;
}
self.list[0] = ch;
}
ch
}
}
pub fn encode(input: &[u8], output: &mut [u8], in_use: &[bool; ALPHABET_SIZE]) -> usize {
let (mut mtf, n_in_use) = Mtf::new_with_in_use(in_use);
for i in 0..input.len() {
output[i] = mtf.encode(input[i]);
}
n_in_use
}
pub fn decode(input: &[u8], output: &mut [u8], in_use: &[bool; ALPHABET_SIZE]) {
let (mut mtf, _) = Mtf::new_with_in_use(in_use);
for i in 0..input.len() {
output[i] = mtf.decode(input[i]);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn encode_decode_roundtrip() {
let input = b"bananaaa";
let mut in_use = [false; ALPHABET_SIZE];
for &b in input.iter() {
in_use[b as usize] = true;
}
let mut encoded = [0u8; 16];
encode(input, &mut encoded, &in_use);
let mut decoded = [0u8; 16];
decode(&encoded[..input.len()], &mut decoded, &in_use);
assert_eq!(&decoded[..input.len()], &input[..]);
}
#[test]
fn repeated_chars_get_zeros() {
let input = [b'A'; 8];
let mut in_use = [false; ALPHABET_SIZE];
in_use[b'A' as usize] = true;
let mut encoded = [0u8; 8];
encode(&input, &mut encoded, &in_use);
assert_eq!(encoded[0], 0); for i in 1..8 {
assert_eq!(encoded[i], 0);
}
}
}