Removed the naive text interface

[SXSI/XMLTree.git] / libcds / src / static_sequence / static_sequence_wvtree_noptrs.cpp

diff --git a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
index 72eeac8..a457afd 100644 (file)
--- a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
+++ b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
@@ -21,7 +21,7 @@
  
 #include <static_sequence_wvtree_noptrs.h>
 
-static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uint n, static_bitsequence_builder * bmb, alphabet_mapper * am) {
+static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uint n, static_bitsequence_builder * bmb, alphabet_mapper * am, bool deleteSymbols) {
   this->n=n;
   this->am=am;
        am->use();
@@ -39,6 +39,13 @@ static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uin
   uint * new_symb = new uint[n+to_add];
   for(uint i=0;i<n;i++)
     new_symb[i] = symbols[i];
+
+  if (deleteSymbols)
+  {
+      delete [] symbols;
+      symbols = 0;
+  }
+
   to_add = 0;
   for(uint i=0;i<max_v;i++)
     if(occurrences[i]==0) {
@@ -71,10 +78,13 @@ static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uin
     delete [] _bm[i];
   }
   delete [] _bm;
-  for(uint i=0;i<n;i++)
-    symbols[i] = am->unmap(symbols[i]);
-       delete [] new_symb;
-       delete [] oc;
+  
+  if (!deleteSymbols)
+      for(uint i=0;i<n;i++)
+          symbols[i] = am->unmap(symbols[i]);
+
+// delete [] new_symb; // already deleted in build_level()!
+  delete [] oc;
 }
 
 static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs() {
@@ -188,6 +198,155 @@ uint static_sequence_wvtree_noptrs::rank(uint symbol, uint pos) {
   return count;
 }
 
+vector<int> static_sequence_wvtree_noptrs::access(uint i, uint j, uint min, uint max)
+{
+    vector<int> resultSet;
+//    cout << "height = " << height << endl;
+    access(resultSet, i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
+    return resultSet;
+}
+
+void static_sequence_wvtree_noptrs::access(vector<int> &result, uint i, uint j, uint min, uint max, uint l, uint pivot, uint start, uint end)
+{
+    uint symbol = pivot | (1 << (height-l-1));
+    //std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
+
+    if (l == height)
+    {
+        if (i <= j && pivot >= min && pivot <= max && start <= end)
+            result.push_back(am->unmap((int)pivot));
+        return;
+    }
+
+    if (j < i || max < min || end < start)
+        return;
+
+    if (min < symbol)
+    {
+        // Recurse left
+        uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
+        uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
+        uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
+
+        uint newmax = max < symbol - 1 ? max : symbol - 1;
+        if (newj > start)
+            access(result, newi, newj-1, min, newmax, l+1, pivot, start, newend);
+    }
+
+    if (max >= symbol)
+    {
+        // Recurse right
+        uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
+        newstart = end - newstart + 1;
+        uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
+        uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
+
+        uint newmin = min > symbol ? min : symbol;
+        if (newj > newstart)
+            access(result, newi, newj-1, newmin, max, l+1, symbol, newstart, end);
+    }
+}
+
+
+vector<int> static_sequence_wvtree_noptrs::accessAll(uint i, uint j)
+{
+    vector<int> resultSet;
+    if (j < i)
+        return resultSet;
+
+    resultSet.reserve(j-i+1);
+    accessAll(resultSet, i, j, 0, 0, 0, n-1);
+    return resultSet;
+}
+
+void static_sequence_wvtree_noptrs::accessAll(vector<int> &result, uint i, uint j, uint l, uint pivot, uint start, uint end)
+{
+    uint symbol = pivot | (1 << (height-l-1));
+//    std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
+
+    if (l == height)
+    {
+        if (i <= j && start <= end)
+            result.push_back(am->unmap((int)pivot));
+        return;
+    }
+
+    if (j < i || end < start)
+        return;
+
+    {
+        // Recurse left
+        uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
+        uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
+        uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
+
+        if (newj > start)
+            accessAll(result, newi, newj-1, l+1, pivot, start, newend);
+    }
+
+    {
+        // Recurse right
+        uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
+        newstart = end - newstart + 1;
+        uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
+        uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
+
+        if (newj > newstart)
+            accessAll(result, newi, newj-1, l+1, symbol, newstart, end);
+    }
+}
+
+
+uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max)
+{
+    return count(i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
+}
+
+uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max, uint l, uint pivot, uint start, uint end)
+{
+    uint symbol = pivot | (1 << (height-l-1));
+    //std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
+
+    if (l == height)
+    {
+        if (i <= j && pivot >= min && pivot <= max && start <= end)
+            return 1;
+        return 0;
+    }
+
+    if (j < i || max < min || end < start)
+        return 0;
+
+    uint result = 0;
+    if (min < symbol)
+    {
+        // Recurse left
+        uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
+        uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
+        uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
+
+        uint newmax = max < symbol - 1 ? max : symbol - 1;
+        if (newj > start)
+            result += count(newi, newj-1, min, newmax, l+1, pivot, start, newend);
+    }
+
+    if (max >= symbol)
+    {
+        // Recurse right
+        uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
+        newstart = end - newstart + 1;
+        uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
+        uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
+
+        uint newmin = min > symbol ? min : symbol;
+        if (newj > newstart)
+            result += count(newi, newj-1, newmin, max, l+1, symbol, newstart, end);
+    }
+    return result;
+}
+
+
+
 inline uint get_start(uint symbol, uint mask) {
   return symbol&mask;
 }
@@ -232,7 +391,11 @@ uint static_sequence_wvtree_noptrs::size() {
 }
 
 void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, uint level, uint length, uint offset) {
-  if(level==height) return;
+  if(level==height)
+  {
+      delete [] symbols;
+      return;
+  }
   uint cleft=0;
   for(uint i=0;i<length;i++)
     if(!is_set(symbols[i],level))
@@ -249,10 +412,16 @@ void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, uint l
     right[cright++]=symbols[i];
     bitset(bm[level],offset+i);
   }
+  
+  delete [] symbols;
+  symbols = 0;
+  
   build_level(bm,left,level+1,cleft,offset);
+  left = 0; // Gets deleted in recursion.
   build_level(bm,right,level+1,cright,offset+cleft);
-  delete [] left;
-  delete [] right;
+  right = 0; // Gets deleted in recursion.
+  //delete [] left;
+  //delete [] right;
 }
 
 uint static_sequence_wvtree_noptrs::max_value(uint *symbols, uint n) {