libcds/src/static_bitsequence/sdarray.cpp

   1
   2 #include <sdarray.h>
   3
   4 #if 0
   5 typedef unsigned int qword;
   6 #define logD 4
   7 #else
   8 typedef unsigned long long qword;
   9 #define logD 5
  10 #endif
  11 #define PBS (sizeof(uint)*8)
  12 #define D (1<<logD)
  13 #define logM 5
  14 #define M (1<<logM)
  15 #define logP 8
  16 #define P (1<<logP)
  17 #define logLL 16                 // size of word
  18 #define LL (1<<logLL)
  19 //#define logLLL 7
  20 #define logLLL 5
  21 //#define LLL 128
  22 //#define LLL 32
  23 #define LLL (1<<logLLL)
  24 //#define logL 10
  25 //#define logL (logLL-3)
  26 #define logL (logLL-1-5)
  27 #define L (1<<logL)
  28
  29 int __blog(int x) {
  30   int l;
  31   l = 0;
  32   while (x>0) {
  33     x>>=1;
  34     l++;
  35   }
  36   return l;
  37 }
  38
  39
  40 int __setbit(uint *B, int i,int x) {
  41   int j,l;
  42   //printf("%u\n",D);
  43   j = i / D;
  44   l = i % D;
  45   if (x==0) B[j] &= (~(1<<(D-1-l)));
  46   else if (x==1) B[j] |= (1<<(D-1-l));
  47   else {
  48     printf("error __setbit x=%d\n",x);
  49     exit(1);
  50   }
  51   return x;
  52 }
  53
  54
  55 int __setbit2(uchar *B, int i,int x) {
  56   int j,l;
  57
  58   j = i / 8;
  59   l = i % 8;
  60   if (x==0) B[j] &= (~(1<<(8-1-l)));
  61   else if (x==1) B[j] |= (1<<(8-1-l));
  62   else {
  63     printf("error __setbit2 x=%d\n",x);
  64     exit(1);
  65   }
  66   return x;
  67 }
  68
  69
  70 int __setbits(uint *B, int i, int d, int x) {
  71   int j;
  72
  73   for (j=0; j<d; j++) {
  74     __setbit(B,i+j,(x>>(d-j-1))&1);
  75   }
  76   return x;
  77 }
  78
  79
  80 int __getbit(uint *B, int i) {
  81   int j,l;
  82
  83   //j = i / D;
  84   //l = i % D;
  85   j = i >> logD;
  86   l = i & (D-1);
  87   return (B[j] >> (D-1-l)) & 1;
  88 }
  89
  90
  91 int __getbit2(uchar *B, int i) {
  92   int j,l;
  93
  94   //j = i / D;
  95   //l = i % D;
  96   j = i >> 3;
  97   l = i & (8-1);
  98   return (B[j] >> (8-1-l)) & 1;
  99 }
 100
 101
 102 #if 1
 103 uint __getbits(uint *B, int i, int d) {
 104   qword x,z;
 105
 106   B += (i >> logD);
 107   i &= (D-1);
 108   if (i+d <= 2*D) {
 109     x = (((qword)B[0]) << D) + B[1];
 110     x <<= i;
 111     x >>= (D*2-1-d);
 112     x >>= 1;
 113   }
 114   else {
 115     x = (((qword)B[0])<<D)+B[1];
 116     z = (x<<D)+B[2];
 117     x <<= i;
 118     x &= (((qword)1L<<D)-1)<<D;
 119     z <<= i;
 120     z >>= D;
 121     x += z;
 122     x >>= (2*D-d);
 123   }
 124
 125   return x;
 126 }
 127 #endif
 128
 129 #if 0
 130 uint __getbits(uint *B, int i, int d) {
 131   uint j,x;
 132
 133   x = 0;
 134   for (j=0; j<d; j++) {
 135     x <<= 1;
 136     x += __getbit(B,i+j);
 137   }
 138   return x;
 139 }
 140 #endif
 141
 142 static const unsigned int _popCount[] = {
 143   0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
 144   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
 145   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
 146   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 147   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
 148   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 149   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 150   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 151   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
 152   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 153   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 154   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 155   2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 156   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 157   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 158   4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
 159 };
 160
 161 static unsigned int __selecttbl[8*256];
 162
 163 void make___selecttbl(void) {
 164   int i,x,r;
 165   uint buf[1];
 166
 167   for (x = 0; x < 256; x++) {
 168     __setbits(buf,0,8,x);
 169     for (r=0; r<8; r++) __selecttbl[(r<<8)+x] = -1;
 170     r = 0;
 171     for (i=0; i<8; i++) {
 172       if (__getbit(buf,i)) {
 173         __selecttbl[(r<<8)+x] = i;
 174         r++;
 175       }
 176     }
 177   }
 178 }
 179
 180
 181 unsigned int __popCount(uint x) {
 182   uint r;
 183   #if 0
 184   r = x;
 185   r = r - ((r>>1) & 0x77777777) - ((r>>2) & 0x33333333) - ((r>>3) & 0x11111111);
 186   r = ((r + (r>>4)) & 0x0f0f0f0f) % 0xff;
 187   #elif 1
 188   r = x;
 189   r = ((r & 0xaaaaaaaa)>>1) + (r & 0x55555555);
 190   r = ((r & 0xcccccccc)>>2) + (r & 0x33333333);
 191   //r = ((r & 0xf0f0f0f0)>>4) + (r & 0x0f0f0f0f);
 192   r = ((r>>4) + r) & 0x0f0f0f0f;
 193   //r = ((r & 0xff00ff00)>>8) + (r & 0x00ff00ff);
 194   r = (r>>8) + r;
 195   //r = ((r & 0xffff0000)>>16) + (r & 0x0000ffff);
 196   r = ((r>>16) + r) & 63;
 197   #else
 198   r = _popCount[x & 0xff];
 199   x >>= 8;
 200   r += _popCount[x & 0xff];
 201   x >>= 8;
 202   r += _popCount[x & 0xff];
 203   x >>= 8;
 204   r += _popCount[x & 0xff];
 205   #endif
 206   return r;
 207 }
 208
 209
 210 unsigned int __popCount8(uint x) {
 211   uint r;
 212   #if 1
 213   r = x;
 214   r = ((r & 0xaa)>>1) + (r & 0x55);
 215   r = ((r & 0xcc)>>2) + (r & 0x33);
 216   r = ((r>>4) + r) & 0x0f;
 217   #else
 218   r = _popCount[x & 0xff];
 219   #endif
 220   return r;
 221 }
 222
 223
 224 int selectd2_save(selectd2 * s, FILE * fp) {
 225   uint wr = 0;
 226   wr += fwrite(&s->n,sizeof(uint),1,fp);
 227   wr += fwrite(&s->m,sizeof(uint),1,fp);
 228   wr += fwrite(&s->size,sizeof(uint),1,fp);
 229   wr += fwrite(&s->ss_len,sizeof(uint),1,fp);
 230   wr += fwrite(&s->sl_len,sizeof(uint),1,fp);
 231   wr += fwrite(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
 232   uint nl = (s->m-1) / L + 1;
 233   wr += fwrite(s->lp,sizeof(uint),nl+1,fp);
 234   wr += fwrite(s->p,sizeof(uint),nl+1,fp);
 235   wr += fwrite(s->ss,sizeof(ushort),s->ss_len,fp);
 236   wr += fwrite(s->sl,sizeof(uint),s->sl_len,fp);
 237   if(wr!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5)
 238     return 1;
 239   return 0;
 240 }
 241
 242
 243 int selectd2_load(selectd2 * s, FILE * fp) {
 244   uint rd = 0;
 245   rd += fread(&s->n,sizeof(uint),1,fp);
 246   rd += fread(&s->m,sizeof(uint),1,fp);
 247   rd += fread(&s->size,sizeof(uint),1,fp);
 248   rd += fread(&s->ss_len,sizeof(uint),1,fp);
 249   rd += fread(&s->sl_len,sizeof(uint),1,fp);
 250   s->buf = new uchar[(s->n+7)/8+1];
 251   rd += fread(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
 252   uint nl = (s->m-1) / L + 1;
 253   s->lp = new uint[nl+1];
 254   rd += fread(s->lp,sizeof(uint),nl+1,fp);
 255   s->p = new uint[nl+1];
 256   rd += fread(s->p,sizeof(uint),nl+1,fp);
 257   s->ss = new ushort[s->ss_len];
 258   rd += fread(s->ss,sizeof(ushort),s->ss_len,fp);
 259   s->sl = new uint[s->sl_len];
 260   rd += fread(s->sl,sizeof(uint),s->sl_len,fp);
 261   if(rd!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5)
 262     return 1;
 263   return 0;
 264 }
 265
 266
 267 void selectd2_free(selectd2 * s) {
 268   //delete [] s->buf;
 269   delete [] s->lp;
 270   delete [] s->p;
 271   delete [] s->ss;
 272   delete [] s->sl;
 273 }
 274
 275
 276 int selectd2_construct(selectd2 *select, int n, uchar *buf) {
 277   int i,m;
 278   int nl;
 279   int p,pp;
 280   int il,is,ml,ms;
 281   int r;
 282   uint *s;
 283
 284   make___selecttbl();
 285
 286   if (L/LLL == 0) {
 287     printf("ERROR: L=%d LLL=%d\n",L,LLL);
 288     exit(1);
 289   }
 290
 291   m = 0;
 292   for (i=0; i<n; i++) m += __getbit2(buf,i);
 293   select->n = n;
 294   select->m = m;
 295   //printf("n=%d m=%d\n",n,m);
 296
 297   select->buf = buf;
 298
 299   s = new uint[m];
 300   m = 0;
 301   for (i=0; i<n; i++) {
 302     if (__getbit2(buf,i)) {
 303       m++;
 304       s[m-1] = i;
 305     }
 306   }
 307
 308   nl = (m-1) / L + 1;
 309   select->size = 0;              //ignoring buf, shared with selects3
 310   select->lp = new uint[nl+1];
 311   for(int k=0;k<nl+1;k++) select->lp[k]=0;
 312   select->size += (nl+1)*sizeof(uint);
 313   select->p = new uint[nl+1];
 314   for(int k=0;k<nl+1;k++) select->p[k]=0;
 315   select->size += (nl+1)*sizeof(uint);
 316
 317   for (r = 0; r < 2; r++) {
 318     ml = ms = 0;
 319     for (il = 0; il < nl; il++) {
 320       pp = s[il*L];
 321       select->lp[il] = pp;
 322       i = min((il+1)*L-1,m-1);
 323       p = s[i];
 324       //printf("%d ",p-pp);
 325       if (p - pp >= LL) {
 326         if (r == 1) {
 327           for (is = 0; is < L; is++) {
 328             if (il*L+is >= m) break;
 329             select->sl[ml*L+is] = s[il*L+is];
 330           }
 331         }
 332         select->p[il] = -((ml<<logL)+1);
 333         ml++;
 334       }
 335       else {
 336         if (r == 1) {
 337           for (is = 0; is < L/LLL; is++) {
 338             if (il*L+is*LLL >= m) break;
 339             select->ss[ms*(L/LLL)+is] = s[il*L+is*LLL] - pp;
 340           }
 341         }
 342         select->p[il] = ms << (logL-logLLL);
 343         ms++;
 344       }
 345     }
 346     if (r == 0) {
 347       select->sl = new uint[ml*L+1];
 348       for(int k=0;k<ml*L+1;k++) select->sl[k]=0;
 349       select->size += sizeof(uint)*(ml*L+1);
 350       select->sl_len = ml*L+1;
 351       select->ss = new ushort[ms*(L/LLL)+1];
 352       for(int k=0;k<ms*(L/LLL)+1;k++) select->ss[k]=0;
 353       select->ss_len = ms*(L/LLL)+1;
 354       select->size += sizeof(ushort)*(ms*(L/LLL)+1);
 355     }
 356   }
 357   delete [] s;
 358   return 0;
 359 }
 360
 361
 362 int selectd2_select(selectd2 *select, int i,int f) {
 363   int p,r;
 364   int il;
 365   int rr;
 366   uchar *q;
 367
 368   if (i == 0) return -1;
 369
 370   #if 0
 371   if (i > select->m) {
 372     printf("ERROR: m=%d i=%d\n",select->m,i);
 373     exit(1);
 374   }
 375   #endif
 376
 377   i--;
 378
 379   il = select->p[i>>logL];
 380   if (il < 0) {
 381     il = -il-1;
 382     //p = select->sl[(il<<logL)+(i & (L-1))];
 383     p = select->sl[il+(i & (L-1))];
 384   }
 385   else {
 386     p = select->lp[i>>logL];
 387     //p += select->ss[(il<<(logL-logLLL))+(i & (L-1))/LLL];
 388     p += select->ss[il+((i & (L-1))>>logLLL)];
 389     r = i - (i & (LLL-1));
 390
 391     q = &(select->buf[p>>3]);
 392
 393     if (f == 1) {
 394       rr = p & (8-1);
 395       r -= _popCount[*q >> (8-1-rr)];
 396       //p = p - rr;
 397
 398       while (1) {
 399         rr = _popCount[*q];
 400         if (r + rr >= i) break;
 401         r += rr;
 402         //p += 8;
 403         q++;
 404       }
 405       p = (q - select->buf) << 3;
 406       p += __selecttbl[((i-r-1)<<8)+(*q)];
 407     }
 408     else {
 409       rr = p & (8-1);
 410       r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
 411       //p = p - rr;
 412
 413       while (1) {
 414         rr = _popCount[*q ^ 0xff];
 415         if (r + rr >= i) break;
 416         r += rr;
 417         //p += 8;
 418         q++;
 419       }
 420       p = (q - select->buf) << 3;
 421       p += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 422     }
 423   }
 424   return p;
 425 }
 426
 427
 428 int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
 429   int p,r,p2;
 430   int il;
 431   int rr;
 432   uchar *q;
 433
 434   if (i == 0) {
 435     *st = -1;
 436     return -1;
 437   }
 438
 439   #if 0
 440   if (i > select->m) {
 441     printf("ERROR: m=%d i=%d\n",select->m,i);
 442     exit(1);
 443   }
 444   #endif
 445
 446   i--;
 447
 448   il = select->p[i>>logL];
 449   if (il < 0) {
 450     il = -il-1;
 451     //p = select->sl[(il<<logL)+(i & (L-1))];
 452     p = select->sl[il+(i & (L-1))];
 453
 454     if ((i>>logL) == ((i+1)>>logL)) {
 455       p2 = select->sl[il+((i+1) & (L-1))];
 456     }
 457     else {
 458       p2 = selectd2_select(select,i+2,f);
 459     }
 460   }
 461   else {
 462     p = select->lp[i>>logL];
 463     //p += select->ss[(il<<(logL-logLLL))+(i & (L-1))/LLL];
 464     p += select->ss[il+((i & (L-1))>>logLLL)];
 465     r = i - (i & (LLL-1));
 466
 467     q = &(select->buf[p>>3]);
 468
 469     if (f == 1) {
 470       rr = p & (8-1);
 471       r -= _popCount[*q >> (8-1-rr)];
 472       //p = p - rr;
 473
 474       while (1) {
 475         rr = _popCount[*q];
 476         if (r + rr >= i) break;
 477         r += rr;
 478         //p += 8;
 479         q++;
 480       }
 481       p = (q - select->buf) << 3;
 482       p += __selecttbl[((i-r-1)<<8)+(*q)];
 483
 484       if ((i>>logL) == ((i+1)>>logL)) {
 485         i++;
 486         while (1) {
 487           rr = _popCount[*q];
 488           if (r + rr >= i) break;
 489           r += rr;
 490           q++;
 491         }
 492         p2 = (q - select->buf) << 3;
 493         p2 += __selecttbl[((i-r-1)<<8)+(*q)];
 494       }
 495       else {
 496         p2 = selectd2_select(select,i+2,f);
 497       }
 498
 499     }
 500     else {
 501       rr = p & (8-1);
 502       r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
 503       //p = p - rr;
 504
 505       while (1) {
 506         rr = _popCount[*q ^ 0xff];
 507         if (r + rr >= i) break;
 508         r += rr;
 509         //p += 8;
 510         q++;
 511       }
 512       p = (q - select->buf) << 3;
 513       p += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 514
 515       if ((i>>logL) == ((i+1)>>logL)) {
 516         i++;
 517         while (1) {
 518           rr = _popCount[*q ^ 0xff];
 519           if (r + rr >= i) break;
 520           r += rr;
 521           q++;
 522         }
 523         p2 = (q - select->buf) << 3;
 524         p2 += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 525       }
 526       else {
 527         p2 = selectd2_select(select,i+2,f);
 528       }
 529     }
 530   }
 531   *st = p;
 532   *en = p2;
 533   return p;
 534 }
 535
 536
 537 int selects3_save(selects3 * s, FILE * fp) {
 538   uint wr = 0;
 539   wr += fwrite(&s->n,sizeof(uint),1,fp);
 540   wr += fwrite(&s->m,sizeof(uint),1,fp);
 541   wr += fwrite(&s->size,sizeof(uint),1,fp);
 542   wr += fwrite(&s->d,sizeof(uint),1,fp);
 543   wr += fwrite(&s->hi_len,sizeof(uint),1,fp);
 544   wr += fwrite(&s->low_len,sizeof(uint),1,fp);
 545   wr += fwrite(s->hi,sizeof(uchar),s->hi_len,fp);
 546   wr += fwrite(s->low,sizeof(uint),s->low_len,fp);
 547   if(wr!=(6+s->hi_len+s->low_len))
 548     return 1;
 549   if(selectd2_save(s->sd0,fp)) return 2;
 550   if(selectd2_save(s->sd1,fp)) return 3;
 551   return 0;
 552 }
 553
 554
 555 int selects3_load(selects3 * s, FILE * fp) {
 556   uint rd = 0;
 557   rd += fread(&s->n,sizeof(uint),1,fp);
 558   rd += fread(&s->m,sizeof(uint),1,fp);
 559   rd += fread(&s->size,sizeof(uint),1,fp);
 560   rd += fread(&s->d,sizeof(uint),1,fp);
 561   rd += fread(&s->hi_len,sizeof(uint),1,fp);
 562   rd += fread(&s->low_len,sizeof(uint),1,fp);
 563   s->hi = new uchar[s->hi_len];
 564   rd += fread(s->hi,sizeof(uchar),s->hi_len,fp);
 565   s->low = new uint[s->low_len];
 566   rd += fread(s->low,sizeof(uint),s->low_len,fp);
 567   if(rd!=(6+s->hi_len+s->low_len))
 568     return 1;
 569   s->sd0 = new selectd2;
 570   if(selectd2_load(s->sd0,fp)) return 2;
 571   s->sd1 = new selectd2;
 572   if(selectd2_load(s->sd1,fp)) return 3;
 573   delete [] s->sd0->buf;
 574   delete [] s->sd1->buf;
 575   s->sd0->buf = s->hi;
 576   s->sd1->buf = s->hi;
 577   return 0;
 578 }
 579
 580
 581 void selects3_free(selects3 * s) {
 582   delete [] s->hi;
 583   delete [] s->low;
 584   //delete [] s->sd0->buf;
 585   selectd2_free(s->sd0);
 586   delete s->sd0;
 587   selectd2_free(s->sd1);
 588   delete s->sd1;
 589 }
 590
 591
 592 int selects3_construct(selects3 *select, int n, uint *buf) {
 593   int i,m;
 594   int d,mm;
 595   uint *low;
 596   uchar *buf2;
 597   selectd2 *sd0,*sd1;
 598
 599   m = 0;
 600   for (i=0; i<n; i++) m += __getbit(buf,i);
 601   select->n = n;
 602   select->m = m;
 603
 604   if (m == 0) return 0;
 605
 606   mm = m;
 607   d = 0;
 608   while (mm < n) {
 609     mm <<= 1;
 610     d++;
 611   }
 612
 613   select->d = d;
 614
 615   buf2 = new uchar[(2*m+8-1)/8+1];
 616   for(int k=0;k<(2*m+8-1)/8+1;k++) buf2[k]=0;
 617   select->hi_len = (2*m+8-1)/8+1;
 618   low = new uint[(d*m+PBS-1)/PBS+1];
 619   for(uint k=0;k<(d*m+PBS-1)/PBS+1;k++) low[k]=0;
 620   select->low_len = (d*m+PBS-1)/PBS+1;
 621
 622   select->hi = buf2;
 623   select->low = low;
 624   select->size = sizeof(uchar)*((2*m+8-1)/8+1) + sizeof(uint)*((d*m+PBS-1)/PBS+1);
 625
 626   for (i=0; i<m*2; i++) __setbit2(buf2,i,0);
 627
 628   m = 0;
 629   for (i=0; i<n; i++) {
 630     if (__getbit(buf,i)) {
 631       __setbit2(buf2,(i>>d)+m,1);
 632       __setbits(low,m*d,d,i & ((1<<d)-1));
 633       m++;
 634     }
 635   }
 636
 637   sd1 = new selectd2;
 638   sd0 = new selectd2;
 639   select->size += 2*sizeof(selectd2);
 640
 641   selectd2_construct(sd1,m*2,buf2);
 642   select->sd1 = sd1;
 643
 644   for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
 645   selectd2_construct(sd0,m*2,buf2);
 646   select->sd0 = sd0;
 647
 648   for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
 649   return 0;
 650 }
 651
 652
 653 int selects3_select(selects3 *select, int i) {
 654   int d,x;
 655
 656   #if 0
 657   if (i > select->m) {
 658     printf("ERROR: m=%d i=%d\n",select->m,i);
 659     exit(1);
 660   }
 661   #endif
 662
 663   if (i == 0) return -1;
 664
 665   d = select->d;
 666
 667   x = selectd2_select(select->sd1,i,1) - (i-1);
 668   x <<= d;
 669   x += __getbits(select->low,(i-1)*d,d);
 670   return x;
 671
 672 }
 673
 674
 675 int selects3_selectnext(selects3 *select, int i) {
 676   int d,x,w,y;
 677   int r,j;
 678   int z,ii;
 679   uint *q;
 680
 681   d = select->d;
 682   q = select->low;
 683
 684   ii = i>>d;
 685   y = selectd2_select(select->sd0,ii,0)+1;
 686         int k2=y-ii;
 687   //  selectd2_select2(select->sd0,ii,0,&y1,&y2);
 688   //y1++;  y2++;
 689   //printf("y %d y1 %d  %d\n",y,y1,y2-y1);
 690
 691   x = y - ii;
 692         int x_orig = x;
 693
 694   j = i - (ii<<d);
 695
 696   r = y & 7;
 697   y >>= 3;
 698   z = select->hi[y];
 699   while (1) {
 700     if (((z << r) & 0x80) == 0) {
 701                         //if(!__getbit2(select->hi,(8*y+r))) k2++;
 702                         if(x!=x_orig) k2++;
 703                         //cout << "??? i=" << i << " bit=" << __getbit2(select->hi,(8*y+r)) << " minirank=" << minirank << endl;
 704                         break;
 705                 }
 706     w = __getbits(q,x*d,d);
 707     if (w >= j) {
 708       if (w == j) {
 709                                 if(__getbit2(select->hi,(8*y+r))) k2++;
 710                                 x++;
 711                                 r++;
 712                         }
 713       break;
 714     }
 715     x++;
 716     r++;
 717                 if(__getbit2(select->hi,(8*y+r))) k2++;
 718     if (r == 8) {
 719       r = 0;
 720       y++;
 721       z = select->hi[y];
 722     }
 723   }
 724
 725         if(x==select->m)
 726                 return (uint)-1;
 727
 728         /*if(i==0) {
 729                 for(int kk=0;kk<40;kk++)
 730                         cout << ((__getbit2(select->hi,kk))?1:0);
 731                 cout << endl;
 732         }*/
 733         int c=8*y+r;//-k2;//+x-r;//x-r;//+r;//-x;
 734         while(!__getbit2(select->hi,c)) c++;
 735         c -= (k2);
 736         //cout << "i=" << i << " y=" << y << " r=" << r << " x=" << x << " k2=" << k2 << " ii=" << ii << " s2=" <<  selectd2_select(select->sd0,ii,0)+1
 737         //      << " j=" << j << " c=" << c << endl;
 738         //while(__getbit2(select->hi,c)==0) c++;
 739         //c+=ii-r+x;
 740         //if(i==601) c=2;
 741         //cout << "c=" << c << " (c<<d)=" << (c<<d) << endl;
 742         /*while(select->hi[y]==0) y++;
 743         int c = 8*y;
 744         z = select->hi[y];
 745         while(__getbit((uint*)&z,i++)==0) c++;*/
 746
 747   return __getbits(q,x*d,d)+((c)<<d);
 748 }
 749
 750 int selects3_rank(selects3 *select, int i) {
 751   int d,x,w,y;
 752   int r,j;
 753   int z,ii;
 754   uint *q;
 755
 756   d = select->d;
 757   q = select->low;
 758
 759   ii = i>>d;
 760   y = selectd2_select(select->sd0,ii,0)+1;
 761   //  selectd2_select2(select->sd0,ii,0,&y1,&y2);
 762   //y1++;  y2++;
 763   //printf("y %d y1 %d  %d\n",y,y1,y2-y1);
 764
 765   x = y - ii;
 766
 767   j = i - (ii<<d);
 768
 769   r = y & 7;
 770   y >>= 3;
 771   z = select->hi[y];
 772   while (1) {
 773     if (((z << r) & 0x80) == 0) break;
 774     w = __getbits(q,x*d,d);
 775     if (w >= j) {
 776       if (w == j) x++;
 777       break;
 778     }
 779     x++;
 780     r++;
 781     if (r == 8) {
 782       r = 0;
 783       y++;
 784       z = select->hi[y];
 785     }
 786   }
 787
 788         return x;
 789 }
 790