*/
#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++)
- symbols[i] = am->unmap(symbols[i]);
- delete [] new_symb;
- delete [] oc;
+ 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++)
+ 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() {
return count;
}
+vector<int> static_sequence_wvtree_noptrs::access(uint i, uint j, uint min, uint max)
+{
+ vector<int> resultSet;
+// cout << "height = " << height << endl;
+ access(resultSet, i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
+ return resultSet;
+}
+
+void static_sequence_wvtree_noptrs::access(vector<int> &result, uint i, uint j, uint min, uint max, uint l, uint pivot, uint start, uint end)
+{
+ uint symbol = pivot | (1 << (height-l-1));
+ //std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
+
+ if (l == height)
+ {
+ if (i <= j && pivot >= min && pivot <= max && start <= end)
+ result.push_back(am->unmap((int)pivot));
+ return;
+ }
+
+ if (j < i || max < min || end < start)
+ return;
+
+ if (min < symbol)
+ {
+ // Recurse left
+ uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
+ uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
+ uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
+
+ uint newmax = max < symbol - 1 ? max : symbol - 1;
+ if (newj > start)
+ access(result, newi, newj-1, min, newmax, l+1, pivot, start, newend);
+ }
+
+ if (max >= symbol)
+ {
+ // Recurse right
+ uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
+ newstart = end - newstart + 1;
+ uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
+ uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
+
+ uint newmin = min > symbol ? min : symbol;
+ if (newj > newstart)
+ access(result, newi, newj-1, newmin, max, l+1, symbol, newstart, end);
+ }
+}
+
+
+vector<int> static_sequence_wvtree_noptrs::accessAll(uint i, uint j)
+{
+ vector<int> resultSet;
+ if (j < i)
+ return resultSet;
+
+ resultSet.reserve(j-i+1);
+ accessAll(resultSet, i, j, 0, 0, 0, n-1);
+ return resultSet;
+}
+
+void static_sequence_wvtree_noptrs::accessAll(vector<int> &result, uint i, uint j, uint l, uint pivot, uint start, uint end)
+{
+ uint symbol = pivot | (1 << (height-l-1));
+// std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
+
+ if (l == height)
+ {
+ if (i <= j && start <= end)
+ result.push_back(am->unmap((int)pivot));
+ return;
+ }
+
+ if (j < i || end < start)
+ return;
+
+ {
+ // Recurse left
+ uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
+ uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
+ uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
+
+ if (newj > start)
+ accessAll(result, newi, newj-1, l+1, pivot, start, newend);
+ }
+
+ {
+ // Recurse right
+ uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
+ newstart = end - newstart + 1;
+ uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
+ uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
+
+ if (newj > newstart)
+ accessAll(result, newi, newj-1, l+1, symbol, newstart, end);
+ }
+}
+
+
+uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max)
+{
+ return count(i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
+}
+
+uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max, uint l, uint pivot, uint start, uint end)
+{
+ uint symbol = pivot | (1 << (height-l-1));
+ //std::cout << "At l = " << l << ", [" << i << ", " << j << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
+
+ if (l == height)
+ {
+ if (i <= j && pivot >= min && pivot <= max && start <= end)
+ return 1;
+ return 0;
+ }
+
+ if (j < i || max < min || end < start)
+ return 0;
+
+ uint result = 0;
+ if (min < symbol)
+ {
+ // Recurse left
+ uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
+ uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
+ uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
+
+ uint newmax = max < symbol - 1 ? max : symbol - 1;
+ if (newj > start)
+ result += count(newi, newj-1, min, newmax, l+1, pivot, start, newend);
+ }
+
+ if (max >= symbol)
+ {
+ // Recurse right
+ uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
+ newstart = end - newstart + 1;
+ uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
+ uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
+
+ uint newmin = min > symbol ? min : symbol;
+ if (newj > newstart)
+ result += count(newi, newj-1, newmin, max, l+1, symbol, newstart, end);
+ }
+ return result;
+}
+
+
+
inline uint get_start(uint symbol, uint mask) {
return symbol&mask;
}
}
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) {
projects / SXSI / XMLTree.git / blobdiff