7 #define mymalloc(p,n,f) {p =(__typeof__(p)) malloc((n)*sizeof(*p)); msize += (f)*(n)*sizeof(*p); /* if (f) printf("malloc %d bytes at line %d total %d\n",(n)*sizeof(*p),__LINE__,msize); */ if ((p)==NULL) {printf("not enough memory (%d bytes) in line %d\n",msize,__LINE__); exit(1);};}
\r
9 int postorder_select_bsearch(bp *b,int s);
\r
11 int naive_depth(bp *b, int s)
\r
14 if (s < 0) return 0;
\r
16 for (i=0; i<=s; i++) {
\r
17 if (getbit(b->B,i)==OP) {
\r
26 void printbp(bp *b, int s, int t)
\r
30 for (i=s; i<=t; i++) {
\r
31 if (getbit(b->B,i)==OP) {
\r
42 int *matchtbl,*parenttbl;
\r
43 void make_naivetbl(pb *B,int n)
\r
48 mymalloc(matchtbl,n,0);
\r
49 mymalloc(parenttbl,n,0);
\r
50 mymalloc(stack,n,0);
\r
52 for (i=0; i<n; i++) matchtbl[i] = parenttbl[i] = -1;
\r
57 for (i=0; i<n; i++) {
\r
58 if (getbit(B,i)==OP) {
\r
61 parenttbl[i] = stack[v-1];
\r
66 matchtbl[stack[v]] = i; // close
\r
67 matchtbl[i] = stack[v]; // open
\r
76 int popCount[1<<ETW];
\r
77 int fwdtbl[(2*ETW+1)*(1<<ETW)];
\r
78 int bwdtbl[(2*ETW+1)*(1<<ETW)];
\r
80 int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];
\r
81 int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];
\r
82 int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];
\r
83 int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];
\r
85 int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];
\r
87 int degtbl2[(2*ETW+1)*(1<<ETW)];
\r
88 int childtbl[(ETW)*(1<<ETW)];
\r
89 int childtbl2[2*ETW+1][ETW][(1<<ETW)];
\r
90 int depthtbl[(2*ETW+1)*(1<<ETW)];
\r
92 void make_matchtbl(void)
\r
99 for (x = 0; x < (1<<ETW); x++) {
\r
100 setbits(buf,0,ETW,x);
\r
101 for (r=-ETW; r<=ETW; r++) fwdtbl[((r+ETW)<<ETW)+x] = ETW;
\r
102 for (r=-ETW; r<=ETW; r++) bwdtbl[((r+ETW)<<ETW)+x] = ETW;
\r
103 for (r=-ETW; r<=ETW; r++) degtbl2[((r+ETW)<<ETW)+x] = 0;
\r
104 for (r=-ETW; r<=ETW; r++) depthtbl[((r+ETW)<<ETW)+x] = 0;
\r
107 for (i=0; i<ETW; i++) {
\r
108 if (getbit(buf,i)==OP) {
\r
113 if (fwdtbl[((r+ETW)<<ETW)+x] == ETW) fwdtbl[((r+ETW)<<ETW)+x] = i;
\r
117 for (i=ETW-1; i>=0; i--) {
\r
118 if (getbit(buf,i)==OP) {
\r
123 if (bwdtbl[((r+ETW)<<ETW)+x] == ETW) bwdtbl[((r+ETW)<<ETW)+x] = ETW-1-i;
\r
127 for (i=0; i<ETW; i++) {
\r
128 if (getbit(buf,i)==OP) {
\r
133 depthtbl[((r+ETW)<<ETW)+x] += (1<<(ETW-1));
\r
137 for (i=0; i<ETW; i++) {
\r
138 if (getbit(buf,i)==OP) r++;
\r
142 r = 0; m = 0; M = 0;
\r
143 m = ETW+1; M = -ETW-1;
\r
144 //maxtbl_lv[x] = -ETW-1;
\r
145 //mintbl_lv[x] = ETW+1;
\r
146 minmaxtbl_v[OPT_MAX | OPT_LEFT][x] = -ETW-1;
\r
147 minmaxtbl_v[OPT_MIN | OPT_LEFT][x] = ETW+1;
\r
149 for (i=0; i<ETW; i++) {
\r
150 if (getbit(buf,i)==OP) {
\r
154 //maxtbl_li[x] = i; maxtbl_lv[x] = r;
\r
155 minmaxtbl_i[OPT_MAX | OPT_LEFT][x] = i;
\r
156 minmaxtbl_v[OPT_MAX | OPT_LEFT][x] = r;
\r
162 childtbl[((deg-1)<<ETW) + x] = i;
\r
166 //mintbl_li[x] = i; mintbl_lv[x] = r;
\r
167 minmaxtbl_i[OPT_MIN | OPT_LEFT][x] = i;
\r
168 minmaxtbl_v[OPT_MIN | OPT_LEFT][x] = r;
\r
170 childtbl[((deg-1)<<ETW) + x] = i;
\r
173 if (r <= m) degtbl2[((r+ETW)<<ETW)+x]++;
\r
177 r = 0; m = 0; M = 0;
\r
178 //maxtbl_rv[x] = -ETW-1;
\r
179 //mintbl_rv[x] = ETW+1;
\r
180 minmaxtbl_v[OPT_MAX | OPT_RIGHT][x] = -ETW-1;
\r
181 minmaxtbl_v[OPT_MIN | OPT_RIGHT][x] = ETW+1;
\r
182 for (i=0; i<ETW; i++) {
\r
183 if (getbit(buf,i)==OP) {
\r
187 //maxtbl_ri[x] = i; maxtbl_rv[x] = r;
\r
188 minmaxtbl_i[OPT_MAX | OPT_RIGHT][x] = i;
\r
189 minmaxtbl_v[OPT_MAX | OPT_RIGHT][x] = r;
\r
195 //mintbl_ri[x] = i; mintbl_rv[x] = r;
\r
196 minmaxtbl_i[OPT_MIN | OPT_RIGHT][x] = i;
\r
197 minmaxtbl_v[OPT_MIN | OPT_RIGHT][x] = r;
\r
202 for (i = 0; i < ETW; i++) {
\r
203 for (j = -ETW; j <= ETW; j++) {
\r
204 childtbl2[j+ETW][i][x] = -1;
\r
208 for (j=-ETW; j<=ETW; j++) {
\r
212 for (i = 0; i < ETW; i++) {
\r
213 if (getbit(buf,i)==OP) {
\r
220 childtbl2[j+ETW][ith-1][x] = i;
\r
230 int bp_construct(bp *b,int n, pb *B, int opt)
\r
240 int r; // # of minimum values
\r
244 printf("warning: SB=%d should be a multiple of D=%d\n",SB,D);
\r
245 // not necessarily?
\r
247 if (SB % RRR != 0) {
\r
248 printf("warning: SB=%d should be a multiple of RRR=%d\n",SB,RRR);
\r
263 b->da_inorder = NULL;
\r
264 b->da_postorder = NULL;
\r
265 b->da_dfuds_leaf = NULL;
\r
266 mymalloc(b->da,1,0);
\r
267 darray_construct(b->da,n,B, opt & OPT_FAST_PREORDER_SELECT);
\r
268 b->idx_size += b->da->idx_size;
\r
269 //Kim: comment this and the following, they polute the printing of the xpath library
\r
270 //printf("preorder rank/select table: %d bytes (%1.2f bpc)\n",b->da->idx_size,(double)b->da->idx_size*8/n);
\r
275 mymalloc(sm, ns, 0); b->idx_size += ns * sizeof(*sm);
\r
276 mymalloc(sM, ns, 0); b->idx_size += ns * sizeof(*sM);
\r
279 if (opt & OPT_DEGREE) {
\r
280 mymalloc(sd, ns, 0); b->idx_size += ns * sizeof(*sd);
\r
282 //printf("SB degree table: %d bytes (%1.2f bpc)\n",ns * sizeof(*sd), (double)ns * sizeof(*sd) * 8/n);
\r
284 //printf("SB table: %d bytes (%1.2f bpc)\n",ns * sizeof(*sm) * 2, (double)ns * sizeof(*sm)*2 * 8/n);
\r
286 for (i=0; i<n; i++) {
\r
300 if (i % SB == SB-1 || i==n-1) {
\r
301 ds = depth(b,(i/SB)*SB-1);
\r
302 if (m - ds + SB < 0 || m - ds + SB > 255) {
\r
303 printf("error m=%d ds=%d\n",m,ds);
\r
305 if (M - ds + 1 < 0 || M - ds + 1 > 255) {
\r
306 printf("error M=%d ds=%d\n",M,ds);
\r
308 sm[i/SB] = m - ds + SB;
\r
309 sM[i/SB] = M - ds + 1;
\r
310 if (opt & OPT_DEGREE) sd[i/SB] = r;
\r
316 for (i=0;i<n/SB;i++) printf("%d ",sd[i]);
\r
322 m_ofs = 1 << blog(nm-1);
\r
325 mymalloc(mm, nm + m_ofs, 0); b->idx_size += (nm+m_ofs) * sizeof(*mm);
\r
326 mymalloc(mM, nm + m_ofs, 0); b->idx_size += (nm+m_ofs) * sizeof(*mM);
\r
329 if (opt & OPT_DEGREE) {
\r
330 mymalloc(md, nm + m_ofs, 0); b->idx_size += (nm+m_ofs) * sizeof(*md);
\r
332 //printf("MB degree table: %d bytes (%1.2f bpc)\n",(nm+m_ofs) * sizeof(*md), (double)(nm+m_ofs) * sizeof(*md) * 8/n);
\r
334 //printf("MB table: %d bytes (%1.2f bpc)\n",(nm+m_ofs) * sizeof(*mm) * 2, (double)(nm+m_ofs) * sizeof(*mm)*2 * 8/n);
\r
336 for (i=0; i<n; i++) {
\r
349 if (i % MB == MB-1 || i==n-1) {
\r
350 mm[m_ofs+ i/MB] = m;
\r
351 mM[m_ofs+ i/MB] = M;
\r
352 if (opt & OPT_DEGREE) md[m_ofs+ i/MB] = r;
\r
356 for (j=m_ofs-1; j > 0; j--) {
\r
358 if (j*2 < nm + m_ofs) m = mm[j*2];
\r
359 if (j*2+1 < nm + m_ofs) m = min(m,mm[j*2+1]);
\r
361 if (j*2 < nm + m_ofs) M = mM[j*2];
\r
362 if (j*2+1 < nm + m_ofs) M = max(M,mM[j*2+1]);
\r
363 mm[j] = m; mM[j] = M;
\r
364 if (opt & OPT_DEGREE) {
\r
366 if (j*2 < nm + m_ofs) d = md[j*2];
\r
367 if (j*2+1 < nm + m_ofs) {
\r
368 if (mm[j*2] == mm[j*2+1]) d += md[j*2+1];
\r
369 if (mm[j*2] > mm[j*2+1]) d = md[j*2+1];
\r
376 if (opt & OPT_DEGREE) {
\r
383 for (i=0;i<m_ofs + n/MB;i++) printf("%d ",md[i]);
\r
387 if (opt & OPT_LEAF) {
\r
388 mymalloc(b->da_leaf,1,0);
\r
389 darray_pat_construct(b->da_leaf, n, B, 2, 0x2, opt & OPT_FAST_LEAF_SELECT);
\r
390 //printf("leaf rank/select table: %d bytes (%1.2f bpc)\n",b->da_leaf->idx_size,(double)b->da_leaf->idx_size*8/n);
\r
391 b->idx_size += b->da_leaf->idx_size;
\r
396 if (opt & OPT_INORDER) {
\r
397 mymalloc(b->da_inorder,1,0);
\r
398 darray_pat_construct(b->da_inorder, n, B, 2, 0x1, opt & OPT_FAST_INORDER_SELECT);
\r
399 //printf("inorder rank/select table: %d bytes (%1.2f bpc)\n",b->da_inorder->idx_size,(double)b->da_inorder->idx_size*8/n);
\r
400 b->idx_size += b->da_inorder->idx_size;
\r
402 b->da_inorder = NULL;
\r
405 if (opt & OPT_FAST_POSTORDER_SELECT) {
\r
406 mymalloc(b->da_postorder,1,0);
\r
407 darray_pat_construct(b->da_postorder, n, B, 1, 0x0, (opt & OPT_FAST_POSTORDER_SELECT) | OPT_NO_RANK);
\r
408 //printf("postorder rank/select table: %d bytes (%1.2f bpc)\n",b->da_postorder->idx_size,(double)b->da_postorder->idx_size*8/n);
\r
409 b->idx_size += b->da_postorder->idx_size;
\r
411 b->da_postorder = NULL;
\r
414 if (opt & OPT_DFUDS_LEAF) {
\r
415 mymalloc(b->da_dfuds_leaf,1,0);
\r
416 darray_pat_construct(b->da_dfuds_leaf, n, B, 2, 0x0, opt & OPT_FAST_DFUDS_LEAF_SELECT);
\r
417 //printf("dfuds leaf rank/select table: %d bytes (%1.2f bpc)\n",b->da_dfuds_leaf->idx_size,(double)b->da_dfuds_leaf->idx_size*8/n);
\r
418 b->idx_size += b->da_dfuds_leaf->idx_size;
\r
420 b->da_dfuds_leaf = NULL;
\r
426 // destroyTree: frees the memory of tree.
\r
427 void destroyTree(bp *b) {
\r
428 if (!b) return; // nothing to free
\r
430 destroyDarray(b->da); // destroys da data structure
\r
431 if (b->da) free(b->da);
\r
433 if (b->sm) free(b->sm);
\r
434 if (b->sM) free(b->sM);
\r
435 if (b->sd) free(b->sd);
\r
436 if (b->mm) free(b->mm);
\r
437 if (b->mM) free(b->mM);
\r
438 if (b->md) free(b->md);
\r
440 destroyDarray(b->da_leaf);
\r
441 if (b->da_leaf) free(b->da_leaf);
\r
443 destroyDarray(b->da_inorder);
\r
444 if (b->da_inorder) free(b->da_inorder);
\r
446 destroyDarray(b->da_postorder);
\r
447 if (b->da_postorder) free(b->da_postorder);
\r
449 destroyDarray(b->da_dfuds_leaf);
\r
450 if (b->da_dfuds_leaf) free(b->da_dfuds_leaf);
\r
454 // saveTree: saves parentheses data structure to file
\r
455 // By Diego Arroyuelo
\r
456 void saveTree(bp *b, FILE *fp) {
\r
458 if (fwrite(&(b->n), sizeof(int), 1, fp) != 1) {
\r
459 printf("Error: cannot save number of parentheses to file\n");
\r
463 if (fwrite(b->B, sizeof(pb), (b->n+D-1)/D, fp) != ((b->n+D-1)/D)) {
\r
464 printf("Error: cannot save parentheses sequence to file\n");
\r
468 if (fwrite(&(b->opt), sizeof(int), 1, fp) != 1) {
\r
469 printf("Error: cannot save opt in parentheses to file\n");
\r
474 // loadTree: load parentheses data structure from file
\r
475 // By Diego Arroyuelo
\r
476 void loadTree(bp *b, FILE *fp) {
\r
481 if (fread(&n, sizeof(int), 1, fp) != 1) {
\r
482 printf("Error: cannot read number of parentheses from file\n");
\r
486 mymalloc(B,(n+D-1)/D,0);
\r
488 if (fread(B, sizeof(pb), (n+D-1)/D, fp) != ((n+D-1)/D)) {
\r
489 printf("Error: cannot read parentheses sequence from file\n");
\r
493 if (fread(&opt, sizeof(int), 1, fp) != 1) {
\r
494 printf("Error: cannot read opt in parentheses from file\n");
\r
498 bp_construct(b, n, B, opt);
\r
504 int naive_fwd_excess(bp *b,int s, int rel)
\r
508 n = b->n; B = b->B;
\r
510 for (i=s+1; i<n; i++) {
\r
511 if (getbit(B,i)==OP) {
\r
516 if (v == rel) return i;
\r
521 int naive_bwd_excess(bp *b,int s, int rel)
\r
527 for (i=s; i>=0; i--) {
\r
528 if (getbit(B,i)==OP) {
\r
533 if (v == rel) return i-1;
\r
538 int naive_search_SB_l(bp *b, int i, int rel)
\r
542 il = (i / SB) * SB;
\r
543 for (; i>=il; i--) {
\r
544 if (getbit(b->B,i)==OP) {
\r
549 if (rel == 0) return i-1;
\r
551 if (i < 0) return -2;
\r
555 int naive_rmq(bp *b, int s, int t,int opt)
\r
559 if (opt & OPT_RIGHT) {
\r
560 d = dm = depth(b,t); im = t;
\r
563 if (getbit(b->B,i+1)==CP) {
\r
565 if (opt & OPT_MAX) {
\r
572 if (!(opt & OPT_MAX)) {
\r
581 d = dm = depth(b,s); im = s;
\r
584 if (getbit(b->B,i)==OP) {
\r
586 if (opt & OPT_MAX) {
\r
593 if (!(opt & OPT_MAX)) {
\r
605 int root_node(bp *b)
\r
611 int rank_open(bp *b, int s)
\r
613 return darray_rank(b->da,s);
\r
616 int rank_close(bp *b, int s)
\r
618 return s+1 - darray_rank(b->da,s);
\r
621 int select_open(bp *b, int s)
\r
623 if (b->opt & OPT_FAST_PREORDER_SELECT) {
\r
624 return darray_select(b->da,s,1);
\r
626 return darray_select_bsearch(b->da,s,getpat_preorder);
\r
630 int select_close(bp *b, int s)
\r
632 if (b->opt & OPT_FAST_POSTORDER_SELECT) {
\r
633 return darray_pat_select(b->da_postorder,s,getpat_postorder);
\r
635 return postorder_select_bsearch(b,s);
\r
639 ///////////////////////////////////////////
\r
640 // find_close(bp *b,int s)
\r
641 // returns the matching close parenthesis of s
\r
642 ///////////////////////////////////////////
\r
643 int find_close(bp *b,int s)
\r
645 return fwd_excess(b,s,-1);
\r
648 ///////////////////////////////////////////
\r
649 // find_open(bp *b,int s)
\r
650 // returns the matching open parenthesis of s
\r
651 ///////////////////////////////////////////
\r
652 int find_open(bp *b,int s)
\r
655 r = bwd_excess(b,s,0);
\r
656 if (r >= -1) return r+1;
\r
660 ///////////////////////////////////////////
\r
661 // parent(bp *b,int s)
\r
662 // returns the parent of s
\r
663 // -1 if s is the root
\r
664 ///////////////////////////////////////////
\r
665 int parent(bp *b,int s)
\r
668 r = bwd_excess(b,s,-2);
\r
669 if (r >= -1) return r+1;
\r
673 int enclose(bp *b,int s)
\r
675 return parent(b,s);
\r
678 ///////////////////////////////////////////
\r
679 // level_ancestor(bp *b,int s,int d)
\r
680 // returns the ancestor of s with relative depth d (d < 0)
\r
681 // -1 if no such node
\r
682 ///////////////////////////////////////////
\r
683 int level_ancestor(bp *b,int s,int d)
\r
686 r = bwd_excess(b,s,d-1);
\r
687 if (r >= -1) return r+1;
\r
691 ///////////////////////////////////////////
\r
692 // lca(bp *b, int s, int t)
\r
693 // returns the lowest common ancestor of s and t
\r
694 ///////////////////////////////////////////
\r
695 int lca(bp *b, int s, int t)
\r
697 return parent(b,rmq(b,s,t,0)+1);
\r
701 ///////////////////////////////////////////
\r
702 // preorder_rank(bp *b,int s)
\r
703 // returns the preorder (>= 1) of node s (s >= 0)
\r
704 ///////////////////////////////////////////
\r
705 int preorder_rank(bp *b,int s)
\r
707 return darray_rank(b->da,s);
\r
710 ///////////////////////////////////////////
\r
711 // preorder_select(bp *b,int s)
\r
712 // returns the node with preorder s (s >= 1)
\r
713 // -1 if no such node
\r
714 ///////////////////////////////////////////
\r
715 int preorder_select(bp *b,int s)
\r
717 // no error handling
\r
718 if (b->opt & OPT_FAST_PREORDER_SELECT) {
\r
719 return darray_select(b->da,s,1);
\r
721 return darray_select_bsearch(b->da,s,getpat_preorder);
\r
725 ///////////////////////////////////////////
\r
726 // postorder_rank(bp *b,int s)
\r
727 // returns the postorder (>= 1) of node s (s >= 0)
\r
728 // -1 if s-th bit is not OP
\r
729 ///////////////////////////////////////////
\r
730 int postorder_rank(bp *b,int s)
\r
733 if (inspect(b,s) == CP) return -1;
\r
734 t = find_close(b,s);
\r
735 // return t+1 - darray_rank(b->da,t);
\r
736 return rank_close(b,t);
\r
739 int postorder_select_bsearch(bp *b,int s)
\r
743 if (s == 0) return -1;
\r
745 if (s > b->da->n - b->da->m) {
\r
748 l = 0; r = b->da->n - 1;
\r
752 //printf("m=%d rank=%d s=%d\n",m,m+1 - darray_rank(b->da,m),s);
\r
753 if (m+1 - darray_rank(b->da,m) >= s) {
\r
762 ///////////////////////////////////////////
\r
763 // postorder_select(bp *b,int s)
\r
764 // returns the position of CP of the node with postorder s (>= 1)
\r
765 ///////////////////////////////////////////
\r
766 int postorder_select(bp *b,int s)
\r
769 if (b->opt & OPT_FAST_POSTORDER_SELECT) {
\r
770 return darray_pat_select(b->da_postorder,s,getpat_postorder);
\r
772 return postorder_select_bsearch(b->da,s);
\r
775 return select_close(b,s);
\r
779 ///////////////////////////////////////////
\r
780 // leaf_rank(bp *b,int s)
\r
781 // returns the number of leaves to the left of s
\r
782 ///////////////////////////////////////////
\r
783 int leaf_rank(bp *b,int s)
\r
785 if ((b->opt & OPT_LEAF) == 0) {
\r
786 printf("leaf_rank: error!!! not supported\n");
\r
792 return darray_pat_rank(b->da_leaf,s,getpat_leaf);
\r
795 ///////////////////////////////////////////
\r
796 // leaf_select(bp *b,int s)
\r
797 // returns the position of s-th leaf
\r
798 ///////////////////////////////////////////
\r
799 int leaf_select(bp *b,int s)
\r
801 if ((b->opt & OPT_LEAF) == 0) {
\r
802 printf("leaf_select: error!!! not supported\n");
\r
805 if (s > b->da_leaf->m) return -1;
\r
806 if (b->opt & OPT_FAST_LEAF_SELECT) {
\r
807 return darray_pat_select(b->da_leaf,s,getpat_leaf);
\r
809 return darray_select_bsearch(b->da_leaf,s,getpat_leaf);
\r
814 ///////////////////////////////////////////
\r
815 // inorder_rank(bp *b,int s)
\r
816 // returns the number of ")(" (s >= 0)
\r
817 ///////////////////////////////////////////
\r
818 int inorder_rank(bp *b,int s)
\r
820 if ((b->opt & OPT_INORDER) == 0) {
\r
821 printf("inorder_rank: error!!! not supported\n");
\r
827 return darray_pat_rank(b->da_inorder,s,getpat_inorder);
\r
830 ///////////////////////////////////////////
\r
831 // inorder_select(bp *b,int s)
\r
832 // returns the s-th position of ")(" (s >= 1)
\r
833 ///////////////////////////////////////////
\r
834 int inorder_select(bp *b,int s)
\r
836 if ((b->opt & OPT_INORDER) == 0) {
\r
837 printf("inorder_select: error!!! not supported\n");
\r
840 if (b->opt & OPT_FAST_INORDER_SELECT) {
\r
841 return darray_pat_select(b->da_inorder,s,getpat_inorder);
\r
843 return darray_select_bsearch(b->da_inorder,s,getpat_inorder);
\r
847 ///////////////////////////////////////////
\r
848 // leftmost_leaf(bp *b, int s)
\r
849 ///////////////////////////////////////////
\r
850 int leftmost_leaf(bp *b, int s)
\r
852 if ((b->opt & OPT_LEAF) == 0) {
\r
853 printf("leftmost_leaf: error!!! not supported\n");
\r
856 return leaf_select(b,leaf_rank(b,s)+1);
\r
859 ///////////////////////////////////////////
\r
860 // rightmost_leaf(bp *b, int s)
\r
861 ///////////////////////////////////////////
\r
862 int rightmost_leaf(bp *b, int s)
\r
865 if ((b->opt & OPT_LEAF) == 0) {
\r
866 printf("leftmost_leaf: error!!! not supported\n");
\r
869 t = find_close(b,s);
\r
870 return leaf_select(b,leaf_rank(b,t));
\r
875 ///////////////////////////////////////////
\r
876 // inspect(bp *b, int s)
\r
877 // returns OP (==1) or CP (==0) at s-th bit (0 <= s < n)
\r
878 ///////////////////////////////////////////
\r
879 int inspect(bp *b, int s)
\r
881 if (s < 0 || s >= b->n) {
\r
882 printf("inspect: error s=%d is out of [%d,%d]\n",s,0,b->n-1);
\r
884 return getbit(b->B,s);
\r
887 int isleaf(bp *b, int s)
\r
889 if (inspect(b,s) != OP) {
\r
890 printf("isleaf: error!!! B[%d] = OP\n",s);
\r
892 if (inspect(b,s+1) == CP) return 1;
\r
897 ///////////////////////////////////////////
\r
898 // subtree_size(bp *b, int s)
\r
899 // returns the number of nodes in the subtree of s
\r
900 ///////////////////////////////////////////
\r
901 int subtree_size(bp *b, int s)
\r
903 return (find_close(b,s) - s + 1) / 2;
\r
906 ///////////////////////////////////////////
\r
907 // first_child(bp *b, int s)
\r
908 // returns the first child
\r
909 // -1 if s is a leaf
\r
910 ///////////////////////////////////////////
\r
911 int first_child(bp *b, int s)
\r
913 if (inspect(b,s+1) == CP) return -1;
\r
917 ///////////////////////////////////////////
\r
918 // next_sibling(bp *b,int s)
\r
919 // returns the next sibling of parent(s)
\r
920 // -1 if s is the last child
\r
921 //////////////////////////////////////////
\r
922 int next_sibling(bp *b, int s)
\r
925 t = find_close(b,s)+1;
\r
927 printf("next_sibling: error s=%d t=%d\n",s,t);
\r
929 if (inspect(b,t) == CP) return -1;
\r
933 ///////////////////////////////////////////
\r
934 // prev_sibling(bp *b,int s)
\r
935 // returns the previous sibling of parent(s)
\r
936 // -1 if s is the first child
\r
937 //////////////////////////////////////////
\r
938 int prev_sibling(bp *b, int s)
\r
942 printf("prev_sibling: error s=%d\n",s);
\r
944 if (s == 0) return -1;
\r
945 if (inspect(b,s-1) == OP) return -1;
\r
946 t = find_open(b,s-1);
\r
950 ///////////////////////////////////////////
\r
951 // deepest_node(bp *b,int s)
\r
952 // returns the first node with the largest depth in the subtree of s
\r
953 ///////////////////////////////////////////
\r
954 int deepest_node(bp *b,int s)
\r
957 t = find_close(b,s);
\r
958 m = rmq(b,s,t, OPT_MAX);
\r
962 ///////////////////////////////////////////
\r
963 // subtree_height(bp *b,int s)
\r
964 // returns the height of the subtree of s
\r
965 // 0 if s is a leaf
\r
966 ///////////////////////////////////////////
\r
967 int subtree_height(bp *b,int s)
\r
970 t = deepest_node(b,s);
\r
971 return depth(b,t) - depth(b,s);
\r
974 int naive_degree(bp *b, int s)
\r
978 t = first_child(b,s);
\r
981 t = next_sibling(b,t);
\r
986 ///////////////////////////////////////////
\r
987 // degree(bp *b, int s)
\r
988 // returns the number of children of s
\r
989 // 0 if s is a leaf
\r
990 ///////////////////////////////////////////
\r
991 int degree(bp *b, int s)
\r
993 if (b->opt & OPT_DEGREE) {
\r
994 return fast_degree(b,s,b->n,0);
\r
996 return naive_degree(b,s);
\r
1000 int naive_child(bp *b, int s, int d)
\r
1003 t = first_child(b,s);
\r
1004 for (i = 1; i < d; i++) {
\r
1005 if (t == -1) break;
\r
1006 t = next_sibling(b,t);
\r
1011 ///////////////////////////////////////////
\r
1012 // child(bp *b, int s, int d)
\r
1013 // returns the d-th child of s (1 <= d <= degree(s))
\r
1014 // -1 if no such node
\r
1015 ///////////////////////////////////////////
\r
1016 int child(bp *b, int s, int d)
\r
1019 if (b->opt & OPT_DEGREE) {
\r
1020 //return find_open(b,fast_degree(b,s,b->n,d));
\r
1021 if (d==1) return first_child(b,s);
\r
1022 r = fast_degree(b,s,b->n,d-1)+1;
\r
1023 if (inspect(b,r) == CP) return -1;
\r
1026 return naive_child(b,s,d);
\r
1032 int naive_child_rank(bp *b, int t)
\r
1038 t = prev_sibling(b,t);
\r
1043 ///////////////////////////////////////////
\r
1044 // child_rank(bp *b, int t)
\r
1045 // returns d if t is the d-th child of the parent of t (d >= 1)
\r
1046 // 1 if t is the root
\r
1047 ///////////////////////////////////////////
\r
1048 int child_rank(bp *b, int t)
\r
1051 if (t == root_node(b)) return 1;
\r
1052 if (b->opt & OPT_DEGREE) {
\r
1054 return fast_degree(b,r,t,0)+1;
\r
1056 return naive_child_rank(b,t);
\r
1062 ///////////////////////////////////////////
\r
1063 // is_ancestor(bp *b, int s, int t)
\r
1064 // returns 1 if s is an ancestor of t
\r
1066 ///////////////////////////////////////////
\r
1067 int is_ancestor(bp *b, int s, int t)
\r
1070 v = find_close(b,s);
\r
1071 if (s <= t && t <= v) return 1;
\r
1075 ///////////////////////////////////////////
\r
1076 // distance(bp *b, int s, int t)
\r
1077 // returns the length of the shortest path from s to t in the tree
\r
1078 ///////////////////////////////////////////
\r
1079 int distance(bp *b, int s, int t)
\r
1084 return (depth(b,s) - d) + (depth(b,t) - d);
\r
1087 ///////////////////////////////////////////
\r
1088 // level_next(bp *b, int d)
\r
1089 ///////////////////////////////////////////
\r
1090 int level_next(bp *b,int s)
\r
1093 t = fwd_excess(b,s,0);
\r
1097 ///////////////////////////////////////////
\r
1098 // level_prev(bp *b, int d)
\r
1099 ///////////////////////////////////////////
\r
1100 int level_prev(bp *b,int s)
\r
1103 t = bwd_excess(b,s,0);
\r
1107 ///////////////////////////////////////////
\r
1108 // level_leftmost(bp *b, int d)
\r
1109 ///////////////////////////////////////////
\r
1110 int level_leftmost(bp *b, int d)
\r
1113 if (d < 1) return -1;
\r
1114 if (d == 1) return 0;
\r
1115 t = fwd_excess(b,0,d);
\r
1119 ///////////////////////////////////////////
\r
1120 // level_rigthmost(bp *b, int d)
\r
1121 ///////////////////////////////////////////
\r
1122 int level_rigthmost(bp *b, int d)
\r
1125 if (d < 1) return -1;
\r
1126 if (d == 1) return 0;
\r
1127 t = bwd_excess(b,0,d-1);
\r
1128 return find_open(b,t);
\r
1131 ///////////////////////////////////////////
\r
1132 // leaf_size(bp *b, int s)
\r
1133 ///////////////////////////////////////////
\r
1134 int leaf_size(bp *b, int s)
\r
1137 if ((b->opt & OPT_LEAF) == 0) {
\r
1138 printf("leaf_size: error!!! not supported\n");
\r
1141 t = find_close(b,s);
\r
1142 return leaf_rank(b,t) - leaf_rank(b,s);
\r