허프만 압축

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();
}