src/lexindex_stub.cpp

   1 #include <cstring>
   2 #include <utility>
   3 #include <algorithm>
   4 #include <vector>
   5 #include <array>
   6 #include "xml-tree.hpp"
   7 #include "utils_stub.hpp"
   8 #include <iostream>
   9
  10 // #include <algorithm>
  11 using namespace std;
  12
  13 struct myclass {
  14   xml_tree * tree;
  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);}
  18 } myobject;
  19
  20 void printVector(vector<int32_t> v){
  21   vector<int32_t>::iterator i=v.begin();
  22   if (i!=v.end()) {
  23       printf("[%i", *i);
  24       for (++i; i!=v.end(); ++i)
  25         printf(",%i",  *i);
  26       printf("]\n");
  27     }
  28 }
  29
  30 //define a type for the lexicographic index
  31 class lex_index {
  32 public:
  33   //The tag IDs
  34   xml_tree::tag_t tag;
  35   xml_tree::tag_t tag2;
  36   //The text data
  37   vector<int32_t> tagVector;
  38   vector<int32_t>::iterator tagVectorIt;
  39   vector<int32_t> tag2Vector;
  40   vector<int32_t>::iterator tag2VectorIt;
  41   void preorderTraverse(xml_tree * tree, xml_tree::tag_t parent_tag, xml_tree::node_t node);
  42   void createIndex(xml_tree * tree);
  43   void print();
  44 };
  45
  46 void lex_index::preorderTraverse(xml_tree * tree, xml_tree::tag_t parent_tag, xml_tree::node_t node){
  47   if (tree->tag(node)==tree->PCDATA_OPEN_TAG_ID)
  48   if (parent_tag==tag) tagVectorIt = tagVector.insert(tagVectorIt, tree->text_id(node));
  49   else if (parent_tag==tag2) tag2VectorIt = tag2Vector.insert(tag2VectorIt, tree->text_id(node));
  50   if (tree->tag(tree->first_child(node))!=0) preorderTraverse(tree,tree->tag(node),tree->first_child(node));
  51   if (tree->tag(tree->next_sibling(node))!=0) preorderTraverse(tree,parent_tag,tree->next_sibling(node));
  52 }
  53
  54 void lex_index::createIndex(xml_tree * tree){
  55   tagVectorIt=tagVector.begin();
  56   tag2VectorIt=tag2Vector.begin();
  57   preorderTraverse(tree, 0, tree->first_child(tree->ROOT));
  58   sort(tagVector.begin(), tagVector.end(), myobject);
  59   sort(tag2Vector.begin(), tag2Vector.end(), myobject);
  60 }
  61
  62 void lex_index::print(){
  63   printf("%i-vector: ", tag);
  64   printVector(tagVector);
  65   printf("%i-vector: ", tag2);
  66   printVector(tag2Vector);
  67 }
  68
  69 class VectorMergeJoin {
  70 public:
  71   xml_tree * tree;
  72   //The tag IDs to be semi-joined
  73   const char * tagname1;
  74   const char * tagname2;
  75   vector<int32_t> resultVector;
  76   void mergeJoin(vector<int32_t> v1, vector<int32_t> v2);
  77 };
  78
  79 void VectorMergeJoin::mergeJoin(vector<int32_t> v1, vector<int32_t> v2){
  80   vector<int32_t>::iterator i=resultVector.begin();
  81   vector<int32_t>::iterator i1=v1.begin();
  82   vector<int32_t>::iterator i2=v2.begin();
  83   int k;
  84
  85   while((i1!=v1.end()) && (i2!=v2.end())){
  86     k = strcmp((const char*) tree->get_text(*i1),
  87                (const char*) tree->get_text(*i2));
  88     if (k==0)
  89       {
  90         i = resultVector.insert( i, *i1 );
  91         //advance left
  92         i1++;
  93         //advance right
  94         i2++;
  95       }
  96     else if (k<0) i1++; //advance left
  97     else i2++; //advance right
  98   }
  99 }
 100
 101 // class prefix_treeNode {
 102 // public:
 103   //  std::map<char, prefix_treeNode> Children;
 104 //  std::array<prefix_treeNode, 256> Children;
 105 //  uint32 textID;
 106 //};
 107
 108 using namespace SXSI;
 109
 110 static xml_tree*& XMLTREE(value v)
 111 {
 112   return Obj_val<xml_tree*>(v);
 113 }
 114
 115 static lex_index*& LEXINDEX(value v)
 116 {
 117   return Obj_val<lex_index*>(v);
 118 }
 119
 120 static xml_tree::node_t TREENODE(value i)
 121 {
 122   return static_cast<xml_tree::node_t>(Int_val(i));
 123 }
 124
 125 static xml_tree::tag_t TAG(value i)
 126 {
 127   return static_cast<xml_tree::tag_t>(Int_val(i));
 128 }
 129
 130 ML_BINDING value caml_build_lex_index(value vtree, value vtag, value vtag2)
 131 {
 132   if ((TAG(vtag)==-1) || (TAG(vtag2)==-1)) caml_failwith("<INVALID TAG>");
 133   CAMLparam2(vtree, vtag);
 134   CAMLlocal1(vindex);
 135   vindex = sxsi_alloc_custom<lex_index*>();
 136   xml_tree * tree = XMLTREE(vtree);
 137   myobject.tree = tree;
 138
 139   //create the index
 140   lex_index* mylindex = new lex_index();
 141   mylindex->tag = TAG(vtag);
 142   mylindex->tag2 = TAG(vtag2);
 143   mylindex->createIndex(tree);
 144
 145   //do a join
 146   VectorMergeJoin* myVMJoin = new VectorMergeJoin();
 147   myVMJoin->tree = tree;
 148   myVMJoin->mergeJoin(mylindex->tagVector, mylindex->tag2Vector);
 149   printf("Result-vector: ");
 150   printVector(myVMJoin->resultVector);
 151
 152   LEXINDEX(vindex)=mylindex;
 153 }
 154
 155 ML_BINDING value caml_print_lex_index(value vindex)
 156 {
 157   CAMLparam1(vindex);
 158   lex_index* index = LEXINDEX(vindex);
 159
 160   //Print the index to the terminal
 161   //  caml_failwith("print_lex_index not implemented");
 162   index->print();
 163   CAMLreturn (Val_unit);
 164 }