Mercurial > dedupe

annotate BitDecoder.hpp @ 20:754e12c927b3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Class for decoding binary datarepresentations, eg. Huffman trees.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Wed, 05 Sep 2012 21:54:18 +0200
parents
children 95a10553ff90
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
1 #ifndef BITDECODER_HPP
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
2 #define BITDECODER_HPP
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
3
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
4 #include <QtCore/QPair>
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
5 #include <QtCore/QDebug>
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
6 #include <QtCore/QBitArray>
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
7
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
8 class BitDecoder {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
9 BitDecoder* low;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
10 BitDecoder* high;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
11 QString _data;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
13 private:
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14 BitDecoder(BitDecoder* low_in, BitDecoder* high_in) : low(low_in), high(high_in)
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
15 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
16 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
17
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
18
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
19 public:
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
20 BitDecoder(const QString& d) : low(0), high(0), _data(d)
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
22 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
23
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24 ~BitDecoder()
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
26 delete low;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27 delete high;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
28 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
30 const QString& data() const
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
31 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
32 return _data;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
33 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
34
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
35 QPair<QString, uint> decode(const QBitArray& bits, uint offset)
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
36 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
37 if (_data.isNull()) {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
38 QPair<QString, uint> retVal = (bits[offset]?high:low)->decode(bits, offset + 1);
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
39 ++retVal.second;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
40 return retVal;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
41 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
42 else {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
43 return QPair<QString, uint>(_data, 1);
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
44 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
45 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
46
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
47 QString decode(const QBitArray& bits)
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
48 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
49 QPair<QString, uint> d;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
50 QString combined;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
51 uint n = bits.size();
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
52 for (uint decodedBits = 0; decodedBits < n; decodedBits += d.second - 1) {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
53 d = decode(bits, decodedBits);
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
54 combined.append(d.first);
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
55 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
56 return combined;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
57 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
58
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
59 static BitDecoder* merge(BitDecoder* low, BitDecoder* high)
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
60 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
61 return new BitDecoder(low, high);
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
62 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
63
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
64 static QBitArray unite(const QBitArray& first, const QBitArray& second)
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
65 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
66 QBitArray result(first.size() + second.size());
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
67 int n = first.size();
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
68 for (int i = 0; i < n; ++i) {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
69 result[i] = first[i];
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
70 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
71 for (int i = 0; i < second.size(); ++i) {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
72 result[n + i] = second[i];
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
73 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
74 return result;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
75 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
76
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
77 QMap<QString, QBitArray> createEncoder() const
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
78 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
79 QMap<QString, QBitArray> retVal;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
80 if (!_data.isNull()) {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
81 retVal.insert(_data, QBitArray());
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
82 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
83 if (low) {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
84 QMap<QString, QBitArray> vals = low->createEncoder();
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
85 for(QMap<QString, QBitArray>::const_iterator it = vals.begin();
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
86 it != vals.end(); ++it) {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
87 retVal.insert(it.key(), unite(QBitArray(1, false), it.value()));
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
88 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
89 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
90 if (high) {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
91 QMap<QString, QBitArray> vals = high->createEncoder();
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
92 for(QMap<QString, QBitArray>::const_iterator it = vals.begin();
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
93 it != vals.end(); ++it) {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
94 retVal.insert(it.key(), unite(QBitArray(1, true), it.value()));
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
95 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
96 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
97 return retVal;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
98 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
99 };
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
100
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
101 #endif //BITDECODER_HPP