Mercurial > dedupe

annotate HuffmanSet.hpp @ 21:3bcdb8bb6914

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Huffman representations.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Wed, 05 Sep 2012 21:54:53 +0200
parents
children f711ddb56ae7
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 #include <QtCore/QBitArray>
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
8
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
9 #include "BitDecoder.hpp"
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
10
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
11 class HuffmanSet {
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12 public:
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
13 typedef uint key_t;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
15 private:
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
16 QMap<key_t, QString> newStrings;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
17 QMap<key_t, QBitArray> map;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
18 QMap<QString, QBitArray> encoder;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
19 uint cutoff;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
20 uint numInserts;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21 BitDecoder* lut;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
22
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
23
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24 public:
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25 HuffmanSet();
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
26 void setCutoff(uint cutoff);
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27 static QStringList chunks(const QString& str);
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
28 BitDecoder* createLut(const QMap<QString, uint>& freqTable);
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29 QString decode(const QBitArray& bits) const;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
30 static QBitArray encode(const QString& string, const QMap<QString, QBitArray>& encoder);
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
31 void rebuild();
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
32 bool contains(key_t key) const;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
33 uint totalElements() const;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
34 key_t hash(const QString& str);
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
35 key_t insert(const QString& str);
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
36 QString value(key_t key) const;
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
37 };
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
38
3bcdb8bb6914 Huffman representations.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
39 #endif //HUFFMANSET_HPP