Added new functionality

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

diff --git a/libcds/src/static_sequence/wt_node_internal.cpp b/libcds/src/static_sequence/wt_node_internal.cpp
index 50bb35f..d39ea4b 100644 (file)
--- a/libcds/src/static_sequence/wt_node_internal.cpp
+++ b/libcds/src/static_sequence/wt_node_internal.cpp
@@ -134,8 +134,8 @@ wt_node_internal::wt_node_internal(uchar * symbols, uint n, uint l, wt_coder * c
        } else {
                right_child = NULL;
        }
-//     delete [] left; // already deleted
-//     delete [] right;
+       delete [] left; // already deleted if count_left > 0
+       delete [] right;
 }
 
 
@@ -183,7 +183,7 @@ uint wt_node_internal::rankLessThan(uint &symbol, uint pos, uint l, wt_coder * c
 
 //    cout << "recursion to leftchild at l = " << l << ", symbol = " << (uchar)symbol << ", rank0 = " << bitmap->rank0(pos) << ", rank1 = " << bitmap->rank1(pos) << endl;
     // check left child for symbols <= givenSymbol
-    if (result != -1 || left_child == NULL)
+    if (result != (uint)-1 || left_child == NULL)
         return result;
     return left_child->rankLessThan(symbol, bitmap->rank0(pos)-1);
 }
@@ -195,11 +195,11 @@ uint wt_node_internal::rankLessThan(uint &symbol, uint pos)
     using std::endl;
 //    cout << "pos = " << pos << ", symbol = " << (uchar)symbol << endl;
     
-    if (pos == -1)
-        return -1;
+    if (pos == (uint)-1)
+        return (uint)-1;
     if(right_child!=NULL)
         result = right_child->rankLessThan(symbol, bitmap->rank1(pos)-1);
-    if(result == -1 && left_child!=NULL)
+    if(result == (uint)-1 && left_child!=NULL)
         return left_child->rankLessThan(symbol, bitmap->rank0(pos)-1);
     return result;
 }
@@ -275,6 +275,110 @@ uint wt_node_internal::access(uint pos, uint &rank)
     }
 }
 
+void wt_node_internal::access(vector<int> &result, uint i, uint j, uint min, uint max, uint l, uint pivot)
+{
+    uint symbol = pivot | (1 << l);
+//    std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], symbol = " << symbol << std::endl;
+
+    if (j < i || max < min)
+        return;
+
+    if (min < symbol)
+    {
+        // Recurse left
+        uint newi = 0;
+        if (i > 0)
+            newi = bitmap->rank0(i - 1);
+        uint newj = bitmap->rank0(j);
+
+        uint newmax = max < symbol - 1 ? max : symbol - 1;
+        if (left_child != NULL && newj > 0)
+            left_child->access(result, newi, newj-1, min, newmax, l-1, pivot);
+    }
+    
+    if (max >= symbol)
+    {
+        // Recurse right
+        uint newi = 0;
+        if (i > 0)
+            newi = bitmap->rank1(i - 1);
+        uint newj = bitmap->rank1(j);
+
+        uint newmin = min > symbol ? min : symbol;
+        if (right_child != NULL && newj > 0)
+            right_child->access(result, newi, newj-1, newmin, max, l-1, symbol);
+    }
+}
+
+void wt_node_internal::access(vector<int> &result, uint i, uint j)
+{
+//    std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], symbol = " << symbol << std::endl;
+
+    if (j < i)
+        return;
+
+    {
+        // Recurse left
+        uint newi = 0;
+        if (i > 0)
+            newi = bitmap->rank0(i - 1);
+        uint newj = bitmap->rank0(j);
+
+        if (left_child != NULL && newj > 0)
+            left_child->access(result, newi, newj-1);
+    }
+    
+    {
+        // Recurse right
+        uint newi = 0;
+        if (i > 0)
+            newi = bitmap->rank1(i - 1);
+        uint newj = bitmap->rank1(j);
+
+        if (right_child != NULL && newj > 0)
+            right_child->access(result, newi, newj-1);
+    }
+}
+
+
+uint wt_node_internal::access(uint i, uint j, uint min, uint max, uint l, uint pivot)
+{
+    uint count = 0;
+    uint symbol = pivot | (1 << l);
+//    std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], symbol = " << symbol << std::endl;
+
+    if (j < i || max < min)
+        return 0;
+
+    if (min < symbol)
+    {
+        // Recurse left
+        uint newi = 0;
+        if (i > 0)
+            newi = bitmap->rank0(i - 1);
+        uint newj = bitmap->rank0(j);
+
+        uint newmax = max < symbol - 1 ? max : symbol - 1;
+        if (left_child != NULL && newj > 0)
+            count += left_child->access(newi, newj-1, min, newmax, l-1, pivot);
+    }
+    
+    if (max >= symbol)
+    {
+        // Recurse right
+        uint newi = 0;
+        if (i > 0)
+            newi = bitmap->rank1(i - 1);
+        uint newj = bitmap->rank1(j);
+
+        uint newmin = min > symbol ? min : symbol;
+        if (right_child != NULL && newj > 0)
+            count += right_child->access(newi, newj-1, newmin, max, l-1, symbol);
+    }
+    return count;
+}
+
+
 uint wt_node_internal::size() {
        uint s = bitmap->size()+sizeof(wt_node_internal);
        if(left_child!=NULL)