commit 2df6d5bf57fc658f70298cbc721a1c3e719490f7
parent bdfb4be423893223653be71a595aa761b73049e7
Author: William Lindholm <a22willi@student.his.se>
Date: Fri, 1 Dec 2023 15:09:40 +0100
Revert "Refactoring."
This reverts commit 5ebf28d498f6a93d17faf60acc10036b4f59876c.
Diffstat:
2 files changed, 87 insertions(+), 66 deletions(-)
diff --git a/Problem2/Problem2.cpp b/Problem2/Problem2.cpp
@@ -22,7 +22,6 @@ public:
int getNumNodes();
void printGraph();
void BFS(int v);
- list<int> getNeighbours(int s);
};
Graph::Graph(int V) {
@@ -44,7 +43,6 @@ bool Graph::isEdge(int v, int w) {
}
}
-
int Graph::getNumNodes() {
return V;
}
@@ -58,38 +56,6 @@ void Graph::printGraph() {
}
}
}
-
-list<int> Graph::getNeighbours(int s) {
- list<int> neighbours;
-
- vector<int>::iterator i;
- for (i = adj[s].begin(); i != adj[s].end(); ++i) {
- cout << "-> " << *i << " ";
- }
-
- return neighbours;
-}
-
-/*
-* Function: printList
-* Description: Print a list of integers
-* @param l: the list to print
-*/
-void printList(list<int> l)
-{
- for (int i = 0; i < (int)l.size(); i++)
- {
- cout << l.front();
- l.pop_front();
- }
- cout << endl;
-}
-
-/*
-* Function: BFS
-* Description: Find the shortest path from a node to all other nodes
-* @param v: the starting node
-*/
void Graph::BFS(int v)
{
vector<bool> visited;
@@ -121,11 +87,6 @@ int main(){
network.addEdge(2, 3); //C dislikes D
network.addEdge(2, 1); //C dislikes B
network.printGraph();
-
- list<int> neighbours = network.getNeighbours(2);
-
- cout << "printing neighbours: \n";
- printList(neighbours);
const int i = network.getNumNodes();
list<int> nodes[4];
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(const vector<char>& bitString = vector<char>()) const
+ void printTree(vector<char>& bitString)
{
// Base Case: If it's a leaf node, print the character and its code
if (!left && !right) {
@@ -90,6 +90,38 @@ 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;
@@ -117,6 +149,24 @@ 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)
+{
+ int weight = 0;
+ for (int i = 0; i < (int)plainText.size(); i++)
+ {
+ if (plainText[i] == targetLetter)
+ {
+ weight++;
+ }
+ }
+ return weight;
+}
class HuffmanEncoder
{
@@ -134,12 +184,25 @@ class HuffmanEncoder
* Encode the string
* @return: the encoded string
*/
- void printCodes()
+ string encode()
{
auto subTrees = createLeaves();
- this->huffmanTree = buildTree(subTrees);
- Tree* root = this->getRoot();
- root->printTree();
+ this->root = buildTree(subTrees);
+
+
+ return "";
+ }
+
+ /*
+ * Generate the bitstring for each character
+ * @return: a map of characters and their bitstrings
+ */
+ map<char, string> generateBitStrings()
+ {
+ map<char, string> bitStrings;
+ vector<char> bitString;
+ root.top().tree->printTree(bitString);
+ return bitStrings;
}
/*
@@ -148,45 +211,37 @@ class HuffmanEncoder
*/
Tree* getRoot()
{
- return huffmanTree.top().tree;
+ return root.top().tree;
}
private:
string plainText;
- priority_queue<TreeWrapper> huffmanTree;
+ priority_queue<TreeWrapper> root;
- /*
- * 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;
- map<char, int> charWeights;
+ //build map of characters and their weights
- // calculate frequencies
- for (char c : plainText)
+ map<char, int> charWeights;
+ for (int i = 0; i < (int)plainText.size(); i++)
{
- charWeights[c]++;
+ if (charWeights.find(plainText[i]) == charWeights.end())
+ {
+ charWeights[plainText[i]] = calculateWeight(plainText, plainText[i]);
+ }
}
- // Create leaves and push them to the queue
- for (auto& pair : charWeights)
+ // create leaves and push them to the queue
+ for (auto it = charWeights.begin(); it != charWeights.end(); it++)
{
- q.push(TreeWrapper(new Tree(pair.second, pair.first)));
+ q.push(TreeWrapper(new Tree(it->second, it->first)));
}
return q;
}
- /*
- * 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)
@@ -207,6 +262,11 @@ class HuffmanEncoder
int main()
{
- HuffmanEncoder huffmanTree("AAAABBBC");
- huffmanTree.printCodes();
+ HuffmanEncoder huffmanTree("aaaabbbc");
+ string encoded = huffmanTree.encode();
+ Tree* root = huffmanTree.getRoot();
+ //create empty char vector
+ vector<char> bitString;
+ root->printTree(bitString);
+ root->printGraph();
};
