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=f5312db058ad0e55140b1cfde383e2b2c118e34f;hpb=317fdc10a3d537fd87b855c4b8714b2472cde608;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 f5312db..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; } @@ -159,6 +159,52 @@ uint wt_node_internal::rank(uint symbol, uint pos, uint l, wt_coder * c) { } } +// return value is rank of symbol (less or equal to the given symbol) that has rank > 0, +// the parameter symbol is updated accordinly +uint wt_node_internal::rankLessThan(uint &symbol, uint pos, uint l, wt_coder * c) +{ + bool is_set = c->is_set(symbol,l); + using std::cout; + using std::endl; +// cout << "l = " << l << ", symbol = " << (uchar)symbol << ", rank0 = " << bitmap->rank0(pos) << ", rank1 = " << bitmap->rank1(pos) << endl; + + uint result = -1; + if(!is_set) { + if(left_child==NULL) return -1; + uint rank = bitmap->rank0(pos); + if(rank != 0) + result = left_child->rankLessThan(symbol,rank-1,l+1,c); + return result; + } + + uint rank = bitmap->rank1(pos); + if (rank != 0 && right_child != NULL) + result = right_child->rankLessThan(symbol, rank-1,l+1,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 != (uint)-1 || left_child == NULL) + return result; + return left_child->rankLessThan(symbol, bitmap->rank0(pos)-1); +} + +uint wt_node_internal::rankLessThan(uint &symbol, uint pos) +{ + uint result = -1; + using std::cout; + using std::endl; +// cout << "pos = " << pos << ", symbol = " << (uchar)symbol << endl; + + if (pos == (uint)-1) + return (uint)-1; + if(right_child!=NULL) + result = right_child->rankLessThan(symbol, bitmap->rank1(pos)-1); + if(result == (uint)-1 && left_child!=NULL) + return left_child->rankLessThan(symbol, bitmap->rank0(pos)-1); + return result; +} + + uint wt_node_internal::select(uint symbol, uint pos, uint l, wt_coder * c) { bool is_set = c->is_set(symbol, l); uint ret = 0; @@ -190,6 +236,149 @@ uint wt_node_internal::access(uint pos) { } } +// Returns the value at given position and its rank +uint wt_node_internal::access(uint pos, uint &rank) +{ + // p is the internal node we are pointing our finger at each step + wt_node_internal *p = this; + + while(1) + { + bool is_set = p->bitmap->access(pos); +// cout << "is_set = " << is_set << ", pos = " << pos << ", rank0 = " << bitmap->rank0(pos) << ", rank1 = " << bitmap->rank1(pos) << endl; + if(!is_set) + { + // recurse left + pos = p->bitmap->rank0(pos)-1; + wt_node_internal *tmp = dynamic_cast(p->left_child); + if (tmp == NULL) + { + // it's a leaf + rank = pos+1; + return p->left_child->access(0); + } + p = tmp; // new internal node + } + else + { + // recurse right + pos = p->bitmap->rank1(pos)-1; + wt_node_internal *tmp = dynamic_cast(p->right_child); + if (tmp == NULL) + { + // it's a leaf + rank = pos+1; + return p->right_child->access(0); + } + p = tmp; // new internal node + } + } +} + +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)