#![warn(missing_docs)]
use super::BitQueue;
use super::Endianness;
use std::collections::BTreeMap;
use std::fmt;
use std::marker::PhantomData;
pub enum ReadHuffmanTree<E: Endianness, T: Clone> {
Done(T, u8, u32, PhantomData<E>),
Continue(Box<[ReadHuffmanTree<E, T>]>),
InvalidState,
}
pub fn compile_read_tree<E, T>(
values: Vec<(T, Vec<u8>)>,
) -> Result<Box<[ReadHuffmanTree<E, T>]>, HuffmanTreeError>
where
E: Endianness,
T: Clone,
{
let tree = FinalHuffmanTree::new(values)?;
let mut result = Vec::with_capacity(256);
result.extend((0..256).map(|_| ReadHuffmanTree::InvalidState));
let queue = BitQueue::from_value(0, 0);
let i = queue.to_state();
result[i] = compile_queue(queue, &tree);
for bits in 1..8 {
for value in 0..(1 << bits) {
let queue = BitQueue::from_value(value, bits);
let i = queue.to_state();
result[i] = compile_queue(queue, &tree);
}
}
assert_eq!(result.len(), 256);
Ok(result.into_boxed_slice())
}
fn compile_queue<E, T>(
mut queue: BitQueue<E, u8>,
tree: &FinalHuffmanTree<T>,
) -> ReadHuffmanTree<E, T>
where
E: Endianness,
T: Clone,
{
match tree {
FinalHuffmanTree::Leaf(ref value) => {
let len = queue.len();
ReadHuffmanTree::Done(value.clone(), queue.value(), len, PhantomData)
}
FinalHuffmanTree::Tree(ref bit0, ref bit1) => {
if queue.is_empty() {
ReadHuffmanTree::Continue(
(0..256)
.map(|byte| compile_queue(BitQueue::from_value(byte as u8, 8), &tree))
.collect::<Vec<ReadHuffmanTree<E, T>>>()
.into_boxed_slice(),
)
} else if queue.pop(1) == 0 {
compile_queue(queue, bit0)
} else {
compile_queue(queue, bit1)
}
}
}
}
enum FinalHuffmanTree<T: Clone> {
Leaf(T),
Tree(Box<FinalHuffmanTree<T>>, Box<FinalHuffmanTree<T>>),
}
impl<T: Clone> FinalHuffmanTree<T> {
fn new(values: Vec<(T, Vec<u8>)>) -> Result<FinalHuffmanTree<T>, HuffmanTreeError> {
let mut tree = WipHuffmanTree::new_empty();
for (symbol, code) in values {
tree.add(code.as_slice(), symbol)?;
}
tree.into_read_tree()
}
}
enum WipHuffmanTree<T: Clone> {
Empty,
Leaf(T),
Tree(Box<WipHuffmanTree<T>>, Box<WipHuffmanTree<T>>),
}
impl<T: Clone> WipHuffmanTree<T> {
fn new_empty() -> WipHuffmanTree<T> {
WipHuffmanTree::Empty
}
fn new_leaf(value: T) -> WipHuffmanTree<T> {
WipHuffmanTree::Leaf(value)
}
fn new_tree() -> WipHuffmanTree<T> {
WipHuffmanTree::Tree(Box::new(Self::new_empty()), Box::new(Self::new_empty()))
}
fn into_read_tree(self) -> Result<FinalHuffmanTree<T>, HuffmanTreeError> {
match self {
WipHuffmanTree::Empty => Err(HuffmanTreeError::MissingLeaf),
WipHuffmanTree::Leaf(v) => Ok(FinalHuffmanTree::Leaf(v)),
WipHuffmanTree::Tree(zero, one) => {
let zero = zero.into_read_tree()?;
let one = one.into_read_tree()?;
Ok(FinalHuffmanTree::Tree(Box::new(zero), Box::new(one)))
}
}
}
fn add(&mut self, code: &[u8], symbol: T) -> Result<(), HuffmanTreeError> {
match self {
WipHuffmanTree::Empty => {
if code.is_empty() {
*self = WipHuffmanTree::new_leaf(symbol);
Ok(())
} else {
*self = WipHuffmanTree::new_tree();
self.add(code, symbol)
}
}
WipHuffmanTree::Leaf(_) => Err(if code.is_empty() {
HuffmanTreeError::DuplicateLeaf
} else {
HuffmanTreeError::OrphanedLeaf
}),
WipHuffmanTree::Tree(ref mut zero, ref mut one) => {
if code.is_empty() {
Err(HuffmanTreeError::DuplicateLeaf)
} else {
match code[0] {
0 => zero.add(&code[1..], symbol),
1 => one.add(&code[1..], symbol),
_ => Err(HuffmanTreeError::InvalidBit),
}
}
}
}
}
}
#[derive(PartialEq, Copy, Clone, Debug)]
pub enum HuffmanTreeError {
InvalidBit,
MissingLeaf,
DuplicateLeaf,
OrphanedLeaf,
}
impl fmt::Display for HuffmanTreeError {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match *self {
HuffmanTreeError::InvalidBit => write!(f, "invalid bit in code"),
HuffmanTreeError::MissingLeaf => write!(f, "missing leaf node in specification"),
HuffmanTreeError::DuplicateLeaf => write!(f, "duplicate leaf node in specification"),
HuffmanTreeError::OrphanedLeaf => write!(f, "orphaned leaf node in specification"),
}
}
}
pub fn compile_write_tree<E, T>(
values: Vec<(T, Vec<u8>)>,
) -> Result<WriteHuffmanTree<E, T>, HuffmanTreeError>
where
E: Endianness,
T: Ord + Clone,
{
let mut map = BTreeMap::new();
for (symbol, code) in values {
let mut encoded = Vec::new();
for bits in code.chunks(32) {
let mut acc = BitQueue::<E, u32>::new();
for bit in bits {
match *bit {
0 => acc.push(1, 0),
1 => acc.push(1, 1),
_ => return Err(HuffmanTreeError::InvalidBit),
}
}
let len = acc.len();
encoded.push((len, acc.value()))
}
map.entry(symbol)
.or_insert_with(|| encoded.into_boxed_slice());
}
Ok(WriteHuffmanTree {
map,
phantom: PhantomData,
})
}
pub struct WriteHuffmanTree<E: Endianness, T: Ord> {
map: BTreeMap<T, Box<[(u32, u32)]>>,
phantom: PhantomData<E>,
}
impl<E: Endianness, T: Ord + Clone> WriteHuffmanTree<E, T> {
#[inline]
pub fn has_symbol(&self, symbol: &T) -> bool {
self.map.contains_key(symbol)
}
#[inline]
pub fn get(&self, symbol: &T) -> &[(u32, u32)] {
self.map[symbol].as_ref()
}
}