lzindex/trie.h

   1
   2  // LZ78 trie data structure
   3
   4 #ifndef TRIEINCLUDED
   5 #define TRIEINCLUDED
   6
   7 #include "basics.h"
   8 #include "heap.h"
   9
  10 typedef struct striebody
  11    { uint id;   // node id
  12      short nchildren;
  13      struct schild
  14        { byte car;
  15          struct striebody *trie;
  16        } *children;
  17    } triebody;
  18
  19 typedef struct strie
  20    { triebody trie;     // trie
  21      heap heaps[256];   // heaps
  22      uint nid;          // nr of nodes
  23    } *trie;
  24
  25         // creates trie
  26 trie createTrie (void);
  27         // inserts word[0...] into pTrie and returns new text ptr
  28         // insertion proceeds until we get a new trie node
  29 uint sizeofTrie(triebody *t);
  30
  31 byte *insertTrie (trie pTrie, byte *word/*, ulong *pos*/);
  32         // inserts word[0..len-1] into pTrie, with id = id
  33         // assumes that no two equal strings are ever inserted
  34 void insertstringTrie (trie pTrie, byte *word, uint len, uint id);
  35         // frees the trie
  36 void destroyTrie (trie pTrie);
  37         // represents pTrie with parentheses, letters and ids
  38 void representTrie (trie pTrie, uint *parent, byte *letters, uint *ids);
  39
  40 #endif