return 0;
}
+//selects3 * lasts3=NULL;
+//int lasti=0;
+//int lasts=0;
int selects3_select(selects3 *select, int i) {
int d,x;
if (i == 0) return -1;
d = select->d;
-
- x = selectd2_select(select->sd1,i,1) - (i-1);
+ /*if(select->lasti==(uint)i-1) {
+ while(!__getbit2(select->sd1->buf,++select->lasts));
+ }
+ else {
+ select->lasts = selectd2_select(select->sd1,i,1);
+ }
+ select->lasti = i;*/
+ //lasts3 = select;
+ x = selectd2_select(select->sd1,i,1) - (i-1);
+ //x = (select->lasts-(i-1)) << d;
x <<= 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);
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);
}