commit 5ebf28d498f6a93d17faf60acc10036b4f59876c
parent d68ce4dd3430ece023a2b550f9c534b60a7f4e24
Author: William Lindholm <a22willi@student.his.se>
Date: Fri, 1 Dec 2023 14:42:29 +0100
Refactoring.
Diffstat:
2 files changed, 66 insertions(+), 87 deletions(-)
diff --git a/Problem2/Problem2.cpp b/Problem2/Problem2.cpp
@@ -22,6 +22,7 @@ public:
int getNumNodes();
void printGraph();
void BFS(int v);
+ list<int> getNeighbours(int s);
};
Graph::Graph(int V) {
@@ -43,6 +44,7 @@ bool Graph::isEdge(int v, int w) {
}
}
+
int Graph::getNumNodes() {
return V;
}
@@ -56,6 +58,38 @@ 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;
@@ -87,6 +121,11 @@ 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(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,24 +117,6 @@ 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
{
@@ -184,25 +134,12 @@ class HuffmanEncoder
* Encode the string
* @return: the encoded string
*/
- string encode()
+ void printCodes()
{
auto subTrees = createLeaves();
- 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;
+ this->huffmanTree = buildTree(subTrees);
+ Tree* root = this->getRoot();
+ root->printTree();
}
/*
@@ -211,37 +148,45 @@ class HuffmanEncoder
*/
Tree* getRoot()
{
- return root.top().tree;
+ return huffmanTree.top().tree;
}
private:
string plainText;
- priority_queue<TreeWrapper> root;
+ priority_queue<TreeWrapper> huffmanTree;
+ /*
+ * 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;
- //build map of characters and their weights
-
map<char, int> charWeights;
- for (int i = 0; i < (int)plainText.size(); i++)
+
+ // calculate frequencies
+ for (char c : plainText)
{
- if (charWeights.find(plainText[i]) == charWeights.end())
- {
- charWeights[plainText[i]] = calculateWeight(plainText, plainText[i]);
- }
+ charWeights[c]++;
}
- // create leaves and push them to the queue
- for (auto it = charWeights.begin(); it != charWeights.end(); it++)
+ // Create leaves and push them to the queue
+ for (auto& pair : charWeights)
{
- q.push(TreeWrapper(new Tree(it->second, it->first)));
+ q.push(TreeWrapper(new Tree(pair.second, pair.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)
@@ -262,11 +207,6 @@ class HuffmanEncoder
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();
};
