X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_sequence%2Fstatic_sequence_bs.cpp;h=283b89c56e60aa017a21bb85e173217fc0be3149;hb=436e9a6d3e2caeb2b883115f064e14d5b3d3280e;hp=fecca78a864bd375521d34f5dc9dac299f997f78;hpb=bbeeb03980ddf51c0f32fd3c42321dc9ef708c27;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 fecca78..283b89c 100644
--- 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() {
@@ -50,6 +58,11 @@ uint static_sequence_bs::select(uint c, uint i) {
 	return bitmaps[am->map(c)]->select1(i);
 }
 
+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::access(uint i) {
 	for(uint j=0;j<sigma;j++) {
 		if(bitmaps[j]->access(i)) return am->unmap(j);