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
106
107
108
//! An implementation of the [Huffman coding algorithm][huff_wiki], enabling
//! one to create a Huffman tree with any alphabet they choose.
//!
//! It mainly revolves around the [`HuffTree`][tree] struct, which provides a way to
//! generate Huffman [prefix codes][huff_wiki_codes] for any collection of types implementing
//! the [`HuffLetter`][letter] trait, where for every letter there is a corresponding weight
//! (To ensure this, the [`Weights`][weights] trait must be implemented on the provided collection).
//! If the provided letters also implement the [`HuffLetterAsBytes`][letter_bytes] trait,
//! the tree can be easily read or returned in binary form.
//!
//! # Examples
//!
//! ```
//! use huff_coding::{
//! prelude::*,
//! bitvec::prelude::*,
//! };
//!
//! // every primitive type (except floats) implements HuffLetter
//! let bytes = [0xff, 0xff, 0xff, 0xaa, 0xaa, 0xcc];
//! let chars = ['a', 'a', 'a', 'b', 'b', 'c'];
//! let ints = [-32, 123, -32, -32, 75, 123];
//!
//! // ------ building weights structs ------
//! // building weights with the ByteWeights struct
//! let byte_weights = ByteWeights::from_bytes(&bytes);
//! // building weights in the form of a HashMap
//! let char_weights = build_weights_map(&chars);
//! let int_weights = build_weights_map(&ints);
//!
//! // ------ initializing HuffTrees ------
//! let tree_bytes = HuffTree::from_weights(byte_weights);
//! let tree_chars = HuffTree::from_weights(char_weights);
//! let tree_ints = HuffTree::from_weights(int_weights);
//!
//! // ------ reading codes from a tree ------
//! let char_codes = tree_chars.read_codes();
//!
//! assert_eq!(
//! char_codes.get(&'a').unwrap(),
//! &bitvec![Msb0, u8; 0]
//! );
//! assert_eq!(
//! char_codes.get(&'b').unwrap(),
//! &bitvec![Msb0, u8; 1, 1]
//! );
//! assert_eq!(
//! char_codes.get(&'c').unwrap(),
//! &bitvec![Msb0, u8; 1, 0]
//! );
//!
//! // ------ HuffTree in binary ------
//! // every integer implements HuffLetterAsBytes
//! let tree_bytes_bin = tree_bytes.as_bin();
//! assert_eq!(tree_bytes_bin.to_string(), "[10111111, 11101100, 11000101, 01010]");
//!
//! // reading a HuffTree from a binary representation
//! let tree_bytes_from_bin = HuffTree::<u8>::try_from_bin(tree_bytes_bin).unwrap();
//! assert_eq!(tree_bytes.read_codes(), tree_bytes_from_bin.read_codes());
//! ```
//!
//! Included are also example [compression][compress]/[decompression][decompress] functions using my implementation
//! of this algorithm.
//! ```
//! use huff_coding::prelude::*;
//!
//! let bytes = b"abbccc";
//!
//! let comp_data = compress(bytes);
//! let decomp_bytes = decompress(&comp_data);
//!
//! assert_eq!(bytes.to_vec(), decomp_bytes);
//! ```
//!
//! Every binary representation in the crate is made thanks to the [`bitvec`][bitvec] crate which
//! I've re-exported for convenience.
//!
//! [tree]:tree::HuffTree
//! [letter]:tree::letter::HuffLetter
//! [letter_bytes]:tree::letter::HuffLetterAsBytes
//! [weights]:weights::Weights
//! [compress]:crate::comp::compress
//! [decompress]:crate::comp::decompress
//! [huff_wiki]:https://en.wikipedia.org/wiki/Huffman_coding
//! [huff_wiki_codes]:https://en.wikipedia.org/wiki/Prefix_code
// when i have time:
// TODO: add some abstraction over returned BitVecs (Deref 'n stuff)
// TODO: look at serde
/// Structs and traits used to represent and construct Huffman trees.
/// Trait signifying that the struct stores the weights of a certain type (letter), so that
/// for any stored letter there is a corresponding `usize`(weight).
/// Example compression/decompression functions using the [`HuffTree`][crate::tree::HuffTree] struct.
/// `huff_coding` prelude.
///
/// This collects the general public API into a single spot for inclusion, as
/// `use huff_coding::prelude::*;`, without polluting the root namespace of the crate.
// `bitvec` re-export
pub use bitvec;