*/
#include <static_sequence_wvtree_noptrs.h>
-
-static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uint n, static_bitsequence_builder * bmb, alphabet_mapper * am) {
+using std::min;
+using std::max;
+static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uint n, static_bitsequence_builder * bmb, alphabet_mapper * am, bool deleteSymbols) {
this->n=n;
this->am=am;
am->use();
uint * new_symb = new uint[n+to_add];
for(uint i=0;i<n;i++)
new_symb[i] = symbols[i];
+
+ if (deleteSymbols)
+ {
+ delete [] symbols;
+ symbols = 0;
+ }
+
to_add = 0;
for(uint i=0;i<max_v;i++)
if(occurrences[i]==0) {
delete [] _bm[i];
}
delete [] _bm;
+
+ if (!deleteSymbols)
+ for(uint i=0;i<n;i++)
+ symbols[i] = am->unmap(symbols[i]);
+
+// delete [] new_symb; // already deleted in build_level()!
+ delete [] oc;
+}
+
+// symbols is an array of elements of "width" bits
+static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uint n, unsigned width, static_bitsequence_builder * bmb, alphabet_mapper * am, bool deleteSymbols) {
+ this->n=n;
+ this->am=am;
+ am->use();
+ for(uint i=0;i<n;i++)
+ set_field(symbols, width, i, am->map(get_field(symbols, width, i)));
+ max_v=max_value(symbols, width, n);
+ height=bits(max_v);
+ uint *occurrences=new uint[max_v+1];
+ for(uint i=0;i<=max_v;i++) occurrences[i]=0;
+ for(uint i=0;i<n;i++)
+ occurrences[get_field(symbols, width, i)]++;
+ uint to_add=0;
+ for(uint i=0;i<max_v;i++)
+ if(occurrences[i]==0) to_add++;
+ uint * new_symb = new uint[((n+to_add)*width)/W + 1];
for(uint i=0;i<n;i++)
- symbols[i] = am->unmap(symbols[i]);
- delete [] new_symb;
- delete [] oc;
+ set_field(new_symb, width, i, get_field(symbols, width, i));
+
+ if (deleteSymbols)
+ {
+ delete [] symbols;
+ symbols = 0;
+ }
+
+ to_add = 0;
+ for(uint i=0;i<max_v;i++)
+ if(occurrences[i]==0) {
+ occurrences[i]++;
+ set_field(new_symb, width, n+to_add, i);
+ to_add++;
+ }
+ uint new_n = n+to_add;
+ for(uint i=1;i<=max_v;i++)
+ occurrences[i] += occurrences[i-1];
+ uint *oc = new uint[(new_n+1)/W+1];
+ for(uint i=0;i<(new_n+1)/W+1;i++)
+ oc[i] = 0;
+ for(uint i=0;i<=max_v;i++)
+ bitset(oc,occurrences[i]-1);
+ bitset(oc,new_n);
+ occ = bmb->build(oc,new_n+1);
+ delete [] occurrences;
+ this->n = new_n;
+ uint ** _bm=new uint*[height];
+ for(uint i=0;i<height;i++) {
+ _bm[i] = new uint[new_n/W+1];
+ for(uint j=0;j<new_n/W+1;j++)
+ _bm[i][j]=0;
+ }
+ build_level(_bm,new_symb,width,0,new_n,0);
+ bitstring = new static_bitsequence*[height];
+ for(uint i=0;i<height;i++) {
+ bitstring[i] = bmb->build(_bm[i],new_n);
+ delete [] _bm[i];
+ }
+ delete [] _bm;
+
+ if (!deleteSymbols)
+ for(uint i=0;i<n;i++)
+ set_field(symbols, width, i, am->unmap(get_field(symbols, width, i)));
+
+// delete [] new_symb; // already deleted in build_level()!
+ delete [] oc;
}
static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs() {
}
void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, uint level, uint length, uint offset) {
- if(level==height) return;
+ if(level==height)
+ {
+ delete [] symbols;
+ return;
+ }
uint cleft=0;
for(uint i=0;i<length;i++)
if(!is_set(symbols[i],level))
right[cright++]=symbols[i];
bitset(bm[level],offset+i);
}
+
+ delete [] symbols;
+ symbols = 0;
+
build_level(bm,left,level+1,cleft,offset);
+ left = 0; // Gets deleted in recursion.
build_level(bm,right,level+1,cright,offset+cleft);
- delete [] left;
- delete [] right;
+ right = 0; // Gets deleted in recursion.
+ //delete [] left;
+ //delete [] right;
+}
+
+// symbols is an array of elements of "width" bits.
+void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, unsigned width, uint level, uint length, uint offset) {
+ if(level==height)
+ {
+ delete [] symbols;
+ return;
+ }
+ uint cleft=0;
+ for(uint i=0;i<length;i++)
+ if(!is_set(get_field(symbols, width, i),level))
+ cleft++;
+ uint cright=length-cleft;
+ uint *left=new uint[(cleft*width)/W + 1],
+ *right=new uint[(cright*width)/W + 1];
+ cleft=cright=0;
+ for(uint i=0;i<length;i++)
+ if(!is_set(get_field(symbols,width,i),level)) {
+ set_field(left,width,cleft++,get_field(symbols, width,i));
+ bitclean(bm[level],offset+i);
+ }
+ else {
+ set_field(right,width,cright++,get_field(symbols,width,i));
+ bitset(bm[level],offset+i);
+ }
+
+ delete [] symbols;
+ symbols = 0;
+
+ build_level(bm,left,width,level+1,cleft,offset);
+ left = 0; // Gets deleted in recursion.
+ build_level(bm,right,width,level+1,cright,offset+cleft);
+ right = 0; // Gets deleted in recursion.
+ //delete [] left;
+ //delete [] right;
}
uint static_sequence_wvtree_noptrs::max_value(uint *symbols, uint n) {
return max_v;
}
+uint static_sequence_wvtree_noptrs::max_value(uint *symbols, unsigned width, uint n) {
+ uint max_v = 0;
+ for(uint i=0;i<n;i++)
+ max_v = max(get_field(symbols, width, i),max_v);
+ return max_v;
+}
+
uint static_sequence_wvtree_noptrs::bits(uint val) {
uint ret = 0;
while(val!=0) {