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 #ifdef __cplusplus
  49 extern "C" {
  50 void destroyLZTrie (lztrie T);
  51 }
  52 #else
  53 void destroyLZTrie (lztrie T);
  54 #endif
  55         // stores lztrie T on file f
  56 #ifdef __cplusplus
  57 extern "C" {
  58 void saveLZTrie (lztrie T, FILE *f);
  59 }
  60 #else
  61 void saveLZTrie (lztrie T, FILE *f);
  62 #endif
  63         // loads lztrie T from file f
  64 #ifdef __cplusplus
  65 extern "C" {
  66 lztrie loadLZTrie (FILE *f);
  67 }
  68 #else
  69 lztrie loadLZTrie (FILE *f);
  70 #endif
  71         // letter by which node i descends
  72 byte letterLZTrie (lztrie T, trieNode i);
  73         // go down by letter c, if possible
  74 trieNode childLZTrie (lztrie T, trieNode i, byte c);
  75         // go up, if possible
  76 trieNode parentLZTrie (lztrie T, trieNode i);
  77         // subtree size
  78 uint subtreesizeLZTrie (lztrie T, trieNode i);
  79         // smallest rank in subtree
  80 uint leftrankLZTrie (lztrie T, trieNode i);
  81         // largest rank in subtree
  82 uint rightrankLZTrie (lztrie T, trieNode i);
  83         // is node i ancestor of node j?
  84 bool ancestorLZTrie (lztrie T, trieNode i, trieNode j);
  85         // next node from i, in preorder, adds/decrements depth accordingly
  86         // assumes it *can* go on!
  87 trieNode nextLZTrie (lztrie T, trieNode i, uint *depth);
  88         // size in bytes of LZTrie T
  89 uint sizeofLZTrie(lztrie T);
  90
  91 #ifdef __cplusplus
  92 extern "C" {
  93 void extract(lztrie T, ulong from, ulong to, byte **snippet, ulong *snippet_length);
  94 }
  95 #else
  96 void extract(lztrie T, ulong from, ulong to, byte **snippet, ulong *snippet_length);
  97 #endif
  98
  99 #endif