DSA-Assignments

commit 4e22c60ae87b388f456a056bd09e1421f2cf3b33
parent 07e5310a636c1b10046a36d5f2508500a0ae62e6
Author: William Lindholm <william_lindholm@outlook.com>
Date:   Mon,  4 Dec 2023 14:37:33 +0100

Implemented full huffman encoder.

Diffstat:
M
Problem3/Problem3.cpp
 | 
62
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

1 file changed, 61 insertions(+), 1 deletion(-)
diff --git a/Problem3/Problem3.cpp b/Problem3/Problem3.cpp
@@ -90,6 +90,26 @@ public:
 		}
 	}
 
+	map<char, string> constructMap(Tree* root, map<char, string>& codes, string bitString = "")
+	{
+		if (!root->left && !root->right)
+		{
+			codes[root->c] = bitString;
+			return codes;
+		}
+
+		if (root->left)
+		{
+			constructMap(root->left, codes, bitString + "0");
+		}
+		if (root->right)
+		{
+			constructMap(root->right, codes, bitString + "1");
+		}
+
+		return codes;
+	}
+
 private:
 	Tree* left;
 	Tree* right;
@@ -142,6 +162,33 @@ public:
 		root->printTree();
 	}
 
+
+	/*
+	* Get the codes of the characters
+	* @return: a map of the characters and their codes
+	*/
+	map<char, string> getCodes()
+	{
+		auto subTrees = createLeaves();
+		this->huffmanTree = buildTree(subTrees);
+		Tree* root = this->getRoot();
+		map<char, string> codes;
+		codes = root->constructMap(root, codes);
+		return codes;
+	}
+
+	string encode()
+	{
+		auto codes = getCodes();
+		string encodedString = "";
+		for (char c : plainText)
+		{
+			encodedString += codes[c];
+			encodedString += " ";
+		}
+		return encodedString;
+	}
+
 	/*
 	* Get the root of the tree
 	* @return: the root of the
@@ -207,6 +254,19 @@ private:
 
 int main()
 {
-	HuffmanEncoder huffmanTree("AAAABBBC");
+	string unEncodedString = "AAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCD";
+	HuffmanEncoder huffmanTree(unEncodedString);
 	huffmanTree.printCodes();
+
+	string encodedString = huffmanTree.encode();
+	printf("Encoded string: %s\n", encodedString.c_str());
+
+	int unEncodedLen = (int)(unEncodedString.length()*8);
+	int encodedLen = (int)encodedString.length();
+	
+	printf("Unencoded length: %d\n", unEncodedLen);
+	printf("Encoded length: %d\n", encodedLen);
+	printf("saved %d bits\n", unEncodedLen - encodedLen);
+
+	return 0;
 };