Added decoder

4 files changed, 102 insertions, 82 deletions

diff --git a/src/decode.cpp b/src/decode.cpp
new file mode 100644
index 0000000..5917d96
--- /dev/null
+++ b/src/decode.cpp
@@ -0,0 +1,15 @@
+#include "common.h"
+#include "huffman.h"
+
+int main() {
+  ifstream enc("test");
+  stringstream ss;
+  ss << enc.rdbuf();
+  string s = ss.str();
+  vector<bool> v;
+  for (auto& c : s) {
+    v.push_back(c == '1');
+    //for (int i = 0; i < 8; ++i) v.push_back(1 & (c >> i));
+  }
+  cout << huffman::decode(v);
+}
\ No newline at end of file
diff --git a/src/main.cpp b/src/encode.cpp
index 7b1546e..d7f3d8d 100644
--- a/src/main.cpp
+++ b/src/encode.cpp
@@ -355,8 +355,10 @@ struct file
 string huffmancompress(string s)
 {
   vector<bool> enc = huffman::encode(s);
+  for (auto b : enc) cout << b;
+  cout << endl;
   string ans;
-  for (int i = 0; i < ((int)enc.size() + 7) / 8; ++i) {
+  for (int i = 0; i < (int)enc.size(); ++i) {
     char out = 0;
     for (int j = i; j < min(i + 8, (int)enc.size()); ++j) {
       if (enc[j]) out += (1 << (j - i));
@@ -370,7 +372,7 @@ int initsize=0;
 int compressrate;
 int targetsize;
 
-int main(int argc, char *argv[]) {
+/*int main(int argc, char *argv[]) {
   getlists();
 	string input="";
 
@@ -448,7 +450,9 @@ int main(int argc, char *argv[]) {
   cout << "Original length: " << orig_size << '\n';
   cout << "Compressed length: " << s.size() << '\n';
   cout << "Percent compression: " << 100.0 - ((double)100.0 * s.size() / orig_size) << "%\n";
-	printf("%s\n", s.c_str()); 
+  cout << s << '\n'; 
+  ofstream cout("test");
+	cout << s << '\n'; 
 
 	// WARNING: Huffman will CRASH if you pass a string with only one unique character
 	/*string orig = "test1234";
@@ -465,4 +469,4 @@ int main(int argc, char *argv[]) {
     cout << "Compressed length: " << (enc.size() + 7) / 8 << '\n';
 	cout << "Percent compression: " << 100.0 - (double)100.0 * (enc.size() + 7) / 8 / orig.size() << "%\n";
   }*/
-}
+//}
diff --git a/src/huffman.cpp b/src/huffman.cpp
index ce90371..ac50f8e 100644
--- a/src/huffman.cpp
+++ b/src/huffman.cpp
@@ -1,79 +1,79 @@
-#include "huffman.h"

-#include "common.h"

-

-namespace huffman {

-  struct node {

-    char c; int f; node * l, * r;

-    node(char _c, int _f) { c = _c, f = _f, l = r = NULL; }

-  };

-  struct comp { bool operator()(node * a, node * b) { return a->f > b->f; } };

-  node * root;

-  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->c) code[n->c] = path;

-  }

-

-  void encode_tree(node * n, vector<bool> & v) {

-    if (n->c) {

-      v.push_back(1);

-      for (int i = 0; i < 7; ++i) v.push_back(1 & (n->c >> i));

-    }

-    else {

-      v.push_back(0);

-      n->l ? v.push_back(1), encode_tree(n->l, v) : v.push_back(0);

-      n->r ? v.push_back(1), encode_tree(n->r, v) : v.push_back(0);

-    }

-  }

-

-  int idx = 0;

+#include "huffman.h"
+#include "common.h"
+
+namespace huffman {
+  struct node {
+    char c; int f; node * l, * r;
+    node(char _c, int _f) { c = _c, f = _f, l = r = NULL; }
+  };
+  struct comp { bool operator()(node * a, node * b) { return a->f > b->f; } };
+  node * root;
+  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->c) code[n->c] = path;
+  }
+
+  void encode_tree(node * n, vector<bool> & v) {
+    if (n->c) {
+      v.push_back(1);
+      for (int i = 0; i < 7; ++i) v.push_back(1 & (n->c >> i));
+    }
+    else {
+      v.push_back(0);
+      n->l ? (v.push_back(1), encode_tree(n->l, v)) : v.push_back(0);
+      n->r ? (v.push_back(1), encode_tree(n->r, v)) : v.push_back(0);
+    }
+  }
+
+  int idx = 0;
   void decode_tree(node * n, vector<bool> & v) {
-    if (idx >= v.size()) return;

-    if (v[idx++] == 1) {

-      for (int i = 0; i < 7; ++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);

-    }    

-  }

-

-  void generate(vector<int> f) {

-    priority_queue<node *, vector<node *>, comp> pq;

-    for (int c = 1; c < 128; ++c) if (f[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 * n = new node(0, l->f + r->f); n->l = l, n->r = r;

-      pq.push(n);

-    }

-    root = pq.top();

-  }

-

-  void solve(node * n, vector<bool> & v, string & 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) {

-    vector<int> f(128, 0);

-    for (auto& c : s) ++f[c];

-    generate(f);

-    traverse(root);

-    vector<bool> ret;

-    encode_tree(root, ret);

-    for (auto& c : s) for (auto b : code[c]) ret.push_back(b);

-    return ret;

-  }

-

-  string decode(vector<bool> v) {

-    root = new node(0, 0);

-    decode_tree(root, v);

-    string ret;

-    solve(root, v, ret);

-    return ret;

-  }

-}

+    if (idx > v.size()) return;
+    if (v[idx++] == 1) {
+      for (int i = 0; i < 7; ++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);
+    }    
+  }
+
+  void generate(vector<int> f) {
+    priority_queue<node *, vector<node *>, comp> pq;
+    for (int c = 1; c < 128; ++c) if (f[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 * n = new node(0, l->f + r->f); n->l = l, n->r = r;
+      pq.push(n);
+    }
+    root = pq.top();
+  }
+
+  void solve(node * n, vector<bool> & v, string & s) {
+	if (idx > v.size() || !n) 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) {
+    vector<int> f(128, 0);
+    for (auto& c : s) ++f[c];
+    generate(f);
+    traverse(root);
+    vector<bool> ret;
+    encode_tree(root, ret);
+    for (auto& c : s) for (auto b : code[c]) ret.push_back(b);
+    return ret;
+  }
+
+  string decode(vector<bool> v) {
+    root = new node(0, 0);
+    decode_tree(root, v);
+    string ret;
+    while (idx < v.size()) solve(root, v, ret);
+    return ret;
+  }
+}
diff --git a/test b/test
new file mode 100644
index 0000000..d7028ce
--- /dev/null
+++ b/test
@@ -0,0 +1 @@
+01010111100111101011111011111000011111010011110110111011101011101111011001101011001101110101100000101011110001110101101000111011101101011011110110101101101111110000111011111101111101011010101011011101010101110100111110011111100111101010101101100111111100111100001101011010011010110101011111001110101100101111010101110010111110110111110001101100100111110001100111011000111100111110000000110110100010010111001111110110101111011101111110001101000110111010010110010111010011010100010001100110010010010100101110010010110100110001010000011100111011100010000111011110001000110111011011001101100010110011011001111011101011011011101111111000111100000101111010010100101110010000100010110001101010001000101111110101110100110010011110010010111101100101100000111001110111000011011111010001000101111110101110100101010100010111111100000111001110111000110001111101100110110
\ No newline at end of file