lzindex/parentheses.h

   1
   2
   3 // Implements operations over a sequence of balanced parentheses
   4
   5 #ifndef PARENTHESESINCLUDED
   6 #define PARENTHESESINCLUDED
   7
   8 #include "basics.h"
   9 #include "bitmap.h"
  10 #include "hash.h"
  11
  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
  21    } *parentheses;
  22
  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);
  39
  40 uint sizeofParentheses(parentheses P);
  41 #endif