#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