+++ /dev/null
-#include "bp.h"\r
-#include <algorithm>\r
-using std::min;\r
-using std::max;\r
-\r
-//#define CHECK\r
-#define RANDOM\r
-\r
-int msize=0;\r
-#define mymalloc(p,n,f) { \\r
- p = (__typeof__(p)) malloc((n)*sizeof(*p)); \\r
-if ((p)==NULL) {printf("not enough memory (%d bytes) in line %d\n",msize,__LINE__); \\r
- exit(1);}; \\r
-msize += (f)*(n)*sizeof(*p); \\r
-;}\r
-\r
-int postorder_select_bsearch(bp *b,int s);\r
-\r
-int naive_depth(bp *b, int s)\r
-{\r
- int i,d;\r
- if (s < 0) return 0;\r
- d = 0;\r
- for (i=0; i<=s; i++) {\r
- if (getbit(b->B,i)==OP) {\r
- d++;\r
- } else {\r
- d--;\r
- }\r
- }\r
- return d;\r
-}\r
-\r
-void printbp(bp *b, int s, int t)\r
-{\r
- int i,c,d;\r
- d = 0;\r
- for (i=s; i<=t; i++) {\r
- if (getbit(b->B,i)==OP) {\r
- c = '(';\r
- d++;\r
- } else {\r
- c = ')';\r
- d--;\r
- }\r
- putchar(c);\r
- }\r
-}\r
-\r
-int *matchtbl,*parenttbl;\r
-void make_naivetbl(pb *B,int n)\r
-{\r
- int i,v;\r
- int *stack,s;\r
-\r
- mymalloc(matchtbl,n,0);\r
- mymalloc(parenttbl,n,0);\r
- mymalloc(stack,n,0);\r
-\r
- for (i=0; i<n; i++) matchtbl[i] = parenttbl[i] = -1;\r
-\r
- s = 0;\r
- v = 0;\r
- stack[0] = -1;\r
- for (i=0; i<n; i++) {\r
- if (getbit(B,i)==OP) {\r
- v++;\r
- if (v > 0) {\r
- parenttbl[i] = stack[v-1];\r
- stack[v] = i;\r
- }\r
- } else {\r
- if (v > 0) {\r
- matchtbl[stack[v]] = i; // close\r
- matchtbl[i] = stack[v]; // open\r
- }\r
- v--;\r
- }\r
- }\r
-\r
- free(stack);\r
-}\r
-\r
-int popCount[1<<ETW];\r
-int fwdtbl[(2*ETW+1)*(1<<ETW)];\r
-int bwdtbl[(2*ETW+1)*(1<<ETW)];\r
-#if 0\r
-int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];\r
-int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];\r
-int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];\r
-int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];\r
-#endif\r
-int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];\r
-int degtbl[1<<ETW];\r
-int degtbl2[(2*ETW+1)*(1<<ETW)];\r
-int childtbl[(ETW)*(1<<ETW)];\r
-int childtbl2[2*ETW+1][ETW][(1<<ETW)];\r
-int depthtbl[(2*ETW+1)*(1<<ETW)];\r
-int inited = 0;\r
-void make_matchtbl(void)\r
-{\r
- int i,j,x,r;\r
- int m,M;\r
- pb buf[1];\r
- int deg;\r
- if (inited)\r
- return;\r
- inited = 1;\r
- for (x = 0; x < (1<<ETW); x++) {\r
- setbits(buf,0,ETW,x);\r
- for (r=-ETW; r<=ETW; r++) fwdtbl[((r+ETW)<<ETW)+x] = ETW;\r
- for (r=-ETW; r<=ETW; r++) bwdtbl[((r+ETW)<<ETW)+x] = ETW;\r
- for (r=-ETW; r<=ETW; r++) degtbl2[((r+ETW)<<ETW)+x] = 0;\r
- for (r=-ETW; r<=ETW; r++) depthtbl[((r+ETW)<<ETW)+x] = 0;\r
-\r
- r = 0;\r
- for (i=0; i<ETW; i++) {\r
- if (getbit(buf,i)==OP) {\r
- r++;\r
- } else {\r
- r--;\r
- }\r
- if (fwdtbl[((r+ETW)<<ETW)+x] == ETW) fwdtbl[((r+ETW)<<ETW)+x] = i;\r
- }\r
-\r
- r = 0;\r
- for (i=ETW-1; i>=0; i--) {\r
- if (getbit(buf,i)==OP) {\r
- r--;\r
- } else {\r
- r++;\r
- }\r
- if (bwdtbl[((r+ETW)<<ETW)+x] == ETW) bwdtbl[((r+ETW)<<ETW)+x] = ETW-1-i;\r
- }\r
-\r
- r = 0;\r
- for (i=0; i<ETW; i++) {\r
- if (getbit(buf,i)==OP) {\r
- r++;\r
- } else {\r
- r--;\r
- }\r
- depthtbl[((r+ETW)<<ETW)+x] += (1<<(ETW-1));\r
- }\r
-\r
- r = 0;\r
- for (i=0; i<ETW; i++) {\r
- if (getbit(buf,i)==OP) r++;\r
- }\r
- popCount[x] = r;\r
-\r
- r = 0; m = 0; M = 0;\r
- m = ETW+1; M = -ETW-1;\r
- //maxtbl_lv[x] = -ETW-1;\r
- //mintbl_lv[x] = ETW+1;\r
- minmaxtbl_v[OPT_MAX | OPT_LEFT][x] = -ETW-1;\r
- minmaxtbl_v[OPT_MIN | OPT_LEFT][x] = ETW+1;\r
- deg = 0;\r
- for (i=0; i<ETW; i++) {\r
- if (getbit(buf,i)==OP) {\r
- r++;\r
- if (r > M) {\r
- M = r; \r
- //maxtbl_li[x] = i; maxtbl_lv[x] = r;\r
- minmaxtbl_i[OPT_MAX | OPT_LEFT][x] = i;\r
- minmaxtbl_v[OPT_MAX | OPT_LEFT][x] = r;\r
- }\r
- } else {\r
- r--;\r
- if (r == m) {\r
- deg++;\r
- childtbl[((deg-1)<<ETW) + x] = i;\r
- }\r
- if (r < m) {\r
- m = r;\r
- //mintbl_li[x] = i; mintbl_lv[x] = r;\r
- minmaxtbl_i[OPT_MIN | OPT_LEFT][x] = i;\r
- minmaxtbl_v[OPT_MIN | OPT_LEFT][x] = r;\r
- deg = 1;\r
- childtbl[((deg-1)<<ETW) + x] = i;\r
- }\r
- }\r
- if (r <= m) degtbl2[((r+ETW)<<ETW)+x]++;\r
- }\r
- degtbl[x] = deg;\r
-\r
- r = 0; m = 0; M = 0;\r
- //maxtbl_rv[x] = -ETW-1;\r
- //mintbl_rv[x] = ETW+1;\r
- minmaxtbl_v[OPT_MAX | OPT_RIGHT][x] = -ETW-1;\r
- minmaxtbl_v[OPT_MIN | OPT_RIGHT][x] = ETW+1;\r
- for (i=0; i<ETW; i++) {\r
- if (getbit(buf,i)==OP) {\r
- r++;\r
- if (r >= M) {\r
- M = r; \r
- //maxtbl_ri[x] = i; maxtbl_rv[x] = r;\r
- minmaxtbl_i[OPT_MAX | OPT_RIGHT][x] = i;\r
- minmaxtbl_v[OPT_MAX | OPT_RIGHT][x] = r;\r
- }\r
- } else {\r
- r--;\r
- if (r <= m) {\r
- m = r;\r
- //mintbl_ri[x] = i; mintbl_rv[x] = r;\r
- minmaxtbl_i[OPT_MIN | OPT_RIGHT][x] = i;\r
- minmaxtbl_v[OPT_MIN | OPT_RIGHT][x] = r;\r
- }\r
- }\r
- }\r
-\r
- for (i = 0; i < ETW; i++) {\r
- for (j = -ETW; j <= ETW; j++) {\r
- childtbl2[j+ETW][i][x] = -1;\r
- }\r
- }\r
-\r
- for (j=-ETW; j<=ETW; j++) {\r
- int ith;\r
- ith = 0;\r
- r = 0;\r
- for (i = 0; i < ETW; i++) {\r
- if (getbit(buf,i)==OP) {\r
- r++;\r
- } else {\r
- r--;\r
- if (r < j) break;\r
- if (r == j) {\r
- ith++;\r
- childtbl2[j+ETW][ith-1][x] = i;\r
- }\r
- }\r
- }\r
- }\r
- }\r
-\r
-}\r
-\r
-\r
-int bp_construct(bp *b,int n, pb *B, int opt)\r
-{\r
- int i,j,d;\r
- int m,M,ds;\r
- int ns,nm;\r
- byte *sm, *sM;\r
- byte *sd;\r
- int *mm, *mM;\r
- int *md;\r
- int m_ofs;\r
- int r; // # of minimum values\r
-\r
-#if 0\r
- if (SB % D != 0) {\r
- printf("warning: SB=%d should be a multiple of D=%d\n",SB,D);\r
- // not necessarily?\r
- }\r
- if (SB % RRR != 0) {\r
- printf("warning: SB=%d should be a multiple of RRR=%d\n",SB,RRR);\r
- }\r
-#endif\r
-\r
- b->B = B;\r
- b->n = n;\r
- b->opt = opt;\r
- b->idx_size = 0;\r
- b->sm = NULL;\r
- b->sM = NULL;\r
- b->sd = NULL;\r
- b->mm = NULL;\r
- b->mM = NULL;\r
- b->md = NULL;\r
- b->da_leaf = NULL;\r
- b->da_inorder = NULL;\r
- b->da_postorder = NULL;\r
- b->da_dfuds_leaf = NULL;\r
- mymalloc(b->da,1,0);\r
- darray_construct(b->da,n,B, opt & OPT_FAST_PREORDER_SELECT);\r
- b->idx_size += b->da->idx_size;\r
- //Kim: comment this and the following, they polute the printing of the xpath library\r
- //printf("preorder rank/select table: %d bytes (%1.2f bpc)\n",b->da->idx_size,(double)b->da->idx_size*8/n);\r
-\r
- make_matchtbl();\r
-\r
- ns = (n+SB-1)/SB;\r
- mymalloc(sm, ns, 0); b->idx_size += ns * sizeof(*sm);\r
- mymalloc(sM, ns, 0); b->idx_size += ns * sizeof(*sM);\r
- b->sm = sm;\r
- b->sM = sM;\r
- if (opt & OPT_DEGREE) {\r
- mymalloc(sd, ns, 0); b->idx_size += ns * sizeof(*sd);\r
- b->sd = sd;\r
- //printf("SB degree table: %d bytes (%1.2f bpc)\n",ns * sizeof(*sd), (double)ns * sizeof(*sd) * 8/n);\r
- }\r
- //printf("SB table: %d bytes (%1.2f bpc)\n",ns * sizeof(*sm) * 2, (double)ns * sizeof(*sm)*2 * 8/n);\r
-\r
- for (i=0; i<n; i++) {\r
- if (i % SB == 0) {\r
- ds = depth(b,i);\r
- m = M = ds;\r
- r = 1;\r
- } else {\r
- d = depth(b,i);\r
- if (d == m) r++;\r
- if (d < m) {\r
- m = d;\r
- r = 1;\r
- }\r
- if (d > M) M = d;\r
- }\r
- if (i % SB == SB-1 || i==n-1) {\r
- ds = depth(b,(i/SB)*SB-1);\r
- if (m - ds + SB < 0 || m - ds + SB > 255) {\r
- printf("error m=%d ds=%d\n",m,ds);\r
- }\r
- if (M - ds + 1 < 0 || M - ds + 1 > 255) {\r
- printf("error M=%d ds=%d\n",M,ds);\r
- }\r
- sm[i/SB] = m - ds + SB;\r
- sM[i/SB] = M - ds + 1;\r
- if (opt & OPT_DEGREE) sd[i/SB] = r;\r
- }\r
- }\r
-\r
-#if 0\r
- printf("sd: ");\r
- for (i=0;i<n/SB;i++) printf("%d ",sd[i]);\r
- printf("\n");\r
-#endif\r
-\r
-\r
- nm = (n+MB-1)/MB;\r
- m_ofs = 1 << blog(nm-1);\r
- b->m_ofs = m_ofs;\r
-\r
- mymalloc(mm, nm + m_ofs, 0); b->idx_size += (nm+m_ofs) * sizeof(*mm);\r
- mymalloc(mM, nm + m_ofs, 0); b->idx_size += (nm+m_ofs) * sizeof(*mM);\r
- b->mm = mm;\r
- b->mM = mM;\r
- if (opt & OPT_DEGREE) {\r
- mymalloc(md, nm + m_ofs, 0); b->idx_size += (nm+m_ofs) * sizeof(*md);\r
- b->md = md;\r
- //printf("MB degree table: %d bytes (%1.2f bpc)\n",(nm+m_ofs) * sizeof(*md), (double)(nm+m_ofs) * sizeof(*md) * 8/n);\r
- }\r
- //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
-\r
- for (i=0; i<n; i++) {\r
- d = depth(b,i);\r
- if (i % MB == 0) {\r
- m = M = d;\r
- r = 1;\r
- } else {\r
- if (d == m) r++;\r
- if (d < m) {\r
- m = d;\r
- r = 1;\r
- }\r
- if (d > M) M = d;\r
- }\r
- if (i % MB == MB-1 || i==n-1) {\r
- mm[m_ofs+ i/MB] = m;\r
- mM[m_ofs+ i/MB] = M;\r
- if (opt & OPT_DEGREE) md[m_ofs+ i/MB] = r;\r
- }\r
- }\r
- \r
- for (j=m_ofs-1; j > 0; j--) {\r
- m = 0;\r
- if (j*2 < nm + m_ofs) m = mm[j*2];\r
- if (j*2+1 < nm + m_ofs) m = min(m,mm[j*2+1]);\r
- M = 0;\r
- if (j*2 < nm + m_ofs) M = mM[j*2];\r
- if (j*2+1 < nm + m_ofs) M = max(M,mM[j*2+1]);\r
- mm[j] = m; mM[j] = M;\r
- if (opt & OPT_DEGREE) {\r
- d = 0;\r
- if (j*2 < nm + m_ofs) d = md[j*2];\r
- if (j*2+1 < nm + m_ofs) {\r
- if (mm[j*2] == mm[j*2+1]) d += md[j*2+1];\r
- if (mm[j*2] > mm[j*2+1]) d = md[j*2+1];\r
- }\r
- md[j] = d;\r
- }\r
- }\r
- mm[0] = -1;\r
- mM[0] = mM[1];\r
- if (opt & OPT_DEGREE) {\r
- md[0] = -1;\r
- }\r
-\r
-\r
-#if 0\r
- printf("md: ");\r
- for (i=0;i<m_ofs + n/MB;i++) printf("%d ",md[i]);\r
- printf("\n");\r
-#endif\r
-\r
- if (opt & OPT_LEAF) {\r
- mymalloc(b->da_leaf,1,0);\r
- darray_pat_construct(b->da_leaf, n, B, 2, 0x2, opt & OPT_FAST_LEAF_SELECT);\r
- //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
- b->idx_size += b->da_leaf->idx_size; \r
- } else {\r
- b->da_leaf = NULL;\r
- }\r
-\r
- if (opt & OPT_INORDER) {\r
- mymalloc(b->da_inorder,1,0);\r
- darray_pat_construct(b->da_inorder, n, B, 2, 0x1, opt & OPT_FAST_INORDER_SELECT);\r
- //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
- b->idx_size += b->da_inorder->idx_size;\r
- } else {\r
- b->da_inorder = NULL;\r
- }\r
-\r
- if (opt & OPT_FAST_POSTORDER_SELECT) {\r
- mymalloc(b->da_postorder,1,0);\r
- darray_pat_construct(b->da_postorder, n, B, 1, 0x0, (opt & OPT_FAST_POSTORDER_SELECT) | OPT_NO_RANK);\r
- //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
- b->idx_size += b->da_postorder->idx_size;\r
- } else {\r
- b->da_postorder = NULL;\r
- }\r
-\r
- if (opt & OPT_DFUDS_LEAF) {\r
- mymalloc(b->da_dfuds_leaf,1,0);\r
- darray_pat_construct(b->da_dfuds_leaf, n, B, 2, 0x0, opt & OPT_FAST_DFUDS_LEAF_SELECT);\r
- //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
- b->idx_size += b->da_dfuds_leaf->idx_size;\r
- } else {\r
- b->da_dfuds_leaf = NULL;\r
- }\r
-\r
- return 0;\r
-}\r
-\r
-// destroyTree: frees the memory of tree.\r
-void destroyTree(bp *b) {\r
- if (!b) return; // nothing to free\r
-\r
- destroyDarray(b->da); // destroys da data structure\r
- if (b->da) free(b->da); \r
- \r
- if (b->sm) free(b->sm);\r
- if (b->sM) free(b->sM);\r
- if (b->sd) free(b->sd);\r
- if (b->mm) free(b->mm);\r
- if (b->mM) free(b->mM);\r
- if (b->md) free(b->md);\r
- \r
- destroyDarray(b->da_leaf);\r
- if (b->da_leaf) free(b->da_leaf);\r
- \r
- destroyDarray(b->da_inorder);\r
- if (b->da_inorder) free(b->da_inorder);\r
- \r
- destroyDarray(b->da_postorder);\r
- if (b->da_postorder) free(b->da_postorder);\r
- \r
- destroyDarray(b->da_dfuds_leaf);\r
- if (b->da_dfuds_leaf) free(b->da_dfuds_leaf);\r
-}\r
-\r
-\r
-// saveTree: saves parentheses data structure to file\r
-// By Diego Arroyuelo\r
-void saveTree(bp *b, FILE *fp) {\r
-\r
- if (fwrite(&(b->n), sizeof(int), 1, fp) != 1) {\r
- printf("Error: cannot save number of parentheses to file\n");\r
- exit(1);\r
- }\r
-\r
- if (fwrite(b->B, sizeof(pb), (b->n+D-1)/D, fp) != ((b->n+D-1)/D)) {\r
- printf("Error: cannot save parentheses sequence to file\n");\r
- exit(1);\r
- }\r
-\r
- if (fwrite(&(b->opt), sizeof(int), 1, fp) != 1) {\r
- printf("Error: cannot save opt in parentheses to file\n");\r
- exit(1);\r
- }\r
-}\r
-\r
-// loadTree: load parentheses data structure from file\r
-// By Diego Arroyuelo\r
-void loadTree(bp *b, FILE *fp) {\r
-\r
- pb *B;\r
- int n, opt;\r
-\r
- if (fread(&n, sizeof(int), 1, fp) != 1) {\r
- printf("Error: cannot read number of parentheses from file\n");\r
- exit(1);\r
- }\r
-\r
- mymalloc(B,(n+D-1)/D,0);\r
- \r
- if (fread(B, sizeof(pb), (n+D-1)/D, fp) != ((n+D-1)/D)) {\r
- printf("Error: cannot read parentheses sequence from file\n");\r
- exit(1);\r
- }\r
-\r
- if (fread(&opt, sizeof(int), 1, fp) != 1) {\r
- printf("Error: cannot read opt in parentheses from file\n");\r
- exit(1);\r
- }\r
- \r
- bp_construct(b, n, B, opt); \r
- \r
-}\r
-\r
-\r
-\r
-int naive_fwd_excess(bp *b,int s, int rel)\r
-{\r
- int i,v,n;\r
- pb *B;\r
- n = b->n; B = b->B;\r
- v = 0;\r
- for (i=s+1; i<n; i++) {\r
- if (getbit(B,i)==OP) {\r
- v++;\r
- } else {\r
- v--;\r
- }\r
- if (v == rel) return i;\r
- }\r
- return -1;\r
-}\r
-\r
-int naive_bwd_excess(bp *b,int s, int rel)\r
-{\r
- int i,v;\r
- pb *B;\r
- B = b->B;\r
- v = 0;\r
- for (i=s; i>=0; i--) {\r
- if (getbit(B,i)==OP) {\r
- v--;\r
- } else {\r
- v++;\r
- }\r
- if (v == rel) return i-1;\r
- }\r
- return -2;\r
-}\r
-\r
-int naive_search_SB_l(bp *b, int i, int rel)\r
-{\r
- int il,v;\r
-\r
- il = (i / SB) * SB;\r
- for (; i>=il; i--) {\r
- if (getbit(b->B,i)==OP) {\r
- rel++;\r
- } else {\r
- rel--;\r
- }\r
- if (rel == 0) return i-1;\r
- }\r
- if (i < 0) return -2;\r
- return -3;\r
-}\r
-\r
-int naive_rmq(bp *b, int s, int t,int opt)\r
-{\r
- int d,i,dm,im;\r
-\r
- if (opt & OPT_RIGHT) {\r
- d = dm = depth(b,t); im = t;\r
- i = t-1;\r
- while (i >= s) {\r
- if (getbit(b->B,i+1)==CP) {\r
- d++;\r
- if (opt & OPT_MAX) {\r
- if (d > dm) {\r
- dm = d; im = i;\r
- }\r
- }\r
- } else {\r
- d--;\r
- if (!(opt & OPT_MAX)) {\r
- if (d < dm) {\r
- dm = d; im = i;\r
- }\r
- }\r
- }\r
- i--;\r
- }\r
- } else {\r
- d = dm = depth(b,s); im = s;\r
- i = s+1;\r
- while (i <= t) {\r
- if (getbit(b->B,i)==OP) {\r
- d++;\r
- if (opt & OPT_MAX) {\r
- if (d > dm) {\r
- dm = d; im = i;\r
- }\r
- }\r
- } else {\r
- d--;\r
- if (!(opt & OPT_MAX)) {\r
- if (d < dm) {\r
- dm = d; im = i;\r
- }\r
- }\r
- }\r
- i++;\r
- }\r
- }\r
- return im;\r
-}\r
-\r
-int root_node(bp *b)\r
-{\r
- return 0;\r
-}\r
-\r
-\r
-int rank_open(bp *b, int s)\r
-{\r
- return darray_rank(b->da,s);\r
-}\r
-\r
-int rank_close(bp *b, int s)\r
-{\r
- return s+1 - darray_rank(b->da,s);\r
-}\r
-\r
-int select_open(bp *b, int s)\r
-{\r
- if (b->opt & OPT_FAST_PREORDER_SELECT) {\r
- return darray_select(b->da,s,1);\r
- } else {\r
- return darray_select_bsearch(b->da,s,getpat_preorder);\r
- }\r
-}\r
-\r
-int select_close(bp *b, int s)\r
-{\r
- if (b->opt & OPT_FAST_POSTORDER_SELECT) {\r
- return darray_pat_select(b->da_postorder,s,getpat_postorder);\r
- } else {\r
- return postorder_select_bsearch(b,s);\r
- }\r
-}\r
-\r
-///////////////////////////////////////////\r
-// find_close(bp *b,int s)\r
-// returns the matching close parenthesis of s\r
-///////////////////////////////////////////\r
-int find_close(bp *b,int s)\r
-{\r
- return fwd_excess(b,s,-1);\r
-}\r
-\r
-///////////////////////////////////////////\r
-// find_open(bp *b,int s)\r
-// returns the matching open parenthesis of s\r
-///////////////////////////////////////////\r
-int find_open(bp *b,int s)\r
-{\r
- int r;\r
- r = bwd_excess(b,s,0);\r
- if (r >= -1) return r+1;\r
- return -1;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// parent(bp *b,int s)\r
-// returns the parent of s\r
-// -1 if s is the root\r
-///////////////////////////////////////////\r
-int parent(bp *b,int s)\r
-{\r
- int r;\r
- r = bwd_excess(b,s,-2);\r
- if (r >= -1) return r+1;\r
- return -1;\r
-}\r
-\r
-int enclose(bp *b,int s)\r
-{\r
- return parent(b,s);\r
-}\r
-\r
-///////////////////////////////////////////\r
-// level_ancestor(bp *b,int s,int d)\r
-// returns the ancestor of s with relative depth d (d < 0)\r
-// -1 if no such node\r
-///////////////////////////////////////////\r
-int level_ancestor(bp *b,int s,int d)\r
-{\r
- int r;\r
- r = bwd_excess(b,s,d-1);\r
- if (r >= -1) return r+1;\r
- return -1;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// lca(bp *b, int s, int t)\r
-// returns the lowest common ancestor of s and t\r
-///////////////////////////////////////////\r
-int lca(bp *b, int s, int t)\r
-{\r
- return parent(b,rmq(b,s,t,0)+1);\r
-}\r
-\r
-\r
-///////////////////////////////////////////\r
-// preorder_rank(bp *b,int s)\r
-// returns the preorder (>= 1) of node s (s >= 0)\r
-///////////////////////////////////////////\r
-int preorder_rank(bp *b,int s)\r
-{\r
- return darray_rank(b->da,s);\r
-}\r
-\r
-///////////////////////////////////////////\r
-// preorder_select(bp *b,int s)\r
-// returns the node with preorder s (s >= 1)\r
-// -1 if no such node\r
-///////////////////////////////////////////\r
-int preorder_select(bp *b,int s)\r
-{\r
- // no error handling\r
- if (b->opt & OPT_FAST_PREORDER_SELECT) {\r
- return darray_select(b->da,s,1);\r
- } else {\r
- return darray_select_bsearch(b->da,s,getpat_preorder);\r
- }\r
-}\r
-\r
-///////////////////////////////////////////\r
-// postorder_rank(bp *b,int s)\r
-// returns the postorder (>= 1) of node s (s >= 0)\r
-// -1 if s-th bit is not OP\r
-///////////////////////////////////////////\r
-int postorder_rank(bp *b,int s)\r
-{\r
- int t;\r
- if (inspect(b,s) == CP) return -1;\r
- t = find_close(b,s);\r
- // return t+1 - darray_rank(b->da,t);\r
- return rank_close(b,t);\r
-}\r
-\r
-int postorder_select_bsearch(bp *b,int s)\r
-{\r
- int l,r,m;\r
-\r
- if (s == 0) return -1;\r
-\r
- if (s > b->da->n - b->da->m) {\r
- return -1;\r
- }\r
- l = 0; r = b->da->n - 1;\r
-\r
- while (l < r) {\r
- m = (l+r)/2;\r
- //printf("m=%d rank=%d s=%d\n",m,m+1 - darray_rank(b->da,m),s);\r
- if (m+1 - darray_rank(b->da,m) >= s) {\r
- r = m;\r
- } else {\r
- l = m+1;\r
- }\r
- }\r
- return l;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// postorder_select(bp *b,int s)\r
-// returns the position of CP of the node with postorder s (>= 1)\r
-///////////////////////////////////////////\r
-int postorder_select(bp *b,int s)\r
-{\r
-#if 0\r
- if (b->opt & OPT_FAST_POSTORDER_SELECT) {\r
- return darray_pat_select(b->da_postorder,s,getpat_postorder);\r
- } else {\r
- return postorder_select_bsearch(b->da,s);\r
- }\r
-#else\r
- return select_close(b,s);\r
-#endif\r
-}\r
-\r
-///////////////////////////////////////////\r
-// leaf_rank(bp *b,int s)\r
-// returns the number of leaves to the left of s\r
-///////////////////////////////////////////\r
-int leaf_rank(bp *b,int s)\r
-{\r
- if ((b->opt & OPT_LEAF) == 0) {\r
- printf("leaf_rank: error!!! not supported\n");\r
- return -1;\r
- }\r
- if (s >= b->n-1) {\r
- s = b->n-2;\r
- }\r
- return darray_pat_rank(b->da_leaf,s,getpat_leaf);\r
-}\r
-\r
-///////////////////////////////////////////\r
-// leaf_select(bp *b,int s)\r
-// returns the position of s-th leaf\r
-///////////////////////////////////////////\r
-int leaf_select(bp *b,int s)\r
-{\r
- if ((b->opt & OPT_LEAF) == 0) {\r
- printf("leaf_select: error!!! not supported\n");\r
- return -1;\r
- }\r
- if (s > b->da_leaf->m) return -1;\r
- if (b->opt & OPT_FAST_LEAF_SELECT) {\r
- return darray_pat_select(b->da_leaf,s,getpat_leaf);\r
- } else {\r
- return darray_select_bsearch(b->da_leaf,s,getpat_leaf);\r
- }\r
-}\r
-\r
-\r
-///////////////////////////////////////////\r
-// inorder_rank(bp *b,int s)\r
-// returns the number of ")(" (s >= 0)\r
-///////////////////////////////////////////\r
-int inorder_rank(bp *b,int s)\r
-{\r
- if ((b->opt & OPT_INORDER) == 0) {\r
- printf("inorder_rank: error!!! not supported\n");\r
- return -1;\r
- }\r
- if (s >= b->n-1) {\r
- s = b->n-2;\r
- }\r
- return darray_pat_rank(b->da_inorder,s,getpat_inorder);\r
-}\r
-\r
-///////////////////////////////////////////\r
-// inorder_select(bp *b,int s)\r
-// returns the s-th position of ")(" (s >= 1)\r
-///////////////////////////////////////////\r
-int inorder_select(bp *b,int s)\r
-{\r
- if ((b->opt & OPT_INORDER) == 0) {\r
- printf("inorder_select: error!!! not supported\n");\r
- return -1;\r
- }\r
- if (b->opt & OPT_FAST_INORDER_SELECT) {\r
- return darray_pat_select(b->da_inorder,s,getpat_inorder);\r
- } else {\r
- return darray_select_bsearch(b->da_inorder,s,getpat_inorder);\r
- }\r
-}\r
-\r
-///////////////////////////////////////////\r
-// leftmost_leaf(bp *b, int s)\r
-///////////////////////////////////////////\r
-int leftmost_leaf(bp *b, int s)\r
-{\r
- if ((b->opt & OPT_LEAF) == 0) {\r
- printf("leftmost_leaf: error!!! not supported\n");\r
- return -1;\r
- }\r
- return leaf_select(b,leaf_rank(b,s)+1);\r
-}\r
-\r
-///////////////////////////////////////////\r
-// rightmost_leaf(bp *b, int s)\r
-///////////////////////////////////////////\r
-int rightmost_leaf(bp *b, int s)\r
-{\r
- int t;\r
- if ((b->opt & OPT_LEAF) == 0) {\r
- printf("leftmost_leaf: error!!! not supported\n");\r
- return -1;\r
- }\r
- t = find_close(b,s);\r
- return leaf_select(b,leaf_rank(b,t));\r
-}\r
-\r
-\r
-\r
-///////////////////////////////////////////\r
-// inspect(bp *b, int s)\r
-// returns OP (==1) or CP (==0) at s-th bit (0 <= s < n)\r
-///////////////////////////////////////////\r
-int inspect(bp *b, int s)\r
-{\r
- if (s < 0 || s >= b->n) {\r
- printf("inspect: error s=%d is out of [%d,%d]\n",s,0,b->n-1);\r
- }\r
- return getbit(b->B,s);\r
-}\r
-\r
-int isleaf(bp *b, int s)\r
-{\r
- if (inspect(b,s) != OP) {\r
- printf("isleaf: error!!! B[%d] = OP\n",s);\r
- }\r
- if (inspect(b,s+1) == CP) return 1;\r
- else return 0;\r
-}\r
-\r
-\r
-///////////////////////////////////////////\r
-// subtree_size(bp *b, int s)\r
-// returns the number of nodes in the subtree of s\r
-///////////////////////////////////////////\r
-int subtree_size(bp *b, int s)\r
-{\r
- return (find_close(b,s) - s + 1) / 2;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// first_child(bp *b, int s)\r
-// returns the first child\r
-// -1 if s is a leaf\r
-///////////////////////////////////////////\r
-int first_child(bp *b, int s)\r
-{\r
- if (inspect(b,s+1) == CP) return -1;\r
- return s+1;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// next_sibling(bp *b,int s)\r
-// returns the next sibling of parent(s)\r
-// -1 if s is the last child\r
-//////////////////////////////////////////\r
-int next_sibling(bp *b, int s)\r
-{\r
- int t;\r
- t = find_close(b,s)+1;\r
- if (t >= b->n) {\r
- printf("next_sibling: error s=%d t=%d\n",s,t);\r
- }\r
- if (inspect(b,t) == CP) return -1;\r
- return t;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// prev_sibling(bp *b,int s)\r
-// returns the previous sibling of parent(s)\r
-// -1 if s is the first child\r
-//////////////////////////////////////////\r
-int prev_sibling(bp *b, int s)\r
-{\r
- int t;\r
- if (s < 0) {\r
- printf("prev_sibling: error s=%d\n",s);\r
- }\r
- if (s == 0) return -1;\r
- if (inspect(b,s-1) == OP) return -1;\r
- t = find_open(b,s-1);\r
- return t;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// deepest_node(bp *b,int s)\r
-// returns the first node with the largest depth in the subtree of s\r
-///////////////////////////////////////////\r
-int deepest_node(bp *b,int s)\r
-{\r
- int t,m;\r
- t = find_close(b,s);\r
- m = rmq(b,s,t, OPT_MAX);\r
- return m;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// subtree_height(bp *b,int s)\r
-// returns the height of the subtree of s\r
-// 0 if s is a leaf\r
-///////////////////////////////////////////\r
-int subtree_height(bp *b,int s)\r
-{\r
- int t;\r
- t = deepest_node(b,s);\r
- return depth(b,t) - depth(b,s);\r
-}\r
-\r
-int naive_degree(bp *b, int s)\r
-{\r
- int t,d;\r
- d = 0;\r
- t = first_child(b,s);\r
- while (t >= 0) {\r
- d++;\r
- t = next_sibling(b,t);\r
- }\r
- return d;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// degree(bp *b, int s)\r
-// returns the number of children of s\r
-// 0 if s is a leaf\r
-///////////////////////////////////////////\r
-int degree(bp *b, int s)\r
-{\r
- if (b->opt & OPT_DEGREE) {\r
- return fast_degree(b,s,b->n,0);\r
- } else {\r
- return naive_degree(b,s);\r
- }\r
-}\r
-\r
-int naive_child(bp *b, int s, int d)\r
-{\r
- int t,i;\r
- t = first_child(b,s);\r
- for (i = 1; i < d; i++) {\r
- if (t == -1) break;\r
- t = next_sibling(b,t);\r
- }\r
- return t;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// child(bp *b, int s, int d)\r
-// returns the d-th child of s (1 <= d <= degree(s))\r
-// -1 if no such node\r
-///////////////////////////////////////////\r
-int child(bp *b, int s, int d)\r
-{\r
- int r;\r
- if (b->opt & OPT_DEGREE) {\r
- //return find_open(b,fast_degree(b,s,b->n,d));\r
- if (d==1) return first_child(b,s);\r
- r = fast_degree(b,s,b->n,d-1)+1;\r
- if (inspect(b,r) == CP) return -1;\r
- return r;\r
- } else {\r
- return naive_child(b,s,d);\r
- }\r
- \r
-}\r
-\r
-\r
-int naive_child_rank(bp *b, int t)\r
-{\r
- int v,d;\r
- d = 0;\r
- while (t != -1) {\r
- d++;\r
- t = prev_sibling(b,t);\r
- }\r
- return d;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// child_rank(bp *b, int t)\r
-// returns d if t is the d-th child of the parent of t (d >= 1)\r
-// 1 if t is the root\r
-///////////////////////////////////////////\r
-int child_rank(bp *b, int t)\r
-{\r
- int r;\r
- if (t == root_node(b)) return 1;\r
- if (b->opt & OPT_DEGREE) {\r
- r = parent(b,t);\r
- return fast_degree(b,r,t,0)+1;\r
- } else {\r
- return naive_child_rank(b,t);\r
- }\r
-}\r
-\r
-\r
-\r
-///////////////////////////////////////////\r
-// is_ancestor(bp *b, int s, int t)\r
-// returns 1 if s is an ancestor of t\r
-// 0 otherwise\r
-///////////////////////////////////////////\r
-int is_ancestor(bp *b, int s, int t)\r
-{\r
- int v;\r
- v = find_close(b,s);\r
- if (s <= t && t <= v) return 1;\r
- return 0;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// distance(bp *b, int s, int t)\r
-// returns the length of the shortest path from s to t in the tree\r
-///////////////////////////////////////////\r
-int distance(bp *b, int s, int t)\r
-{\r
- int v,d;\r
- v = lca(b,s,t);\r
- d = depth(b,v);\r
- return (depth(b,s) - d) + (depth(b,t) - d);\r
-}\r
-\r
-///////////////////////////////////////////\r
-// level_next(bp *b, int d)\r
-///////////////////////////////////////////\r
-int level_next(bp *b,int s)\r
-{\r
- int t;\r
- t = fwd_excess(b,s,0);\r
- return t;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// level_prev(bp *b, int d)\r
-///////////////////////////////////////////\r
-int level_prev(bp *b,int s)\r
-{\r
- int t;\r
- t = bwd_excess(b,s,0);\r
- return t;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// level_leftmost(bp *b, int d)\r
-///////////////////////////////////////////\r
-int level_leftmost(bp *b, int d)\r
-{\r
- int t;\r
- if (d < 1) return -1;\r
- if (d == 1) return 0;\r
- t = fwd_excess(b,0,d);\r
- return t;\r
-}\r
-\r
-///////////////////////////////////////////\r
-// level_rigthmost(bp *b, int d)\r
-///////////////////////////////////////////\r
-int level_rigthmost(bp *b, int d)\r
-{\r
- int t;\r
- if (d < 1) return -1;\r
- if (d == 1) return 0;\r
- t = bwd_excess(b,0,d-1);\r
- return find_open(b,t);\r
-}\r
-\r
-///////////////////////////////////////////\r
-// leaf_size(bp *b, int s)\r
-///////////////////////////////////////////\r
-int leaf_size(bp *b, int s)\r
-{\r
- int t;\r
- if ((b->opt & OPT_LEAF) == 0) {\r
- printf("leaf_size: error!!! not supported\n");\r
- return -1;\r
- }\r
- t = find_close(b,s);\r
- return leaf_rank(b,t) - leaf_rank(b,s);\r
-}\r
projects / SXSI / XMLTree.git / blobdiff