X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_bitsequence%2Fsdarray.cpp;h=28758d36200932ab9e3de41f268efc09a0cda3af;hb=14640e9a1cfbbe8d6669d17d098fcabc3652cd77;hp=9e0a8a59226f6c55ae85865e7c87f7d3f6292505;hpb=935f20b93a3db7cd2f9f39573d4ab434fcc4356a;p=SXSI%2FXMLTree.git

diff --git a/libcds/src/static_bitsequence/sdarray.cpp b/libcds/src/static_bitsequence/sdarray.cpp
index 9e0a8a5..28758d3 100644
--- a/libcds/src/static_bitsequence/sdarray.cpp
+++ b/libcds/src/static_bitsequence/sdarray.cpp
@@ -649,6 +649,9 @@ int selects3_construct(selects3 *select, int n, uint *buf) {
   return 0;
 }
 
+selects3 * lasts3=NULL;
+int lasti=0;
+int lasts=0;
 
 int selects3_select(selects3 *select, int i) {
   int d,x;
@@ -663,44 +666,40 @@ int selects3_select(selects3 *select, int i) {
   if (i == 0) return -1;
 
   d = select->d;
-
-  x = selectd2_select(select->sd1,i,1) - (i-1);
-  x <<= d;
+	if(lasts3==select && lasti==i) {
+		while(!__getbit2(select->sd1->buf,++lasti));
+	} 
+	else {
+	  lasts = selectd2_select(select->sd1,i,1);
+	}
+	lasti = i;
+	lasts3 = select;
+  x = (lasts-(i-1)) << d;
   x += __getbits(select->low,(i-1)*d,d);
   return x;
-
 }
 
 
 int selects3_selectnext(selects3 *select, int i) {
+	return selects3_select(select,selects3_rank(select,i)+1);
   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);
@@ -721,29 +720,26 @@ int selects3_selectnext(selects3 *select, int i) {
       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++;
+	int c=8*y+r;
+	int fin=0;
+	for(int kk=0;kk<8-r;kk++) {
+		if(__getbit2(select->hi,c)) {
+			fin=1;
+			break;
+		}
+		c++;
+	}
+	if(!fin) {
+		int pp = c/8;
+		while(select->hi[pp]==0) {
+			pp++;
+			c+=8;
+		}
+		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);
 }