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
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);
58 trieNode parentLZTrie (lztrie T, trieNode i);
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);
75 void extract(lztrie T, ulong from, ulong to, byte **snippet, ulong *snippet_length);
78 void extract(lztrie T, ulong from, ulong to, byte **snippet, ulong *snippet_length);