Mercurial > dedupe

comparison BitDecoder.hpp @ 20:754e12c927b3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Class for decoding binary datarepresentations, eg. Huffman trees.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Wed, 05 Sep 2012 21:54:18 +0200
parents
children 95a10553ff90
comparison
equal deleted inserted replaced
19:1ad6fa6dc039 20:754e12c927b3
1 #ifndef BITDECODER_HPP
2 #define BITDECODER_HPP
3
4 #include <QtCore/QPair>
5 #include <QtCore/QDebug>
6 #include <QtCore/QBitArray>
7
8 class BitDecoder {
9 BitDecoder* low;
10 BitDecoder* high;
11 QString _data;
12
13 private:
14 BitDecoder(BitDecoder* low_in, BitDecoder* high_in) : low(low_in), high(high_in)
15 {
16 }
17
18
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 }
42 else {
43 return QPair<QString, uint>(_data, 1);
44 }
45 }
46
47 QString decode(const QBitArray& bits)
48 {
49 QPair<QString, uint> d;
50 QString combined;
51 uint n = bits.size();
52 for (uint decodedBits = 0; decodedBits < n; decodedBits += d.second - 1) {
53 d = decode(bits, decodedBits);
54 combined.append(d.first);
55 }
56 return combined;
57 }
58
59 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)
65 {
66 QBitArray result(first.size() + second.size());
67 int n = first.size();
68 for (int i = 0; i < n; ++i) {
69 result[i] = first[i];
70 }
71 for (int i = 0; i < second.size(); ++i) {
72 result[n + i] = second[i];
73 }
74 return result;
75 }
76
77 QMap<QString, QBitArray> createEncoder() const
78 {
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 };
100
101 #endif //BITDECODER_HPP