Mercurial > dedupe

changeset 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 ef429402e03b
children f9fa7ea71d37
files BitDecoder.cpp BitDecoder.hpp FastBitDecoder.cpp FastBitDecoder.hpp HuffmanSet.cpp HuffmanSet.hpp
diffstat 6 files changed, 59 insertions(+), 46 deletions(-) [+]
line wrap: on
line diff
--- a/BitDecoder.cpp	Mon Sep 10 23:59:25 2012 +0200
+++ b/BitDecoder.cpp	Mon Sep 10 23:59:46 2012 +0200
@@ -41,37 +41,37 @@
 }
 */
 
-QMap<QString, QBitArray> BitDecoder::createEncoder() const
+QMap<QString, BitArray> BitDecoder::createEncoder() const
 {
-  QMap<QString, QBitArray> retVal;
+  QMap<QString, BitArray> retVal;
   if (!_data.isNull()) {
-    retVal.insert(_data, QBitArray());
+    retVal.insert(_data, BitArray());
   }
   if (low) {
-    QMap<QString, QBitArray> vals = low->createEncoder();
-    for(QMap<QString, QBitArray>::const_iterator it = vals.begin();
+    QMap<QString, BitArray> vals = low->createEncoder();
+    for(QMap<QString, BitArray>::const_iterator it = vals.begin();
 	it != vals.end(); ++it) {
-      retVal.insert(it.key(), unite(QBitArray(1, false), it.value()));
+      retVal.insert(it.key(), unite(BitArray(1, false), it.value()));
     }
   }
   if (high) {
-    QMap<QString, QBitArray> vals = high->createEncoder();
-    for(QMap<QString, QBitArray>::const_iterator it = vals.begin();
+    QMap<QString, BitArray> vals = high->createEncoder();
+    for(QMap<QString, BitArray>::const_iterator it = vals.begin();
 	it != vals.end(); ++it) {
-      retVal.insert(it.key(), unite(QBitArray(1, true), it.value()));
+      retVal.insert(it.key(), unite(BitArray(1, true), it.value()));
     }
   }
   return retVal;
 }
 
-QBitArray BitDecoder::bitsFromString(const QString& str)
+BitArray BitDecoder::bitsFromString(const QString& str)
 {
-  QBitArray bits(str.size());
+  BitArray bits(str.size());
   for (int i = 0; i < str.size(); ++i) {
     if (str[i] == '1')
-      bits[i] = true;
+      bits.setBit(i, true);
     else if (str[i] == '0')
-      bits[i] = false;
+      bits.setBit(i, false);
     else
       throw InvalidDataException();
   }
--- a/BitDecoder.hpp	Mon Sep 10 23:59:25 2012 +0200
+++ b/BitDecoder.hpp	Mon Sep 10 23:59:46 2012 +0200
@@ -1,10 +1,12 @@
 #ifndef BITDECODER_HPP
 #define BITDECODER_HPP
 
-#include <QtCore/QBitArray>
+//#include <QtCore/QBitArray>
 #include <QtCore/QMap>
 #include <QtCore/QString>
 
+#include "BitArray.hpp"
+
 class BitDecoder {
   BitDecoder* low;
   BitDecoder* high;
@@ -13,7 +15,7 @@
 private:
   BitDecoder(BitDecoder* low_in, BitDecoder* high_in);
 
-  uint decode(QString& resString, const QBitArray& bits, uint offset) const
+  uint decode(QString& resString, const BitArray& bits, uint offset) const
   {
     //Data is always stored in a leaf node.
     if (high) {
@@ -30,7 +32,7 @@
   ~BitDecoder();
   const QString& data() const;
 
-  QString decode(const QBitArray& bits) const
+  QString decode(const BitArray& bits) const
   {
     QString combined;
     uint n = bits.size();
@@ -43,13 +45,13 @@
   QString decode(const QString& bits) const;
 
   static BitDecoder* merge(BitDecoder* low, BitDecoder* high);
-  static QBitArray bitsFromString(const QString& str);
+  static BitArray bitsFromString(const QString& str);
 
-  static QBitArray unite(const QBitArray& first, const QBitArray& second)
+  static BitArray unite(const BitArray& first, const BitArray& second)
   {
     int n = first.size();
     int n2 = second.size();
-    QBitArray result(n + n2);
+    BitArray result(n + n2);
     for (int i = 0; i < n; ++i) {
       result.setBit(i, first.testBit(i));
     }
@@ -60,7 +62,7 @@
   }
 
 
-  QMap<QString, QBitArray> createEncoder() const;
+  QMap<QString, BitArray> createEncoder() const;
 };
 
 #endif //BITDECODER_HPP
--- a/FastBitDecoder.cpp	Mon Sep 10 23:59:25 2012 +0200
+++ b/FastBitDecoder.cpp	Mon Sep 10 23:59:46 2012 +0200
@@ -6,7 +6,7 @@
 
 #include <cassert>
 
-unsigned char FastBitDecoder::getPaddedChar(const QBitArray& bits, uint offset)
+unsigned char FastBitDecoder::getPaddedChar(const BitArray& bits, uint offset)
 {
   unsigned char retVal = 0;
   size_t n = std::min(8u, bits.size() - offset);
@@ -16,14 +16,14 @@
   return retVal;
 }
 
-QBitArray FastBitDecoder::removeFirst(const QBitArray& bits)
+BitArray FastBitDecoder::removeFirst(const BitArray& bits)
 {
   size_t N = bits.size();
   assert(N - 8 > 0);
   size_t n = N - 8;
-  QBitArray retVal(n);
+  BitArray retVal(n);
   for (size_t i = 0; i < n; ++i) {
-    retVal.setBit(i, bits.at(i + 8));
+    retVal.setBit(i, bits.testBit(i + 8));
   }
   return retVal;
 }
@@ -58,10 +58,10 @@
 }
 
 
-FastBitDecoder::FastBitDecoder(const QMap<QString, QBitArray>& encoder)
+FastBitDecoder::FastBitDecoder(const QMap<QString, BitArray>& encoder)
 {
   blank();
-  for(QMap<QString, QBitArray>::const_iterator it =  encoder.begin();
+  for(QMap<QString, BitArray>::const_iterator it =  encoder.begin();
       it != encoder.end(); ++it) {
     insert(it.value(), it.key());
   }
@@ -69,7 +69,7 @@
 }
 
 
-void FastBitDecoder::insert(const QBitArray& key, const QString& value)
+void FastBitDecoder::insert(const BitArray& key, const QString& value)
 {
   unsigned char l = getPaddedChar(key);
   if (key.size() <= 8) {
@@ -85,7 +85,7 @@
 }
 
 
-uint FastBitDecoder::decode(QString& resString, const QBitArray& bits, uint offset) const
+uint FastBitDecoder::decode(QString& resString, const BitArray& bits, uint offset) const
 {
   unsigned char l = getPaddedChar(bits, offset);
   if (data[l]) {
--- a/FastBitDecoder.hpp	Mon Sep 10 23:59:25 2012 +0200
+++ b/FastBitDecoder.hpp	Mon Sep 10 23:59:46 2012 +0200
@@ -1,9 +1,10 @@
 #ifndef FASTBITDECODER_HPP
 #define FASTBITDECODER_HPP
 
+#include "BitArray.hpp"
+
 #include <QtCore/QString>
 #include <QtCore/QMap>
-#include <QtCore/QBitArray>
 
 class FastBitDecoder {
   static const size_t N = 256;
@@ -11,18 +12,18 @@
   unsigned char numBits[N];
   QString* data[N];
 
-  static unsigned char getPaddedChar(const QBitArray& bitArray, uint offset = 0);
-  static QBitArray removeFirst(const QBitArray& bits);
+  static unsigned char getPaddedChar(const BitArray& bitArray, uint offset = 0);
+  static BitArray removeFirst(const BitArray& bits);
 
   void fill();
   void blank();
   FastBitDecoder();
-  void insert(const QBitArray& key, const QString& value);
-  uint decode(QString& resString, const QBitArray& bits, uint offset) const;
+  void insert(const BitArray& key, const QString& value);
+  uint decode(QString& resString, const BitArray& bits, uint offset) const;
 
 public:
-  FastBitDecoder(const QMap<QString, QBitArray>& encoder);
-  QString decode(const QBitArray& bits) const
+  FastBitDecoder(const QMap<QString, BitArray>& encoder);
+  QString decode(const BitArray& bits) const
   {
     QString combined;
     uint n = bits.size();
--- a/HuffmanSet.cpp	Mon Sep 10 23:59:25 2012 +0200
+++ b/HuffmanSet.cpp	Mon Sep 10 23:59:46 2012 +0200
@@ -1,5 +1,8 @@
 #include "HuffmanString.hpp"
 
+#include "FastBitDecoder.hpp"
+#include "BitDecoder.hpp"
+
 #include "Exception/InvalidDataException.hpp"
 #include "Exception/NoSuchValueException.hpp"
 
@@ -48,14 +51,14 @@
   return retVal;
 }
 
-QString HuffmanSet::decode(const QBitArray& bits) const
+QString HuffmanSet::decode(const BitArray& bits) const
 {
   return lut->decode(bits);
 }
 
-QBitArray HuffmanSet::encode(const QString& string, const QMap<QString, QBitArray>& encoder)
+BitArray HuffmanSet::encode(const QString& string, const QMap<QString, BitArray>& encoder)
 {
-  QBitArray retVal;
+  BitArray retVal;
   QStringList c = chunks(string);
   foreach(const QString& fragment, c) {
     if (encoder.contains(fragment))
@@ -98,6 +101,10 @@
   }
   numInserts = 0;
   delete lut;
+  /*
+  lut = new FastBitDecoder(encoder);
+  delete newLut;
+  */
   lut = newLut;
   newStrings.clear();
 }
@@ -120,7 +127,7 @@
   key_t key = hash(str);
   if (!contains(key)) {
     try {
-      QBitArray bits = encode(str, encoder);
+      BitArray bits = encode(str, encoder);
       map.insert(key, bits);
     }
     catch (InvalidDataException& e) {
--- a/HuffmanSet.hpp	Mon Sep 10 23:59:25 2012 +0200
+++ b/HuffmanSet.hpp	Mon Sep 10 23:59:46 2012 +0200
@@ -1,23 +1,26 @@
 #ifndef HUFFMANSET_HPP
 #define HUFFMANSET_HPP
 
-#include "BitDecoder.hpp"
-
-#include <QtCore/QBitArray>
 #include <QtCore/QMap>
 #include <QtCore/QString>
 #include <QtCore/QStringList>
 
+#include "BitArray.hpp"
+
+class BitDecoder;
+class FastBitDecoder;
+
 class HuffmanSet {
 public:
   typedef uint key_t;
 
 private:
   QMap<key_t, QString> newStrings;
-  QMap<key_t, QBitArray> map;
-  QMap<QString, QBitArray> encoder;
+  QMap<key_t, BitArray> map;
+  QMap<QString, BitArray> encoder;
   uint cutoff;
   uint numInserts;
+  //FastBitDecoder* lut;
   BitDecoder* lut;
 
 
@@ -26,8 +29,8 @@
   void setCutoff(uint cutoff);
   static QStringList chunks(const QString& str);
   BitDecoder* createLut(const QMap<QString, uint>& freqTable);
-  QString decode(const QBitArray& bits) const;
-  static QBitArray encode(const QString& string, const QMap<QString, QBitArray>& encoder);
+  QString decode(const BitArray& bits) const;
+  static BitArray encode(const QString& string, const QMap<QString, BitArray>& encoder);
   void rebuild();
   bool contains(key_t key) const;
   uint totalElements() const;