From: nvalimak <nvalimak@3cdefd35-fc62-479d-8e8d-bae585ffb9ca>
Date: Tue, 19 May 2009 12:26:53 +0000 (+0000)
Subject: New WVTree constructor
X-Git-Url: http://git.nguyen.vg/gitweb/?p=SXSI%2FXMLTree.git;a=commitdiff_plain;h=5489b44ed5656cad39498675305ea9f2bd49dd07

New WVTree constructor

git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@400 3cdefd35-fc62-479d-8e8d-bae585ffb9ca
---

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
--- 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) {
diff --git a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.h b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.h
index 3f7a977..399f3c2 100644
--- a/libcds/src/static_sequence/static_sequence_wvtree_noptrs.h
+++ b/libcds/src/static_sequence/static_sequence_wvtree_noptrs.h
@@ -40,6 +40,9 @@ class static_sequence_wvtree_noptrs : public static_sequence {
      * equals n and uses bmb to build the bitsequence */
     static_sequence_wvtree_noptrs(uint * symbols, uint n, static_bitsequence_builder * bmb, alphabet_mapper * am, bool deleteSymbols = false);
 
+    // symbols is an array of elements of "width" bits.
+    static_sequence_wvtree_noptrs(uint * symbols, uint n, unsigned width, static_bitsequence_builder * bmb, alphabet_mapper * am, bool deleteSymbols = false);
+
     /** Destroys the Wavelet Tree */
     virtual ~static_sequence_wvtree_noptrs();
 
@@ -75,6 +78,7 @@ class static_sequence_wvtree_noptrs : public static_sequence {
     /** Obtains the maximum value from the string
      * symbols of length n */
     uint max_value(uint * symbols, uint n);
+    uint max_value(uint * symbols, unsigned width, uint n);
 
     /** How many bits are needed to represent val */
     uint bits(uint val);
@@ -88,5 +92,6 @@ class static_sequence_wvtree_noptrs : public static_sequence {
 
     /** Recursive function for building the Wavelet Tree. */
     void build_level(uint **bm, uint *symbols, uint level, uint length, uint offset);
+    void build_level(uint **bm, uint *symbols, unsigned width, uint level, uint length, uint offset);
 };
 #endif