X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_sequence%2Fwt_node_internal.cpp;h=0232a73e01f6baa08a674c032ac73e7b7956109a;hb=f32808a35be7a1e62830a5972473178014fa44e5;hp=d39ea4b126be3f11cd79adc1b2363ad6e1a82cb4;hpb=816fe5fd2e5c2ef306227c6870a45b026b923f2e;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 d39ea4b..0232a73 100644 --- a/libcds/src/static_sequence/wt_node_internal.cpp +++ b/libcds/src/static_sequence/wt_node_internal.cpp @@ -70,72 +70,67 @@ wt_node_internal::wt_node_internal(uint * symbols, uint n, uint l, wt_coder * c, delete [] right; } -// Deletes symbols array! -wt_node_internal::wt_node_internal(uchar * symbols, uint n, uint l, wt_coder * c, static_bitsequence_builder * bmb) { +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],l)) + if(c->is_set((uint)symbols[i + left],l)) bitset(ibitmap,i); bitmap = bmb->build(ibitmap, n); - delete [] ibitmap; + delete [] ibitmap; + uint count_right = bitmap->rank1(n-1); - uint count_left = n-count_right+1; - uchar * left = new uchar[count_left+1]; - uchar * right = new uchar[count_right+1]; - count_right = count_left = 0; + uint count_left = n-count_right; + + 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; + } + bool match_left = true, match_right = true; - for(uint i=0;iaccess(i)) { - right[count_right++]=symbols[i]; - if(count_right>1) - if(right[count_right-1]!=right[count_right-2]) - match_right = false; - } - else { - left[count_left++]=symbols[i]; - if(count_left>1) - if(left[count_left-1]!=left[count_left-2]) - match_left = false; - } - } + 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; - delete [] symbols; - symbols = 0; if(count_left>0) { if(match_left/* && c->done(left[0],l+1)*/) - { - left_child = new wt_node_leaf((uint)left[0], count_left); - delete [] left; - left = 0; - } + left_child = new wt_node_leaf((uint)symbols[left], count_left); else - { - left_child = new wt_node_internal(left, count_left, l+1, c, bmb); - left = 0; // Already deleted - } + 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)right[0], count_right); - delete [] right; - right = 0; - } + right_child = new wt_node_leaf((uint)symbols[left+count_left], count_right); else - { - right_child = new wt_node_internal(right, count_right, l+1, c, bmb); - right = 0; // Already deleted - } + right_child = new wt_node_internal(symbols, count_right, l+1, c, bmb, left+count_left, done); } else { right_child = NULL; } - delete [] left; // already deleted if count_left > 0 - delete [] right; } @@ -161,39 +156,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; @@ -239,42 +207,22 @@ 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 = bitmap->access(pos); + if(!is_set) { - 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 - } + // recurse left + pos = bitmap->rank0(pos)-1; + return left_child->access(pos, rank); + } + else + { + // recurse right + pos = bitmap->rank1(pos)-1; + return right_child->access(pos, 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); @@ -340,7 +288,7 @@ void wt_node_internal::access(vector &result, uint i, uint j) } } - +// Count uint wt_node_internal::access(uint i, uint j, uint min, uint max, uint l, uint pivot) { uint count = 0;