#include <utility>
#include <algorithm>
#include <vector>
+#include <array>
#include "xml-tree.hpp"
#include "utils_stub.hpp"
+#include <iostream>
+// #include <algorithm>
+using namespace std;
+
+vector<int32_t> myvector;
+vector<int32_t>::iterator it=myvector.begin();
+vector<int32_t> myvector2;
+vector<int32_t>::iterator it2=myvector2.begin();
+xml_tree * tree;
+xml_tree::tag_t tag;
+xml_tree::tag_t tag2;
//define a type for the lexicographic index
std::vector<std::pair<std::string, xml_tree::node_t> > data;
};
-
+// class prefix_treeNode {
+// public:
+ // std::map<char, prefix_treeNode> Children;
+// std::array<prefix_treeNode, 256> Children;
+// uint32 textID;
+//};
using namespace SXSI;
return static_cast<xml_tree::tag_t>(Int_val(i));
}
+void preorderTraverse(xml_tree::tag_t parent_tag, xml_tree::node_t node){
+ if (tree->tag(node)==tree->PCDATA_OPEN_TAG_ID)
+ if (parent_tag==tag) it = myvector.insert(it, tree->text_id(node));
+ else if (parent_tag==tag2) it2 = myvector2.insert(it2, tree->text_id(node));
+ if (tree->tag(tree->first_child(node))!=0) preorderTraverse(tree->tag(node), tree->first_child(node));
+ if (tree->tag(tree->next_sibling(node))!=0) preorderTraverse(parent_tag, tree->next_sibling(node));
+}
+bool myfunction (int32_t i,int32_t j) {
+ return (strcmp((const char*) tree->get_text(i),
+ (const char*) tree->get_text(j))<0);
+}
+vector<int32_t> mergeJoin(vector<int32_t> v1, vector<int32_t> v2){
+ vector<int32_t> v;
+ vector<int32_t>::iterator i=v.begin();
+ vector<int32_t>::iterator i1=v1.begin();
+ vector<int32_t>::iterator i2=v2.begin();
+ int k;
+
+ while((i1!=v1.end()) && (i2!=v2.end())){
+ k = strcmp((const char*) tree->get_text(*i1),
+ (const char*) tree->get_text(*i2));
+ if (k==0)
+ {
+ i = v.insert( i, *i1 );
+ //advance left
+ i1++;
+ //advance right
+ i2++;
+ }
+ else if (k<0) i1++; //advance left
+ else i2++; //advance right
+ }
+ return(v);
+}
-extern "C" value caml_build_lex_index(value vtree, value vtag)
+void printIndex(const char * label, vector<int32_t> v){
+ vector<int32_t>::iterator i=v.begin();
+ if (i!=v.end()) {
+ printf("%s-vector: [%i", label, *i);
+ for (++i; i!=v.end(); ++i)
+ printf(",%i", *i);
+ printf("]\n");
+ }
+}
+
+ML_BINDING value caml_build_lex_index(value vtree, value vtag, value vtag2)
{
CAMLparam2(vtree, vtag);
CAMLlocal1(vindex);
+ const char * s;
vindex = sxsi_alloc_custom<lex_index*>();
- xml_tree * tree = XMLTREE(vtree);
- xml_tree::tag_t tag = TAG(vtag);
-
+ tree = XMLTREE(vtree);
+ tag = TAG(vtag);
+ tag2 = TAG(vtag2);
+
//Uncomment the following and comment the failwith line
//LEXINDEX(vindex) = ... return a lex_index* ....
+ if ((tag==-1) || (tag2==-1)) caml_failwith("<INVALID TAG>");
- caml_failwith("build_lex_index not implemented");
-
-
- CAMLreturn (vindex);
+ preorderTraverse(0, tree->first_child(tree->ROOT));
+ sort(myvector.begin(), myvector.end(), myfunction);
+ sort(myvector2.begin(), myvector2.end(), myfunction);
+ printIndex(tree->get_tag_name_by_ref(tag), myvector);
+ printIndex(tree->get_tag_name_by_ref(tag2), myvector2);
+ printIndex("Result" , mergeJoin(myvector, myvector2));
}
-extern "C" value caml_print_lex_index(value vindex)
+ML_BINDING value caml_print_lex_index(value vindex)
{
CAMLparam1(vindex);
lex_index* index = LEXINDEX(vindex);
caml_failwith("print_lex_index not implemented");
-
CAMLreturn (Val_unit);
}