testing
[SXSI/XMLTree.git] / XMLTree.cpp
1 \r
2 #include "XMLTree.h"\r
3 #include <cstring>\r
4 // functions to convert tag positions to the corresponding tree node and viceversa. \r
5 // These are implemented in order to be able to change the tree and Tags representations, \r
6 // without affecting the code so much.\r
7 // Current implementation corresponds to balanced-parentheses representation for\r
8 // the tree, and storing 2 tags per tree node (opening and closing tags).\r
9 \r
10 // tag position -> tree node\r
11 inline treeNode tagpos2node(int t) {\r
12    return (treeNode)t;\r
13 }\r
14 \r
15 // tree node -> tag position\r
16 inline int node2tagpos(treeNode x) {\r
17    return (int)x;\r
18 }\r
19 \r
20 // Save: saves XML tree data structure to file. \r
21 void XMLTree::Save(unsigned char *filename) \r
22  {\r
23 \r
24     FILE *fp;\r
25     char filenameaux[1024];\r
26     int i;\r
27    \r
28     sprintf(filenameaux, "%s.srx", filename);\r
29     fp = fopen(filenameaux, "w");\r
30     if (fp == NULL) {\r
31        printf("Error: cannot create file %s to store the tree structure of XML collection\n", filenameaux);\r
32        exit(1);\r
33     } \r
34     \r
35     // first stores the tree topology\r
36     saveTree(Par, fp);\r
37  \r
38     // stores the table with tag names\r
39     fwrite(&ntagnames, sizeof(int), 1, fp);\r
40     for (i=0; i<ntagnames;i++)\r
41        fprintf(fp, "%s\n",TagName[i]);\r
42     \r
43     // stores the flags\r
44     fwrite(&indexing_empty_texts, sizeof(bool), 1, fp);\r
45     fwrite(&initialized, sizeof(bool), 1, fp);\r
46     fwrite(&finished, sizeof(bool), 1, fp);\r
47     \r
48     if (!indexing_empty_texts) EBVector->save(fp);\r
49     \r
50     // stores the tags\r
51     Tags->save(fp);\r
52 \r
53     // stores the texts   \r
54     //Text->Save(fp);\r
55 \r
56     fclose(fp);\r
57 \r
58  }\r
59 \r
60 \r
61 // Load: loads XML tree data structure from file. Returns\r
62 // a pointer to the loaded data structure\r
63 XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) \r
64  {\r
65 \r
66     FILE *fp;\r
67     char filenameaux[1024];\r
68     XMLTree *XML_Tree;\r
69     int i;\r
70     \r
71     // first load the tree topology\r
72     sprintf(filenameaux, "%s.srx", filename);\r
73     fp = fopen(filenameaux, "r");\r
74     if (fp == NULL) {\r
75        printf("Error: cannot open file %s to load the tree structure of XML collection\n", filenameaux);\r
76        exit(1);\r
77     } \r
78 \r
79     XML_Tree = new XMLTree();\r
80 \r
81     XML_Tree->Par = (bp *)malloc(sizeof(bp));\r
82 \r
83     loadTree(XML_Tree->Par, fp); \r
84     \r
85     // stores the table with tag names\r
86     fread(&XML_Tree->ntagnames, sizeof(int), 1, fp);\r
87 \r
88     XML_Tree->TagName = (unsigned char **)malloc(XML_Tree->ntagnames*sizeof(unsigned char *));\r
89 \r
90     for (i=0; i<XML_Tree->ntagnames;i++) {\r
91        int k = feof(fp);\r
92        fscanf(fp, "%s\n",filenameaux);\r
93        XML_Tree->TagName[i] = (unsigned char *)malloc(sizeof(unsigned char)*(strlen((const char *)filenameaux)+1));\r
94        strcpy((char *)XML_Tree->TagName[i], (const char *)filenameaux);\r
95     }\r
96         \r
97     // loads the flags\r
98     fread(&(XML_Tree->indexing_empty_texts), sizeof(bool), 1, fp);\r
99     fread(&(XML_Tree->initialized), sizeof(bool), 1, fp);\r
100     fread(&(XML_Tree->finished), sizeof(bool), 1, fp);\r
101     \r
102     if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);\r
103 \r
104     // loads the tags\r
105     XML_Tree->Tags = static_sequence_wvtree::load(fp);\r
106 \r
107     // loads the texts   \r
108     //XML_Tree->Text->Load(fp,sample_rate_text);\r
109 \r
110     fclose(fp);\r
111     \r
112     return XML_Tree;\r
113  }\r
114 \r
115 \r
116 // ~XMLTree: frees memory of XML tree.\r
117 XMLTree::~XMLTree() \r
118  { \r
119     int i;\r
120 \r
121     destroyTree(Par);\r
122     free(Par); // frees the memory of struct Par\r
123    \r
124     for (i=0; i<ntagnames;i++) \r
125        free(TagName[i]);\r
126     \r
127     free(TagName);\r
128 \r
129     if (!indexing_empty_texts) {\r
130        EBVector->~static_bitsequence_rrr02();\r
131        delete EBVector;\r
132        EBVector = NULL;\r
133     }\r
134 \r
135     Tags->~static_sequence_wvtree();\r
136     delete Tags;\r
137     Tags = NULL;\r
138 \r
139     //Text->~TextCollection();\r
140    // delete Text;\r
141    // Text = NULL;\r
142 \r
143     initialized = false;\r
144     finished = false;\r
145  }\r
146 \r
147 // root(): returns the tree root.\r
148 treeNode XMLTree::Root() \r
149  {\r
150     return root_node(Par);\r
151  }\r
152 \r
153 // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.\r
154 int XMLTree::SubtreeSize(treeNode x) \r
155  {\r
156     return subtree_size(Par, x);\r
157  }\r
158 \r
159 // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.\r
160 int XMLTree::SubtreeTags(treeNode x, TagType tag) \r
161  {\r
162     int s = x + 2*subtree_size(Par, x) - 1;\r
163  \r
164     return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1);\r
165  }\r
166 \r
167 // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation\r
168 // this is just a bit inspection.\r
169 bool XMLTree::IsLeaf(treeNode x) \r
170  {\r
171     return isleaf(Par, x);\r
172  } \r
173 \r
174 // IsAncestor(x,y): returns whether node x is ancestor of node y.\r
175 bool XMLTree::IsAncestor(treeNode x, treeNode y) \r
176  {\r
177     return is_ancestor(Par, x, y);\r
178  }\r
179 \r
180 // IsChild(x,y): returns whether node x is parent of node y.\r
181 bool XMLTree::IsChild(treeNode x, treeNode y) \r
182  {\r
183     if (!is_ancestor(Par, x, y)) return false;\r
184     return depth(Par, x) == (depth(Par, y) + 1);\r
185  }\r
186 \r
187 // NumChildren(x): number of children of node x. Constant time with the data structure\r
188 // of Sadakane.\r
189 int XMLTree::NumChildren(treeNode x) \r
190  {\r
191     return degree(Par, x);\r
192  }\r
193 \r
194 // ChildNumber(x): returns i if node x is the i-th children of its parent.\r
195 int XMLTree::ChildNumber(treeNode x) \r
196  {\r
197     return child_rank(Par, x);\r
198  }\r
199 \r
200 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.\r
201 int XMLTree::Depth(treeNode x) \r
202  {\r
203     return depth(Par, x);\r
204  }\r
205 \r
206 // Preorder(x): returns the preorder number of node x, just counting the tree\r
207 // nodes (i.e., tags, it disregards the texts in the tree).\r
208 int XMLTree::Preorder(treeNode x) \r
209  {\r
210     return preorder_rank(Par, x);\r
211  }\r
212 \r
213 // Postorder(x): returns the postorder number of node x, just counting the tree\r
214 // nodes (i.e., tags, it disregards the texts in the tree).\r
215 int XMLTree::Postorder(treeNode x) \r
216  {\r
217     return postorder_rank(Par, x);\r
218  }\r
219 \r
220 // Tag(x): returns the tag identifier of node x.\r
221 TagType XMLTree::Tag(treeNode x) \r
222  {\r
223     return Tags->access(node2tagpos(x));\r
224  }\r
225 \r
226 // DocIds(x): returns the range of text identifiers that descend from node x.\r
227 // returns {NULLT, NULLT} when there are no texts descending from x.\r
228 range XMLTree::DocIds(treeNode x) \r
229  {\r
230     range r;\r
231     if (indexing_empty_texts) { // faster, no rank needed\r
232        r.min = x;\r
233        r.max = x+2*subtree_size(Par, x)-2;\r
234     }\r
235     else { // we are not indexing empty texts, we need rank\r
236        int min = EBVector->rank1(x-1);                          \r
237        int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); \r
238        if (min==max) { // range is empty, no texts within the subtree of x\r
239           r.min = NULLT;\r
240           r.max = NULLT;\r
241        }\r
242        else { // the range is non-empty, there are texts within the subtree of x\r
243           r.min = min+1;\r
244           r.max = max;\r
245        }\r
246     }\r
247     return r;\r
248  }\r
249 \r
250 // Parent(x): returns the parent node of node x.\r
251 treeNode XMLTree::Parent(treeNode x) \r
252  {\r
253     return parent(Par, x);\r
254  }\r
255 \r
256 // Child(x,i): returns the i-th child of node x, assuming it exists.\r
257 treeNode XMLTree::Child(treeNode x, int i) \r
258  {\r
259     if (i <= OPTD) return naive_child(Par, x, i);\r
260     else return child(Par, x, i);\r
261  }\r
262 \r
263 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.\r
264 treeNode XMLTree::FirstChild(treeNode x) \r
265  {\r
266     return first_child(Par, x);\r
267  }\r
268 \r
269 // NextSibling(x): returns the next sibling of node x, assuming it exists.\r
270 treeNode XMLTree::NextSibling(treeNode x) \r
271  {\r
272     return next_sibling(Par, x);\r
273  }\r
274 \r
275 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.\r
276 treeNode XMLTree::PrevSibling(treeNode x) \r
277  {\r
278     return prev_sibling(Par, x);\r
279  }\r
280 \r
281 // TaggedChild(x,i,tag): returns the i-th child of node x tagged tag, or NULLT if there is none.\r
282 // Because of the balanced-parentheses representation of the tree, this operation is not supported\r
283 // efficiently, just iterating among the children of node x until finding the desired child.\r
284 treeNode XMLTree::TaggedChild(treeNode x, int i, TagType tag) \r
285  {\r
286     treeNode child;\r
287    \r
288     child = first_child(Par, x); // starts at first child of node x\r
289     if (child==(treeNode)-1) return NULLT; // node x is a leaf, there is no such child\r
290     while (child!=(treeNode)-1) {\r
291        if (Tags->access(node2tagpos(child)) == tag) { // current child is labeled with tag of interest\r
292           i--;\r
293           if (i==0) return child; // we have seen i children of x tagged tag, this is the one we are looking for\r
294        }\r
295        child = next_sibling(Par, x); // OK, let's try with the next child\r
296     }\r
297     return NULLT; // no such child was found  \r
298  }\r
299 \r
300 // TaggedDesc(x,tag): returns the first node tagged tag with larger preorder than x and within\r
301 // the subtree of x. Returns NULLT if there is none.\r
302 treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) \r
303  {\r
304     int r, s;\r
305     treeNode y;\r
306     r = (int) Tags->rank(tag, node2tagpos(x));\r
307     s = (int) Tags->select(tag, r+1);\r
308     if (s == -1) return NULLT; // there is no such node\r
309     y = tagpos2node(s); // transforms the tag position into a node position\r
310     if (!is_ancestor(Par, x, y)) return NULLT; // the next node tagged tag (in preorder) is not within the subtree of x.\r
311     else return y;\r
312  }\r
313 \r
314 // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an\r
315 // ancestor of x. Returns NULLT if there is none.\r
316 treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) \r
317  {\r
318     int r, s;\r
319     treeNode node_s, root;\r
320     r = (int)Tags->rank(tag, node2tagpos(x)-1);\r
321     if (r==0) return NULLT; // there is no such node.\r
322     s = (int)Tags->select(tag, r);\r
323     root = root_node(Par);\r
324     node_s = tagpos2node(s);\r
325     while (is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x\r
326        r--;\r
327        if (r==0) return NULLT; // there is no such node\r
328        s = (int)Tags->select(tag, r);  // we should use select_prev instead when provided\r
329        node_s = tagpos2node(s);\r
330     }\r
331     return NULLT; // there is no such node \r
332  }\r
333 \r
334 // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in\r
335 // the subtree of x. Returns NULLT if there is none.\r
336 treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) \r
337  {\r
338     int r, s;\r
339     r = (int) Tags->rank(tag, node2tagpos(next_sibling(Par, x))-1);\r
340     s = (int) Tags->select(tag, r+1);  // select returns -1 in case that there is no r+1-th tag.\r
341     if (s==-1) return NULLT;\r
342     else return tagpos2node(s);\r
343  }\r
344 \r
345 // PrevText(x): returns the document identifier of the text to the left \r
346 // of node x, or NULLT if x is the root node or the text is empty.\r
347 // Assumes Doc ids start from 0.\r
348 DocID XMLTree::PrevText(treeNode x) \r
349  {\r
350     if (x == Root()) return NULLT;\r
351     if (indexing_empty_texts)  // faster, no rank needed\r
352        return (DocID)x-1;\r
353     else { // we are not indexing empty texts, rank is needed\r
354        if (EBVector->access(x-1) == 0) \r
355           return (DocID)NULLT;  // there is no text to the left of node (text is empty)\r
356        else\r
357           return (DocID)EBVector->rank1(x-1)-1;  //-1 because document ids start from 0\r
358     }\r
359  }\r
360 \r
361 // NextText(x): returns the document identifier of the text to the right\r
362 // of node x, or NULLT if x is the root node. Assumes Doc ids start from 0.\r
363 DocID XMLTree::NextText(treeNode x) \r
364  {\r
365     if (x == Root()) return NULLT;\r
366     if (indexing_empty_texts)  // faster, no rank needed\r
367        return (DocID)x+2*subtree_size(Par, x)-1;\r
368     else { // we are not indexing empty texts, rank is needed\r
369        int p = x+2*subtree_size(Par, x)-1;\r
370        if (EBVector->access(p) == 0) // there is no text to the right of node\r
371           return (DocID)NULLT;\r
372        else\r
373           return (DocID)EBVector->rank1(p)-1; //-1 because document ids start from 0\r
374     }\r
375  }\r
376 \r
377 // MyText(x): returns the document identifier of the text below node x, \r
378 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc \r
379 // ids start from 0.\r
380 DocID XMLTree::MyText(treeNode x) \r
381  {\r
382     if (!IsLeaf(x)) return NULLT;\r
383     if (indexing_empty_texts) // faster, no rank needed\r
384        return (DocID)x;\r
385     else { // we are not indexing empty texts, rank is needed\r
386        if (EBVector->access(x) == 0)  // there is no text below node x\r
387           return (DocID)NULLT;\r
388        else\r
389           return (DocID)EBVector->rank1(x)-1; //-1 because document ids start from 0\r
390     } \r
391  }\r
392 \r
393 // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of\r
394 // all tree nodes and all text nodes. Assumes that the tree root has preorder 1.\r
395 int XMLTree::TextXMLId(DocID d) \r
396  {\r
397     if (indexing_empty_texts) \r
398        return d + rank_open(Par, d)+1; // +1 because root has preorder 1\r
399     else { // slower, needs rank and select\r
400        int s = EBVector->select1(d+1);\r
401        return rank_open(Par, s) + d + 1; // +1 because root has preorder 1\r
402     }\r
403  }\r
404 \r
405 // NodeXMLId(x): returns the preorder of node x in the tree consisting \r
406 // of all tree nodes and all text nodes. Assumes that the tree root has\r
407 // preorder 0;\r
408 int XMLTree::NodeXMLId(treeNode x) \r
409  {\r
410     if (indexing_empty_texts)\r
411        return x - 1 + rank_open(Par, x);\r
412     else {\r
413        if (x == Root()) return 1; // root node has preorder 1\r
414        else\r
415           return rank_open(Par, x) + EBVector->rank1(x-1);\r
416     }\r
417  }\r
418 \r
419 // ParentNode(d): returns the parent node of document identifier d.\r
420 treeNode XMLTree::ParentNode(DocID d) \r
421  {\r
422     int s;\r
423     if (indexing_empty_texts) s = d;\r
424     else s = EBVector->select1(d);\r
425     \r
426     if (inspect(Par,s) == CP) // is a closing parenthesis\r
427        return parent(Par, find_open(Par, s));\r
428     else // is an opening parenthesis\r
429        return (treeNode)s;\r
430      \r
431  }\r
432 \r
433 \r
434 // OpenDocument(empty_texts): it starts the construction of the data structure for\r
435 // the XML document. Parameter empty_texts indicates whether we index empty texts\r
436 // in document or not. Returns a non-zero value upon success, NULLT in case of error.\r
437 int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text)\r
438  {\r
439     initialized = true;\r
440     finished = false;\r
441     npar = 0;\r
442     ntagnames = 0;\r
443     \r
444     indexing_empty_texts = empty_texts;\r
445     \r
446     par_aux = (pb *)malloc(sizeof(pb));\r
447     if (!par_aux) {\r
448        fprintf(stderr, "Error: not enough memory\n");\r
449        return NULLT;\r
450     }\r
451     setbit(par_aux,npar,OP);  // marks a new opening parenthesis for the tree root\r
452     npar++;\r
453     \r
454     tags_aux = (TagType *)malloc(sizeof(TagType));\r
455     if (!tags_aux) {\r
456        fprintf(stderr, "Error: not enough memory\n");\r
457        return NULLT;\r
458     }\r
459     \r
460     if (!indexing_empty_texts) {\r
461        empty_texts_aux = (unsigned int *)malloc(sizeof(unsigned int));\r
462        if (!empty_texts_aux) {\r
463           fprintf(stderr, "Error: not enough memory\n");\r
464           return NULLT;\r
465        }\r
466     }\r
467     \r
468     //Text = TextCollection::InitTextCollection(sample_rate_text);\r
469     \r
470     return 1;  // indicates success in the initialization of the data structure\r
471  }\r
472 \r
473 // CloseDocument(): it finishes the construction of the data structure for the XML\r
474 // document. Tree and tags are represented in the final form, dynamic data \r
475 // structures are made static, and the flag "finished" is set to true. After that, \r
476 // the data structure can be queried.\r
477 int XMLTree::CloseDocument()\r
478  {\r
479     if (!initialized) {  // data structure has not been initialized properly\r
480        fprintf(stderr, "Error: data structure has not been initialized properly (by calling method OpenDocument)\n");\r
481        return NULLT;\r
482     }\r
483     \r
484     // closing parenthesis for the tree root\r
485     par_aux = (pb *)realloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb))));\r
486     if (!par_aux) {\r
487        fprintf(stderr, "Error: not enough memory\n");\r
488        return NULLT;    \r
489     }\r
490     setbit(par_aux,npar,CP); \r
491     npar++;\r
492     \r
493     // creates the data structure for the tree topology\r
494     Par = (bp *)malloc(sizeof(bp));      \r
495     bp_construct(Par, npar, par_aux, OPT_DEGREE|0);    \r
496     // creates structure for tags\r
497     alphabet_mapper * am = new alphabet_mapper_none();\r
498     static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(32); \r
499     wt_coder * wtc = new wt_coder_huff((uint *)tags_aux,npar-1,am);\r
500     Tags = new static_sequence_wvtree((uint *) tags_aux, (uint) npar-1, wtc, bmb, am);\r
501 \r
502     // makes the text collection static\r
503     //Text->MakeStatic();\r
504     \r
505     // creates the data structure marking the non-empty texts (just in the case it is necessary)\r
506     if (!indexing_empty_texts) \r
507        EBVector = new static_bitsequence_rrr02((uint *)empty_texts_aux,(ulong)npar,(uint)32);\r
508 \r
509     finished = true;\r
510 \r
511     return 1; // indicates success in the inicialization\r
512  }\r
513 \r
514 \r
515 // NewOpenTag(tagname): indicates the event of finding a new opening tag in the document.\r
516 // Tag name is given. Returns a non-zero value upon success, and returns NULLT\r
517 // in case of failing when trying to insert the new tag.\r
518 int XMLTree::NewOpenTag(unsigned char *tagname)\r
519  {\r
520     int i;\r
521 \r
522     if (!initialized) {  // data structure has not been initialized properly\r
523        fprintf(stderr, "Error: you cannot insert a new opening tag without first calling method OpenDocument first\n");\r
524        return NULLT;\r
525     }\r
526     \r
527     // inserts a new opening parentheses in the bit sequence\r
528     par_aux = (pb *)realloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb))));\r
529     if (!par_aux) {\r
530        fprintf(stderr, "Error: not enough memory\n");\r
531        return NULLT;    \r
532     }\r
533     setbit(par_aux,npar,OP);  // marks a new opening parenthesis\r
534 \r
535     // transforms the tagname into a tag identifier. If the tag is new, we insert\r
536     // it in the table.\r
537     for (i=0; i<ntagnames; i++)\r
538        if (strcmp((const char *)tagname,(const char *)TagName[i])==0) break;\r
539  \r
540     if (i==ntagnames) { // the tag is a new one, then we insert it\r
541        TagName = (unsigned char **)realloc(TagName, sizeof(char *)*(ntagnames+1));\r
542        \r
543        if (!TagName) {\r
544           fprintf(stderr, "Error: not enough memory\n");\r
545           return NULLT;\r
546        }\r
547        \r
548        ntagnames++;\r
549        TagName[i] = (unsigned char *)malloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1));\r
550        strcpy((char *)TagName[i], (const char *)tagname);\r
551     } \r
552     \r
553     tags_aux = (TagType *)realloc(tags_aux, sizeof(TagType)*(npar + 1));\r
554 \r
555     if (!tags_aux) {\r
556        fprintf(stderr, "Error: not enough memory\n");\r
557        return NULLT;\r
558     }\r
559 \r
560     tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags\r
561     \r
562     npar++;\r
563 \r
564     return 1;\r
565     \r
566  }\r
567 \r
568 \r
569 // NewClosingTag(tagname): indicates the event of finding a new closing tag in the document.\r
570 // Tag name is given. Returns a non-zero value upon success, and returns NULLT\r
571 // in case of failing when trying to insert the new tag.\r
572 int XMLTree::NewClosingTag(unsigned char *tagname)\r
573  {\r
574     int i;\r
575 \r
576     if (!initialized) {  // data structure has not been initialized properly\r
577        fprintf(stderr, "Error: you cannot insert a new closing tag without first calling method OpenDocument first\n");\r
578        return NULLT;\r
579     }\r
580     \r
581     // inserts a new closing parentheses in the bit sequence\r
582     par_aux = (pb *)realloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb))));\r
583     if (!par_aux) {\r
584        fprintf(stderr, "Error: not enough memory\n");\r
585        return NULLT;    \r
586     }\r
587     setbit(par_aux,npar,CP);  // marks a new closing opening parenthesis\r
588 \r
589     // transforms the tagname into a tag identifier. If the tag is new, we insert\r
590     // it in the table.\r
591     for (i=0; i<ntagnames; i++)\r
592        if (strcmp((const char *)tagname,(const char *)TagName[i])==0) break;\r
593  \r
594     if (i==ntagnames) { // the tag is a new one, then we insert it\r
595        TagName = (unsigned char **)realloc(TagName, sizeof(char *)*(ntagnames+1));\r
596        \r
597        if (!TagName) {\r
598           fprintf(stderr, "Error: not enough memory\n");\r
599           return NULLT;\r
600        }\r
601        \r
602        ntagnames++;\r
603        TagName[i] = (unsigned char *)malloc(sizeof(char)*(strlen((const char *)tagname)+1));\r
604        strcpy((char *)TagName[i], (const char *)tagname);\r
605     } \r
606 \r
607     tags_aux = (TagType *)realloc(tags_aux, sizeof(TagType)*(npar + 1));\r
608 \r
609     if (!tags_aux) {\r
610        fprintf(stderr, "Error: not enough memory\n");\r
611        return NULLT;\r
612     }\r
613 \r
614     tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags\r
615     \r
616     npar++;\r
617 \r
618     return 1; // success\r
619     \r
620  }\r
621 \r
622 \r
623 // NewText(s): indicates the event of finding a new (non-empty) text s in the document.\r
624 // The new text is inserted within the text collection. Returns a non-zero value upon\r
625 // success, NULLT in case of error.\r
626 int XMLTree::NewText(unsigned char *s)\r
627  {\r
628     if (!initialized) {  // data structure has not been initialized properly\r
629        fprintf(stderr, "Error: you cannot insert a new text without first calling method OpenDocument first\n");\r
630        return NULLT;\r
631     }\r
632 \r
633     if (!indexing_empty_texts) {\r
634        empty_texts_aux = (unsigned int *)realloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb))));\r
635        if (!empty_texts_aux) {\r
636           fprintf(stderr, "Error: not enough memory\n");\r
637           return NULLT;\r
638        }\r
639        \r
640        bitset(empty_texts_aux, npar-1);  // marks the non-empty text with a 1 in the bit vector\r
641     }\r
642     \r
643     //Text->InsertText(s);\r
644     \r
645     return 1; // success\r
646  }\r
647 \r
648 // NewEmptyText(): indicates the event of finding a new empty text in the document.\r
649 // In case of indexing empty and non-empty texts, we insert the empty texts into the\r
650 // text collection. In case of indexing only non-empty texts, it just indicates an\r
651 // empty text in the bit vector of empty texts. Returns a non-zero value upon\r
652 // success, NULLT in case of error.\r
653 int XMLTree::NewEmptyText() \r
654  {\r
655     unsigned char c = 0;\r
656     if (!initialized) {  // data structure has not been initialized properly\r
657        fprintf(stderr, "Error: you cannot insert a new empty text without first calling method OpenDocument first\n");\r
658        return NULLT;\r
659     }\r
660 \r
661     if (!indexing_empty_texts) {\r
662        empty_texts_aux = (unsigned int *)realloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb))));\r
663        if (!empty_texts_aux) {\r
664           fprintf(stderr, "Error: not enough memory\n");\r
665           return NULLT;\r
666        }\r
667        \r
668        bitclean(empty_texts_aux, npar-1);  // marks the empty text with a 0 in the bit vector\r
669     }\r
670    // else Text->InsertText(&c); // we insert the empty text just in case we index all the texts\r
671     \r
672     return 1; // success    \r
673  }\r
674 \r
675 \r
676 // GetTagId: returns the tag identifier corresponding to a given tag name.\r
677 // Returns NULLT in case that the tag name does not exists.\r
678 TagType XMLTree::GetTagId(unsigned char *tagname)\r
679  {\r
680     int i;\r
681     // this should be changed for more efficient processing\r
682     for (i=0; i<ntagnames; i++)\r
683        if (strcmp((const char *)tagname,(const char *)TagName[i])==0) break; \r
684     if (i==ntagnames) return (TagType)NULLT; // tagname does not exists in the table\r
685     else return i;\r
686  }\r
687 \r
688 \r
689 // GetTagName(tagid): returns the tag name of a given tag identifier.\r
690 // Returns NULL in case that the tag identifier is not valid.\r
691 unsigned char *XMLTree::GetTagName(TagType tagid)\r
692  {\r
693     unsigned char *s;\r
694 \r
695     if (tagid >= ntagnames) return NULL; // invalid tag identifier\r
696     s = (unsigned char *)malloc((strlen((const char *)TagName[tagid])+1)*sizeof(unsigned char));\r
697     strcpy((char *)s, (const char *)TagName[tagid]);\r
698     return s;\r
699  }\r
700 \r