X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=src%2Flexindex_stub.cpp;h=bf038b2596687c33570410311ea7f861cd131870;hb=8f5b2f0c7e95245c1b7f4cc18aa137ba8e784166;hp=a09216ef0096fee40110a870752928d614a0d273;hpb=852a21ccb090cc11e996d7bae3322882cc694e3e;p=SXSI%2Fxpathcomp.git

diff --git a/src/lexindex_stub.cpp b/src/lexindex_stub.cpp
index a09216e..bf038b2 100644
--- a/src/lexindex_stub.cpp
+++ b/src/lexindex_stub.cpp
@@ -2,9 +2,21 @@
 #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
 
@@ -16,7 +28,12 @@ public:
   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;
 
@@ -41,25 +58,74 @@ static xml_tree::tag_t TAG(value i)
   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");
+    }
+}
+
+extern "C" 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)
@@ -71,6 +137,5 @@ extern "C" value caml_print_lex_index(value vindex)
 
   caml_failwith("print_lex_index not implemented");
 
-
   CAMLreturn (Val_unit);
 }