bp.c

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