#ifndef BITDECODER_HPP
#define BITDECODER_HPP

#include <QtCore/QBitArray>
#include <QtCore/QString>
#include <QtCore/QMap>

class BitDecoder {
  BitDecoder* low;
  BitDecoder* high;
  QString _data;

private:
  BitDecoder(BitDecoder* low_in, BitDecoder* high_in);

  uint decode(QString& resString, const QBitArray& bits, uint offset)
  {
    //Data is always stored in a leaf node.
    if (high) {
      return (bits.testBit(offset) ? high : low)->decode(resString, bits, offset + 1) + 1;
    }
    else {
      resString.append(_data);
      return 1;
    }
  }

public:
  BitDecoder(const QString& d);
  ~BitDecoder();
  const QString& data() const;

  QString decode(const QBitArray& bits)
  {
    QString combined;
    uint n = bits.size();
    //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);
  static QBitArray unite(const QBitArray& first, const QBitArray& second)
  {
    int n = first.size();
    int n2 = second.size();
    QBitArray result(n + n2);
    for (int i = 0; i < n; ++i) {
      result.setBit(i, first.testBit(i));
    }
    for (int i = 0; i < n2; ++i) {
      result.setBit(n + i, second.testBit(i));
    }
    return result;
  }


  QMap<QString, QBitArray> createEncoder() const;
};

#endif //BITDECODER_HPP