X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_sequence%2Fwt_node_internal.cpp;h=4e6871a802ddf7bad3f2ec02900376490cb574b1;hb=95f2dabec7cabe4002865e5f9d12651e6e32229a;hp=16dc441715ad4f0a0ed8743e38f9065d1623b03b;hpb=bbeeb03980ddf51c0f32fd3c42321dc9ef708c27;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..4e6871a 100644 --- a/libcds/src/static_sequence/wt_node_internal.cpp +++ b/libcds/src/static_sequence/wt_node_internal.cpp @@ -138,6 +138,95 @@ wt_node_internal::wt_node_internal(uchar * symbols, uint n, uint l, wt_coder * c delete [] right; } +wt_node_internal::wt_node_internal(uchar * symbols, uint n, uint l, wt_coder * c, static_bitsequence_builder * bmb, uint left, uint *done) { + uint * ibitmap = new uint[n/W+1]; + for(uint i=0;iis_set((uint)symbols[i + left],l)) + bitset(ibitmap,i); + bitmap = bmb->build(ibitmap, n); + delete [] ibitmap; + + uint count_right = bitmap->rank1(n-1); + uint count_left = n-count_right; +/* uchar * leftarr = new uchar[count_left+1]; + uchar * rightarr = new uchar[count_right+1]; + count_right = count_left = 0; + for(uint i=0;iaccess(i)) { + rightarr[count_right++]=symbols[i+left]; + } + else { + leftarr[count_left++]=symbols[i+left]; + } + } +*/ + + for (uint i=0;iis_set(swap,l)) + j = bitmap->rank0(k)-1; + else + j = count_left + bitmap->rank1(k)-1; + uchar temp = symbols[j+left]; + symbols[j+left] = swap; + swap = temp; + set_field(done,1,k+left,1); + } + + while (get_field(done,1,i+left)) + ++i; + } + + // checking + /* for (uint i=0;iis_set(symbols[i+left], l)) + { + std::cout << symbols[i+left] << " != " << leftarr[i] << " lev = " << l << "\n"; + exit(0); + } + for (uint i=count_left;iis_set(symbols[i+left],l)) + std::cout << symbols[i+left] << " != " << rightarr[i-count_left] << " lev = " << l << "\n"; + */ + bool match_left = true, match_right = true; + for (uint i=1; i < count_left; i++) + if (symbols[i+left] != symbols[i+left-1]) + match_left = false; + for (uint i=count_left + 1; i < n; i++) + if (symbols[i+left] != symbols[i+left-1]) + match_right = false; + + + if(count_left>0) { + if(match_left/* && c->done(left[0],l+1)*/) + left_child = new wt_node_leaf((uint)symbols[left], count_left); + else + left_child = new wt_node_internal(symbols, count_left, l+1, c, bmb, left, done); + } else { + left_child = NULL; + } + if(count_right>0) { + if(match_right/* && c->done(right[0],l+1)*/) + right_child = new wt_node_leaf((uint)symbols[left+count_left], count_right); + else + right_child = new wt_node_internal(symbols, count_right, l+1, c, bmb, left+count_left, done); + } else { + right_child = NULL; + } +} + wt_node_internal::wt_node_internal() { } @@ -161,39 +250,12 @@ 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; +// cout << "pos = " << pos << ", symbol = " << symbol << endl; if (pos == (uint)-1) return (uint)-1; @@ -275,6 +337,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); + } +} + +// Count +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)