X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_sequence%2Fstatic_sequence_wvtree_noptrs.cpp;h=c1c114bb629fbd96147ada7785cc84c88862b97d;hb=3d052e0d8f4d581503b9fe53e956b3fc25b0764a;hp=72eeac868e9b626bed4f60ead3463c7661004711;hpb=52cb7bbcda67f4676335cdd4eb96d4d87ad1445d;p=SXSI%2FXMLTree.git

diff --git a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
index 72eeac8..c1c114b 100644
--- a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
+++ b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
@@ -188,6 +188,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;
 }