Mercurial > dedupe

annotate BitDecoder.hpp @ 64:b9515dc35fe4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Make sure no file has greater linewidth than 80.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Fri, 14 Sep 2012 22:50:45 +0200
parents f8d0ea827db3
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