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 static inline unsigned int
 161 _fast_popcount2(int x)
 162 {
 163     uint m1 = 0x55555555;
 164     uint m2 = 0x33333333;
 165     uint m4 = 0x0f0f0f0f;
 166     x -= (x >> 1) & m1;
 167     x = (x & m2) + ((x >> 2) & m2);
 168     x = (x + (x >> 4)) & m4;
 169     x += x >>  8;
 170     return (x + (x >> 16)) & 0x3f;
 171 }
 172
 173 static inline unsigned int
 174 _fast_popcount3(int x)
 175 {
 176   uint m1 = 0x55555555;
 177   uint m2 = 0xc30c30c3;
 178   x -= (x >> 1) & m1;
 179   x = (x & m2) + ((x >> 2) & m2) + ((x >> 4) & m2);
 180   x += x >> 6;
 181   return  (x + (x >> 12) + (x >> 24)) & 0x3f;
 182 }
 183
 184 static inline unsigned int
 185 _fast_popcount(int x) {
 186   return _popCount[x];
 187 }
 188
 189 static unsigned int __selecttbl[8*256];
 190 static int built = 0;
 191
 192 void make___selecttbl(void) {
 193   if(built) return;
 194   built = 1;
 195   int i,x,r;
 196   uint buf[1];
 197
 198   for (x = 0; x < 256; x++) {
 199     __setbits(buf,0,8,x);
 200     for (r=0; r<8; r++) __selecttbl[(r<<8)+x] = -1;
 201     r = 0;
 202     for (i=0; i<8; i++) {
 203       if (__getbit(buf,i)) {
 204         __selecttbl[(r<<8)+x] = i;
 205         r++;
 206       }
 207     }
 208   }
 209 }
 210
 211
 212 unsigned int __popCount(uint x) {
 213   uint r;
 214   #if 0
 215   r = x;
 216   r = r - ((r>>1) & 0x77777777) - ((r>>2) & 0x33333333) - ((r>>3) & 0x11111111);
 217   r = ((r + (r>>4)) & 0x0f0f0f0f) % 0xff;
 218   #elif 1
 219   r = x;
 220   r = ((r & 0xaaaaaaaa)>>1) + (r & 0x55555555);
 221   r = ((r & 0xcccccccc)>>2) + (r & 0x33333333);
 222   //r = ((r & 0xf0f0f0f0)>>4) + (r & 0x0f0f0f0f);
 223   r = ((r>>4) + r) & 0x0f0f0f0f;
 224   //r = ((r & 0xff00ff00)>>8) + (r & 0x00ff00ff);
 225   r = (r>>8) + r;
 226   //r = ((r & 0xffff0000)>>16) + (r & 0x0000ffff);
 227   r = ((r>>16) + r) & 63;
 228   #else
 229   r = _popCount[x & 0xff];
 230   x >>= 8;
 231   r += _popCount[x & 0xff];
 232   x >>= 8;
 233   r += _popCount[x & 0xff];
 234   x >>= 8;
 235   r += _popCount[x & 0xff];
 236   #endif
 237   return r;
 238 }
 239
 240
 241 unsigned int __popCount8(uint x) {
 242   uint r;
 243   #if 1
 244   r = x;
 245   r = ((r & 0xaa)>>1) + (r & 0x55);
 246   r = ((r & 0xcc)>>2) + (r & 0x33);
 247   r = ((r>>4) + r) & 0x0f;
 248   #else
 249   r = _popCount[x & 0xff];
 250   #endif
 251   return r;
 252 }
 253
 254
 255 int selectd2_save(selectd2 * s, FILE * fp) {
 256   uint wr = 0;
 257   wr += fwrite(&s->n,sizeof(uint),1,fp);
 258   wr += fwrite(&s->m,sizeof(uint),1,fp);
 259   wr += fwrite(&s->size,sizeof(uint),1,fp);
 260   wr += fwrite(&s->ss_len,sizeof(uint),1,fp);
 261   wr += fwrite(&s->sl_len,sizeof(uint),1,fp);
 262   wr += fwrite(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
 263   uint nl = (s->m-1) / L + 1;
 264   wr += fwrite(s->lp,sizeof(uint),nl+1,fp);
 265   wr += fwrite(s->p,sizeof(uint),nl+1,fp);
 266   wr += fwrite(s->ss,sizeof(ushort),s->ss_len,fp);
 267   wr += fwrite(s->sl,sizeof(uint),s->sl_len,fp);
 268   if(wr!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5)
 269     return 1;
 270   return 0;
 271 }
 272
 273
 274 int selectd2_load(selectd2 * s, FILE * fp) {
 275   uint rd = 0;
 276   rd += fread(&s->n,sizeof(uint),1,fp);
 277   rd += fread(&s->m,sizeof(uint),1,fp);
 278   rd += fread(&s->size,sizeof(uint),1,fp);
 279   rd += fread(&s->ss_len,sizeof(uint),1,fp);
 280   rd += fread(&s->sl_len,sizeof(uint),1,fp);
 281   s->buf = new uchar[(s->n+7)/8+1];
 282   rd += fread(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
 283   uint nl = (s->m-1) / L + 1;
 284   s->lp = new uint[nl+1];
 285   rd += fread(s->lp,sizeof(uint),nl+1,fp);
 286   s->p = new uint[nl+1];
 287   rd += fread(s->p,sizeof(uint),nl+1,fp);
 288   s->ss = new ushort[s->ss_len];
 289   rd += fread(s->ss,sizeof(ushort),s->ss_len,fp);
 290   s->sl = new uint[s->sl_len];
 291   rd += fread(s->sl,sizeof(uint),s->sl_len,fp);
 292   if(rd!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5)
 293     return 1;
 294   return 0;
 295 }
 296
 297
 298 void selectd2_free(selectd2 * s) {
 299   //delete [] s->buf;
 300   delete [] s->lp;
 301   delete [] s->p;
 302   delete [] s->ss;
 303   delete [] s->sl;
 304 }
 305
 306
 307 int selectd2_construct(selectd2 *select, int n, uchar *buf) {
 308   int i,m;
 309   int nl;
 310   int p,pp;
 311   int il,is,ml,ms;
 312   int r;
 313   uint *s;
 314
 315   make___selecttbl();
 316
 317   if (L/LLL == 0) {
 318     printf("ERROR: L=%d LLL=%d\n",L,LLL);
 319     exit(1);
 320   }
 321
 322   m = 0;
 323   for (i=0; i<n; i++) m += __getbit2(buf,i);
 324   select->n = n;
 325   select->m = m;
 326   //printf("n=%d m=%d\n",n,m);
 327
 328   select->buf = buf;
 329
 330   s = new uint[m];
 331   m = 0;
 332   for (i=0; i<n; i++) {
 333     if (__getbit2(buf,i)) {
 334       m++;
 335       s[m-1] = i;
 336     }
 337   }
 338
 339   nl = (m-1) / L + 1;
 340   select->size = 0;              //ignoring buf, shared with selects3
 341   select->lp = new uint[nl+1];
 342   for(int k=0;k<nl+1;k++) select->lp[k]=0;
 343   select->size += (nl+1)*sizeof(uint);
 344   select->p = new uint[nl+1];
 345   for(int k=0;k<nl+1;k++) select->p[k]=0;
 346   select->size += (nl+1)*sizeof(uint);
 347
 348   for (r = 0; r < 2; r++) {
 349     ml = ms = 0;
 350     for (il = 0; il < nl; il++) {
 351       pp = s[il*L];
 352       select->lp[il] = pp;
 353       i = min((il+1)*L-1,m-1);
 354       p = s[i];
 355       //printf("%d ",p-pp);
 356       if (p - pp >= LL) {
 357         if (r == 1) {
 358           for (is = 0; is < L; is++) {
 359             if (il*L+is >= m) break;
 360             select->sl[ml*L+is] = s[il*L+is];
 361           }
 362         }
 363         select->p[il] = -((ml<<logL)+1);
 364         ml++;
 365       }
 366       else {
 367         if (r == 1) {
 368           for (is = 0; is < L/LLL; is++) {
 369             if (il*L+is*LLL >= m) break;
 370             select->ss[ms*(L/LLL)+is] = s[il*L+is*LLL] - pp;
 371           }
 372         }
 373         select->p[il] = ms << (logL-logLLL);
 374         ms++;
 375       }
 376     }
 377     if (r == 0) {
 378       select->sl = new uint[ml*L+1];
 379       for(int k=0;k<ml*L+1;k++) select->sl[k]=0;
 380       select->size += sizeof(uint)*(ml*L+1);
 381       select->sl_len = ml*L+1;
 382       select->ss = new ushort[ms*(L/LLL)+1];
 383       for(int k=0;k<ms*(L/LLL)+1;k++) select->ss[k]=0;
 384       select->ss_len = ms*(L/LLL)+1;
 385       select->size += sizeof(ushort)*(ms*(L/LLL)+1);
 386     }
 387   }
 388   delete [] s;
 389   return 0;
 390 }
 391
 392
 393 int selectd2_select(selectd2 *select, int i,int f) {
 394   int p,r;
 395   int il;
 396   int rr;
 397   uchar *q;
 398
 399   if (i == 0) return -1;
 400
 401   #if 0
 402   if (i > select->m) {
 403     printf("ERROR: m=%d i=%d\n",select->m,i);
 404     exit(1);
 405   }
 406   #endif
 407
 408   i--;
 409
 410   il = select->p[i>>logL];
 411   if (il < 0) {
 412     il = -il-1;
 413     //p = select->sl[(il<<logL)+(i & (L-1))];
 414     p = select->sl[il+(i & (L-1))];
 415   }
 416   else {
 417     p = select->lp[i>>logL];
 418     //p += select->ss[(il<<(logL-logLLL))+(i & (L-1))/LLL];
 419     p += select->ss[il+((i & (L-1))>>logLLL)];
 420     r = i - (i & (LLL-1));
 421
 422     q = &(select->buf[p>>3]);
 423
 424     if (f == 1) {
 425       rr = p & (8-1);
 426       //r -= _popCount[*q >> (8-1-rr)];
 427       r -= _fast_popcount(*q >> (8-1-rr));
 428       //p = p - rr;
 429
 430       while (1) {
 431         //rr = _popCount[*q];
 432         rr = _fast_popcount(*q);
 433         if (r + rr >= i) break;
 434         r += rr;
 435         //p += 8;
 436         q++;
 437       }
 438       p = (q - select->buf) << 3;
 439       p += __selecttbl[((i-r-1)<<8)+(*q)];
 440     }
 441     else {
 442       rr = p & (8-1);
 443       //r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
 444       r -= _fast_popcount((*q ^ 0xff) >> (8-1-rr));
 445       //p = p - rr;
 446
 447       while (1) {
 448         //rr = _popCount[*q ^ 0xff];
 449         rr = _fast_popcount(*q ^ 0xff);
 450         if (r + rr >= i) break;
 451         r += rr;
 452         //p += 8;
 453         q++;
 454       }
 455       p = (q - select->buf) << 3;
 456       p += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 457     }
 458   }
 459   return p;
 460 }
 461
 462
 463 int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
 464   int p,r,p2;
 465   int il;
 466   int rr;
 467   uchar *q;
 468
 469   if (i == 0) {
 470     *st = -1;
 471     return -1;
 472   }
 473
 474   #if 0
 475   if (i > select->m) {
 476     printf("ERROR: m=%d i=%d\n",select->m,i);
 477     exit(1);
 478   }
 479   #endif
 480
 481   i--;
 482
 483   il = select->p[i>>logL];
 484   if (il < 0) {
 485     il = -il-1;
 486     //p = select->sl[(il<<logL)+(i & (L-1))];
 487     p = select->sl[il+(i & (L-1))];
 488
 489     if ((i>>logL) == ((i+1)>>logL)) {
 490       p2 = select->sl[il+((i+1) & (L-1))];
 491     }
 492     else {
 493       p2 = selectd2_select(select,i+2,f);
 494     }
 495   }
 496   else {
 497     p = select->lp[i>>logL];
 498     //p += select->ss[(il<<(logL-logLLL))+(i & (L-1))/LLL];
 499     p += select->ss[il+((i & (L-1))>>logLLL)];
 500     r = i - (i & (LLL-1));
 501
 502     q = &(select->buf[p>>3]);
 503
 504     if (f == 1) {
 505       rr = p & (8-1);
 506       //r -= _popCount[*q >> (8-1-rr)];
 507       r -= _fast_popcount(*q >> (8-1-rr));
 508       //p = p - rr;
 509
 510       while (1) {
 511         //rr = _popCount[*q];
 512         rr = _fast_popcount(*q);
 513         if (r + rr >= i) break;
 514         r += rr;
 515         //p += 8;
 516         q++;
 517       }
 518       p = (q - select->buf) << 3;
 519       p += __selecttbl[((i-r-1)<<8)+(*q)];
 520
 521       if ((i>>logL) == ((i+1)>>logL)) {
 522         i++;
 523         while (1) {
 524           //rr = _popCount[*q];
 525           r = _fast_popcount(*q);
 526           if (r + rr >= i) break;
 527           r += rr;
 528           q++;
 529         }
 530         p2 = (q - select->buf) << 3;
 531         p2 += __selecttbl[((i-r-1)<<8)+(*q)];
 532       }
 533       else {
 534         p2 = selectd2_select(select,i+2,f);
 535       }
 536
 537     }
 538     else {
 539       rr = p & (8-1);
 540       //r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
 541       r -= _fast_popcount((*q ^ 0xff) >> (8-1-rr));
 542       //p = p - rr;
 543
 544       while (1) {
 545         //rr = _popCount[*q ^ 0xff];
 546         rr = _fast_popcount(*q ^ 0xff);
 547         if (r + rr >= i) break;
 548         r += rr;
 549         //p += 8;
 550         q++;
 551       }
 552       p = (q - select->buf) << 3;
 553       p += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 554
 555       if ((i>>logL) == ((i+1)>>logL)) {
 556         i++;
 557         while (1) {
 558           //rr = _popCount[*q ^ 0xff];
 559           rr = _fast_popcount(*q ^ 0xff);
 560           if (r + rr >= i) break;
 561           r += rr;
 562           q++;
 563         }
 564         p2 = (q - select->buf) << 3;
 565         p2 += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 566       }
 567       else {
 568         p2 = selectd2_select(select,i+2,f);
 569       }
 570     }
 571   }
 572   *st = p;
 573   *en = p2;
 574   return p;
 575 }
 576
 577
 578 int selects3_save(selects3 * s, FILE * fp) {
 579   uint wr = 0;
 580   wr += fwrite(&s->n,sizeof(uint),1,fp);
 581   wr += fwrite(&s->m,sizeof(uint),1,fp);
 582   wr += fwrite(&s->size,sizeof(uint),1,fp);
 583   wr += fwrite(&s->d,sizeof(uint),1,fp);
 584   wr += fwrite(&s->hi_len,sizeof(uint),1,fp);
 585   wr += fwrite(&s->low_len,sizeof(uint),1,fp);
 586   wr += fwrite(s->hi,sizeof(uchar),s->hi_len,fp);
 587   wr += fwrite(s->low,sizeof(uint),s->low_len,fp);
 588   if(wr!=(6+s->hi_len+s->low_len))
 589     return 1;
 590   if(selectd2_save(s->sd0,fp)) return 2;
 591   if(selectd2_save(s->sd1,fp)) return 3;
 592   return 0;
 593 }
 594
 595
 596 int selects3_load(selects3 * s, FILE * fp) {
 597   uint rd = 0;
 598   rd += fread(&s->n,sizeof(uint),1,fp);
 599   rd += fread(&s->m,sizeof(uint),1,fp);
 600   rd += fread(&s->size,sizeof(uint),1,fp);
 601   rd += fread(&s->d,sizeof(uint),1,fp);
 602   rd += fread(&s->hi_len,sizeof(uint),1,fp);
 603   rd += fread(&s->low_len,sizeof(uint),1,fp);
 604   s->hi = new uchar[s->hi_len];
 605   rd += fread(s->hi,sizeof(uchar),s->hi_len,fp);
 606   s->low = new uint[s->low_len];
 607   rd += fread(s->low,sizeof(uint),s->low_len,fp);
 608   if(rd!=(6+s->hi_len+s->low_len))
 609     return 1;
 610   s->sd0 = new selectd2;
 611   if(selectd2_load(s->sd0,fp)) return 2;
 612   s->sd1 = new selectd2;
 613   if(selectd2_load(s->sd1,fp)) return 3;
 614   delete [] s->sd0->buf;
 615   delete [] s->sd1->buf;
 616   s->sd0->buf = s->hi;
 617   s->sd1->buf = s->hi;
 618   return 0;
 619 }
 620
 621
 622 void selects3_free(selects3 * s) {
 623   delete [] s->hi;
 624   delete [] s->low;
 625   //delete [] s->sd0->buf;
 626   selectd2_free(s->sd0);
 627   delete s->sd0;
 628   selectd2_free(s->sd1);
 629   delete s->sd1;
 630 }
 631
 632
 633 int selects3_construct(selects3 *select, int n, uint *buf) {
 634   int i,m;
 635   int d,mm;
 636   uint *low;
 637   uchar *buf2;
 638   selectd2 *sd0,*sd1;
 639
 640   m = 0;
 641   for (i=0; i<n; i++) m += __getbit(buf,i);
 642   select->n = n;
 643   select->m = m;
 644
 645   if (m == 0) return 0;
 646
 647   mm = m;
 648   d = 0;
 649   while (mm < n) {
 650     mm <<= 1;
 651     d++;
 652   }
 653
 654   select->d = d;
 655
 656   buf2 = new uchar[(2*m+8-1)/8+1];
 657   for(int k=0;k<(2*m+8-1)/8+1;k++) buf2[k]=0;
 658   select->hi_len = (2*m+8-1)/8+1;
 659   low = new uint[(d*m+PBS-1)/PBS+1];
 660   for(uint k=0;k<(d*m+PBS-1)/PBS+1;k++) low[k]=0;
 661   select->low_len = (d*m+PBS-1)/PBS+1;
 662
 663   select->hi = buf2;
 664   select->low = low;
 665   select->size = sizeof(uchar)*((2*m+8-1)/8+1) + sizeof(uint)*((d*m+PBS-1)/PBS+1);
 666
 667   for (i=0; i<m*2; i++) __setbit2(buf2,i,0);
 668
 669   m = 0;
 670   for (i=0; i<n; i++) {
 671     if (__getbit(buf,i)) {
 672       __setbit2(buf2,(i>>d)+m,1);
 673       __setbits(low,m*d,d,i & ((1<<d)-1));
 674       m++;
 675     }
 676   }
 677
 678   sd1 = new selectd2;
 679   sd0 = new selectd2;
 680   select->size += 2*sizeof(selectd2);
 681
 682   selectd2_construct(sd1,m*2,buf2);
 683   select->sd1 = sd1;
 684
 685   for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
 686   selectd2_construct(sd0,m*2,buf2);
 687   select->sd0 = sd0;
 688
 689   for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
 690   return 0;
 691 }
 692
 693 //selects3 * lasts3=NULL;
 694 //int lasti=0;
 695 //int lasts=0;
 696
 697 int selects3_select(selects3 *select, int i) {
 698   int d,x;
 699
 700   #if 0
 701   if (i > select->m) {
 702     printf("ERROR: m=%d i=%d\n",select->m,i);
 703     exit(1);
 704   }
 705   #endif
 706
 707   if (i == 0) return -1;
 708
 709   d = select->d;
 710         /*if(select->lasti==(uint)i-1) {
 711                 while(!__getbit2(select->sd1->buf,++select->lasts));
 712         }
 713         else {
 714           select->lasts = selectd2_select(select->sd1,i,1);
 715         }
 716         select->lasti = i;
 717         //lasts3 = select; */
 718         x = selectd2_select(select->sd1,i,1) - (i-1);
 719   //x = (select->lasts-(i-1)) << d;
 720   x <<= d;
 721   x += __getbits(select->low,(i-1)*d,d);
 722   return x;
 723 }
 724
 725
 726 int selects3_selectnext(selects3 *select, int i) {
 727         //return selects3_select(select,selects3_rank(select,i)+1);
 728   int d,x,w,y;
 729   int r,j;
 730   int z,ii;
 731   uint *q;
 732   d = select->d;
 733   q = select->low;
 734   ii = i>>d;
 735   y = selectd2_select(select->sd0,ii,0)+1;
 736         int k2=y-ii;
 737   x = y - ii;
 738         int x_orig = x;
 739   j = i - (ii<<d);
 740   r = y & 7;
 741   y >>= 3;
 742   z = select->hi[y];
 743   while (1) {
 744     if (((z << r) & 0x80) == 0) {
 745                         if(x!=x_orig) k2++;
 746                         break;
 747                 }
 748     w = __getbits(q,x*d,d);
 749     if (w >= j) {
 750       if (w == j) {
 751                                 if(__getbit2(select->hi,(8*y+r))) k2++;
 752                                 x++;
 753                                 r++;
 754                         }
 755       break;
 756     }
 757     x++;
 758     r++;
 759                 if(__getbit2(select->hi,(8*y+r))) k2++;
 760     if (r == 8) {
 761       r = 0;
 762       y++;
 763       z = select->hi[y];
 764     }
 765   }
 766         if(x==select->m)
 767                 return (uint)-1;
 768         int c=8*y+r;
 769         int fin=0;
 770         for(int kk=0;kk<8-r;kk++) {
 771                 if(__getbit2(select->hi,c)) {
 772                         fin=1;
 773                         break;
 774                 }
 775                 c++;
 776         }
 777         if(!fin) {
 778                 int pp = c/8;
 779                 while(select->hi[pp]==0) {
 780                         pp++;
 781                         c+=8;
 782                 }
 783                 while(!__getbit2(select->hi,c)) c++;
 784         }
 785         c -= (k2);
 786   return __getbits(q,x*d,d)+((c)<<d);
 787 }
 788
 789 int selects3_rank(selects3 *select, int i) {
 790   int d,x,w,y;
 791   int r,j;
 792   int z,ii;
 793   uint *q;
 794
 795   d = select->d;
 796   q = select->low;
 797
 798   ii = i>>d;
 799
 800   y = selectd2_select(select->sd0,ii,0)+1;
 801   //  selectd2_select2(select->sd0,ii,0,&y1,&y2);
 802   //y1++;  y2++;
 803   //printf("y %d y1 %d  %d\n",y,y1,y2-y1);
 804
 805   x = y - ii;
 806
 807   j = i - (ii<<d);
 808
 809   r = y & 7;
 810   y >>= 3;
 811   z = select->hi[y];
 812   while (1) {
 813     if (((z << r) & 0x80) == 0) break;
 814     w = __getbits(q,x*d,d);
 815     if (w >= j) {
 816       if (w == j) x++;
 817       break;
 818     }
 819     x++;
 820     r++;
 821     if (r == 8) {
 822       r = 0;
 823       y++;
 824       z = select->hi[y];
 825     }
 826   }
 827
 828         return x;
 829 }
 830