X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_sequence%2Fstatic_sequence_bs.cpp;h=f04325e32150c72e4e131384e15a950b714c94bf;hb=f32808a35be7a1e62830a5972473178014fa44e5;hp=3a4aaa24dd3ff3ca2a59a9fc7245ed86492fd1be;hpb=935f20b93a3db7cd2f9f39573d4ab434fcc4356a;p=SXSI%2FXMLTree.git

diff --git a/libcds/src/static_sequence/static_sequence_bs.cpp b/libcds/src/static_sequence/static_sequence_bs.cpp
index 3a4aaa2..f04325e 100644
--- a/libcds/src/static_sequence/static_sequence_bs.cpp
+++ b/libcds/src/static_sequence/static_sequence_bs.cpp
@@ -1,26 +1,34 @@
 
 #include <static_sequence_bs.h>
-
+using std::max;
 static_sequence_bs::static_sequence_bs(uint * seq, uint n, alphabet_mapper * am, static_bitsequence_builder * bmb) {
 	sigma = 0;
 	len = n;
 	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);