From 816fe5fd2e5c2ef306227c6870a45b026b923f2e Mon Sep 17 00:00:00 2001 From: nvalimak Date: Fri, 27 Mar 2009 15:35:35 +0000 Subject: [PATCH] Added new functionality git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@295 3cdefd35-fc62-479d-8e8d-bae585ffb9ca --- libcds/src/static_sequence/static_sequence.h | 25 ++++- .../static_sequence_wvtree.cpp | 28 +++++ .../static_sequence/static_sequence_wvtree.h | 6 + libcds/src/static_sequence/wt_coder.h | 4 + libcds/src/static_sequence/wt_coder_binary.h | 1 + libcds/src/static_sequence/wt_node.h | 4 + .../src/static_sequence/wt_node_internal.cpp | 104 ++++++++++++++++++ libcds/src/static_sequence/wt_node_internal.h | 3 + libcds/src/static_sequence/wt_node_leaf.cpp | 25 +++++ libcds/src/static_sequence/wt_node_leaf.h | 4 + 10 files changed, 203 insertions(+), 1 deletion(-) diff --git a/libcds/src/static_sequence/static_sequence.h b/libcds/src/static_sequence/static_sequence.h index 363437b..baff3f1 100644 --- a/libcds/src/static_sequence/static_sequence.h +++ b/libcds/src/static_sequence/static_sequence.h @@ -25,6 +25,7 @@ #include #include +#include #define WVTREE_HDR 2 #define GMR_CHUNK_HDR 3 @@ -64,7 +65,29 @@ public: //assert(0); // Implemented only in static_sequence_wvtree return -1; } - + + // Returns all elements from interval [i, j] such that + // their value is in [min, max]. + virtual vector access(uint i, uint j, uint min, uint max) + { + //assert(0); // Implemented only in static_sequence_wvtree + return vector(); + } + + // Returns all elements from interval [i, j] + virtual vector accessAll(uint i, uint j) + { + //assert(0); // Implemented only in static_sequence_wvtree + return vector(); + } + + // Counts the number of elements in interval [i,j] such that + // their values are in [min,max] + virtual uint count(uint i, uint j, uint min, uint max) + { + //assert(0); // Implemented only in static_sequence_wvtree + return 0; + } /** Returns the length of the sequence */ virtual uint length(); diff --git a/libcds/src/static_sequence/static_sequence_wvtree.cpp b/libcds/src/static_sequence/static_sequence_wvtree.cpp index baabf02..ef504bd 100644 --- a/libcds/src/static_sequence/static_sequence_wvtree.cpp +++ b/libcds/src/static_sequence/static_sequence_wvtree.cpp @@ -81,6 +81,34 @@ uint static_sequence_wvtree::access(uint pos) { return am->unmap(root->access(pos)); } +vector static_sequence_wvtree::access(uint i, uint j, uint min, uint max) +{ + vector resultSet; + root->access(resultSet, i, j, am->map(min), am->map(max), c->depth()-1, 0); + for (vector::iterator it = resultSet.begin(); it != resultSet.end(); ++it) + *it = am->unmap(*it); + return resultSet; +} + +vector static_sequence_wvtree::accessAll(uint i, uint j) +{ + vector resultSet; + if (j > i) + return resultSet; + + resultSet.reserve(j-i+1); + root->access(resultSet, i, j); + for (vector::iterator it = resultSet.begin(); it != resultSet.end(); ++it) + *it = am->unmap(*it); + return resultSet; +} + +uint static_sequence_wvtree::count(uint i, uint j, uint min, uint max) +{ + return root->access(i, j, am->map(min), am->map(max), c->depth()-1, 0); +} + + uint static_sequence_wvtree::size() { /*cout << "WT: " << root->size() << endl; cout << "Coder: " << c->size() << endl; diff --git a/libcds/src/static_sequence/static_sequence_wvtree.h b/libcds/src/static_sequence/static_sequence_wvtree.h index dd1259e..5216585 100644 --- a/libcds/src/static_sequence/static_sequence_wvtree.h +++ b/libcds/src/static_sequence/static_sequence_wvtree.h @@ -61,6 +61,12 @@ class static_sequence_wvtree : public static_sequence { return root->access(pos, rank); } + // Returns all elements from interval [i, j] such that + // their value is in [min, max]. + virtual vector access(uint i, uint j, uint min, uint max); + virtual vector accessAll(uint i, uint j); + virtual uint count(uint i, uint j, uint min, uint max); + virtual uint count(uint s); virtual uint size(); diff --git a/libcds/src/static_sequence/wt_coder.h b/libcds/src/static_sequence/wt_coder.h index 3d22b21..5f6d436 100644 --- a/libcds/src/static_sequence/wt_coder.h +++ b/libcds/src/static_sequence/wt_coder.h @@ -46,6 +46,10 @@ class wt_coder { virtual bool done(uint symbol, uint l)=0; /** Returns the size of the coder */ virtual uint size()=0; + /** Returns the depth of the tree */ + virtual uint depth() { + return -1; // Implemented in wt_coder_binary + } /** Saves the coder to a file, returns 0 in case of success */ virtual uint save(FILE *fp)=0; /** Loads a coder from a file, returns NULL in case of error */ diff --git a/libcds/src/static_sequence/wt_coder_binary.h b/libcds/src/static_sequence/wt_coder_binary.h index 850daf2..1df2cbe 100644 --- a/libcds/src/static_sequence/wt_coder_binary.h +++ b/libcds/src/static_sequence/wt_coder_binary.h @@ -40,6 +40,7 @@ class wt_coder_binary: public wt_coder { virtual ~wt_coder_binary(); virtual bool is_set(uint symbol, uint l); virtual bool done(uint symbol, uint l); + virtual uint depth() { return h; } virtual uint size(); virtual uint save(FILE *fp); static wt_coder_binary * load(FILE *fp); diff --git a/libcds/src/static_sequence/wt_node.h b/libcds/src/static_sequence/wt_node.h index 7bfa975..5f8c84f 100644 --- a/libcds/src/static_sequence/wt_node.h +++ b/libcds/src/static_sequence/wt_node.h @@ -24,6 +24,7 @@ #include #include +#include #define WT_NODE_NULL_HDR 0 #define WT_NODE_INTERNAL_HDR 2 @@ -46,6 +47,9 @@ class wt_node { assert(0); // Implemented only in wt_node_internal return -1; } + virtual void access(std::vector &result, uint i, uint j, uint min, uint max, uint l, uint pivot)=0; + virtual void access(std::vector &result, uint i, uint j)=0; + virtual uint access(uint i, uint j, uint min, uint max, uint l, uint pivot)=0; virtual uint size()=0; virtual uint save(FILE *fp)=0; static wt_node * load(FILE *fp); 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 &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 &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) diff --git a/libcds/src/static_sequence/wt_node_internal.h b/libcds/src/static_sequence/wt_node_internal.h index fed8e17..0b1bbc3 100644 --- a/libcds/src/static_sequence/wt_node_internal.h +++ b/libcds/src/static_sequence/wt_node_internal.h @@ -45,6 +45,9 @@ class wt_node_internal: public wt_node { virtual uint select(uint symbol, uint pos, uint level, wt_coder * c); virtual uint access(uint pos); virtual uint access(uint pos, uint &rank); + virtual void access(vector &result, uint i, uint j, uint min, uint max, uint l, uint pivot); + virtual void access(vector &result, uint i, uint j); + virtual uint access(uint i, uint j, uint min, uint max, uint l, uint pivot); virtual uint size(); virtual uint save(FILE *fp); static wt_node_internal * load(FILE *fp); diff --git a/libcds/src/static_sequence/wt_node_leaf.cpp b/libcds/src/static_sequence/wt_node_leaf.cpp index f712f85..43ca7ca 100644 --- a/libcds/src/static_sequence/wt_node_leaf.cpp +++ b/libcds/src/static_sequence/wt_node_leaf.cpp @@ -65,6 +65,31 @@ uint wt_node_leaf::access(uint pos) { return symbol; } +void wt_node_leaf::access(vector &result, uint i, uint j, uint min, uint max, uint l, uint pivot) +{ +// std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << min << ", " << max << "], symbol = " << symbol << std::endl; + + if (i <= j && symbol >= min && symbol <= max) + result.push_back((int)symbol); +} + +void wt_node_leaf::access(vector &result, uint i, uint j) +{ +// std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << min << ", " << max << "], symbol = " << symbol << std::endl; + + if (i <= j) + result.push_back((int)symbol); +} + +uint wt_node_leaf::access(uint i, uint j, uint min, uint max, uint l, uint pivot) +{ +// std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << min << ", " << max << "], symbol = " << symbol << std::endl; + + if (i <= j && symbol >= min && symbol <= max) + return 1; + return 0; +} + uint wt_node_leaf::size() { return sizeof(wt_node_leaf); } diff --git a/libcds/src/static_sequence/wt_node_leaf.h b/libcds/src/static_sequence/wt_node_leaf.h index 39f02d1..0f5e5aa 100644 --- a/libcds/src/static_sequence/wt_node_leaf.h +++ b/libcds/src/static_sequence/wt_node_leaf.h @@ -26,6 +26,7 @@ #include #include #include +#include /** Class for representing leaves of the wavelet tree. * @@ -40,6 +41,9 @@ class wt_node_leaf: public wt_node { virtual uint rankLessThan(uint &symbol, uint pos); virtual uint select(uint symbol, uint pos, uint l, wt_coder * c); virtual uint access(uint pos); + virtual void access(std::vector &result, uint i, uint j, uint min, uint max, uint l, uint pivot); + virtual void access(std::vector &result, uint i, uint j); + virtual uint access(uint i, uint j, uint min, uint max, uint l, uint pivot); virtual uint size(); virtual uint save(FILE *fp); static wt_node_leaf * load(FILE *fp); -- 2.17.1