lzindex/lztrie.h

   1
   2
   3 // Implements the LZtrie data structure
   4
   5 #ifndef LZTRIEINCLUDED
   6 #define LZTRIEINCLUDED
   7
   8 #include "basics.h"
   9 #include "trie.h"
  10 #include "parentheses.h"
  11 #include "nodemap.h"
  12 #include "position.h"
  13
  14 //typedef uint trieNode; // a node of lztrie
  15
  16 #define NULLT ((trieNode)(~0)) // a null node
  17 #define ROOT ((trieNode)(0)) // the root node
  18
  19 typedef struct slztrie
  20    {
  21       uint *data;       // bitmap data
  22       parentheses pdata; // parentheses structure
  23       uint n;           // # of parentheses
  24       byte *letters;    // letters of the trie
  25       uint nbits;       // log n
  26       nodemap Node;     // ids of the trie
  27       position TPos;    // text position data structure
  28       uint text_length; // length of the original text
  29       trieNode *boost;    // direct pointers to first children
  30    } *lztrie;
  31
  32
  33         // creates a lztrie structure from a parentheses bitstring,
  34         // a letter array in preorder, and an id array in preorder,
  35         // all of which except the latter become owned
  36         // n is the total number of nodes (n letters/ids, 2n parentheses)
  37 lztrie createLZTrie (uint *string, byte *letters, uint *id, uint n, uint text_length);
  38         // builds an lztrie from a text. "s" is the text terminator.
  39 #ifdef __cplusplus
  40 extern "C" {
  41  lztrie buildLZTrie(byte *text, byte s, uint text_length);
  42 }
  43 #else
  44  lztrie buildLZTrie(byte *text, byte s, uint text_length);
  45 #endif
  46
  47         // frees LZTrie structure, including the owned data
  48 void destroyLZTrie (lztrie T);
  49         // stores lztrie T on file f
  50 void saveLZTrie (lztrie T, FILE *f);
  51         // loads lztrie T from file f
  52 lztrie loadLZTrie (FILE *f);
  53         // letter by which node i descends
  54 byte letterLZTrie (lztrie T, trieNode i);
  55         // go down by letter c, if possible
  56 trieNode childLZTrie (lztrie T, trieNode i, byte c);
  57         // go up, if possible
  58 trieNode parentLZTrie (lztrie T, trieNode i);
  59         // subtree size
  60 uint subtreesizeLZTrie (lztrie T, trieNode i);
  61         // smallest rank in subtree
  62 uint leftrankLZTrie (lztrie T, trieNode i);
  63         // largest rank in subtree
  64 uint rightrankLZTrie (lztrie T, trieNode i);
  65         // is node i ancestor of node j?
  66 bool ancestorLZTrie (lztrie T, trieNode i, trieNode j);
  67         // next node from i, in preorder, adds/decrements depth accordingly
  68         // assumes it *can* go on!
  69 trieNode nextLZTrie (lztrie T, trieNode i, uint *depth);
  70         // size in bytes of LZTrie T
  71 uint sizeofLZTrie(lztrie T);
  72
  73 #ifdef __cplusplus
  74 extern "C" {
  75 void extract(lztrie T, ulong from, ulong to, byte **snippet, ulong *snippet_length);
  76 }
  77 #else
  78 void extract(lztrie T, ulong from, ulong to, byte **snippet, ulong *snippet_length);
  79 #endif
  80
  81 #endif