bp.c

   1 #include "bp.h"
   2 #include <unistd.h>
   3
   4 //#define CHECK
   5 #define RANDOM
   6
   7
   8 #define max(a,b) \
   9   ({ __typeof__ (a) _a = (a); \
  10   __typeof__ (b) _b = (b); \
  11   _a > _b ? _a : _b; })
  12
  13
  14 #define min(a,b) \
  15   ({ __typeof__ (a) _a = (a); \
  16   __typeof__ (b) _b = (b); \
  17    _a <= _b ? _a : _b; })
  18
  19
  20
  21 static int postorder_select_bsearch(bp *b,int s);
  22
  23 static int naive_depth(bp *b, int s)
  24 {
  25   int i,d;
  26   if (s < 0) return 0;
  27   d = 0;
  28   for (i=0; i<=s; i++) {
  29     if (bp_getbit(b->B,i)==OP) {
  30       d++;
  31     } else {
  32       d--;
  33     }
  34   }
  35   return d;
  36 }
  37
  38 void bp_print(bp *b, int s, int t)
  39 {
  40   int i,c,d;
  41   d = 0;
  42   for (i=s; i<=t; i++) {
  43     if (bp_getbit(b->B,i)==OP) {
  44       c = '(';
  45       d++;
  46     } else {
  47       c = ')';
  48       d--;
  49     }
  50     putchar(c);
  51   }
  52 }
  53
  54 int *matchtbl,*parenttbl;
  55 static void make_naivetbl(pb *B,int n)
  56 {
  57   int i,v;
  58   int *stack,s;
  59
  60   bp_xmalloc(matchtbl,n);
  61   bp_xmalloc(parenttbl,n);
  62   bp_xmalloc(stack,n);
  63
  64   for (i=0; i<n; i++) matchtbl[i] = parenttbl[i] = -1;
  65
  66   s = 0;
  67   v = 0;
  68   stack[0] = -1;
  69   for (i=0; i<n; i++) {
  70     if (bp_getbit(B,i)==OP) {
  71       v++;
  72       if (v > 0) {
  73         parenttbl[i] = stack[v-1];
  74         stack[v] = i;
  75       }
  76     } else {
  77       if (v > 0) {
  78         matchtbl[stack[v]] = i;  // close
  79         matchtbl[i] = stack[v];   // open
  80       }
  81       v--;
  82     }
  83   }
  84
  85   free(stack);
  86 }
  87
  88
  89 int fwdtbl[(2*ETW+1)*(1<<ETW)];
  90 int bwdtbl[(2*ETW+1)*(1<<ETW)];
  91 #if 0
  92 int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];
  93 int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];
  94 int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];
  95 int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];
  96 #endif
  97 int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];
  98 int degtbl[1<<ETW];
  99 int degtbl2[(2*ETW+1)*(1<<ETW)];
 100 int childtbl[(ETW)*(1<<ETW)];
 101 int childtbl2[2*ETW+1][ETW][(1<<ETW)];
 102 int depthtbl[(2*ETW+1)*(1<<ETW)];
 103 int inited = 0;
 104
 105 static void make_matchtbl(void)
 106 {
 107   int i,j,x,r;
 108   int m,M;
 109   pb buf[1];
 110   int deg;
 111   if (inited)
 112     return;
 113   inited = 1;
 114   for (x = 0; x < (1<<ETW); x++) {
 115     bp_setbits(buf,0,ETW,x);
 116     for (r=-ETW; r<=ETW; r++) fwdtbl[((r+ETW)<<ETW)+x] = ETW;
 117     for (r=-ETW; r<=ETW; r++) bwdtbl[((r+ETW)<<ETW)+x] = ETW;
 118     for (r=-ETW; r<=ETW; r++) degtbl2[((r+ETW)<<ETW)+x] = 0;
 119     for (r=-ETW; r<=ETW; r++) depthtbl[((r+ETW)<<ETW)+x] = 0;
 120
 121     r = 0;
 122     for (i=0; i<ETW; i++) {
 123       if (bp_getbit(buf,i)==OP) {
 124         r++;
 125       } else {
 126         r--;
 127       }
 128       if (fwdtbl[((r+ETW)<<ETW)+x] == ETW) fwdtbl[((r+ETW)<<ETW)+x] = i;
 129     }
 130
 131     r = 0;
 132     for (i=ETW-1; i>=0; i--) {
 133       if (bp_getbit(buf,i)==OP) {
 134         r--;
 135       } else {
 136         r++;
 137       }
 138       if (bwdtbl[((r+ETW)<<ETW)+x] == ETW) bwdtbl[((r+ETW)<<ETW)+x] = ETW-1-i;
 139     }
 140
 141     r = 0;
 142     for (i=0; i<ETW; i++) {
 143       if (bp_getbit(buf,i)==OP) {
 144         r++;
 145       } else {
 146         r--;
 147       }
 148       depthtbl[((r+ETW)<<ETW)+x] += (1<<(ETW-1));
 149     }
 150
 151
 152     r = 0;  m = 0;  M = 0;
 153     m = ETW+1;  M = -ETW-1;
 154     //maxtbl_lv[x] = -ETW-1;
 155     //mintbl_lv[x] = ETW+1;
 156     minmaxtbl_v[OPT_MAX | OPT_LEFT][x] = -ETW-1;
 157     minmaxtbl_v[OPT_MIN | OPT_LEFT][x] = ETW+1;
 158     deg = 0;
 159     for (i=0; i<ETW; i++) {
 160       if (bp_getbit(buf,i)==OP) {
 161         r++;
 162         if (r > M) {
 163           M = r;
 164           //maxtbl_li[x] = i;  maxtbl_lv[x] = r;
 165           minmaxtbl_i[OPT_MAX | OPT_LEFT][x] = i;
 166           minmaxtbl_v[OPT_MAX | OPT_LEFT][x] = r;
 167         }
 168       } else {
 169         r--;
 170         if (r == m) {
 171           deg++;
 172           childtbl[((deg-1)<<ETW) + x] = i;
 173         }
 174         if (r < m) {
 175           m = r;
 176           //mintbl_li[x] = i;  mintbl_lv[x] = r;
 177           minmaxtbl_i[OPT_MIN | OPT_LEFT][x] = i;
 178           minmaxtbl_v[OPT_MIN | OPT_LEFT][x] = r;
 179           deg = 1;
 180           childtbl[((deg-1)<<ETW) + x] = i;
 181         }
 182       }
 183       if (r <= m) degtbl2[((r+ETW)<<ETW)+x]++;
 184     }
 185     degtbl[x] = deg;
 186
 187     r = 0;  m = 0;  M = 0;
 188     //maxtbl_rv[x] = -ETW-1;
 189     //mintbl_rv[x] = ETW+1;
 190     minmaxtbl_v[OPT_MAX | OPT_RIGHT][x] = -ETW-1;
 191     minmaxtbl_v[OPT_MIN | OPT_RIGHT][x] = ETW+1;
 192     for (i=0; i<ETW; i++) {
 193       if (bp_getbit(buf,i)==OP) {
 194         r++;
 195         if (r >= M) {
 196           M = r;
 197           //maxtbl_ri[x] = i;  maxtbl_rv[x] = r;
 198           minmaxtbl_i[OPT_MAX | OPT_RIGHT][x] = i;
 199           minmaxtbl_v[OPT_MAX | OPT_RIGHT][x] = r;
 200         }
 201       } else {
 202         r--;
 203         if (r <= m) {
 204           m = r;
 205           //mintbl_ri[x] = i;  mintbl_rv[x] = r;
 206           minmaxtbl_i[OPT_MIN | OPT_RIGHT][x] = i;
 207           minmaxtbl_v[OPT_MIN | OPT_RIGHT][x] = r;
 208         }
 209       }
 210     }
 211
 212     for (i = 0; i < ETW; i++) {
 213       for (j = -ETW; j <= ETW; j++) {
 214         childtbl2[j+ETW][i][x] = -1;
 215       }
 216     }
 217
 218     for (j=-ETW; j<=ETW; j++) {
 219       int ith;
 220       ith = 0;
 221       r = 0;
 222       for (i = 0; i < ETW; i++) {
 223         if (bp_getbit(buf,i)==OP) {
 224           r++;
 225         } else {
 226           r--;
 227           if (r < j) break;
 228           if (r == j) {
 229             ith++;
 230             childtbl2[j+ETW][ith-1][x] = i;
 231           }
 232         }
 233       }
 234     }
 235   }
 236
 237 };
 238
 239
 240 bp * bp_construct(int n, pb *B, int opt)
 241 {
 242   bp *b;
 243   int i,j,d;
 244   int m,M,ds;
 245   int ns,nm;
 246   byte *sm, *sM;
 247   byte *sd;
 248   int *mm, *mM;
 249   int *md;
 250   int m_ofs;
 251   int r; // # of minimum values
 252   bp_xmalloc(b, 1);
 253
 254   b->B = B;
 255   b->n = n;
 256   b->opt = opt;
 257   b->idx_size = 0;
 258   b->sm = NULL;
 259   b->sM = NULL;
 260   b->sd = NULL;
 261   b->mm = NULL;
 262   b->mM = NULL;
 263   b->md = NULL;
 264   b->da_leaf = NULL;
 265   b->da_inorder = NULL;
 266   b->da_postorder = NULL;
 267   b->da_dfuds_leaf = NULL;
 268   b->da = bp_darray_construct(n,B, opt & OPT_FAST_PREORDER_SELECT);
 269   b->idx_size += b->da->idx_size;
 270
 271   //TODO check.
 272   make_matchtbl();
 273
 274   ns = (n+SB-1)/SB;
 275
 276   bp_xmalloc(sm, ns);
 277   b->idx_size += ns * sizeof(*sm);
 278
 279   bp_xmalloc(sM, ns);
 280   b->idx_size += ns * sizeof(*sM);
 281
 282   b->sm = sm;
 283   b->sM = sM;
 284
 285   if (opt & OPT_DEGREE) {
 286     bp_xmalloc(sd, ns);
 287     b->idx_size += ns * sizeof(*sd);
 288     b->sd = sd;
 289   }
 290
 291   for (i=0; i<n; i++) {
 292     if (i % SB == 0) {
 293       ds = bp_depth(b,i);
 294       m = M = ds;
 295       r = 1;
 296     } else {
 297       d = bp_depth(b,i);
 298       if (d == m) r++;
 299       if (d < m) {
 300         m = d;
 301         r = 1;
 302       }
 303       if (d > M) M = d;
 304     }
 305     if (i % SB == SB-1 || i==n-1) {
 306       ds = bp_depth(b,(i/SB)*SB-1);
 307       if (m - ds + SB < 0 || m - ds + SB > 255) {
 308         printf("error m=%d ds=%d\n",m,ds);
 309       }
 310       if (M - ds + 1 < 0 || M - ds + 1 > 255) {
 311         printf("error M=%d ds=%d\n",M,ds);
 312       }
 313       sm[i/SB] = m - ds + SB;
 314       sM[i/SB] = M - ds + 1;
 315       if (opt & OPT_DEGREE) sd[i/SB] = r;
 316     }
 317   }
 318
 319
 320   nm = (n+MB-1)/MB;
 321   m_ofs = 1 << blog(nm-1);
 322   b->m_ofs = m_ofs;
 323
 324   bp_xmalloc(mm, nm + m_ofs);
 325   b->idx_size += (nm+m_ofs) * sizeof(*mm);
 326
 327   bp_xmalloc(mM, nm + m_ofs);
 328   b->idx_size += (nm+m_ofs) * sizeof(*mM);
 329   b->mm = mm;
 330   b->mM = mM;
 331
 332   if (opt & OPT_DEGREE) {
 333     bp_xmalloc(md, nm + m_ofs);
 334     b->idx_size += (nm+m_ofs) * sizeof(*md);
 335     b->md = md;
 336   }
 337
 338   for (i=0; i<n; i++) {
 339     d = bp_depth(b,i);
 340     if (i % MB == 0) {
 341       m = M = d;
 342       r = 1;
 343     } else {
 344       if (d == m) r++;
 345       if (d < m) {
 346         m = d;
 347         r = 1;
 348       }
 349       if (d > M) M = d;
 350     }
 351     if (i % MB == MB-1 || i==n-1) {
 352       mm[m_ofs+ i/MB] = m;
 353       mM[m_ofs+ i/MB] = M;
 354       if (opt & OPT_DEGREE) md[m_ofs+ i/MB] = r;
 355     }
 356   }
 357
 358   for (j=m_ofs-1; j > 0; j--) {
 359     m = 0;
 360     if (j*2 < nm + m_ofs) m = mm[j*2];
 361     if (j*2+1 < nm + m_ofs) m = min(m,mm[j*2+1]);
 362     M = 0;
 363     if (j*2 < nm + m_ofs) M = mM[j*2];
 364     if (j*2+1 < nm + m_ofs) M = max(M,mM[j*2+1]);
 365     mm[j] = m;  mM[j] = M;
 366     if (opt & OPT_DEGREE) {
 367       d = 0;
 368       if (j*2 < nm + m_ofs) d = md[j*2];
 369       if (j*2+1 < nm + m_ofs) {
 370         if (mm[j*2] == mm[j*2+1]) d += md[j*2+1];
 371         if (mm[j*2] > mm[j*2+1]) d = md[j*2+1];
 372       }
 373       md[j] = d;
 374     }
 375   }
 376   mm[0] = -1;
 377   mM[0] = mM[1];
 378   if (opt & OPT_DEGREE) {
 379     md[0] = -1;
 380   }
 381
 382
 383   if (opt & OPT_LEAF) {
 384     b->da_leaf = bp_darray_pat_construct(n, B, 2, 0x2, opt & OPT_FAST_LEAF_SELECT);
 385     b->idx_size += b->da_leaf->idx_size;
 386   } else {
 387     b->da_leaf = NULL;
 388   }
 389
 390   if (opt & OPT_INORDER) {
 391
 392     b->da_inorder = bp_darray_pat_construct(n, B, 2, 0x1, opt & OPT_FAST_INORDER_SELECT);
 393     b->idx_size += b->da_inorder->idx_size;
 394
 395   } else {
 396     b->da_inorder = NULL;
 397   }
 398
 399   if (opt & OPT_FAST_POSTORDER_SELECT) {
 400
 401     b->da_postorder = bp_darray_pat_construct(n, B, 1, 0x0, (opt & OPT_FAST_POSTORDER_SELECT) | OPT_NO_RANK);
 402     b->idx_size += b->da_postorder->idx_size;
 403
 404   } else {
 405     b->da_postorder = NULL;
 406   }
 407
 408   if (opt & OPT_DFUDS_LEAF) {
 409     b->da_dfuds_leaf = bp_darray_pat_construct( n, B, 2, 0x0, opt & OPT_FAST_DFUDS_LEAF_SELECT);
 410     b->idx_size += b->da_dfuds_leaf->idx_size;
 411
 412   } else {
 413     b->da_dfuds_leaf = NULL;
 414   }
 415
 416   return b;
 417 }
 418
 419 void bp_delete(bp *b) {
 420    if (!b) return; // nothing to free
 421
 422    bp_darray_free(b->da); // destroys da data structure
 423    if (b->sm) free(b->sm);
 424    if (b->sM) free(b->sM);
 425    if (b->sd) free(b->sd);
 426    if (b->mm) free(b->mm);
 427    if (b->mM) free(b->mM);
 428    if (b->md) free(b->md);
 429
 430    bp_darray_free(b->da_leaf);
 431
 432    bp_darray_free(b->da_inorder);
 433
 434    bp_darray_free(b->da_postorder);
 435
 436    bp_darray_free(b->da_dfuds_leaf);
 437
 438    bp_free(b);
 439 }
 440
 441
 442 // saveTree: saves parentheses data structure to file
 443 // By Diego Arroyuelo
 444 void saveTree(bp *b, FILE *fp) {
 445
 446    if (fwrite(&(b->n), sizeof(int), 1, fp) != 1) {
 447       printf("Error: cannot save number of parentheses to file\n");
 448       exit(1);
 449    }
 450    if (fwrite(b->B, sizeof(pb), (b->n+D-1)/D, fp) != ((b->n+D-1)/D)) {
 451       printf("Error: cannot save parentheses sequence to file\n");
 452       exit(1);
 453    }
 454
 455    if (fwrite(&(b->opt), sizeof(int), 1, fp) != 1) {
 456       printf("Error: cannot save opt in parentheses to file\n");
 457       exit(1);
 458    }
 459 }
 460
 461 static ssize_t uwrite(int fd, const void* buff, size_t count)
 462 {
 463   ssize_t written;
 464   char *p = (char *) buff;
 465   do {
 466     written = write(fd, p, count);
 467     p += written;
 468     count -= written;
 469   } while (written > 0);
 470
 471   return (written == -1);
 472 }
 473
 474 static ssize_t uread(int fd, const void* buff, size_t count)
 475 {
 476   ssize_t loaded;
 477   char *p = (char *) buff;
 478   do {
 479     loaded = read(fd, p, count);
 480     p += loaded;
 481     count -= loaded;
 482   } while (loaded > 0);
 483
 484   return (loaded == -1);
 485 }
 486
 487 int bp_save(bp *b, int fd)
 488 {
 489   if (uwrite(fd, &b->n, sizeof(int))) return 1;
 490   if (uwrite(fd, b->B, sizeof(pb) * (b->n+D-1)/D)) return 1;
 491   if (uwrite(fd, &b->opt, sizeof(int))) return 1;
 492   return 0;
 493 }
 494
 495 bp* bp_load(int fd)
 496 {
 497   pb *B;
 498   int n, opt;
 499   if (uread(fd, &n, sizeof(int))) return NULL;
 500   bp_xmalloc(B, (n+D-1)/D);
 501
 502   if (B == NULL) return NULL;
 503
 504   if (uread(fd, B, sizeof(pb) * (n+D-1)/D)) {
 505     free(B);
 506     return NULL;
 507   };
 508
 509   if (uread(fd, &opt, sizeof(int))){
 510     free(B);
 511     return NULL;
 512   };
 513
 514   return bp_construct(n, B, opt);
 515 }
 516
 517
 518 // loadTree: load parentheses data structure from file
 519 // By Diego Arroyuelo
 520 bp * loadTree(FILE *fp) {
 521
 522    pb *B;
 523    int n, opt;
 524
 525    if (fread(&n, sizeof(int), 1, fp) != 1) {
 526       printf("Error: cannot read number of parentheses from file\n");
 527       exit(1);
 528    }
 529
 530    bp_xmalloc(B, (n+D-1)/D);
 531
 532    if (fread(B, sizeof(pb), (n+D-1)/D, fp) != ((n+D-1)/D)) {
 533       printf("Error: cannot read parentheses sequence from file\n");
 534       exit(1);
 535    }
 536
 537    if (fread(&opt, sizeof(int), 1, fp) != 1) {
 538       printf("Error: cannot read opt in parentheses from file\n");
 539       exit(1);
 540    }
 541
 542    return bp_construct(n, B, opt);
 543
 544 }
 545
 546
 547 static int naive_fwd_excess(bp *b,int s, int rel)
 548 {
 549   int i,v,n;
 550   pb *B;
 551   n = b->n;  B = b->B;
 552   v = 0;
 553   for (i=s+1; i<n; i++) {
 554     if (bp_getbit(B,i)==OP) {
 555       v++;
 556     } else {
 557       v--;
 558     }
 559     if (v == rel) return i;
 560   }
 561   return -1;
 562 }
 563
 564 static int naive_bwd_excess(bp *b,int s, int rel)
 565 {
 566   int i,v;
 567   pb *B;
 568   B = b->B;
 569   v = 0;
 570   for (i=s; i>=0; i--) {
 571     if (bp_getbit(B,i)==OP) {
 572       v--;
 573     } else {
 574       v++;
 575     }
 576     if (v == rel) return i-1;
 577   }
 578   return -2;
 579 }
 580
 581 static int naive_search_SB_l(bp *b, int i, int rel)
 582 {
 583   int il,v;
 584
 585   il = (i / SB) * SB;
 586   for (; i>=il; i--) {
 587     if (bp_getbit(b->B,i)==OP) {
 588       rel++;
 589     } else {
 590       rel--;
 591     }
 592     if (rel == 0) return i-1;
 593   }
 594   if (i < 0) return -2;
 595   return -3;
 596 }
 597
 598 int bp_naive_rmq(bp *b, int s, int t,int opt)
 599 {
 600   int d,i,dm,im;
 601
 602   if (opt & OPT_RIGHT) {
 603     d = dm = bp_depth(b,t);  im = t;
 604     i = t-1;
 605     while (i >= s) {
 606       if (bp_getbit(b->B,i+1)==CP) {
 607         d++;
 608         if (opt & OPT_MAX) {
 609           if (d > dm) {
 610             dm = d;  im = i;
 611           }
 612         }
 613       } else {
 614         d--;
 615         if (!(opt & OPT_MAX)) {
 616           if (d < dm) {
 617             dm = d;  im = i;
 618           }
 619         }
 620       }
 621       i--;
 622     }
 623   } else {
 624     d = dm = bp_depth(b,s);  im = s;
 625     i = s+1;
 626     while (i <= t) {
 627       if (bp_getbit(b->B,i)==OP) {
 628         d++;
 629         if (opt & OPT_MAX) {
 630           if (d > dm) {
 631             dm = d;  im = i;
 632           }
 633         }
 634       } else {
 635         d--;
 636         if (!(opt & OPT_MAX)) {
 637           if (d < dm) {
 638             dm = d;  im = i;
 639           }
 640         }
 641       }
 642       i++;
 643     }
 644   }
 645   return im;
 646 }
 647
 648
 649
 650 int bp_rank_open(bp *b, int s)
 651 {
 652   return bp_darray_rank(b->da, s);
 653 }
 654
 655 int bp_rank_close(bp *b, int s)
 656 {
 657   return s+1 - bp_darray_rank(b->da, s);
 658 }
 659
 660 int bp_select_open(bp *b, int s)
 661 {
 662   if (b->opt & OPT_FAST_PREORDER_SELECT) {
 663     return bp_darray_select(b->da,s,1);
 664   } else {
 665     return bp_darray_select_bsearch(b->da, s, getpat_preorder);
 666   }
 667 }
 668
 669 int bp_select_close(bp *b, int s)
 670 {
 671   if (b->opt & OPT_FAST_POSTORDER_SELECT) {
 672     return bp_darray_pat_select(b->da_postorder, s, getpat_postorder);
 673   } else {
 674     return postorder_select_bsearch(b,s);
 675   }
 676 }
 677
 678
 679 ///////////////////////////////////////////
 680 //  bp_postorder_rank(bp *b,int s)
 681 //    returns the postorder (>= 1) of node s (s >= 0)
 682 //            -1 if s-th bit is not OP
 683 ///////////////////////////////////////////
 684 int bp_postorder_rank(bp *b,int s)
 685 {
 686   int t;
 687   if (bp_inspect(b,s) == CP) return -1;
 688   t = bp_find_close(b,s);
 689   //  return t+1 - darray_rank(b->da,t);
 690   return bp_rank_close(b,t);
 691 }
 692
 693 static int postorder_select_bsearch(bp *b,int s)
 694 {
 695   int l,r,m;
 696
 697   if (s == 0) return -1;
 698
 699   if (s > b->da->n - b->da->m) {
 700     return -1;
 701   }
 702   l = 0;  r = b->da->n - 1;
 703
 704   while (l < r) {
 705     m = (l+r)/2;
 706     //printf("m=%d rank=%d s=%d\n",m,m+1 - darray_rank(b->da,m),s);
 707     if (m+1 - bp_darray_rank(b->da,m) >= s) {
 708       r = m;
 709     } else {
 710       l = m+1;
 711     }
 712   }
 713   return l;
 714 }
 715
 716 ///////////////////////////////////////////
 717 //  bp_postorder_select(bp *b,int s)
 718 //    returns the position of CP of the node with postorder s (>= 1)
 719 ///////////////////////////////////////////
 720 int bp_postorder_select(bp *b,int s)
 721 {
 722 #if 0
 723   if (b->opt & OPT_FAST_POSTORDER_SELECT) {
 724     return bp_darray_pat_select(b->da_postorder,s,getpat_postorder);
 725   } else {
 726     return postorder_select_bsearch(b->da,s);
 727   }
 728 #else
 729   return bp_select_close(b,s);
 730 #endif
 731 }
 732
 733 ///////////////////////////////////////////
 734 //  bp_leaf_rank(bp *b,int s)
 735 //    returns the number of leaves to the left of s
 736 ///////////////////////////////////////////
 737 int bp_leaf_rank(bp *b,int s)
 738 {
 739   if ((b->opt & OPT_LEAF) == 0) {
 740     printf("leaf_rank: error!!!   not supported\n");
 741     return -1;
 742   }
 743   if (s >= b->n-1) {
 744     s = b->n-2;
 745   }
 746   return bp_darray_pat_rank(b->da_leaf,s,getpat_leaf);
 747 }
 748
 749 ///////////////////////////////////////////
 750 //  leaf_select(bp *b,int s)
 751 //    returns the position of s-th leaf
 752 ///////////////////////////////////////////
 753 int bp_leaf_select(bp *b,int s)
 754 {
 755   if ((b->opt & OPT_LEAF) == 0) {
 756     printf("leaf_select: error!!!   not supported\n");
 757     return -1;
 758   }
 759   if (s > b->da_leaf->m) return -1;
 760   if (b->opt & OPT_FAST_LEAF_SELECT) {
 761     return bp_darray_pat_select(b->da_leaf,s,getpat_leaf);
 762   } else {
 763     return bp_darray_select_bsearch(b->da_leaf,s,getpat_leaf);
 764   }
 765 }
 766
 767
 768 ///////////////////////////////////////////
 769 //  bp_inorder_rank(bp *b,int s)
 770 //    returns the number of ")("  (s >= 0)
 771 ///////////////////////////////////////////
 772 int bp_inorder_rank(bp *b,int s)
 773 {
 774   if ((b->opt & OPT_INORDER) == 0) {
 775     printf("inorder_rank: error!!!   not supported\n");
 776     return -1;
 777   }
 778   if (s >= b->n-1) {
 779     s = b->n-2;
 780   }
 781   return bp_darray_pat_rank(b->da_inorder,s,getpat_inorder);
 782 }
 783
 784 ///////////////////////////////////////////
 785 //  bp_inorder_select(bp *b,int s)
 786 //    returns the s-th position of ")("  (s >= 1)
 787 ///////////////////////////////////////////
 788 int bp_inorder_select(bp *b,int s)
 789 {
 790   if ((b->opt & OPT_INORDER) == 0) {
 791     printf("inorder_select: error!!!   not supported\n");
 792     return -1;
 793   }
 794   if (b->opt & OPT_FAST_INORDER_SELECT) {
 795     return bp_darray_pat_select(b->da_inorder,s,getpat_inorder);
 796   } else {
 797     return bp_darray_select_bsearch(b->da_inorder,s,getpat_inorder);
 798   }
 799 }
 800
 801 ///////////////////////////////////////////
 802 //  bp_leftmost_leaf(bp *b, int s)
 803 ///////////////////////////////////////////
 804 int bp_leftmost_leaf(bp *b, int s)
 805 {
 806   if ((b->opt & OPT_LEAF) == 0) {
 807     printf("leftmost_leaf: error!!!   not supported\n");
 808     return -1;
 809   }
 810   return bp_leaf_select(b, bp_leaf_rank(b,s)+1);
 811 }
 812
 813 ///////////////////////////////////////////
 814 //  rightmost_leaf(bp *b, int s)
 815 ///////////////////////////////////////////
 816 int bp_rightmost_leaf(bp *b, int s)
 817 {
 818   int t;
 819   if ((b->opt & OPT_LEAF) == 0) {
 820     printf("leftmost_leaf: error!!!   not supported\n");
 821     return -1;
 822   }
 823   t = bp_find_close(b,s);
 824   return bp_leaf_select(b, bp_leaf_rank(b,t));
 825 }
 826
 827
 828 ///////////////////////////////////////////
 829 //  bp_prev_sibling(bp *b,int s)
 830 //    returns the previous sibling of parent(s)
 831 //            -1 if s is the first child
 832 //////////////////////////////////////////
 833 int bp_prev_sibling(bp *b, int s)
 834 {
 835   int t;
 836   if (s == 0) return -1;
 837   if (bp_inspect(b,s-1) == OP) return -1;
 838   t = bp_find_open(b,s-1);
 839   return t;
 840 }
 841
 842 ///////////////////////////////////////////
 843 //  bp_deepest_node(bp *b,int s)
 844 //    returns the first node with the largest depth in the subtree of s
 845 ///////////////////////////////////////////
 846 int bp_deepest_node(bp *b,int s)
 847 {
 848   int t,m;
 849   t = bp_find_close(b,s);
 850   m = bp_rmq(b,s,t, OPT_MAX);
 851   return m;
 852 }
 853
 854 ///////////////////////////////////////////
 855 //  bp_subtree_height(bp *b,int s)
 856 //    returns the height of the subtree of s
 857 //            0 if s is a leaf
 858 ///////////////////////////////////////////
 859 int bp_subtree_height(bp *b,int s)
 860 {
 861   int t;
 862   t = bp_deepest_node(b,s);
 863   return bp_depth(b,t) - bp_depth(b,s);
 864 }
 865
 866 int bp_naive_degree(bp *b, int s)
 867 {
 868   int t,d;
 869   d = 0;
 870   t = bp_first_child(b,s);
 871   while (t >= 0) {
 872     d++;
 873     t = bp_next_sibling(b,t);
 874   }
 875   return d;
 876 }
 877
 878 ///////////////////////////////////////////
 879 //  bp_degree(bp *b, int s)
 880 //    returns the number of children of s
 881 //            0 if s is a leaf
 882 ///////////////////////////////////////////
 883 int bp_degree(bp *b, int s)
 884 {
 885   if (b->opt & OPT_DEGREE) {
 886     return bp_fast_degree(b,s,b->n,0);
 887   } else {
 888     return bp_naive_degree(b,s);
 889   }
 890 }
 891
 892 int bp_naive_child(bp *b, int s, int d)
 893 {
 894   int t,i;
 895   t = bp_first_child(b,s);
 896   for (i = 1; i < d; i++) {
 897     if (t == -1) break;
 898     t = bp_next_sibling(b,t);
 899   }
 900   return t;
 901 }
 902
 903 ///////////////////////////////////////////
 904 //  bp_child(bp *b, int s, int d)
 905 //    returns the d-th child of s  (1 <= d <= degree(s))
 906 //            -1 if no such node
 907 ///////////////////////////////////////////
 908 int bp_child(bp *b, int s, int d)
 909 {
 910   int r;
 911   if (b->opt & OPT_DEGREE) {
 912     //return find_open(b,fast_degree(b,s,b->n,d));
 913     if (d==1) return bp_first_child(b,s);
 914     r = bp_fast_degree(b,s,b->n,d-1)+1;
 915     if (bp_inspect(b,r) == CP) return -1;
 916     return r;
 917   } else {
 918     return bp_naive_child(b,s,d);
 919   }
 920
 921 }
 922
 923
 924 int bp_naive_child_rank(bp *b, int t)
 925 {
 926   int v,d;
 927   d = 0;
 928   while (t != -1) {
 929     d++;
 930     t = bp_prev_sibling(b,t);
 931   }
 932   return d;
 933 }
 934
 935 ///////////////////////////////////////////
 936 //  bp_child_rank(bp *b, int t)
 937 //    returns d if t is the d-th child of the parent of t (d >= 1)
 938 //            1 if t is the root
 939 ///////////////////////////////////////////
 940 int bp_child_rank(bp *b, int t)
 941 {
 942   int r;
 943   if (t == bp_root_node(b)) return 1;
 944   if (b->opt & OPT_DEGREE) {
 945     r = bp_parent(b,t);
 946     return bp_fast_degree(b,r,t,0)+1;
 947   } else {
 948     return bp_naive_child_rank(b,t);
 949   }
 950 }
 951
 952
 953 ///////////////////////////////////////////
 954 //  distance(bp *b, int s, int t)
 955 //    returns the length of the shortest path from s to t in the tree
 956 ///////////////////////////////////////////
 957 int bp_distance(bp *b, int s, int t)
 958 {
 959   int v,d;
 960   v = bp_lca(b,s,t);
 961   d = bp_depth(b,v);
 962   return (bp_depth(b,s) - d) + (bp_depth(b,t) - d);
 963 }
 964
 965 ///////////////////////////////////////////
 966 //  level_next(bp *b, int d)
 967 ///////////////////////////////////////////
 968 int bp_level_next(bp *b,int s)
 969 {
 970   int t;
 971   t = bp_fwd_excess(b,s,0);
 972   return t;
 973 }
 974
 975 ///////////////////////////////////////////
 976 //  level_prev(bp *b, int d)
 977 ///////////////////////////////////////////
 978 int bp_level_prev(bp *b,int s)
 979 {
 980   int t;
 981   t = bp_bwd_excess(b,s,0);
 982   return t;
 983 }
 984
 985 ///////////////////////////////////////////
 986 //  bp_level_leftmost(bp *b, int d)
 987 ///////////////////////////////////////////
 988 int bp_level_leftmost(bp *b, int d)
 989 {
 990   int t;
 991   if (d < 1) return -1;
 992   if (d == 1) return 0;
 993   t = bp_fwd_excess(b,0,d);
 994   return t;
 995 }
 996
 997 ///////////////////////////////////////////
 998 //  bp_level_rigthmost(bp *b, int d)
 999 ///////////////////////////////////////////
1000 int level_rigthmost(bp *b, int d)
1001 {
1002   int t;
1003   if (d < 1) return -1;
1004   if (d == 1) return 0;
1005   t = bp_bwd_excess(b,0,d-1);
1006   return bp_find_open(b,t);
1007 }
1008
1009 ///////////////////////////////////////////
1010 //  leaf_size(bp *b, int s)
1011 ///////////////////////////////////////////
1012 int bp_leaf_size(bp *b, int s)
1013 {
1014   int t;
1015   if ((b->opt & OPT_LEAF) == 0) {
1016     printf("leaf_size: error!!!   not supported\n");
1017     return -1;
1018   }
1019   t = bp_find_close(b,s);
1020   return bp_leaf_rank(b,t) - bp_leaf_rank(b,s);
1021 }