commit 40b412b39023c30fe43cf977a4cae355c87e3568
parent 2df6d5bf57fc658f70298cbc721a1c3e719490f7
Author: William Lindholm <a22willi@student.his.se>
Date: Fri, 1 Dec 2023 15:10:28 +0100
Refactoring.
Diffstat:
| M | Problem3/Problem3.cpp | | | 196 | ++++++++++++++++++++++++++++--------------------------------------------------- |
1 file changed, 68 insertions(+), 128 deletions(-)
diff --git a/Problem3/Problem3.cpp b/Problem3/Problem3.cpp
@@ -66,7 +66,7 @@ public:
* 1 1 : b
* @param bitString: the bitstring of the node
*/
- void printTree(vector<char>& bitString)
+ void printTree(const vector<char>& bitString = vector<char>()) const
{
// Base Case: If it's a leaf node, print the character and its code
if (!left && !right) {
@@ -90,38 +90,6 @@ public:
}
}
- /*
- * Print the tree as a graph
- * Example of output:
- * +-- 10
- * +-- A : 4
- * |-- 6
- * | +-- B : 3
- * | |-- 3
- * | | +-- D : 1
- * | | |-- C : 2
- */
- void printGraph(const string& prefix = "", bool isLeft = true)
- {
- // Check if the current node is a leaf node
- if (!left && !right) {
- cout << prefix << (isLeft ? "+-- " : "|-- ") << this->c << " : " << weight << endl;
- return;
- }
-
- // If not a leaf node, print the node weight
- cout << prefix << (isLeft ? "+-- " : "|-- ") << weight << endl;
-
- // Construct the next level prefix
- string childPrefix = prefix + (isLeft ? " " : "| ");
-
- // Recursive calls for left and right children
- if (left)
- left->printGraph(childPrefix, true);
- if (right)
- right->printGraph(childPrefix, false);
- }
-
private:
Tree* left;
Tree* right;
@@ -149,124 +117,96 @@ struct TreeWrapper
Tree* tree;
};
-/*
-* Function: calculateWeight
-* Calculate the weight of a string
-* @param plainText: the string to calculate the weight of
-* @param targetLetter: the letter to calculate the weight of
-*/
-int calculateWeight(string plainText, char targetLetter)
+
+class HuffmanEncoder
{
- int weight = 0;
- for (int i = 0; i < (int)plainText.size(); i++)
+public:
+ /*
+ * Constructor
+ * @param plainText: the string to encode
+ */
+ HuffmanEncoder(string plainText)
{
- if (plainText[i] == targetLetter)
- {
- weight++;
- }
+ this->plainText = plainText;
}
- return weight;
-}
-class HuffmanEncoder
-{
- public:
- /*
- * Constructor
- * @param plainText: the string to encode
- */
- HuffmanEncoder(string plainText)
- {
- this->plainText = plainText;
- }
+ /*
+ * Encode the string
+ * @return: the encoded string
+ */
+ void printCodes()
+ {
+ auto subTrees = createLeaves();
+ this->huffmanTree = buildTree(subTrees);
+ Tree* root = this->getRoot();
+ root->printTree();
+ }
- /*
- * Encode the string
- * @return: the encoded string
- */
- string encode()
- {
- auto subTrees = createLeaves();
- this->root = buildTree(subTrees);
+ /*
+ * Get the root of the tree
+ * @return: the root of the
+ */
+ Tree* getRoot()
+ {
+ return huffmanTree.top().tree;
+ }
+private:
+ string plainText;
+ priority_queue<TreeWrapper> huffmanTree;
- return "";
- }
+ /*
+ * Create the leaves of the tree, and push them to a priority queue
+ * Note: the priority queue is sorted by the weight of the nodes
+ * But the tree is not built yet
+ * @return: a priority queue of the leaves
+ */
+ priority_queue<TreeWrapper> createLeaves()
+ {
+ priority_queue<TreeWrapper> q;
- /*
- * Generate the bitstring for each character
- * @return: a map of characters and their bitstrings
- */
- map<char, string> generateBitStrings()
+ map<char, int> charWeights;
+
+ // calculate frequencies
+ for (char c : plainText)
{
- map<char, string> bitStrings;
- vector<char> bitString;
- root.top().tree->printTree(bitString);
- return bitStrings;
+ charWeights[c]++;
}
- /*
- * Get the root of the tree
- * @return: the root of the
- */
- Tree* getRoot()
+ // Create leaves and push them to the queue
+ for (auto& pair : charWeights)
{
- return root.top().tree;
+ q.push(TreeWrapper(new Tree(pair.second, pair.first)));
}
- private:
- string plainText;
- priority_queue<TreeWrapper> root;
+ return q;
+ }
- priority_queue<TreeWrapper> createLeaves()
+ /*
+ * Build the tree from the priority queue
+ * @param q: the priority queue of the leaves
+ * @return: the root of the tree
+ */
+ priority_queue<TreeWrapper> buildTree(priority_queue<TreeWrapper> q)
+ {
+ if (q.size() == 1)
{
- priority_queue<TreeWrapper> q;
-
- //build map of characters and their weights
-
- map<char, int> charWeights;
- for (int i = 0; i < (int)plainText.size(); i++)
- {
- if (charWeights.find(plainText[i]) == charWeights.end())
- {
- charWeights[plainText[i]] = calculateWeight(plainText, plainText[i]);
- }
- }
-
- // create leaves and push them to the queue
- for (auto it = charWeights.begin(); it != charWeights.end(); it++)
- {
- q.push(TreeWrapper(new Tree(it->second, it->first)));
- }
-
return q;
}
- priority_queue<TreeWrapper> buildTree(priority_queue<TreeWrapper> q)
- {
- if (q.size() == 1)
- {
- return q;
- }
+ TreeWrapper t1 = q.top();
+ q.pop();
+ TreeWrapper t2 = q.top();
+ q.pop();
+ q.push(TreeWrapper(new Tree(t1.tree->getWeight() + t2.tree->getWeight(), t1.tree, t2.tree)));
- TreeWrapper t1 = q.top();
- q.pop();
- TreeWrapper t2 = q.top();
- q.pop();
- q.push(TreeWrapper(new Tree(t1.tree->getWeight() + t2.tree->getWeight(), t1.tree, t2.tree)));
-
- return buildTree(q);
- }
+ return buildTree(q);
+ }
};
int main()
{
- HuffmanEncoder huffmanTree("aaaabbbc");
- string encoded = huffmanTree.encode();
- Tree* root = huffmanTree.getRoot();
- //create empty char vector
- vector<char> bitString;
- root->printTree(bitString);
- root->printGraph();
+ HuffmanEncoder huffmanTree("AAAABBBC");
+ huffmanTree.printCodes();
};
