Mercurial > dedupe

annotate BitDecoder.hpp @ 49:f8d0ea827db3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use BitArray.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Mon, 10 Sep 2012 23:59:46 +0200
parents 41cc0d8ac77f
children b9515dc35fe4
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
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
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
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
8 #include "BitArray.hpp"
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
9
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
10 class BitDecoder {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
11 BitDecoder* low;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12 BitDecoder* high;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
13 QString _data;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
15 private:
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
16 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
17
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
18 uint decode(QString& resString, const BitArray& bits, uint offset) const
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
19 {
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
20 //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
21 if (high) {
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
22 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
23 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24 else {
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
25 resString.append(_data);
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
26 return 1;
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27 }
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
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
30 public:
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
31 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
32 ~BitDecoder();
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
33 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
34
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
35 QString decode(const BitArray& bits) const
20
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 QString combined;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
38 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
39 //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
40 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
41 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
42 combined.squeeze();
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
43 return combined;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
44 }
45
41cc0d8ac77f Decode directly from bitString.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
45 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
46
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
47 static BitDecoder* merge(BitDecoder* low, BitDecoder* high);
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
48 static BitArray bitsFromString(const QString& str);
45
41cc0d8ac77f Decode directly from bitString.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
49
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
50 static BitArray unite(const BitArray& first, const BitArray& second)
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
51 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
52 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
53 int n2 = second.size();
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
54 BitArray result(n + n2);
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
55 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
56 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
57 }
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
58 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
59 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
60 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
61 return result;
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
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
64
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
65 QMap<QString, BitArray> createEncoder() const;
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
66 };
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
67
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
68 #endif //BITDECODER_HPP