--- a/BitDecoder.hpp	Thu Sep 06 18:18:49 2012 +0200
+++ b/BitDecoder.hpp	Thu Sep 06 18:20:11 2012 +0200
@@ -1,9 +1,9 @@
 #ifndef BITDECODER_HPP
 #define BITDECODER_HPP
 
-#include <QtCore/QPair>
-#include <QtCore/QDebug>
 #include <QtCore/QBitArray>
+#include <QtCore/QString>
+#include <QtCore/QMap>
 
 class BitDecoder {
   BitDecoder* low;
@@ -11,91 +11,53 @@
   QString _data;
 
 private:
-  BitDecoder(BitDecoder* low_in, BitDecoder* high_in) : low(low_in), high(high_in)
-  {
-  }
-
+  BitDecoder(BitDecoder* low_in, BitDecoder* high_in);
 
-public:
-  BitDecoder(const QString& d) : low(0), high(0), _data(d)
-  {
-  }
-
-  ~BitDecoder()
+  uint decode(QString& resString, const QBitArray& bits, uint offset)
   {
-    delete low;
-    delete high;
-  }
-
-  const QString& data() const
-  {
-    return _data;
-  }
-
-  QPair<QString, uint> decode(const QBitArray& bits, uint offset)
-  {
-    if (_data.isNull()) {
-      QPair<QString, uint> retVal = (bits[offset]?high:low)->decode(bits, offset + 1);
-      ++retVal.second;
-      return retVal;
+    //Data is always stored in a leaf node.
+    if (high) {
+      return (bits.testBit(offset) ? high : low)->decode(resString, bits, offset + 1) + 1;
     }
     else {
-      return QPair<QString, uint>(_data, 1);
+      resString.append(_data);
+      return 1;
     }
   }
 
+public:
+  BitDecoder(const QString& d);
+  ~BitDecoder();
+  const QString& data() const;
+
   QString decode(const QBitArray& bits)
   {
-    QPair<QString, uint> d;
     QString combined;
     uint n = bits.size();
-    for (uint decodedBits = 0; decodedBits < n; decodedBits += d.second - 1) {
-      d = decode(bits, decodedBits);
-      combined.append(d.first);
-    }
+    //Just a qualified overestimate guess on what we will need.
+    combined.reserve(n/4);
+    for (uint decodedBits = 0; decodedBits < n; decodedBits += decode(combined, bits, decodedBits) - 1);
+    combined.squeeze();
     return combined;
   }
 
-  static BitDecoder* merge(BitDecoder* low, BitDecoder* high)
-  {
-    return new BitDecoder(low, high);
-  }
-
+  static BitDecoder* merge(BitDecoder* low, BitDecoder* high);
   static QBitArray unite(const QBitArray& first, const QBitArray& second)
   {
-    QBitArray result(first.size() + second.size());
     int n = first.size();
+    int n2 = second.size();
+    QBitArray result(n + n2);
     for (int i = 0; i < n; ++i) {
-      result[i] = first[i];
+      result.setBit(i, first.testBit(i));
     }
-    for (int i = 0; i < second.size(); ++i) {
-      result[n + i] = second[i];
+    for (int i = 0; i < n2; ++i) {
+      result.setBit(n + i, second.testBit(i));
     }
     return result;
   }
 
-  QMap<QString, QBitArray> createEncoder() const
-  {
-    QMap<QString, QBitArray> retVal;
-    if (!_data.isNull()) {
-      retVal.insert(_data, QBitArray());
-    }
-    if (low) {
-      QMap<QString, QBitArray> vals = low->createEncoder();
-      for(QMap<QString, QBitArray>::const_iterator it = vals.begin();
-	  it != vals.end(); ++it) {
-	retVal.insert(it.key(), unite(QBitArray(1, false), it.value()));
-      }
-    }
-    if (high) {
-      QMap<QString, QBitArray> vals = high->createEncoder();
-      for(QMap<QString, QBitArray>::const_iterator it = vals.begin();
-	  it != vals.end(); ++it) {
-	retVal.insert(it.key(), unite(QBitArray(1, true), it.value()));
-      }
-    }
-    return retVal;
-  }
+
+  QMap<QString, QBitArray> createEncoder() const;
 };
 
 #endif //BITDECODER_HPP