hfmn 0.1.0

A flexible Huffman coding implementation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

use rustc_hash::FxHashMap as HashMap;
use std::{cmp::Ordering, collections::VecDeque, fmt::Debug, hash::Hash};

use crate::code::{Bit, HfmnCode};

pub struct Node<T> {
    #[allow(clippy::type_complexity)]
    children: Option<(Box<Node<T>>, Box<Node<T>>)>,
    probability: f64,
    symbol: Option<T>,
}

impl<T: Hash + Eq> Node<T> {
    pub fn new(children: Option<(Self, Self)>, probability: f64, symbol: Option<T>) -> Self {
        Self {
            children: children.map(|(l, r)| (Box::new(l), Box::new(r))),
            probability,
            symbol,
        }
    }

    pub const fn probability(&self) -> f64 {
        self.probability
    }

    pub fn traverse(self, symbols: &mut HashMap<T, HfmnCode>, preceeding_bits: HfmnCode) {
        match self.children {
            Some((l, r)) => {
                let mut left_preceeding_bits = preceeding_bits;
                left_preceeding_bits.push(Bit::Zero);

                l.traverse(symbols, left_preceeding_bits);

                let mut right_preceeding_bits = preceeding_bits;
                right_preceeding_bits.push(Bit::One);

                r.traverse(symbols, right_preceeding_bits);
            }
            None => {
                if symbols
                    .insert(
                        self.symbol
                            .expect("No symbol found, presumably a parent node?"),
                        preceeding_bits,
                    )
                    .is_some()
                {
                    panic!("Symbol was already in use.");
                };
            }
        }
    }
}

impl<T: Debug> Debug for Node<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "Node ({},{:?})", self.probability, self.symbol)
    }
}

impl<T> PartialEq for Node<T> {
    fn eq(&self, other: &Self) -> bool {
        self.probability == other.probability
    }
}

impl<T> PartialOrd for Node<T> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        // Comparison in the sense of priority, ie smaller probabilities are larger
        // (higher priority)
        other.probability.partial_cmp(&self.probability)
    }
}

pub fn get_smallest_node<T>(
    leaf_nodes: &mut VecDeque<Node<T>>,
    internal_nodes: &mut VecDeque<Node<T>>,
) -> Node<T> {
    match leaf_nodes.front().partial_cmp(&internal_nodes.front()) {
        Some(Ordering::Less) => {
            // Leaf node is lower priority than internal or
            // Leaf node is None and internal is Some
            internal_nodes
                .pop_front()
                .expect("Internal nodes queue was empty")
        }
        Some(Ordering::Greater) => {
            // Leaf node is higher priority than internal or
            // Leaf node is Some and internal is None
            leaf_nodes.pop_front().expect("Leaf nodes queue was empty")
        }
        Some(Ordering::Equal) => {
            if leaf_nodes.front().is_some() && internal_nodes.front().is_some() {
                leaf_nodes.pop_front().expect("Leaf nodes queue was empty")
            } else {
                // We shouldn't get here, since there should always be two Some values left
                panic!("Something went wrong!")
            }
        }
        None => {
            // We shouldn't get here, since the probabilities should never be Nan
            panic!("Probabilities were NaN.")
        }
    }
}