| 46 | |
| 47 | impl HuffmanTree { |
| 48 | pub fn from(input: &str) -> Self { |
| 49 | let counts = input.chars().fold(HashMap::new(), |mut map, c| { |
| 50 | *map.entry(c).or_insert(0) += 1; |
| 51 | map |
| 52 | }); |
| 53 | let mut queue = counts |
| 54 | .iter() |
| 55 | .map(|(&value, &count)| HuffmanTree::Leaf { value, count }) |
| 56 | .collect::<BinaryHeap<HuffmanTree>>(); |
| 57 | |
| 58 | while queue.len() > 1 { |
| 59 | let left = queue.pop().unwrap(); |
| 60 | let right = queue.pop().unwrap(); |
| 61 | queue.push(HuffmanTree::Branch { |
| 62 | count: left.count() + right.count(), |
| 63 | left: Box::new(left), |
| 64 | right: Box::new(right), |
| 65 | }) |
| 66 | } |
| 67 | |
| 68 | queue.pop().expect("The Huffman tree has to have a root") |
| 69 | } |
| 70 | |
| 71 | pub fn count(&self) -> i32 { |
| 72 | match *self { |