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=16dc441715ad4f0a0ed8743e38f9065d1623b03b;hpb=79d19dd14db25dd04e9fc9e0137ce9e8c6e4744f;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 16dc441..d39ea4b 100644
--- a/libcds/src/static_sequence/wt_node_internal.cpp
+++ b/libcds/src/static_sequence/wt_node_internal.cpp
@@ -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)