--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/BitDecoder.hpp	Wed Sep 05 21:54:18 2012 +0200
@@ -0,0 +1,101 @@
+#ifndef BITDECODER_HPP
+#define BITDECODER_HPP
+
+#include <QtCore/QPair>
+#include <QtCore/QDebug>
+#include <QtCore/QBitArray>
+
+class BitDecoder {
+  BitDecoder* low;
+  BitDecoder* high;
+  QString _data;
+
+private:
+  BitDecoder(BitDecoder* low_in, BitDecoder* high_in) : low(low_in), high(high_in)
+  {
+  }
+
+
+public:
+  BitDecoder(const QString& d) : low(0), high(0), _data(d)
+  {
+  }
+
+  ~BitDecoder()
+  {
+    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;
+    }
+    else {
+      return QPair<QString, uint>(_data, 1);
+    }
+  }
+
+  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);
+    }
+    return combined;
+  }
+
+  static BitDecoder* merge(BitDecoder* low, BitDecoder* high)
+  {
+    return new BitDecoder(low, high);
+  }
+
+  static QBitArray unite(const QBitArray& first, const QBitArray& second)
+  {
+    QBitArray result(first.size() + second.size());
+    int n = first.size();
+    for (int i = 0; i < n; ++i) {
+      result[i] = first[i];
+    }
+    for (int i = 0; i < second.size(); ++i) {
+      result[n + i] = second[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;
+  }
+};
+
+#endif //BITDECODER_HPP

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/TestBitDecoder.cpp	Wed Sep 05 21:54:18 2012 +0200
@@ -0,0 +1,38 @@
+#include "BitDecoder.hpp"
+#include "TestFramework.hpp"
+
+#include "InvalidDataException.hpp"
+#include <QtCore/QDebug>
+
+QBitArray bitsFromString(const QString& str)
+{
+  QBitArray bits(str.size());
+  for (int i = 0; i < str.size(); ++i) {
+    if (str[i] == '1')
+      bits[i] = true;
+    else if (str[i] == '0')
+      bits[i] = false;
+    else
+      throw InvalidDataException();
+  }
+  return bits;
+}
+
+BOOST_AUTO_TEST_CASE( TestSimple )
+{
+  BitDecoder* up = new BitDecoder("a");
+  BitDecoder* down = new BitDecoder("b");
+
+  BitDecoder* full = BitDecoder::merge(down, up);
+
+  BOOST_REQUIRE(full->data().isNull());
+  BOOST_REQUIRE_EQUAL(up->data(), "a");
+  BOOST_REQUIRE_EQUAL(down->data(), "b");
+
+  BOOST_REQUIRE_EQUAL(full->decode(bitsFromString("1")), "a");
+  BOOST_REQUIRE_EQUAL(full->decode(bitsFromString("0")), "b");
+  BOOST_REQUIRE_EQUAL(full->decode(bitsFromString("1111")), "aaaa");
+  BOOST_REQUIRE_EQUAL(full->decode(bitsFromString("0000")), "bbbb");
+  BOOST_REQUIRE_EQUAL(full->decode(bitsFromString("1101")), "aaba");
+  BOOST_REQUIRE_EQUAL(full->decode(bitsFromString("1111")), "aaaa");
+}