From 27a8f46b4d66ba249e5ecf8fbfa954e15d582509 Mon Sep 17 00:00:00 2001 From: nvalimak Date: Thu, 16 Apr 2009 11:40:46 +0000 Subject: [PATCH 1/1] Added new functions git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@316 3cdefd35-fc62-479d-8e8d-bae585ffb9ca --- .../static_sequence_wvtree_noptrs.cpp | 149 ++++++++++++++++++ 1 file changed, 149 insertions(+) diff --git a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp index 72eeac8..99e0c6a 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 static_sequence_wvtree_noptrs::access(uint i, uint j, uint min, uint max) +{ + vector 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 &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 static_sequence_wvtree_noptrs::accessAll(uint i, uint j) +{ + vector 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 &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; } -- 2.17.1