Mercurial > dedupe

annotate BitDecoder.hpp @ 40:f711ddb56ae7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Sort up includes.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Fri, 07 Sep 2012 13:32:33 +0200
parents 95a10553ff90
children 41cc0d8ac77f
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
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
16 uint decode(QString& resString, const QBitArray& bits, uint offset)
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
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
33 QString decode(const QBitArray& bits)
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 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
43
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
44 static BitDecoder* merge(BitDecoder* low, BitDecoder* high);
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
45 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
46 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
47 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
48 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
49 QBitArray result(n + n2);
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
50 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
51 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
52 }
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
53 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
54 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
55 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
56 return result;
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
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
59
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
60 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
61 };
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 #endif //BITDECODER_HPP