aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTa180m2020-05-24 19:51:28 -0500
committerTa180m2020-05-24 19:51:28 -0500
commit92d61616bdc448e081f88ae25ed1352404e20bf3 (patch)
tree7958bf0659c207055790627396fa1543e27f619a
parentcf623bac8392d051a53c5c77ac6bad8076285c0c (diff)
fixed Huffman codes
-rw-r--r--.vscode/settings.json6
-rw-r--r--src/huffman.cpp55
-rw-r--r--src/main.cpp7
3 files changed, 23 insertions, 45 deletions
diff --git a/.vscode/settings.json b/.vscode/settings.json
new file mode 100644
index 0000000..462dc46
--- /dev/null
+++ b/.vscode/settings.json
@@ -0,0 +1,6 @@
+{
+ "files.associations": {
+ "iostream": "cpp",
+ "string": "cpp"
+ }
+} \ No newline at end of file
diff --git a/src/huffman.cpp b/src/huffman.cpp
index e6709f0..dfe36cb 100644
--- a/src/huffman.cpp
+++ b/src/huffman.cpp
@@ -8,19 +8,10 @@ namespace huffman {
};
struct comp { bool operator()(node * a, node * b) { return a->f > b->f; } };
node * root;
- vector<bool> path;
- vector<vector<bool>> code(128);
+ vector<bool> path, code[128];
void traverse(node * n) {
- if (n->l) {
- path.push_back(0);
- traverse(n->l);
- path.pop_back();
- }
- if (n->r) {
- path.push_back(1);
- traverse(n->r);
- path.pop_back();
- }
+ if (n->l) path.push_back(0), traverse(n->l), path.pop_back();
+ if (n->r) path.push_back(1), traverse(n->r), path.pop_back();
if (n->c) code[n->c] = path;
}
@@ -31,15 +22,9 @@ namespace huffman {
}
else {
v.push_back(0);
- if (n->l) {
- v.push_back(1);
- encode_tree(n->l, v);
- }
+ if (n->l) v.push_back(1), encode_tree(n->l, v);
else v.push_back(0);
- if (n->r) {
- v.push_back(1);
- encode_tree(n->r, v);
- }
+ if (n->r) v.push_back(1), encode_tree(n->r, v);
else v.push_back(0);
}
}
@@ -47,29 +32,22 @@ namespace huffman {
int idx = 0;
void decode_tree(node * n, vector<bool> & v) {
if (v[idx++] == 1) {
- for (int i = 0; i < 8; ++i) n->c |= (1 << v[idx++]);
+ for (int i = 0; i < 8; ++i) if (v[idx++]) n->c |= (1 << i);
}
else {
- if (v[idx++] == 1) {
- n->l = new node(0, 0);
- decode_tree(n->l, v);
- }
- if (v[idx++] == 1) {
- n->r = new node(0, 0);
- decode_tree(n->r, v);
- }
+ if (v[idx++] == 1) n->l = new node(0, 0), decode_tree(n->l, v);
+ if (v[idx++] == 1) n->r = new node(0, 0), decode_tree(n->r, v);
}
}
void generate(vector<int> f) {
priority_queue<node *, vector<node *>, comp> pq;
- for (int c = 0; c < 128; ++c) {
+ for (int c = 1; c < 128; ++c) {
node * n = new node(c, f[c]);
pq.push(n);
}
while (pq.size() > 1) {
- node * l = pq.top(); pq.pop();
- node * r = pq.top(); pq.pop();
+ node * l = pq.top(); pq.pop(); node * r = pq.top(); pq.pop();
node * n = new node(0, l->f + r->f);
n->l = l, n->r = r;
pq.push(n);
@@ -78,16 +56,9 @@ namespace huffman {
}
void solve(node * n, vector<bool> & v, string & s) {
- if (n->c) {
- s += n->c;
- //cout << (int)n->c << '\n';
- if (idx > v.size()) return;
- solve(root, v, s);
- }
- else {
- if (v[idx++] == 0) solve(n->l, v, s);
- else solve(n->r, v, s);
- }
+ if (idx > v.size()) return;
+ if (n->c) s += n->c, solve(root, v, s);
+ else v[idx++] == 0 ? solve(n->l, v, s) : solve(n->r, v, s);
}
vector<bool> encode(string s) {
diff --git a/src/main.cpp b/src/main.cpp
index f81cd77..904375d 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -115,7 +115,7 @@ void init()
for(auto& i:text)i.parse();
}
int main() {
- init();
+ /*init();
for(sentence& i:text)
{
for(clause& j:i.clauses)
@@ -125,10 +125,11 @@ int main() {
cout<<k<<endl;
}
}
- }
+ }*/
- vector<bool> test = huffman::encode("test");
+ vector<bool> test = huffman::encode("asdfjkl;1234");
for (auto b : test) cout << b;
+ cout << '\n';
string s = huffman::decode(test);
cout << s << '\n';
} \ No newline at end of file