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
 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 // loadTree: load parentheses data structure from file
 462 // By Diego Arroyuelo
 463 bp * loadTree(FILE *fp) {
 464
 465    pb *B;
 466    int n, opt;
 467
 468    if (fread(&n, sizeof(int), 1, fp) != 1) {
 469       printf("Error: cannot read number of parentheses from file\n");
 470       exit(1);
 471    }
 472
 473    bp_xmalloc(B, (n+D-1)/D);
 474
 475    if (fread(B, sizeof(pb), (n+D-1)/D, fp) != ((n+D-1)/D)) {
 476       printf("Error: cannot read parentheses sequence from file\n");
 477       exit(1);
 478    }
 479
 480    if (fread(&opt, sizeof(int), 1, fp) != 1) {
 481       printf("Error: cannot read opt in parentheses from file\n");
 482       exit(1);
 483    }
 484
 485    return bp_construct(n, B, opt);
 486
 487 }
 488
 489
 490 static int naive_fwd_excess(bp *b,int s, int rel)
 491 {
 492   int i,v,n;
 493   pb *B;
 494   n = b->n;  B = b->B;
 495   v = 0;
 496   for (i=s+1; i<n; i++) {
 497     if (bp_getbit(B,i)==OP) {
 498       v++;
 499     } else {
 500       v--;
 501     }
 502     if (v == rel) return i;
 503   }
 504   return -1;
 505 }
 506
 507 static int naive_bwd_excess(bp *b,int s, int rel)
 508 {
 509   int i,v;
 510   pb *B;
 511   B = b->B;
 512   v = 0;
 513   for (i=s; i>=0; i--) {
 514     if (bp_getbit(B,i)==OP) {
 515       v--;
 516     } else {
 517       v++;
 518     }
 519     if (v == rel) return i-1;
 520   }
 521   return -2;
 522 }
 523
 524 static int naive_search_SB_l(bp *b, int i, int rel)
 525 {
 526   int il,v;
 527
 528   il = (i / SB) * SB;
 529   for (; i>=il; i--) {
 530     if (bp_getbit(b->B,i)==OP) {
 531       rel++;
 532     } else {
 533       rel--;
 534     }
 535     if (rel == 0) return i-1;
 536   }
 537   if (i < 0) return -2;
 538   return -3;
 539 }
 540
 541 int bp_naive_rmq(bp *b, int s, int t,int opt)
 542 {
 543   int d,i,dm,im;
 544
 545   if (opt & OPT_RIGHT) {
 546     d = dm = bp_depth(b,t);  im = t;
 547     i = t-1;
 548     while (i >= s) {
 549       if (bp_getbit(b->B,i+1)==CP) {
 550         d++;
 551         if (opt & OPT_MAX) {
 552           if (d > dm) {
 553             dm = d;  im = i;
 554           }
 555         }
 556       } else {
 557         d--;
 558         if (!(opt & OPT_MAX)) {
 559           if (d < dm) {
 560             dm = d;  im = i;
 561           }
 562         }
 563       }
 564       i--;
 565     }
 566   } else {
 567     d = dm = bp_depth(b,s);  im = s;
 568     i = s+1;
 569     while (i <= t) {
 570       if (bp_getbit(b->B,i)==OP) {
 571         d++;
 572         if (opt & OPT_MAX) {
 573           if (d > dm) {
 574             dm = d;  im = i;
 575           }
 576         }
 577       } else {
 578         d--;
 579         if (!(opt & OPT_MAX)) {
 580           if (d < dm) {
 581             dm = d;  im = i;
 582           }
 583         }
 584       }
 585       i++;
 586     }
 587   }
 588   return im;
 589 }
 590
 591
 592
 593 int bp_rank_open(bp *b, int s)
 594 {
 595   return bp_darray_rank(b->da, s);
 596 }
 597
 598 int bp_rank_close(bp *b, int s)
 599 {
 600   return s+1 - bp_darray_rank(b->da, s);
 601 }
 602
 603 int bp_select_open(bp *b, int s)
 604 {
 605   if (b->opt & OPT_FAST_PREORDER_SELECT) {
 606     return bp_darray_select(b->da,s,1);
 607   } else {
 608     return bp_darray_select_bsearch(b->da, s, getpat_preorder);
 609   }
 610 }
 611
 612 int bp_select_close(bp *b, int s)
 613 {
 614   if (b->opt & OPT_FAST_POSTORDER_SELECT) {
 615     return bp_darray_pat_select(b->da_postorder, s, getpat_postorder);
 616   } else {
 617     return postorder_select_bsearch(b,s);
 618   }
 619 }
 620
 621
 622 ///////////////////////////////////////////
 623 //  bp_postorder_rank(bp *b,int s)
 624 //    returns the postorder (>= 1) of node s (s >= 0)
 625 //            -1 if s-th bit is not OP
 626 ///////////////////////////////////////////
 627 int bp_postorder_rank(bp *b,int s)
 628 {
 629   int t;
 630   if (bp_inspect(b,s) == CP) return -1;
 631   t = bp_find_close(b,s);
 632   //  return t+1 - darray_rank(b->da,t);
 633   return bp_rank_close(b,t);
 634 }
 635
 636 static int postorder_select_bsearch(bp *b,int s)
 637 {
 638   int l,r,m;
 639
 640   if (s == 0) return -1;
 641
 642   if (s > b->da->n - b->da->m) {
 643     return -1;
 644   }
 645   l = 0;  r = b->da->n - 1;
 646
 647   while (l < r) {
 648     m = (l+r)/2;
 649     //printf("m=%d rank=%d s=%d\n",m,m+1 - darray_rank(b->da,m),s);
 650     if (m+1 - bp_darray_rank(b->da,m) >= s) {
 651       r = m;
 652     } else {
 653       l = m+1;
 654     }
 655   }
 656   return l;
 657 }
 658
 659 ///////////////////////////////////////////
 660 //  bp_postorder_select(bp *b,int s)
 661 //    returns the position of CP of the node with postorder s (>= 1)
 662 ///////////////////////////////////////////
 663 int bp_postorder_select(bp *b,int s)
 664 {
 665 #if 0
 666   if (b->opt & OPT_FAST_POSTORDER_SELECT) {
 667     return bp_darray_pat_select(b->da_postorder,s,getpat_postorder);
 668   } else {
 669     return postorder_select_bsearch(b->da,s);
 670   }
 671 #else
 672   return bp_select_close(b,s);
 673 #endif
 674 }
 675
 676 ///////////////////////////////////////////
 677 //  bp_leaf_rank(bp *b,int s)
 678 //    returns the number of leaves to the left of s
 679 ///////////////////////////////////////////
 680 int bp_leaf_rank(bp *b,int s)
 681 {
 682   if ((b->opt & OPT_LEAF) == 0) {
 683     printf("leaf_rank: error!!!   not supported\n");
 684     return -1;
 685   }
 686   if (s >= b->n-1) {
 687     s = b->n-2;
 688   }
 689   return bp_darray_pat_rank(b->da_leaf,s,getpat_leaf);
 690 }
 691
 692 ///////////////////////////////////////////
 693 //  leaf_select(bp *b,int s)
 694 //    returns the position of s-th leaf
 695 ///////////////////////////////////////////
 696 int bp_leaf_select(bp *b,int s)
 697 {
 698   if ((b->opt & OPT_LEAF) == 0) {
 699     printf("leaf_select: error!!!   not supported\n");
 700     return -1;
 701   }
 702   if (s > b->da_leaf->m) return -1;
 703   if (b->opt & OPT_FAST_LEAF_SELECT) {
 704     return bp_darray_pat_select(b->da_leaf,s,getpat_leaf);
 705   } else {
 706     return bp_darray_select_bsearch(b->da_leaf,s,getpat_leaf);
 707   }
 708 }
 709
 710
 711 ///////////////////////////////////////////
 712 //  bp_inorder_rank(bp *b,int s)
 713 //    returns the number of ")("  (s >= 0)
 714 ///////////////////////////////////////////
 715 int bp_inorder_rank(bp *b,int s)
 716 {
 717   if ((b->opt & OPT_INORDER) == 0) {
 718     printf("inorder_rank: error!!!   not supported\n");
 719     return -1;
 720   }
 721   if (s >= b->n-1) {
 722     s = b->n-2;
 723   }
 724   return bp_darray_pat_rank(b->da_inorder,s,getpat_inorder);
 725 }
 726
 727 ///////////////////////////////////////////
 728 //  bp_inorder_select(bp *b,int s)
 729 //    returns the s-th position of ")("  (s >= 1)
 730 ///////////////////////////////////////////
 731 int bp_inorder_select(bp *b,int s)
 732 {
 733   if ((b->opt & OPT_INORDER) == 0) {
 734     printf("inorder_select: error!!!   not supported\n");
 735     return -1;
 736   }
 737   if (b->opt & OPT_FAST_INORDER_SELECT) {
 738     return bp_darray_pat_select(b->da_inorder,s,getpat_inorder);
 739   } else {
 740     return bp_darray_select_bsearch(b->da_inorder,s,getpat_inorder);
 741   }
 742 }
 743
 744 ///////////////////////////////////////////
 745 //  bp_leftmost_leaf(bp *b, int s)
 746 ///////////////////////////////////////////
 747 int bp_leftmost_leaf(bp *b, int s)
 748 {
 749   if ((b->opt & OPT_LEAF) == 0) {
 750     printf("leftmost_leaf: error!!!   not supported\n");
 751     return -1;
 752   }
 753   return bp_leaf_select(b, bp_leaf_rank(b,s)+1);
 754 }
 755
 756 ///////////////////////////////////////////
 757 //  rightmost_leaf(bp *b, int s)
 758 ///////////////////////////////////////////
 759 int bp_rightmost_leaf(bp *b, int s)
 760 {
 761   int t;
 762   if ((b->opt & OPT_LEAF) == 0) {
 763     printf("leftmost_leaf: error!!!   not supported\n");
 764     return -1;
 765   }
 766   t = bp_find_close(b,s);
 767   return bp_leaf_select(b, bp_leaf_rank(b,t));
 768 }
 769
 770
 771 ///////////////////////////////////////////
 772 //  bp_prev_sibling(bp *b,int s)
 773 //    returns the previous sibling of parent(s)
 774 //            -1 if s is the first child
 775 //////////////////////////////////////////
 776 int bp_prev_sibling(bp *b, int s)
 777 {
 778   int t;
 779   if (s == 0) return -1;
 780   if (bp_inspect(b,s-1) == OP) return -1;
 781   t = bp_find_open(b,s-1);
 782   return t;
 783 }
 784
 785 ///////////////////////////////////////////
 786 //  bp_deepest_node(bp *b,int s)
 787 //    returns the first node with the largest depth in the subtree of s
 788 ///////////////////////////////////////////
 789 int bp_deepest_node(bp *b,int s)
 790 {
 791   int t,m;
 792   t = bp_find_close(b,s);
 793   m = bp_rmq(b,s,t, OPT_MAX);
 794   return m;
 795 }
 796
 797 ///////////////////////////////////////////
 798 //  bp_subtree_height(bp *b,int s)
 799 //    returns the height of the subtree of s
 800 //            0 if s is a leaf
 801 ///////////////////////////////////////////
 802 int bp_subtree_height(bp *b,int s)
 803 {
 804   int t;
 805   t = bp_deepest_node(b,s);
 806   return bp_depth(b,t) - bp_depth(b,s);
 807 }
 808
 809 int bp_naive_degree(bp *b, int s)
 810 {
 811   int t,d;
 812   d = 0;
 813   t = bp_first_child(b,s);
 814   while (t >= 0) {
 815     d++;
 816     t = bp_next_sibling(b,t);
 817   }
 818   return d;
 819 }
 820
 821 ///////////////////////////////////////////
 822 //  bp_degree(bp *b, int s)
 823 //    returns the number of children of s
 824 //            0 if s is a leaf
 825 ///////////////////////////////////////////
 826 int bp_degree(bp *b, int s)
 827 {
 828   if (b->opt & OPT_DEGREE) {
 829     return bp_fast_degree(b,s,b->n,0);
 830   } else {
 831     return bp_naive_degree(b,s);
 832   }
 833 }
 834
 835 int bp_naive_child(bp *b, int s, int d)
 836 {
 837   int t,i;
 838   t = bp_first_child(b,s);
 839   for (i = 1; i < d; i++) {
 840     if (t == -1) break;
 841     t = bp_next_sibling(b,t);
 842   }
 843   return t;
 844 }
 845
 846 ///////////////////////////////////////////
 847 //  bp_child(bp *b, int s, int d)
 848 //    returns the d-th child of s  (1 <= d <= degree(s))
 849 //            -1 if no such node
 850 ///////////////////////////////////////////
 851 int bp_child(bp *b, int s, int d)
 852 {
 853   int r;
 854   if (b->opt & OPT_DEGREE) {
 855     //return find_open(b,fast_degree(b,s,b->n,d));
 856     if (d==1) return bp_first_child(b,s);
 857     r = bp_fast_degree(b,s,b->n,d-1)+1;
 858     if (bp_inspect(b,r) == CP) return -1;
 859     return r;
 860   } else {
 861     return bp_naive_child(b,s,d);
 862   }
 863
 864 }
 865
 866
 867 int bp_naive_child_rank(bp *b, int t)
 868 {
 869   int v,d;
 870   d = 0;
 871   while (t != -1) {
 872     d++;
 873     t = bp_prev_sibling(b,t);
 874   }
 875   return d;
 876 }
 877
 878 ///////////////////////////////////////////
 879 //  bp_child_rank(bp *b, int t)
 880 //    returns d if t is the d-th child of the parent of t (d >= 1)
 881 //            1 if t is the root
 882 ///////////////////////////////////////////
 883 int bp_child_rank(bp *b, int t)
 884 {
 885   int r;
 886   if (t == bp_root_node(b)) return 1;
 887   if (b->opt & OPT_DEGREE) {
 888     r = bp_parent(b,t);
 889     return bp_fast_degree(b,r,t,0)+1;
 890   } else {
 891     return bp_naive_child_rank(b,t);
 892   }
 893 }
 894
 895
 896 ///////////////////////////////////////////
 897 //  distance(bp *b, int s, int t)
 898 //    returns the length of the shortest path from s to t in the tree
 899 ///////////////////////////////////////////
 900 int bp_distance(bp *b, int s, int t)
 901 {
 902   int v,d;
 903   v = bp_lca(b,s,t);
 904   d = bp_depth(b,v);
 905   return (bp_depth(b,s) - d) + (bp_depth(b,t) - d);
 906 }
 907
 908 ///////////////////////////////////////////
 909 //  level_next(bp *b, int d)
 910 ///////////////////////////////////////////
 911 int bp_level_next(bp *b,int s)
 912 {
 913   int t;
 914   t = bp_fwd_excess(b,s,0);
 915   return t;
 916 }
 917
 918 ///////////////////////////////////////////
 919 //  level_prev(bp *b, int d)
 920 ///////////////////////////////////////////
 921 int bp_level_prev(bp *b,int s)
 922 {
 923   int t;
 924   t = bp_bwd_excess(b,s,0);
 925   return t;
 926 }
 927
 928 ///////////////////////////////////////////
 929 //  bp_level_leftmost(bp *b, int d)
 930 ///////////////////////////////////////////
 931 int bp_level_leftmost(bp *b, int d)
 932 {
 933   int t;
 934   if (d < 1) return -1;
 935   if (d == 1) return 0;
 936   t = bp_fwd_excess(b,0,d);
 937   return t;
 938 }
 939
 940 ///////////////////////////////////////////
 941 //  bp_level_rigthmost(bp *b, int d)
 942 ///////////////////////////////////////////
 943 int level_rigthmost(bp *b, int d)
 944 {
 945   int t;
 946   if (d < 1) return -1;
 947   if (d == 1) return 0;
 948   t = bp_bwd_excess(b,0,d-1);
 949   return bp_find_open(b,t);
 950 }
 951
 952 ///////////////////////////////////////////
 953 //  leaf_size(bp *b, int s)
 954 ///////////////////////////////////////////
 955 int bp_leaf_size(bp *b, int s)
 956 {
 957   int t;
 958   if ((b->opt & OPT_LEAF) == 0) {
 959     printf("leaf_size: error!!!   not supported\n");
 960     return -1;
 961   }
 962   t = bp_find_close(b,s);
 963   return bp_leaf_rank(b,t) - bp_leaf_rank(b,s);
 964 }