#![allow(non_snake_case)]
use std::{collections::BinaryHeap, fs::File, io::{BufRead, BufReader, BufWriter}};
use std::io::Write;
#[derive(PartialEq, Eq, Debug)]
enum HuffmanNode {
Leaf {
prio: u32,
chr: u32
},
Internal {
prio: u32,
left: Box<HuffmanNode>,
right: Box<HuffmanNode>,
}
}
#[derive(Debug, Clone)]
struct Encoding {
val: u64,
num_bits: u8,
}
impl HuffmanNode {
fn prio(&self) -> u32 {
match self{
HuffmanNode::Leaf { prio, chr: _ } => *prio,
HuffmanNode::Internal { prio, left: _, right: _ } => *prio,
}
}
fn new_leaf(prio: u32, chr: u32) -> Self {
HuffmanNode::Leaf { prio, chr }
}
fn new_inner(left: Self, right: Self) -> Self {
let prio = left.prio() + right.prio();
HuffmanNode::Internal { prio , left: Box::new(left), right: Box::new(right) }
}
fn create_encoding_impl(node: &Self, existing_encodings: &mut Vec<Encoding>, current_encoding: Encoding) {
match node{
HuffmanNode::Leaf { prio: _, chr } => {
existing_encodings[*chr as usize] = current_encoding;
},
HuffmanNode::Internal { prio: _, left, right } => {
let left_encoding = Encoding {
val: current_encoding.val * 2,
num_bits: current_encoding.num_bits + 1,
};
let right_encoding = Encoding {
val: current_encoding.val * 2 + 1,
num_bits: current_encoding.num_bits + 1,
};
Self::create_encoding_impl(left.as_ref(), existing_encodings, left_encoding);
Self::create_encoding_impl(right.as_ref(), existing_encodings, right_encoding);
},
}
}
fn create_encoding(&self, N: usize) -> Vec<Encoding> {
let mut encodings = vec![Encoding{ val: 0, num_bits: 0 };N];
let zero_encoding = Encoding{ val: 0, num_bits: 0 };
Self::create_encoding_impl(self, &mut encodings, zero_encoding);
encodings
}
}
impl PartialOrd for HuffmanNode {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
other.prio().partial_cmp(&self.prio())
}
}
impl Ord for HuffmanNode {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other.prio().cmp(&self.prio())
}
}
fn create_huffman_tree(mut h: BinaryHeap<HuffmanNode>) -> (HuffmanNode, u64){
if h.is_empty() {
panic!("Nopenopenopenope");
}
let mut total_num_bits = 0u64;
while h.len() >= 2 {
let left = h.pop().unwrap();
let right = h.pop().unwrap();
let new_node = HuffmanNode::new_inner(left, right);
total_num_bits += new_node.prio() as u64;
h.push(new_node);
}
(h.pop().unwrap(), total_num_bits)
}
fn main() {
let input_file: File = File::open("huffman.in").unwrap();
let mut input_file: BufReader<File> = BufReader::new(input_file);
let mut N = String::new();
let _ = input_file.read_line(&mut N).unwrap();
let N = N.trim().parse::<usize>().unwrap();
let mut H = BinaryHeap::with_capacity(N);
input_file.lines().enumerate().for_each(|(idx,line)| {
let vi = line.unwrap().trim().parse::<u32>().unwrap();
H.push(HuffmanNode::new_leaf(vi, idx as u32));
});
let (H, total_num_bits) = create_huffman_tree(H);
let encodings = H.create_encoding(N);
let mut output_file = BufWriter::new(File::create("huffman.out").unwrap());
let _ = writeln!(output_file, "{total_num_bits}").unwrap();
for encoding in encodings {
let _ = writeln!(output_file, "{} {}", encoding.num_bits, encoding.val);
}
}