3 // Implements the LZtrie data structure
10 #include "parentheses.h"
14 //typedef uint trieNode; // a node of lztrie
16 #define NULLT ((trieNode)(~0)) // a null node
17 #define ROOT ((trieNode)(0)) // the root node
19 typedef struct slztrie
21 uint *data; // bitmap data
22 parentheses pdata; // parentheses structure
23 uint n; // # of parentheses
24 byte *letters; // letters of the trie
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
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.
41 lztrie buildLZTrie(byte *text, byte s, uint text_length);
44 lztrie buildLZTrie(byte *text, byte s, uint text_length);
47 // frees LZTrie structure, including the owned data
50 void destroyLZTrie (lztrie T);
53 void destroyLZTrie (lztrie T);
55 // stores lztrie T on file f
58 void saveLZTrie (lztrie T, FILE *f);
61 void saveLZTrie (lztrie T, FILE *f);
63 // loads lztrie T from file f
66 lztrie loadLZTrie (FILE *f);
69 lztrie loadLZTrie (FILE *f);
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);
76 trieNode parentLZTrie (lztrie T, trieNode i);
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);
93 void extract(lztrie T, ulong from, ulong to, byte **snippet, ulong *snippet_length);
96 void extract(lztrie T, ulong from, ulong to, byte **snippet, ulong *snippet_length);