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,
mut map: HashMap<&'a char, u32>,
) -> HashMap<&'a char, u32> {
match node {
Node::Nonterminal { left, right } => get_huffmanencoding(
right.as_ref(),
1 | code << 1,
get_huffmanencoding(left.as_ref(), 0 | code << 1, map),
),
Node::Terminal { value } => {
map.insert(value, 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, HashMap::new());
for (key, code) in &table {
println!("{:?} {:b}", key, code);
}
let mut array = Vec::new();
let mut byte = 0u8;
let mut reft_bit = 8;
let encoded = text.iter()
.map(|ch| table.get(ch).unwrap());
text.iter()
.map(|ch| table.get(ch).unwrap()).for_each(|it|{
print!("{:b}", it);
});
println!("\n\n");
for it in encoded{
let mut bit_count = {
let mut radix = 0;
loop{
if *it >> radix ==0{
break radix;
}
radix += 1;
}
};
//println!("{:b} bit count: {}",it, bit_count);
while bit_count != 0{
if bit_count - reft_bit >= 0{
//println!("\nif {}, {}", bit_count, reft_bit);
byte = byte | (*it >> (bit_count - reft_bit)) as u8;
bit_count -= reft_bit;
reft_bit = 0;
}
else{
//("\nelse {}, {}", bit_count, reft_bit);
byte = byte | ((*it & (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| print!("{:b}", it));
}