Mercurial > dedupe

annotate BitDecoder.hpp @ 81:69a30d9f126e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Make the DBLink reusable.
author Tom Fredrik Blenning Klaussen <bfg@bfgconsult.no>
date Thu, 10 Oct 2013 14:12:17 +0200
parents b9515dc35fe4
children
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) {
64
b9515dc35fe4 Make sure no file has greater linewidth than 80.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
22 return (bits.testBit(offset) ? high : low)->
b9515dc35fe4 Make sure no file has greater linewidth than 80.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
23 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
24 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25 else {
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
26 resString.append(_data);
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
27 return 1;
20
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
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
31 public:
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
32 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
33 ~BitDecoder();
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
34 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
35
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
36 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
37 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
38 QString combined;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
39 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
40 //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
41 combined.reserve(n/4);
64
b9515dc35fe4 Make sure no file has greater linewidth than 80.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
42 for (uint decodedBits = 0; decodedBits < n;
b9515dc35fe4 Make sure no file has greater linewidth than 80.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
43 decodedBits += decode(combined, bits, decodedBits) - 1);
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
44 combined.squeeze();
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
45 return combined;
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
46 }
45
41cc0d8ac77f Decode directly from bitString.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
47 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
48
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
49 static BitDecoder* merge(BitDecoder* low, BitDecoder* high);
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
50 static BitArray bitsFromString(const QString& str);
45
41cc0d8ac77f Decode directly from bitString.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
51
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
52 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
53 {
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
54 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
55 int n2 = second.size();
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
56 BitArray result(n + n2);
20
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
57 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
58 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
59 }
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
60 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
61 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
62 }
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
63 return result;
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
27
95a10553ff90 Optimize BitDecoder, and refactor functions that are not timecritical
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 20
diff changeset
66
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 45
diff changeset
67 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
68 };
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
69
754e12c927b3 Class for decoding binary datarepresentations, eg. Huffman trees.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
70 #endif //BITDECODER_HPP