Mercurial > dedupe

comparison BitDecoder.hpp @ 27:95a10553ff90

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Optimize BitDecoder, and refactor functions that are not timecritical out of header.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Thu, 06 Sep 2012 18:20:11 +0200
parents 754e12c927b3
children f711ddb56ae7
comparison
equal deleted inserted replaced
26:c0ddc978475a 27:95a10553ff90
1 #ifndef BITDECODER_HPP 1 #ifndef BITDECODER_HPP
2 #define BITDECODER_HPP 2 #define BITDECODER_HPP
3 3
4 #include <QtCore/QPair>
5 #include <QtCore/QDebug>
6 #include <QtCore/QBitArray> 4 #include <QtCore/QBitArray>
5 #include <QtCore/QString>
6 #include <QtCore/QMap>
7 7
8 class BitDecoder { 8 class BitDecoder {
9 BitDecoder* low; 9 BitDecoder* low;
10 BitDecoder* high; 10 BitDecoder* high;
11 QString _data; 11 QString _data;
12 12
13 private: 13 private:
14 BitDecoder(BitDecoder* low_in, BitDecoder* high_in) : low(low_in), high(high_in) 14 BitDecoder(BitDecoder* low_in, BitDecoder* high_in);
15
16 uint decode(QString& resString, const QBitArray& bits, uint offset)
15 { 17 {
16 } 18 //Data is always stored in a leaf node.
17 19 if (high) {
18 20 return (bits.testBit(offset) ? high : low)->decode(resString, bits, offset + 1) + 1;
19 public:
20 BitDecoder(const QString& d) : low(0), high(0), _data(d)
21 {
22 }
23
24 ~BitDecoder()
25 {
26 delete low;
27 delete high;
28 }
29
30 const QString& data() const
31 {
32 return _data;
33 }
34
35 QPair<QString, uint> decode(const QBitArray& bits, uint offset)
36 {
37 if (_data.isNull()) {
38 QPair<QString, uint> retVal = (bits[offset]?high:low)->decode(bits, offset + 1);
39 ++retVal.second;
40 return retVal;
41 } 21 }
42 else { 22 else {
43 return QPair<QString, uint>(_data, 1); 23 resString.append(_data);
24 return 1;
44 } 25 }
45 } 26 }
46 27
28 public:
29 BitDecoder(const QString& d);
30 ~BitDecoder();
31 const QString& data() const;
32
47 QString decode(const QBitArray& bits) 33 QString decode(const QBitArray& bits)
48 { 34 {
49 QPair<QString, uint> d;
50 QString combined; 35 QString combined;
51 uint n = bits.size(); 36 uint n = bits.size();
52 for (uint decodedBits = 0; decodedBits < n; decodedBits += d.second - 1) { 37 //Just a qualified overestimate guess on what we will need.
53 d = decode(bits, decodedBits); 38 combined.reserve(n/4);
54 combined.append(d.first); 39 for (uint decodedBits = 0; decodedBits < n; decodedBits += decode(combined, bits, decodedBits) - 1);
55 } 40 combined.squeeze();
56 return combined; 41 return combined;
57 } 42 }
58 43
59 static BitDecoder* merge(BitDecoder* low, BitDecoder* high) 44 static BitDecoder* merge(BitDecoder* low, BitDecoder* high);
60 {
61 return new BitDecoder(low, high);
62 }
63
64 static QBitArray unite(const QBitArray& first, const QBitArray& second) 45 static QBitArray unite(const QBitArray& first, const QBitArray& second)
65 { 46 {
66 QBitArray result(first.size() + second.size());
67 int n = first.size(); 47 int n = first.size();
48 int n2 = second.size();
49 QBitArray result(n + n2);
68 for (int i = 0; i < n; ++i) { 50 for (int i = 0; i < n; ++i) {
69 result[i] = first[i]; 51 result.setBit(i, first.testBit(i));
70 } 52 }
71 for (int i = 0; i < second.size(); ++i) { 53 for (int i = 0; i < n2; ++i) {
72 result[n + i] = second[i]; 54 result.setBit(n + i, second.testBit(i));
73 } 55 }
74 return result; 56 return result;
75 } 57 }
76 58
77 QMap<QString, QBitArray> createEncoder() const 59
78 { 60 QMap<QString, QBitArray> createEncoder() const;
79 QMap<QString, QBitArray> retVal;
80 if (!_data.isNull()) {
81 retVal.insert(_data, QBitArray());
82 }
83 if (low) {
84 QMap<QString, QBitArray> vals = low->createEncoder();
85 for(QMap<QString, QBitArray>::const_iterator it = vals.begin();
86 it != vals.end(); ++it) {
87 retVal.insert(it.key(), unite(QBitArray(1, false), it.value()));
88 }
89 }
90 if (high) {
91 QMap<QString, QBitArray> vals = high->createEncoder();
92 for(QMap<QString, QBitArray>::const_iterator it = vals.begin();
93 it != vals.end(); ++it) {
94 retVal.insert(it.key(), unite(QBitArray(1, true), it.value()));
95 }
96 }
97 return retVal;
98 }
99 }; 61 };
100 62
101 #endif //BITDECODER_HPP 63 #endif //BITDECODER_HPP