extern crate priority_queue;
use priority_queue::PriorityQueue;
use std::collections::HashMap;
use std::collections::LinkedList;
#[derive(Hash, PartialEq, Eq, Debug)]
enum Node {
Terminal { value: char },
Nonterminal { left: Box<Node>, right: Box<Node> },
}
impl Node {
fn terminal(val: char) -> Self {
Node::Terminal { value: val }
}
fn noneterminal(left: Self, right: Self) -> Self {
Node::Nonterminal {
left: Box::new(left),
right: Box::new(right),
}
}
}
fn get_huffmanencoding<'a>(
node: &'a Node,
code: u32,
depth:u32,
mut map: HashMap<&'a char, (u32, u32)>,
) -> HashMap<&'a char, (u32, u32)> {
match node {
Node::Nonterminal { left, right } => get_huffmanencoding(
right.as_ref(),
1 | code << 1,
depth + 1,
get_huffmanencoding(left.as_ref(), 0 | code << 1, depth + 1, map),
),
Node::Terminal { value } => {
map.insert(value, (depth, code));
map
}
}
}
fn main() {
let text: Vec<char> = include_str!("./main.rs").chars().collect();
let hash_map = {
let mut map = HashMap::new();
for it in text.iter() {
if !map.contains_key(it) {
map.insert(it.clone(), 0);
}
*map.get_mut(it).unwrap() += 1;
}
map
};
let mut queue = PriorityQueue::new();
for (key, count) in hash_map.into_iter() {
queue.push(Node::terminal(key), -1 * count);
}
let mut rl = true;
let res = loop {
let node1 = queue.pop().unwrap();
let node2 = match queue.pop() {
None => break node1.0,
Some(node) => node,
};
let new_node = match rl {
true => (Node::noneterminal(node1.0, node2.0), (node1.1 + node2.1)),
false => (Node::noneterminal(node2.0, node1.0), (node1.1 + node2.1)),
};
queue.push(new_node.0, new_node.1);
rl = !rl;
};
let table = get_huffmanencoding(&res, 0, 0, HashMap::new());
for (key, code) in &table {
print!("{:?} ", key);
for i in 1..=code.0{
print!("{}", (code.1 >> (code.0 - i)) & 1);
}
println!(" len:{}", code.0);
}
let mut array = Vec::new();
let mut byte = 0u8;
let mut reft_bit = 8;
let encoded = text.iter()
.map(|ch| table.get(ch).unwrap());
/*
let mut bit_count = 0;
for it in text.iter()
.map(|ch| table.get(ch).unwrap()){
for i in 1..=it.0{
print!("{}", (it.1 >> (it.0 - i)) & 1);
bit_count += 1;
if bit_count == 8{
print!("\n");
bit_count = 0;
}
}
}
println!("\n\n");
*/
let mut compressed_size = 0;
for it in encoded{
let mut bit_count = it.0;
//println!("{:b} bit count: {}",it, bit_count);
compressed_size += it.0;
while bit_count != 0{
if bit_count >= reft_bit{
//println!("\nif {}, {}", bit_count, reft_bit);
byte = byte | (it.1 >> (bit_count - reft_bit)) as u8;
bit_count -= reft_bit;
reft_bit = 0;
}
else{
//("\nelse {}, {}", bit_count, reft_bit);
byte = byte | ((it.1 & (0xFF >>(8 - bit_count))) << (reft_bit - bit_count)) as u8;
reft_bit -= bit_count;
bit_count = 0;
}
if reft_bit == 0{
//print!("{:b}", byte);
array.push(byte);
byte = 0;
reft_bit = 8;
}
}
}
if reft_bit != 0{
array.push(byte);
}
//println!("\n\n");
//array.iter().for_each(|it| println!("{:08b}", it));
let mut res = std::fs::File::create("./hff.compress").unwrap();
use std::io::Write;
res.write_all(&unsafe{std::mem::transmute::<_, [u8;4]>(compressed_size)});
res.write_all(array.as_slice());
res.flush();
}