Update: libcds WT, empty texts in bitv.

[SXSI/TextCollection.git] / GapEncode.cpp

diff --git a/GapEncode.cpp b/GapEncode.cpp
new file mode 100644 (file)
index 0000000..32102ac
--- /dev/null
+++ b/GapEncode.cpp
@@ -0,0 +1,151 @@
+/**
+ * Gap encoding scheme
+ * Niko Välimäki
+ *
+ */
+
+#include "GapEncode.h"
+#include <stdexcept>
+using namespace std;
+
+
+GapEncode::GapEncode(ulong *B, ulong u, bool freeB = false)
+{
+    ulong i, lastIndex, *bitRun, *runLength;
+    this->u = u;
+    this->numberOfRuns = 0;
+    bitRun = new ulong[u/W + 1];
+    for (i = 0; i < u/W + 1; i ++)
+        bitRun[i]  = 0;
+
+    // Collect the runs of 1- or 0-bits
+    totalLength = 0;
+    uchar curBit = 0xFF;
+    lastIndex = 0;
+    for (i = 0; i < u; i ++)
+        if (Tools::GetField(B, 1, i) != curBit)
+        {
+            if (curBit == 1)
+                totalLength += i - lastIndex;
+            else if (Tools::GetField(B, 1, i))
+                Tools::SetField(bitRun, 1, i, 1);
+
+            lastIndex = i;
+            curBit = Tools::GetField(B, 1, i);
+        }
+    // Handle the last run
+    if (curBit == 1)
+        totalLength += i - lastIndex;
+    
+    runLength = new ulong[totalLength/W + 1];
+    for (i = 0; i < totalLength/W + 1; i ++)
+        runLength[i] = 0;
+    
+    // Calculate run lengths
+    totalLength = 0;
+    curBit = 0xFF;
+    lastIndex = 0;
+    for (i = 0; i < u; i ++)
+        if (Tools::GetField(B, 1, i) != curBit)
+        {
+            if (curBit == 1)
+            {
+                totalLength += i - lastIndex;
+                Tools::SetField(runLength, 1, totalLength - 1, 1);
+            }
+            lastIndex = i;
+            curBit = Tools::GetField(B, 1, i);
+        }
+    // Handle the last run
+    if (curBit == 1)
+    {
+        totalLength += i - lastIndex;
+        Tools::SetField(runLength, 1, totalLength - 1, 1);
+    }
+    
+    // Construct BSGAP structures
+    this->bitRun = new BSGAP(bitRun, u, true, 0);
+    numberOfRuns = this->bitRun->rank(u-1);
+    this->runLength = new BSGAP(runLength, totalLength, true, 0);
+    
+    if (freeB)
+        delete [] B;
+}
+
+GapEncode::~GapEncode()
+{
+    // Free BSGAP structures
+    delete bitRun;
+    delete runLength;
+}
+
+ulong GapEncode::rank(ulong i)
+{
+    ulong pred, r = bitRun->rank(i);
+    if (r == 0)
+        return 0;
+    pred = bitRun->select(r);
+    
+    ulong bitsBeforeRun = 0;
+    if (r > 1)
+        bitsBeforeRun = runLength->select(r - 1) + 1;
+    
+    ulong bitsInRun = runLength->select(r) + 1 - bitsBeforeRun;
+    if (i - pred >= bitsInRun)
+        return bitsBeforeRun + bitsInRun;
+    
+    return bitsBeforeRun + i - pred + 1;
+}
+
+ulong GapEncode::rank0(ulong i)
+{
+    return i - rank(i) + 1;
+}
+
+ulong GapEncode::select(ulong i)
+{
+    throw logic_error("GapEncode::select() is not implemented");
+    return 0;
+}
+
+ulong GapEncode::select0(ulong i)
+{
+    throw logic_error("GapEncode::select0() is not implemented");
+    return 0; // To be implemented...
+}
+
+/**
+ * Saving data fields:
+    ulong u;                // Universe size, number of bits in B
+    ulong numberOfRuns;     // Number of 1-bit runs
+    BSGAP *bitRun,          // Contains 1-bit at the start of each 1-bit-run
+          *runLength;       // Contains run lengths for each 1-bit-run
+    ulong totalLength;      // Total length of runs
+*/
+void GapEncode::Save(FILE *file) const
+{
+    if (std::fwrite(&(this->u), sizeof(ulong), 1, file) != 1)
+        throw std::runtime_error("GapEncode::Save(): file write error (u).");
+    if (std::fwrite(&(this->numberOfRuns), sizeof(ulong), 1, file) != 1)
+        throw std::runtime_error("GapEncode::Save(): file write error (numberOfRuns).");
+
+    bitRun->Save(file);
+    runLength->Save(file);
+
+    if (std::fwrite(&(this->totalLength), sizeof(ulong), 1, file) != 1)
+        throw std::runtime_error("GapEncode::Save(): file write error (totalLength).");
+}
+
+GapEncode::GapEncode(FILE *file)
+{
+    if (std::fread(&(this->u), sizeof(ulong), 1, file) != 1)
+        throw std::runtime_error("GapEncode::Load(): file read error (u).");
+    if (std::fread(&(this->numberOfRuns), sizeof(ulong), 1, file) != 1)
+        throw std::runtime_error("GapEncode::Load(): file read error (numberOfRuns).");
+
+    bitRun = new BSGAP(file);
+    runLength = new BSGAP(file);
+
+    if (std::fread(&(this->totalLength), sizeof(ulong), 1, file) != 1)
+        throw std::runtime_error("GapEncode::Load(): file read error (totalLength).");
+}