New WVTree constructor

[SXSI/XMLTree.git] / libcds / src / static_sequence / static_sequence_wvtree_noptrs.cpp

diff --git a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
index a457afd..9a4d64c 100644 (file)
--- a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
+++ b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
@@ -87,6 +87,73 @@ static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uin
   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++)
+      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() {
 }
 
@@ -424,6 +491,42 @@ void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, uint l
   //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) {
   uint max_v = 0;
   for(uint i=0;i<n;i++)
@@ -431,6 +534,13 @@ 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) {