.

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

diff --git a/libcds/src/static_sequence/static_sequence_bs.cpp b/libcds/src/static_sequence/static_sequence_bs.cpp
index 3a4aaa2..83f18c7 100644 (file)
--- a/libcds/src/static_sequence/static_sequence_bs.cpp
+++ b/libcds/src/static_sequence/static_sequence_bs.cpp
@@ -7,20 +7,28 @@ static_sequence_bs::static_sequence_bs(uint * seq, uint n, alphabet_mapper * am,
        this->am = am;
        am->use();
        for(uint i=0;i<n;i++) sigma=max(sigma,am->map(seq[i]));
-       bitmaps = new static_bitsequence*[++sigma];
-       uint ** bm = new uint*[sigma];
+       sigma++;
+       uint * occ = new uint[sigma+1];
+       for(uint i=0;i<=sigma;i++) occ[i] = 0;
+       for(uint i=0;i<n;i++) occ[am->map(seq[i])+1]++;
+       for(uint i=1;i<sigma;i++) occ[i] += occ[i-1];
+       uint * pos = new uint[n];
+       for(uint i=0;i<n;i++) pos[i] = 0;
+       for(uint i=0;i<n;i++) pos[occ[am->map(seq[i])]++]=i;
+       bitmaps = new static_bitsequence*[sigma];
+       uint * bm = new uint[uint_len(n,1)];
+       uint pp=0;
        for(uint i=0;i<sigma;i++) {
-               bm[i] = new uint[uint_len(len,1)];
-               for(uint j=0;j<uint_len(len,1);j++)
-                       bm[i][j] = 0;
+               for(uint j=0;j<uint_len(n,1);j++) bm[j]=0;
+               while(pp<occ[i]) {
+                       bitset(bm,pos[pp]);
+                       pp++;
+               }
+               bitmaps[i] = bmb->build(bm,len);
        }
-       for(uint i=0;i<n;i++) 
-               bitset(bm[am->map(seq[i])],i);
-       for(uint i=0;i<sigma;i++)
-               bitmaps[i] = bmb->build(bm[i],len);
-       for(uint i=0;i<sigma;i++)
-               delete [] bm[i];
        delete [] bm;
+       delete [] occ;
+       delete [] pos;
 }
 
 static_sequence_bs::static_sequence_bs() {
@@ -44,7 +52,7 @@ uint static_sequence_bs::rank(uint c, uint i) {
        if(am->map(c)>=sigma) return (uint)-1;
        return bitmaps[am->map(c)]->rank1(i);
 }
-
+/*
 uint static_sequence_bs::select(uint c, uint i) {
        if(am->map(c)>=sigma) return (uint)-1;
        return bitmaps[am->map(c)]->select1(i);
@@ -54,7 +62,15 @@ uint static_sequence_bs::select_next(uint c, uint i) {
        if(am->map(c)>=sigma) return (uint)-1;
        return bitmaps[am->map(c)]->select_next1(i);
 }
-
+*/
+uint static_sequence_bs::select(uint c, uint i) {
+       if(c>=sigma) return (uint)-1;
+       return bitmaps[c]->select1(i);
+}
+uint static_sequence_bs::select_next(uint c, uint i) {
+       if(c>=sigma) return (uint)-1;
+       return bitmaps[c]->select_next1(i);
+}
 uint static_sequence_bs::access(uint i) {
        for(uint j=0;j<sigma;j++) {
                if(bitmaps[j]->access(i)) return am->unmap(j);