Implementation of LZ-index for extracting text

[SXSI/TextCollection.git] / lzindex / lztrie.h

diff --git a/lzindex/lztrie.h b/lzindex/lztrie.h
new file mode 100644 (file)
index 0000000..691a2aa
--- /dev/null
+++ b/lzindex/lztrie.h
@@ -0,0 +1,81 @@
+
+
+// Implements the LZtrie data structure
+
+#ifndef LZTRIEINCLUDED
+#define LZTRIEINCLUDED
+
+#include "basics.h"
+#include "trie.h"
+#include "parentheses.h"
+#include "nodemap.h"
+#include "position.h"
+
+//typedef uint trieNode; // a node of lztrie
+
+#define NULLT ((trieNode)(~0)) // a null node
+#define ROOT ((trieNode)(0)) // the root node
+
+typedef struct slztrie
+   { 
+      uint *data;      // bitmap data
+      parentheses pdata; // parentheses structure
+      uint n;          // # of parentheses
+      byte *letters;   // letters of the trie
+      uint nbits;      // log n
+      nodemap Node;    // ids of the trie
+      position TPos;    // text position data structure
+      uint text_length; // length of the original text
+      trieNode *boost;    // direct pointers to first children
+   } *lztrie;
+
+
+       // creates a lztrie structure from a parentheses bitstring,
+       // a letter array in preorder, and an id array in preorder,
+        // all of which except the latter become owned
+        // n is the total number of nodes (n letters/ids, 2n parentheses)
+lztrie createLZTrie (uint *string, byte *letters, uint *id, uint n, uint text_length);
+        // builds an lztrie from a text. "s" is the text terminator.
+#ifdef __cplusplus
+extern "C" {
+ lztrie buildLZTrie(byte *text, byte s, uint text_length);
+}
+#else
+ lztrie buildLZTrie(byte *text, byte s, uint text_length);
+#endif
+
+       // frees LZTrie structure, including the owned data
+void destroyLZTrie (lztrie T);
+        // stores lztrie T on file f
+void saveLZTrie (lztrie T, FILE *f);
+        // loads lztrie T from file f
+lztrie loadLZTrie (FILE *f);
+       // letter by which node i descends
+byte letterLZTrie (lztrie T, trieNode i);
+       // go down by letter c, if possible
+trieNode childLZTrie (lztrie T, trieNode i, byte c);
+       // go up, if possible
+trieNode parentLZTrie (lztrie T, trieNode i);
+       // subtree size
+uint subtreesizeLZTrie (lztrie T, trieNode i);
+       // smallest rank in subtree
+uint leftrankLZTrie (lztrie T, trieNode i);
+       // largest rank in subtree
+uint rightrankLZTrie (lztrie T, trieNode i);
+        // is node i ancestor of node j?
+bool ancestorLZTrie (lztrie T, trieNode i, trieNode j);
+       // next node from i, in preorder, adds/decrements depth accordingly
+       // assumes it *can* go on!
+trieNode nextLZTrie (lztrie T, trieNode i, uint *depth);
+        // size in bytes of LZTrie T
+uint sizeofLZTrie(lztrie T);
+
+#ifdef __cplusplus
+extern "C" {
+void extract(lztrie T, ulong from, ulong to, byte **snippet, ulong *snippet_length);
+}
+#else
+void extract(lztrie T, ulong from, ulong to, byte **snippet, ulong *snippet_length);
+#endif
+
+#endif