3 // Implements operations over a sequence of balanced parentheses
5 #ifndef PARENTHESESINCLUDED
6 #define PARENTHESESINCLUDED
12 typedef struct sparentheses
13 { uint *data; // string
14 bitmap bdata; // bitmap of string
15 uint n; // # of parentheses
16 uint sbits; // bits for near pointers
17 hash sftable; // table of far forward pointers
18 hash sbtable; // table of far backward pointers
19 hash bftable; // table of near forward pointers
20 hash bbtable; // table of near backward pointers
23 // creates a parentheses structure from a bitstring, which gets owned
24 // n is the total number of parentheses, opening + closing
25 // bwd says if you will want to perform findopen and enclose
26 parentheses createParentheses (uint *string, uint n, bool bwd);
27 // frees parentheses structure, including the bitstream
28 void destroyParentheses (parentheses P);
29 // the position of the closing parenthesis corresponding to (opening)
30 // parenthesis at position i
31 uint findclose (parentheses P, uint i);
32 // respectively, for closing parenthesis i
33 uint findopen (parentheses P, uint i);
34 // # open - # close at position i, not included
35 uint excess (parentheses P, uint i);
36 // open position of closest parentheses pair that contains the pair
37 // that opens at i, ~0 if no parent
38 uint enclose (parentheses P, uint i);
40 uint sizeofParentheses(parentheses P);