X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_sequence%2Fwt_node_internal.cpp;h=d39ea4b126be3f11cd79adc1b2363ad6e1a82cb4;hb=816fe5fd2e5c2ef306227c6870a45b026b923f2e;hp=50bb35f9e5757742cde72653e888fb6720542376;hpb=0412eaf977e4ef67f68db6ded4f1cee0e12cee4f;p=SXSI%2FXMLTree.git

diff --git a/libcds/src/static_sequence/wt_node_internal.cpp b/libcds/src/static_sequence/wt_node_internal.cpp
index 50bb35f..d39ea4b 100644
--- 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)