X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_sequence%2Fstatic_sequence_wvtree_noptrs.cpp;h=18ddcbd2c6670d8fb6edbb6c86df1d24f39b80a8;hb=f32808a35be7a1e62830a5972473178014fa44e5;hp=c1c114bb629fbd96147ada7785cc84c88862b97d;hpb=3d052e0d8f4d581503b9fe53e956b3fc25b0764a;p=SXSI%2FXMLTree.git

diff --git a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
index c1c114b..18ddcbd 100644
--- a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
+++ b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp
@@ -20,8 +20,9 @@
  */
  
 #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();
@@ -39,6 +40,13 @@ static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uin
   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) {
@@ -71,10 +79,80 @@ static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uin
     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() {
@@ -381,7 +459,11 @@ uint static_sequence_wvtree_noptrs::size() {
 }
 
 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))
@@ -398,10 +480,52 @@ void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, uint l
     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) {
@@ -411,6 +535,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) {