6 #include "xml-tree.hpp"
7 #include "utils_stub.hpp"
10 // #include <algorithm>
15 bool operator() (int32_t i,int32_t j) {
16 return (strcmp((const char*) tree->get_text(i),
17 (const char*) tree->get_text(j))<0);}
20 //define a type for the lexicographic index
27 vector<int32_t> tagVector;
28 vector<int32_t>::iterator tagVectorIt;
29 vector<int32_t> tag2Vector;
30 vector<int32_t>::iterator tag2VectorIt;
31 void printVector(xml_tree::tag_t t, vector<int32_t> v);
35 void lex_index::printVector(xml_tree::tag_t t, vector<int32_t> v){
36 vector<int32_t>::iterator i=v.begin();
38 printf("%i-vector: [%i", t, *i);
39 for (++i; i!=v.end(); ++i)
45 void lex_index::print(){
46 printf("Print called\n");
47 printVector(tag, tagVector);
48 printVector(tag2, tag2Vector);
51 // class prefix_treeNode {
53 // std::map<char, prefix_treeNode> Children;
54 // std::array<prefix_treeNode, 256> Children;
60 static xml_tree*& XMLTREE(value v)
62 return Obj_val<xml_tree*>(v);
65 static lex_index*& LEXINDEX(value v)
67 return Obj_val<lex_index*>(v);
70 static xml_tree::node_t TREENODE(value i)
72 return static_cast<xml_tree::node_t>(Int_val(i));
75 static xml_tree::tag_t TAG(value i)
77 return static_cast<xml_tree::tag_t>(Int_val(i));
80 void preorderTraverse(xml_tree * tree, xml_tree::tag_t parent_tag, xml_tree::node_t node, lex_index* lindex){
81 if (tree->tag(node)==tree->PCDATA_OPEN_TAG_ID)
82 if (parent_tag==lindex->tag) lindex->tagVectorIt =
83 lindex->tagVector.insert(lindex->tagVectorIt, tree->text_id(node));
84 else if (parent_tag==lindex->tag2) lindex->tag2VectorIt =
85 lindex->tag2Vector.insert(lindex->tag2VectorIt, tree->text_id(node));
86 if (tree->tag(tree->first_child(node))!=0) preorderTraverse(tree,tree->tag(node),tree->first_child(node),lindex);
87 if (tree->tag(tree->next_sibling(node))!=0) preorderTraverse(tree,parent_tag,tree->next_sibling(node),lindex);
90 vector<int32_t> mergeJoin(xml_tree * tree, vector<int32_t> v1, vector<int32_t> v2){
92 vector<int32_t>::iterator i=v.begin();
93 vector<int32_t>::iterator i1=v1.begin();
94 vector<int32_t>::iterator i2=v2.begin();
97 while((i1!=v1.end()) && (i2!=v2.end())){
98 k = strcmp((const char*) tree->get_text(*i1),
99 (const char*) tree->get_text(*i2));
102 i = v.insert( i, *i1 );
108 else if (k<0) i1++; //advance left
109 else i2++; //advance right
114 void printVector(const char * label, vector<int32_t> v){
115 vector<int32_t>::iterator i=v.begin();
117 printf("%s-vector: [%i", label, *i);
118 for (++i; i!=v.end(); ++i)
124 ML_BINDING value caml_build_lex_index(value vtree, value vtag, value vtag2)
126 CAMLparam2(vtree, vtag);
128 vindex = sxsi_alloc_custom<lex_index*>();
129 xml_tree * tree = XMLTREE(vtree);
130 myobject.tree = tree;
132 //allocate a lex index
133 lex_index* mylindex = new lex_index();
135 //take the tag parameter given by ocaml and convert
136 //it to a C++ tag and store it in the tag field of mylindex
137 if ((TAG(vtag)==-1) || (TAG(vtag2)==-1)) caml_failwith("<INVALID TAG>");
138 mylindex->tag = TAG(vtag);
139 mylindex->tag2 = TAG(vtag2);
141 //initialize iterators for the two vectors
142 mylindex->tagVectorIt=mylindex->tagVector.begin();
143 mylindex->tag2VectorIt=mylindex->tag2Vector.begin();
145 preorderTraverse(tree, 0, tree->first_child(tree->ROOT), mylindex);
146 sort(mylindex->tagVector.begin(), mylindex->tagVector.end(), myobject);
147 sort(mylindex->tag2Vector.begin(), mylindex->tag2Vector.end(), myobject);
148 printVector(tree->get_tag_name_by_ref(mylindex->tag), mylindex->tagVector);
149 printVector(tree->get_tag_name_by_ref(mylindex->tag2), mylindex->tag2Vector);
150 printVector("Result" , mergeJoin(tree, mylindex->tagVector, mylindex->tag2Vector));
152 //Uncomment the following and comment the failwith line
153 //LEXINDEX(vindex) = ... return a lex_index* ....
154 LEXINDEX(vindex)=mylindex;
157 ML_BINDING value caml_print_lex_index(value vindex)
160 lex_index* index = LEXINDEX(vindex);
162 //Print the index to the terminal
163 // caml_failwith("print_lex_index not implemented");
165 CAMLreturn (Val_unit);