From 935f20b93a3db7cd2f9f39573d4ab434fcc4356a Mon Sep 17 00:00:00 2001
From: fclaude <fclaude@3cdefd35-fc62-479d-8e8d-bae585ffb9ca>
Date: Sun, 26 Apr 2009 04:01:12 +0000
Subject: [PATCH] improvements...

git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@345 3cdefd35-fc62-479d-8e8d-bae585ffb9ca
---
 XMLTree.cpp                                   |  37 ++-
 libcds/src/static_bitsequence/sdarray.cpp     | 283 ++++++++++++------
 libcds/src/static_bitsequence/sdarray.h       |   1 +
 .../static_bitsequence/static_bitsequence.cpp |   8 +
 .../static_bitsequence/static_bitsequence.h   |   3 +
 .../static_bitsequence_sdarray.cpp            | 102 ++++---
 .../static_bitsequence_sdarray.h              |   1 +
 .../src/static_sequence/static_sequence.cpp   |   4 +
 libcds/src/static_sequence/static_sequence.h  |   1 +
 .../static_sequence/static_sequence_bs.cpp    |   5 +
 .../src/static_sequence/static_sequence_bs.h  |   1 +
 libcds/tests/static_bitsequence_test.cpp      |  13 +-
 libcds/tests/static_bitsequence_tester.cpp    |  31 +-
 libcds/tests/static_bitsequence_tester.h      |   1 +
 14 files changed, 328 insertions(+), 163 deletions(-)

diff --git a/XMLTree.cpp b/XMLTree.cpp
index 249143c..2a1da84 100644
--- a/XMLTree.cpp
+++ b/XMLTree.cpp
@@ -566,13 +566,14 @@ treeNode XMLTree::TaggedDesc(treeNode x, TagType tag)
        exit(1);
     }
 
-    int r, s;
+    //int r, s;
     treeNode y;
     if (isleaf(Par,x))
       return NULLT;
 
-    r = (int) Tags->rank(tag, node2tagpos(x));
-    s = (int) Tags->select(tag, r+1);
+		int s = (int) Tags->select_next(tag,node2tagpos(x));
+    /*r = (int) Tags->rank(tag, node2tagpos(x));
+    s = (int) Tags->select(tag, r+1);*/
     if (s == -1) return NULLT; // there is no such node
     y = tagpos2node(s); // transforms the tag position into a node position
     if (!is_ancestor(Par, x, y)) return NULLT; // the next node tagged tag (in preorder) is not within the subtree of x.
@@ -659,14 +660,15 @@ treeNode XMLTree::TaggedDescOrFollOnly(treeNode x,TagType *folltags, unsigned in
 {
 
   treeNode res,y,lim;
-  int r,s;
+  //int r,s;
   lim = find_close(Par,root);   
   res=NULLT;
   for (unsigned int i = 0; i < ftlen; i ++ )
     {
 
-      r = (int) Tags->rank(folltags[i], node2tagpos(x));
-      s = (int) Tags->select(folltags[i], r+1);
+			int s = (int) Tags->select_next(folltags[i],node2tagpos(x));
+      /*r = (int) Tags->rank(folltags[i], node2tagpos(x));
+      s = (int) Tags->select(folltags[i], r+1);*/
       if (s == -1) 
 	y = NULLT; // there is no such node
       else {
@@ -762,12 +764,13 @@ treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)
        exit(1);
     }
 
-    int r, s;
+    //int r, s;
     if (x ==NULLT || x == Root())
        return NULLT;
-                   
-    r = (int) Tags->rank(tag, find_close(Par, x));
-    s = (int) Tags->select(tag, r+1);  // select returns -1 in case that there is no r+1-th tag.
+     
+		int s = (int) Tags->select_next(tag,find_close(Par,x));
+    /*r = (int) Tags->rank(tag, find_close(Par, x));
+    s = (int) Tags->select(tag, r+1);  // select returns -1 in case that there is no r+1-th tag. */
     if (s==-1) return NULLT;
     else return tagpos2node(s);
  } 
@@ -777,13 +780,14 @@ treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)
 treeNode XMLTree::TaggedFollBelow(treeNode x, TagType tag, treeNode root)
  {
 
-    int r, s;
+    //int r, s;
     int lim = node2tagpos(find_close(Par,root));
     if (x ==NULLT || x == Root())
        return NULLT;
                    
-    r = (int) Tags->rank(tag,find_close(Par,x));
-    s = (int) Tags->select(tag, r+1);  // select returns -1 in case that there is no r+1-th tag.
+		int s = (int) Tags->select_next(tag,find_close(Par,x));
+    /*r = (int) Tags->rank(tag,find_close(Par,x));
+    s = (int) Tags->select(tag, r+1);  // select returns -1 in case that there is no r+1-th tag.*/
     if (s==-1 || s >= lim) 
       return NULLT;
     else 
@@ -800,14 +804,15 @@ treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag)
        exit(1);
     }
 
-    int r, s;
+    //int r, s;
     treeNode ns = next_sibling(Par,x);
 
     if (x == NULLT || x == Root() || ns == -1)
       return NULLT;
 
-    r = (int) Tags->rank(tag, node2tagpos(ns)-1);
-    s = (int) Tags->select(tag, r+1);  // select returns -1 in case that there is no r+1-th tag.
+		int s = (int) Tags->select_next(tag,node2tagpos(ns)-1);
+    /*r = (int) Tags->rank(tag, node2tagpos(ns)-1);
+    s = (int) Tags->select(tag, r+1);  // select returns -1 in case that there is no r+1-th tag.*/
     if (s==-1) return NULLT;
     else return tagpos2node(s);
  }
diff --git a/libcds/src/static_bitsequence/sdarray.cpp b/libcds/src/static_bitsequence/sdarray.cpp
index f904aa3..9e0a8a5 100644
--- a/libcds/src/static_bitsequence/sdarray.cpp
+++ b/libcds/src/static_bitsequence/sdarray.cpp
@@ -39,7 +39,7 @@ int __blog(int x) {
 
 int __setbit(uint *B, int i,int x) {
   int j,l;
-//printf("%u\n",D);
+  //printf("%u\n",D);
   j = i / D;
   l = i % D;
   if (x==0) B[j] &= (~(1<<(D-1-l)));
@@ -177,6 +177,7 @@ void make___selecttbl(void) {
   }
 }
 
+
 unsigned int __popCount(uint x) {
   uint r;
   #if 0
@@ -219,55 +220,59 @@ unsigned int __popCount8(uint x) {
   return r;
 }
 
+
 int selectd2_save(selectd2 * s, FILE * fp) {
-	uint wr = 0;
-	wr += fwrite(&s->n,sizeof(uint),1,fp);
-	wr += fwrite(&s->m,sizeof(uint),1,fp);
-	wr += fwrite(&s->size,sizeof(uint),1,fp);
-	wr += fwrite(&s->ss_len,sizeof(uint),1,fp);
-	wr += fwrite(&s->sl_len,sizeof(uint),1,fp);
-	wr += fwrite(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
-	uint nl = (s->m-1) / L + 1;
-	wr += fwrite(s->lp,sizeof(uint),nl+1,fp);
-	wr += fwrite(s->p,sizeof(uint),nl+1,fp);
-	wr += fwrite(s->ss,sizeof(ushort),s->ss_len,fp);
-	wr += fwrite(s->sl,sizeof(uint),s->sl_len,fp);
-	if(wr!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5) 
-		return 1;
-	return 0;
+  uint wr = 0;
+  wr += fwrite(&s->n,sizeof(uint),1,fp);
+  wr += fwrite(&s->m,sizeof(uint),1,fp);
+  wr += fwrite(&s->size,sizeof(uint),1,fp);
+  wr += fwrite(&s->ss_len,sizeof(uint),1,fp);
+  wr += fwrite(&s->sl_len,sizeof(uint),1,fp);
+  wr += fwrite(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
+  uint nl = (s->m-1) / L + 1;
+  wr += fwrite(s->lp,sizeof(uint),nl+1,fp);
+  wr += fwrite(s->p,sizeof(uint),nl+1,fp);
+  wr += fwrite(s->ss,sizeof(ushort),s->ss_len,fp);
+  wr += fwrite(s->sl,sizeof(uint),s->sl_len,fp);
+  if(wr!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5)
+    return 1;
+  return 0;
 }
 
+
 int selectd2_load(selectd2 * s, FILE * fp) {
-	uint rd = 0;
-	rd += fread(&s->n,sizeof(uint),1,fp);
-	rd += fread(&s->m,sizeof(uint),1,fp);
-	rd += fread(&s->size,sizeof(uint),1,fp);
-	rd += fread(&s->ss_len,sizeof(uint),1,fp);
-	rd += fread(&s->sl_len,sizeof(uint),1,fp);
-	s->buf = new uchar[(s->n+7)/8+1];
-	rd += fread(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
-	uint nl = (s->m-1) / L + 1;
-	s->lp = new uint[nl+1];
-	rd += fread(s->lp,sizeof(uint),nl+1,fp);
-	s->p = new uint[nl+1];
-	rd += fread(s->p,sizeof(uint),nl+1,fp);
-	s->ss = new ushort[s->ss_len];
-	rd += fread(s->ss,sizeof(ushort),s->ss_len,fp);
-	s->sl = new uint[s->sl_len];
-	rd += fread(s->sl,sizeof(uint),s->sl_len,fp);
-	if(rd!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5) 
-		return 1;
-	return 0;
+  uint rd = 0;
+  rd += fread(&s->n,sizeof(uint),1,fp);
+  rd += fread(&s->m,sizeof(uint),1,fp);
+  rd += fread(&s->size,sizeof(uint),1,fp);
+  rd += fread(&s->ss_len,sizeof(uint),1,fp);
+  rd += fread(&s->sl_len,sizeof(uint),1,fp);
+  s->buf = new uchar[(s->n+7)/8+1];
+  rd += fread(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
+  uint nl = (s->m-1) / L + 1;
+  s->lp = new uint[nl+1];
+  rd += fread(s->lp,sizeof(uint),nl+1,fp);
+  s->p = new uint[nl+1];
+  rd += fread(s->p,sizeof(uint),nl+1,fp);
+  s->ss = new ushort[s->ss_len];
+  rd += fread(s->ss,sizeof(ushort),s->ss_len,fp);
+  s->sl = new uint[s->sl_len];
+  rd += fread(s->sl,sizeof(uint),s->sl_len,fp);
+  if(rd!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5)
+    return 1;
+  return 0;
 }
 
+
 void selectd2_free(selectd2 * s) {
-	//delete [] s->buf;
-	delete [] s->lp;
-	delete [] s->p;
-	delete [] s->ss;
-	delete [] s->sl;
+  //delete [] s->buf;
+  delete [] s->lp;
+  delete [] s->p;
+  delete [] s->ss;
+  delete [] s->sl;
 }
 
+
 int selectd2_construct(selectd2 *select, int n, uchar *buf) {
   int i,m;
   int nl;
@@ -301,12 +306,12 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
   }
 
   nl = (m-1) / L + 1;
-  select->size = 0; //ignoring buf, shared with selects3
+  select->size = 0;              //ignoring buf, shared with selects3
   select->lp = new uint[nl+1];
-	for(int k=0;k<nl+1;k++) select->lp[k]=0;
+  for(int k=0;k<nl+1;k++) select->lp[k]=0;
   select->size += (nl+1)*sizeof(uint);
   select->p = new uint[nl+1];
-	for(int k=0;k<nl+1;k++) select->p[k]=0;
+  for(int k=0;k<nl+1;k++) select->p[k]=0;
   select->size += (nl+1)*sizeof(uint);
 
   for (r = 0; r < 2; r++) {
@@ -340,17 +345,17 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
     }
     if (r == 0) {
       select->sl = new uint[ml*L+1];
-			for(int k=0;k<ml*L+1;k++) select->sl[k]=0;
+      for(int k=0;k<ml*L+1;k++) select->sl[k]=0;
       select->size += sizeof(uint)*(ml*L+1);
-			select->sl_len = ml*L+1;
+      select->sl_len = ml*L+1;
       select->ss = new ushort[ms*(L/LLL)+1];
-			for(int k=0;k<ms*(L/LLL)+1;k++) select->ss[k]=0;
-			select->ss_len = ms*(L/LLL)+1;
+      for(int k=0;k<ms*(L/LLL)+1;k++) select->ss[k]=0;
+      select->ss_len = ms*(L/LLL)+1;
       select->size += sizeof(ushort)*(ms*(L/LLL)+1);
     }
   }
   delete [] s;
-	return 0;
+  return 0;
 }
 
 
@@ -530,57 +535,60 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
 
 
 int selects3_save(selects3 * s, FILE * fp) {
-	uint wr = 0;
-	wr += fwrite(&s->n,sizeof(uint),1,fp);
-	wr += fwrite(&s->m,sizeof(uint),1,fp);
-	wr += fwrite(&s->size,sizeof(uint),1,fp);
-        wr += fwrite(&s->d,sizeof(uint),1,fp);
-	wr += fwrite(&s->hi_len,sizeof(uint),1,fp);
-        wr += fwrite(&s->low_len,sizeof(uint),1,fp);
-	wr += fwrite(s->hi,sizeof(uchar),s->hi_len,fp);
-	wr += fwrite(s->low,sizeof(uint),s->low_len,fp);
-	if(wr!=(6+s->hi_len+s->low_len))
-		return 1;
-	if(selectd2_save(s->sd0,fp)) return 2;
-	if(selectd2_save(s->sd1,fp)) return 3;
-	return 0;
+  uint wr = 0;
+  wr += fwrite(&s->n,sizeof(uint),1,fp);
+  wr += fwrite(&s->m,sizeof(uint),1,fp);
+  wr += fwrite(&s->size,sizeof(uint),1,fp);
+  wr += fwrite(&s->d,sizeof(uint),1,fp);
+  wr += fwrite(&s->hi_len,sizeof(uint),1,fp);
+  wr += fwrite(&s->low_len,sizeof(uint),1,fp);
+  wr += fwrite(s->hi,sizeof(uchar),s->hi_len,fp);
+  wr += fwrite(s->low,sizeof(uint),s->low_len,fp);
+  if(wr!=(6+s->hi_len+s->low_len))
+    return 1;
+  if(selectd2_save(s->sd0,fp)) return 2;
+  if(selectd2_save(s->sd1,fp)) return 3;
+  return 0;
 }
 
+
 int selects3_load(selects3 * s, FILE * fp) {
-	uint rd = 0;
-	rd += fread(&s->n,sizeof(uint),1,fp);
-	rd += fread(&s->m,sizeof(uint),1,fp);
-	rd += fread(&s->size,sizeof(uint),1,fp);
-	rd += fread(&s->d,sizeof(uint),1,fp);
-	rd += fread(&s->hi_len,sizeof(uint),1,fp);
-	rd += fread(&s->low_len,sizeof(uint),1,fp);
-	s->hi = new uchar[s->hi_len];
-	rd += fread(s->hi,sizeof(uchar),s->hi_len,fp);
-	s->low = new uint[s->low_len];
-	rd += fread(s->low,sizeof(uint),s->low_len,fp);
-	if(rd!=(6+s->hi_len+s->low_len))
-		return 1;
-	s->sd0 = new selectd2;
-	if(selectd2_load(s->sd0,fp)) return 2;
-	s->sd1 = new selectd2;
-	if(selectd2_load(s->sd1,fp)) return 3;
-	delete [] s->sd0->buf;
-	delete [] s->sd1->buf;
-	s->sd0->buf = s->hi;
-	s->sd1->buf = s->hi;
-	return 0;
+  uint rd = 0;
+  rd += fread(&s->n,sizeof(uint),1,fp);
+  rd += fread(&s->m,sizeof(uint),1,fp);
+  rd += fread(&s->size,sizeof(uint),1,fp);
+  rd += fread(&s->d,sizeof(uint),1,fp);
+  rd += fread(&s->hi_len,sizeof(uint),1,fp);
+  rd += fread(&s->low_len,sizeof(uint),1,fp);
+  s->hi = new uchar[s->hi_len];
+  rd += fread(s->hi,sizeof(uchar),s->hi_len,fp);
+  s->low = new uint[s->low_len];
+  rd += fread(s->low,sizeof(uint),s->low_len,fp);
+  if(rd!=(6+s->hi_len+s->low_len))
+    return 1;
+  s->sd0 = new selectd2;
+  if(selectd2_load(s->sd0,fp)) return 2;
+  s->sd1 = new selectd2;
+  if(selectd2_load(s->sd1,fp)) return 3;
+  delete [] s->sd0->buf;
+  delete [] s->sd1->buf;
+  s->sd0->buf = s->hi;
+  s->sd1->buf = s->hi;
+  return 0;
 }
 
+
 void selects3_free(selects3 * s) {
-	delete [] s->hi;
-	delete [] s->low;
-	//delete [] s->sd0->buf;
-	selectd2_free(s->sd0);
-	delete s->sd0;
-	selectd2_free(s->sd1);
-	delete s->sd1;
+  delete [] s->hi;
+  delete [] s->low;
+  //delete [] s->sd0->buf;
+  selectd2_free(s->sd0);
+  delete s->sd0;
+  selectd2_free(s->sd1);
+  delete s->sd1;
 }
 
+
 int selects3_construct(selects3 *select, int n, uint *buf) {
   int i,m;
   int d,mm;
@@ -605,11 +613,11 @@ int selects3_construct(selects3 *select, int n, uint *buf) {
   select->d = d;
 
   buf2 = new uchar[(2*m+8-1)/8+1];
-	for(int k=0;k<(2*m+8-1)/8+1;k++) buf2[k]=0;
-	select->hi_len = (2*m+8-1)/8+1;
+  for(int k=0;k<(2*m+8-1)/8+1;k++) buf2[k]=0;
+  select->hi_len = (2*m+8-1)/8+1;
   low = new uint[(d*m+PBS-1)/PBS+1];
-	for(uint k=0;k<(d*m+PBS-1)/PBS+1;k++) low[k]=0;
-	select->low_len = (d*m+PBS-1)/PBS+1;
+  for(uint k=0;k<(d*m+PBS-1)/PBS+1;k++) low[k]=0;
+  select->low_len = (d*m+PBS-1)/PBS+1;
 
   select->hi = buf2;
   select->low = low;
@@ -638,14 +646,14 @@ int selects3_construct(selects3 *select, int n, uint *buf) {
   select->sd0 = sd0;
 
   for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
-	return 0;
+  return 0;
 }
 
 
 int selects3_select(selects3 *select, int i) {
   int d,x;
 
-  #if 1
+  #if 0
   if (i > select->m) {
     printf("ERROR: m=%d i=%d\n",select->m,i);
     exit(1);
@@ -663,6 +671,82 @@ int selects3_select(selects3 *select, int i) {
 
 }
 
+
+int selects3_selectnext(selects3 *select, int i) {
+  int d,x,w,y;
+  int r,j;
+  int z,ii;
+  uint *q;
+
+  d = select->d;
+  q = select->low;
+
+  ii = i>>d;
+  y = selectd2_select(select->sd0,ii,0)+1;
+	int k2=y-ii;
+  //  selectd2_select2(select->sd0,ii,0,&y1,&y2);
+  //y1++;  y2++;
+  //printf("y %d y1 %d  %d\n",y,y1,y2-y1);
+
+  x = y - ii;
+	int x_orig = x;
+
+  j = i - (ii<<d);
+
+  r = y & 7;
+  y >>= 3;
+  z = select->hi[y];
+  while (1) {
+    if (((z << r) & 0x80) == 0) {
+			//if(!__getbit2(select->hi,(8*y+r))) k2++;
+			if(x!=x_orig) k2++;
+			//cout << "??? i=" << i << " bit=" << __getbit2(select->hi,(8*y+r)) << " minirank=" << minirank << endl;
+			break;
+		}
+    w = __getbits(q,x*d,d);
+    if (w >= j) {
+      if (w == j) {
+				if(__getbit2(select->hi,(8*y+r))) k2++;
+				x++;
+				r++;
+			}
+      break;
+    }
+    x++;
+    r++;
+		if(__getbit2(select->hi,(8*y+r))) k2++;
+    if (r == 8) {
+      r = 0;
+      y++;
+      z = select->hi[y];
+    }
+  }
+
+	if(x==select->m)
+		return (uint)-1;
+
+	/*if(i==0) {
+		for(int kk=0;kk<40;kk++)
+			cout << ((__getbit2(select->hi,kk))?1:0);
+		cout << endl;
+	}*/
+	int c=8*y+r;//-k2;//+x-r;//x-r;//+r;//-x;
+	while(!__getbit2(select->hi,c)) c++;
+	c -= (k2);
+	//cout << "i=" << i << " y=" << y << " r=" << r << " x=" << x << " k2=" << k2 << " ii=" << ii << " s2=" <<  selectd2_select(select->sd0,ii,0)+1 
+	//	<< " j=" << j << " c=" << c << endl;
+	//while(__getbit2(select->hi,c)==0) c++;
+	//c+=ii-r+x;
+	//if(i==601) c=2;
+	//cout << "c=" << c << " (c<<d)=" << (c<<d) << endl;
+	/*while(select->hi[y]==0) y++;
+	int c = 8*y;
+	z = select->hi[y];
+	while(__getbit((uint*)&z,i++)==0) c++;*/
+
+  return __getbits(q,x*d,d)+((c)<<d);
+}
+
 int selects3_rank(selects3 *select, int i) {
   int d,x,w,y;
   int r,j;
@@ -701,5 +785,6 @@ int selects3_rank(selects3 *select, int i) {
     }
   }
 
-  return x;
+	return x;
 }
+
diff --git a/libcds/src/static_bitsequence/sdarray.h b/libcds/src/static_bitsequence/sdarray.h
index 0eb7ee7..f908fbe 100644
--- a/libcds/src/static_bitsequence/sdarray.h
+++ b/libcds/src/static_bitsequence/sdarray.h
@@ -32,6 +32,7 @@ typedef struct {
 int selects3_construct(selects3 *select, int n, uint *buf);
 int selects3_select(selects3 *select, int i);
 int selects3_rank(selects3 *select, int i);
+int selects3_selectnext(selects3 *select, int i);
 
 void make___selecttbl(void);
 int __setbit(uint *B, int i,int x);
diff --git a/libcds/src/static_bitsequence/static_bitsequence.cpp b/libcds/src/static_bitsequence/static_bitsequence.cpp
index e4740ea..ad07b84 100644
--- a/libcds/src/static_bitsequence/static_bitsequence.cpp
+++ b/libcds/src/static_bitsequence/static_bitsequence.cpp
@@ -78,6 +78,14 @@ uint static_bitsequence::select1(uint i) {
 	return ini;
 }
 
+uint static_bitsequence::select_next1(uint i) {
+	return select1(rank1(i)+1);
+}
+
+uint static_bitsequence::select_next0(uint i) {
+	return select0(rank0(i)+1);
+}
+
 bool static_bitsequence::access(uint i) {
   return (rank1(i)-(i!=0?rank1(i-1):0))>0;
 }
diff --git a/libcds/src/static_bitsequence/static_bitsequence.h b/libcds/src/static_bitsequence/static_bitsequence.h
index 4b6e83a..b150974 100644
--- a/libcds/src/static_bitsequence/static_bitsequence.h
+++ b/libcds/src/static_bitsequence/static_bitsequence.h
@@ -58,6 +58,9 @@ public:
 	 * @return (uint)-1 if i=0, len if i>num_ones or the position */
   virtual uint select1(uint i);
 
+	virtual uint select_next1(uint i);
+	virtual uint select_next0(uint i);
+
 	/** Returns the i-th bit */
   virtual bool access(uint i);
 
diff --git a/libcds/src/static_bitsequence/static_bitsequence_sdarray.cpp b/libcds/src/static_bitsequence/static_bitsequence_sdarray.cpp
index 0b0dab1..6fc1989 100644
--- a/libcds/src/static_bitsequence/static_bitsequence_sdarray.cpp
+++ b/libcds/src/static_bitsequence/static_bitsequence_sdarray.cpp
@@ -2,70 +2,80 @@
 #include <static_bitsequence_sdarray.h>
 
 static_bitsequence_sdarray::static_bitsequence_sdarray(uint * buff, uint len) {
-	uint * tmp_seq = new uint[uint_len(len,1)+1];
-	ones = 0;
-	for(uint i=0;i<uint_len(len,1)+1;i++)
-		tmp_seq[i] = 0;
-	for(uint i=0;i<len;i++)
-		if(bitget(buff,i)) {
-			__setbit(tmp_seq,i,1);
-			ones++;
-		}
-	if(ones)
-		selects3_construct(&sd,len,tmp_seq);
-	this->len = len;
-	//this->ones = sd.m;
-	delete [] tmp_seq;
+  uint * tmp_seq = new uint[uint_len(len,1)+1];
+  ones = 0;
+  for(uint i=0;i<uint_len(len,1)+1;i++)
+    tmp_seq[i] = 0;
+  for(uint i=0;i<len;i++)
+  if(bitget(buff,i)) {
+    __setbit(tmp_seq,i,1);
+    ones++;
+  }
+  if(ones)
+    selects3_construct(&sd,len,tmp_seq);
+  this->len = len;
+  //this->ones = sd.m;
+  delete [] tmp_seq;
 }
 
+
 static_bitsequence_sdarray::static_bitsequence_sdarray() {make___selecttbl();}
 
 static_bitsequence_sdarray::~static_bitsequence_sdarray() {
-	if(ones)
-		selects3_free(&sd);
+  if(ones)
+    selects3_free(&sd);
 }
 
+
 uint static_bitsequence_sdarray::rank1(uint i) {
-	if(i>=len) return -1;
-	if(ones)
-		return selects3_rank(&sd,i);
-	else
-		return 0;
+  if(i>=len) return -1;
+  if(ones)
+    return selects3_rank(&sd,i);
+  else
+    return 0;
 }
 
+
 uint static_bitsequence_sdarray::select1(uint i) {
-	if(i>ones || i==0) return -1;
-	if(ones)
-		return selects3_select(&sd,i);
-	else
-		return (uint)-1;
+  if(i>ones || i==0) return -1;
+  if(ones)
+    return selects3_select(&sd,i);
+  else
+    return (uint)-1;
+}
+
+
+uint static_bitsequence_sdarray::select_next1(uint i) {
+  return selects3_selectnext(&sd,i);
 }
 
+
 uint static_bitsequence_sdarray::size() {
-	return sizeof(static_bitsequence_sdarray)+(ones?(sd.size + sd.sd0->size + sd.sd1->size):0);
+  return sizeof(static_bitsequence_sdarray)+(ones?(sd.size + sd.sd0->size + sd.sd1->size):0);
 }
 
+
 int static_bitsequence_sdarray::save(FILE * fp) {
-	uint wr = SDARRAY_HDR;
-	wr = fwrite(&wr,sizeof(uint),1,fp);
-	wr += fwrite(&len,sizeof(uint),1,fp);
-	wr += fwrite(&ones,sizeof(uint),1,fp);
-	if(wr!=3 || (ones?(selects3_save(&sd,fp)):false))
-		return 1;
-	return 0;
+  uint wr = SDARRAY_HDR;
+  wr = fwrite(&wr,sizeof(uint),1,fp);
+  wr += fwrite(&len,sizeof(uint),1,fp);
+  wr += fwrite(&ones,sizeof(uint),1,fp);
+  if(wr!=3 || (ones?(selects3_save(&sd,fp)):false))
+    return 1;
+  return 0;
 }
 
+
 static_bitsequence_sdarray * static_bitsequence_sdarray::load(FILE * fp) {
-	uint id;
-	if(fread(&id,sizeof(uint),1,fp)!=1) return NULL;
-	if(id!=SDARRAY_HDR) return NULL;
-	static_bitsequence_sdarray * ret = new static_bitsequence_sdarray();
-	id = fread(&ret->len,sizeof(uint),1,fp);
-	id += fread(&ret->ones,sizeof(uint),1,fp);
-	if(ret->ones && selects3_load(&ret->sd,fp)) {
-		delete ret;
-		return NULL;
-	}
-	return ret;
+  uint id;
+  if(fread(&id,sizeof(uint),1,fp)!=1) return NULL;
+  if(id!=SDARRAY_HDR) return NULL;
+  static_bitsequence_sdarray * ret = new static_bitsequence_sdarray();
+  id = fread(&ret->len,sizeof(uint),1,fp);
+  id += fread(&ret->ones,sizeof(uint),1,fp);
+  if(ret->ones && selects3_load(&ret->sd,fp)) {
+    delete ret;
+    return NULL;
+  }
+  return ret;
 }
-
diff --git a/libcds/src/static_bitsequence/static_bitsequence_sdarray.h b/libcds/src/static_bitsequence/static_bitsequence_sdarray.h
index 6dc23d5..54ab29a 100644
--- a/libcds/src/static_bitsequence/static_bitsequence_sdarray.h
+++ b/libcds/src/static_bitsequence/static_bitsequence_sdarray.h
@@ -12,6 +12,7 @@ class static_bitsequence_sdarray: public static_bitsequence {
 		virtual ~static_bitsequence_sdarray();
 		virtual uint select1(uint i);
 		virtual uint rank1(uint i);
+		virtual uint select_next1(uint i);
 		virtual uint size();
 		virtual int save(FILE * fp);
 		static static_bitsequence_sdarray * load(FILE * fp);
diff --git a/libcds/src/static_sequence/static_sequence.cpp b/libcds/src/static_sequence/static_sequence.cpp
index 71622fb..9e8c0e4 100644
--- a/libcds/src/static_sequence/static_sequence.cpp
+++ b/libcds/src/static_sequence/static_sequence.cpp
@@ -43,6 +43,10 @@ static_sequence * static_sequence::load(FILE * fp) {
   return NULL;
 }
 
+uint static_sequence::select_next(uint c, uint i) { 
+	return select(c,rank(c,i)+1);
+}
+
 bool static_sequence::test(uint * seq, uint n) {
 	uint sigma = 0;
 	for(uint i=0;i<n;i++)
diff --git a/libcds/src/static_sequence/static_sequence.h b/libcds/src/static_sequence/static_sequence.h
index baff3f1..4fa5da4 100644
--- a/libcds/src/static_sequence/static_sequence.h
+++ b/libcds/src/static_sequence/static_sequence.h
@@ -57,6 +57,7 @@ public:
   /** Returns the position of the i-th c 
    * @return (uint)-1 if i=0, len if i exceeds the number of cs */
   virtual uint select(uint c, uint i)=0;
+	virtual uint select_next(uint c, uint i);
 
   /** Returns the i-th element */
   virtual uint access(uint i)=0;
diff --git a/libcds/src/static_sequence/static_sequence_bs.cpp b/libcds/src/static_sequence/static_sequence_bs.cpp
index fecca78..3a4aaa2 100644
--- a/libcds/src/static_sequence/static_sequence_bs.cpp
+++ b/libcds/src/static_sequence/static_sequence_bs.cpp
@@ -50,6 +50,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);
diff --git a/libcds/src/static_sequence/static_sequence_bs.h b/libcds/src/static_sequence/static_sequence_bs.h
index 7161667..76de5ae 100644
--- a/libcds/src/static_sequence/static_sequence_bs.h
+++ b/libcds/src/static_sequence/static_sequence_bs.h
@@ -40,6 +40,7 @@ public:
   virtual uint rank(uint c, uint i);
   
   virtual uint select(uint c, uint i);
+	virtual uint select_next(uint c, uint i);
 
   virtual uint access(uint i);
 
diff --git a/libcds/tests/static_bitsequence_test.cpp b/libcds/tests/static_bitsequence_test.cpp
index 9fc08f0..7c57fe3 100644
--- a/libcds/tests/static_bitsequence_test.cpp
+++ b/libcds/tests/static_bitsequence_test.cpp
@@ -29,7 +29,7 @@ using namespace std;
 
 int main(int argc, char ** argv) {
 	if(argc!=5) {
-		cout << "usage: " << argv[0] << " <bitmap_file> <b|r> <sample_rate> <t|s>" << endl;
+		cout << "usage: " << argv[0] << " <bitmap_file> <b|r|s> <sample_rate> <t|s>" << endl;
 		return 0;
 	}
 	FILE * fp = fopen(argv[1],"r");
@@ -51,11 +51,20 @@ int main(int argc, char ** argv) {
 	static_bitsequence * bs;
   
   if(string(argv[2])==string("r")) bs = new static_bitsequence_rrr02(bitseq,len,sample_rate);
+  if(string(argv[2])==string("s")) bs = new static_bitsequence_sdarray(bitseq,len);
   else bs = new static_bitsequence_brw32(bitseq,len,sample_rate);
 	
   cout << "Size: " << bs->size() << endl;
   cout << "bpb = " << bs->size()*8./len << endl;
   
+	/*for(uint kk=0;kk<30;kk++)
+		cout << bs->access(kk);
+	cout << endl;*/
+
+	/*for(uint kk=0;kk<20;kk++) {
+		bs->select_next1(kk);
+	}*/
+
 	if(string(argv[4])==string("t"))
 	  test_bitsequence(bitseq,len,bs);
   cout << "******************************************" << endl;
@@ -68,4 +77,6 @@ int main(int argc, char ** argv) {
   speed_select0(bs, bitseq, len);
   cout << "******************************************" << endl;
   speed_select1(bs, bitseq, len);
+  cout << "******************************************" << endl;
+  speed_selectnext1(bs, bitseq, len);
 }
diff --git a/libcds/tests/static_bitsequence_tester.cpp b/libcds/tests/static_bitsequence_tester.cpp
index bd801ed..509107d 100644
--- a/libcds/tests/static_bitsequence_tester.cpp
+++ b/libcds/tests/static_bitsequence_tester.cpp
@@ -65,6 +65,7 @@ void load(char *fname, uint ** text, uint * n) {
 
 void test_bitsequence(uint * bitseq, uint len, static_bitsequence * bs) {
   uint ones = 0;
+	uint last_one = 0;
   bool error = false;
   for(uint i=0;i<len && !error;i++) {
     //cout << "i="<<i<< endl;
@@ -72,7 +73,20 @@ void test_bitsequence(uint * bitseq, uint len, static_bitsequence * bs) {
       if(i%max((uint)1,(bs->length()/100))==0) { cout << "."; cout.flush(); }
       if(i%max((uint)1,(bs->length()/10))==0) { cout << endl; cout.flush(); }
     }
-    if(bitget(bitseq,i)) ones++;
+    if(bitget(bitseq,i)) {
+			for(uint k=last_one; !error && k<i;k++) {
+				if(bs->select_next1(k)!=i) {
+					uint ans= bs->select_next1(k);
+					cout << "Error select_next1" << endl;
+					cout << " got: (k=" << k << ") " << ans << " expected: " << i << endl;
+					cout << " rank(" << k << ")=" << bs->rank1(k) << " access(" << k << ")=" << bs->access(k) << endl;
+					cout << " rank(" << ans << ")=" << bs->rank1(ans) << " access(" << ans << ")=" << bs->access(ans) << endl;
+					error = true;
+				}
+			}
+			last_one = i;
+			ones++;
+		}
     if(bs->access(i) != (bitget(bitseq,i)!=0)) {
       cout << "Access error for position " << i << endl;
       cout << " got: " << bs->access(i) << " expected: " << (bitget(bitseq,i)!=0) << endl;
@@ -178,3 +192,18 @@ void speed_select1(static_bitsequence * ss, uint * bitseq, uint n) {
   cout << " * Time per select1: " << 1000*t/NQUERIES << " msecs" << endl;
   cout << " - Check sum: " << acc << endl;
 }
+
+void speed_selectnext1(static_bitsequence * ss, uint * bitseq, uint n) {
+  uint acc=0;
+  srand(SEED);
+
+  start_clock();
+  for(uint i=0;i<NQUERIES;i++) {
+    uint pos = rand()%n;
+    acc += ss->select_next1(pos);
+  }
+  double t = stop_clock();
+  cout << " * Time for " << NQUERIES << " select_next1s: " << t << " secs" << endl;
+  cout << " * Time per select_next1: " << 1000*t/NQUERIES << " msecs" << endl;
+  cout << " - Check sum: " << acc << endl;
+}
diff --git a/libcds/tests/static_bitsequence_tester.h b/libcds/tests/static_bitsequence_tester.h
index d7120b6..c5de5cf 100644
--- a/libcds/tests/static_bitsequence_tester.h
+++ b/libcds/tests/static_bitsequence_tester.h
@@ -39,5 +39,6 @@ void speed_rank0(static_bitsequence * ss, uint * bitseq, uint n);
 void speed_rank1(static_bitsequence * ss, uint * bitseq, uint n);
 void speed_select0(static_bitsequence * ss, uint * bitseq, uint n);
 void speed_select1(static_bitsequence * ss, uint * bitseq, uint n);
+void speed_selectnext1(static_bitsequence * ss, uint * bitseq, uint n);
 
 #endif
-- 
2.17.1