X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_sequence%2Fwt_node_internal.cpp;h=50bb35f9e5757742cde72653e888fb6720542376;hb=0412eaf977e4ef67f68db6ded4f1cee0e12cee4f;hp=e741b6f5e7198a5f46ea48953d800d9726ce2391;hpb=0bf9688e2615a9fc07860c5762240e4ce26ee5d3;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 e741b6f..50bb35f 100644 --- a/libcds/src/static_sequence/wt_node_internal.cpp +++ b/libcds/src/static_sequence/wt_node_internal.cpp @@ -1,7 +1,26 @@ - +/* wt_node_internal.cpp + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * wt_node_internal + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + */ + #include - wt_node_internal::wt_node_internal(uint * symbols, uint n, uint l, wt_coder * c, static_bitsequence_builder * bmb) { uint * ibitmap = new uint[n/W+1]; for(uint i=0;i0) { - if(match_left) + if(match_left/* && c->done(left[0],l+1)*/) left_child = new wt_node_leaf(left[0], count_left); else left_child = new wt_node_internal(left, count_left, l+1, c, bmb); @@ -40,7 +59,7 @@ wt_node_internal::wt_node_internal(uint * symbols, uint n, uint l, wt_coder * c, left_child = NULL; } if(count_right>0) { - if(match_right) + if(match_right/* && c->done(right[0],l+1)*/) right_child = new wt_node_leaf(right[0], count_right); else right_child = new wt_node_internal(right, count_right, l+1, c, bmb); @@ -51,6 +70,75 @@ 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) { + uint * ibitmap = new uint[n/W+1]; + for(uint i=0;iis_set((uint)symbols[i],l)) + bitset(ibitmap,i); + bitmap = bmb->build(ibitmap, n); + 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; + 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; + } + } + + 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; + } + else + { + left_child = new wt_node_internal(left, count_left, l+1, c, bmb); + left = 0; // Already deleted + } + } 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; + } + else + { + right_child = new wt_node_internal(right, count_right, l+1, c, bmb); + right = 0; // Already deleted + } + } else { + right_child = NULL; + } +// delete [] left; // already deleted +// delete [] right; +} + + wt_node_internal::wt_node_internal() { } wt_node_internal::~wt_node_internal() { @@ -71,21 +159,70 @@ 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 != -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 == -1) + return -1; + if(right_child!=NULL) + result = right_child->rankLessThan(symbol, bitmap->rank1(pos)-1); + if(result == -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; if(!is_set) { if(left_child==NULL) return (uint)(-1); uint new_pos = left_child->select(symbol, pos, l+1,c); if(new_pos+1==0) return (uint)(-1); - return bitmap->select0(new_pos)+1; + ret = bitmap->select0(new_pos)+1; } else { if(right_child==NULL) return (uint)(-1); uint new_pos = right_child->select(symbol, pos, l+1,c); if(new_pos+1==0) return (uint)(-1); - return bitmap->select1(new_pos)+1; + ret = bitmap->select1(new_pos)+1; } + if(ret==0) return (uint)-1; + return ret; } uint wt_node_internal::access(uint pos) { @@ -99,6 +236,45 @@ 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 + } + } +} + uint wt_node_internal::size() { uint s = bitmap->size()+sizeof(wt_node_internal); if(left_child!=NULL)