Mercurial > dedupe

annotate BitDecoder.hpp @ 45:41cc0d8ac77f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Decode directly from bitString.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Mon, 10 Sep 2012 21:29:43 +0200
parents f711ddb56ae7
children f8d0ea827db3
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/QBitArray>
40
f711ddb56ae7 Sort up includes.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 27
diff changeset
5 #include <QtCore/QMap>
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
6 #include <QtCore/QString>
20
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:
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
14 BitDecoder(BitDecoder* low_in, BitDecoder* high_in);
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
15
45
41cc0d8ac77f Decode directly from bitString.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
16 uint decode(QString& resString, const QBitArray& bits, uint offset) const
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
17 {
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
18 //Data is always stored in a leaf node.
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
19 if (high) {
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
20 return (bits.testBit(offset) ? high : low)->decode(resString, bits, offset + 1) + 1;
20
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 else {
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
23 resString.append(_data);
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
24 return 1;
20
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 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
28 public:
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
29 BitDecoder(const QString& d);
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
30 ~BitDecoder();
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
31 const QString& data() const;
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
32
45
41cc0d8ac77f Decode directly from bitString.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
33 QString decode(const QBitArray& bits) const
20
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 QString combined;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
36 uint n = bits.size();
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
37 //Just a qualified overestimate guess on what we will need.
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
38 combined.reserve(n/4);
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
39 for (uint decodedBits = 0; decodedBits < n; decodedBits += decode(combined, bits, decodedBits) - 1);
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
40 combined.squeeze();
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
41 return combined;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
42 }
45
41cc0d8ac77f Decode directly from bitString.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
43 QString decode(const QString& bits) const;
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
44
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
45 static BitDecoder* merge(BitDecoder* low, BitDecoder* high);
45
41cc0d8ac77f Decode directly from bitString.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
46 static QBitArray bitsFromString(const QString& str);
41cc0d8ac77f Decode directly from bitString.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
47
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
48 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
49 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
50 int n = first.size();
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
51 int n2 = second.size();
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
52 QBitArray result(n + n2);
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
53 for (int i = 0; i < n; ++i) {
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
54 result.setBit(i, first.testBit(i));
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
55 }
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
56 for (int i = 0; i < n2; ++i) {
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
57 result.setBit(n + i, second.testBit(i));
20
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 return result;
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
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
62
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
63 QMap<QString, QBitArray> createEncoder() const;
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
64 };
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 #endif //BITDECODER_HPP