Mercurial > dedupe

annotate HuffmanSet.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 f711ddb56ae7
children 19b2a2d98788
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
21
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
1 #ifndef HUFFMANSET_HPP
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
2 #define HUFFMANSET_HPP
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
3
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
4 #include <QtCore/QMap>
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
5 #include <QtCore/QString>
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
6 #include <QtCore/QStringList>
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
7
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
8 #include "BitArray.hpp"
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
9
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
10 class BitDecoder;
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
11 class FastBitDecoder;
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
12
21
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
13 class HuffmanSet {
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14 public:
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
15 typedef uint key_t;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
16
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
17 private:
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
18 QMap<key_t, QString> newStrings;
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
19 QMap<key_t, BitArray> map;
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
20 QMap<QString, BitArray> encoder;
21
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21 uint cutoff;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
22 uint numInserts;
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
23 //FastBitDecoder* lut;
21
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24 BitDecoder* lut;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
26
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27 public:
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
28 HuffmanSet();
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29 void setCutoff(uint cutoff);
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
30 static QStringList chunks(const QString& str);
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
31 BitDecoder* createLut(const QMap<QString, uint>& freqTable);
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
32 QString decode(const BitArray& bits) const;
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 40
diff changeset
33 static BitArray encode(const QString& string, const QMap<QString, BitArray>& encoder);
21
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
34 void rebuild();
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
35 bool contains(key_t key) const;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
36 uint totalElements() const;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
37 key_t hash(const QString& str);
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
38 key_t insert(const QString& str);
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
39 QString value(key_t key) const;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
40 };
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
41
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
42 #endif //HUFFMANSET_HPP