2 // LZ78 trie data structure
12 pTrie = malloc (sizeof(struct strie));
14 pTrie->trie.id = pTrie->nid++;
15 pTrie->trie.nchildren = 0;
16 pTrie->trie.children = NULL;
17 pTrie->heaps[0] = createHeap(sizeof(triebody));
19 pTrie->heaps[i] = createHeap(i*sizeof(struct schild));
23 uint sizeofTrie(triebody *t)
26 size = sizeof(uint)+sizeof(short)+sizeof(struct schild *);
27 for (i=0;i<t->nchildren;i++)
28 size += sizeof(byte)+sizeof(struct striebody *)+sizeofTrie(t->children[i].trie);
34 void destroyTrie (trie pTrie)
37 for (i=0;i<256;i++) destroyHeap (pTrie->heaps[i]);
41 // inserts word[0...] into pTrie and returns new text ptr
42 // insertion proceeds until we get a new trie node
44 byte *insertTrie (trie pTrie, byte *word)
46 { triebody *t = &pTrie->trie;
51 // traverse pTrie with word[0...]
54 while (i < t->nchildren)
55 { if (t->children[i].car >= word[m]) break;
58 if ((i == t->nchildren) || (t->children[i].car > word[m]))
59 break; // not found, get out
60 t = t->children[i].trie;
63 // at this point we fell off the trie, which is guaranteed to occur
64 // since the text finishes with the unique character 0
65 newc = mallocHeap(pTrie->heaps[t->nchildren+1]);
66 memcpy (newc,t->children,i*sizeof(struct schild));
67 memcpy (newc+i+1,t->children+i,(t->nchildren-i)*sizeof(struct schild));
68 freeHeap (pTrie->heaps[t->nchildren],t->children);
70 t->children[i].car = word[m];
71 nt = mallocHeap (pTrie->heaps[0]);
72 t->children[i].trie = nt;
75 nt->id = pTrie->nid++;
78 // return rest of text
82 // inserts word[0..len-1] into pTrie, with id = id
83 // assumes that no two equal strings are ever inserted
85 void insertstringTrie (trie pTrie, byte *word, uint len, uint id)
90 // traverse pTrie with word[0...]
95 while (i < t->nchildren)
96 { if (t->children[i].car >= word[m]) break;
99 if ((i == t->nchildren) || (t->children[i].car > word[m]))
100 break; // not found, get out
101 t = t->children[i].trie;
104 // if we fell off the trie, we create more (unary and empty) nodes
106 { newc = mallocHeap(pTrie->heaps[t->nchildren+1]);
107 memcpy (newc,t->children,i*sizeof(struct schild));
108 memcpy (newc+i+1,t->children+i,(t->nchildren-i)*sizeof(struct schild));
109 freeHeap (pTrie->heaps[t->nchildren],t->children);
111 if ((t->id == ~0) && (t->nchildren == 1)) pTrie->nid++; //not mute now
112 t->children[i].car = word[m];
113 nt = mallocHeap (pTrie->heaps[0]);
114 nt->id = ~0; // empty node, at least for now
117 t->children[i].trie = nt;
122 // new node created or existing node with id added
124 if (t->nchildren <= 1) pTrie->nid++; //not mute now
127 // represents pTrie with parentheses, letters and ids
129 // also returns the leftmost id
130 static uint traverse(triebody *t, uint *parent, byte *letters, uint *ids,
133 uint i,chid,oldpli,myid;
136 bitclean(parent,*pi);
141 for (i=0; i<t->nchildren; i++) {
143 letters[*pli] = t->children[i].car;
144 chid = traverse(t->children[i].trie,parent,letters,ids,pi,pli);
149 // return leftmost id
153 void representTrie (trie pTrie, uint *parent, byte *letters, uint *ids)
156 letters[0] = 0; // dummy value
158 traverse(&pTrie->trie,parent,letters,ids,&pi,&pli);