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 void printPairVector(vector<pair<int32_t,int32_t>> v){
  31     vector<pair<int32_t,int32_t>>::iterator i=v.begin();
  32   if (i!=v.end()) {
  33     printf("[(%i,%i)", (*i).first, (*i).second);
  34       for (++i; i!=v.end(); ++i)
  35         printf(",(%i,%i)", (*i).first, (*i).second);
  36       printf("]\n");
  37     }
  38 }
  39
  40 //define a type for the lexicographic index
  41 class lex_index {
  42 public:
  43   xml_tree::tag_t tag;
  44   xml_tree::tag_t tag2;
  45   vector<int32_t> tagVector;
  46   vector<int32_t> tag2Vector;
  47   void preorderTraverse(xml_tree * tree, xml_tree::tag_t parent_tag, xml_tree::node_t node);
  48   void createIndex(xml_tree * tree);
  49   void print();
  50 };
  51
  52 void lex_index::preorderTraverse(xml_tree * tree, xml_tree::tag_t parent_tag, xml_tree::node_t node){
  53   if (tree->tag(node)==tree->PCDATA_OPEN_TAG_ID)
  54   if (parent_tag==tag) tagVector.push_back(tree->text_id(node));
  55   else if (parent_tag==tag2) tag2Vector.push_back(tree->text_id(node));
  56   if (tree->tag(tree->first_child(node))!=0) preorderTraverse(tree,tree->tag(node),tree->first_child(node));
  57   if (tree->tag(tree->next_sibling(node))!=0) preorderTraverse(tree,parent_tag,tree->next_sibling(node));
  58 }
  59
  60 void lex_index::createIndex(xml_tree * tree){
  61   preorderTraverse(tree, 0, tree->first_child(tree->ROOT));
  62   sort(tagVector.begin(), tagVector.end(), myobject);
  63   sort(tag2Vector.begin(), tag2Vector.end(), myobject);
  64 }
  65
  66 void lex_index::print(){
  67   printf("%i-vector: ", tag);
  68   printVector(tagVector);
  69   printf("%i-vector: ", tag2);
  70   printVector(tag2Vector);
  71 }
  72
  73 class lex_index_count : public lex_index {
  74 public:
  75   vector<pair<int32_t,int32_t>> tcountVector;
  76   vector<pair<int32_t,int32_t>> tcount2Vector;
  77   void createCounts(xml_tree * tree);
  78   void print();
  79 };
  80
  81 void lex_index_count::createCounts(xml_tree * tree){
  82   int k;
  83   int i=0;
  84   while((i+1)<tagVector.size())
  85     {
  86       k=1;
  87       while(strcmp((const char*) tree->get_text(tagVector[i]),
  88                    (const char*) tree->get_text(tagVector[i+1]))==0){
  89         k++;
  90         tcountVector.push_back(make_pair(tagVector[i],1));
  91         i++;
  92       }
  93       if(k>1) tcountVector[i-k+1]=make_pair((tcountVector[i-k+1]).first,k);
  94       tcountVector.push_back(make_pair(tagVector[i],1));
  95       i++;
  96     }
  97   if(i<tagVector.size())
  98     tcountVector.push_back(make_pair(tagVector[i],1));
  99   i=0;
 100   while((i+1)<tag2Vector.size())
 101     {
 102       k=1;
 103       while(strcmp((const char*) tree->get_text(tag2Vector[i]),
 104                    (const char*) tree->get_text(tag2Vector[i+1]))==0){
 105         k++;
 106         tcount2Vector.push_back(make_pair(tag2Vector[i],1));
 107         i++;
 108       }
 109       if(k>1) tcount2Vector[i-k+1]=make_pair((tcount2Vector[i-k+1]).first,k);
 110       tcount2Vector.push_back(make_pair(tag2Vector[i],1));
 111       i++;
 112     }
 113   if(i<tag2Vector.size())
 114     tcount2Vector.push_back(make_pair(tag2Vector[i],1));
 115 }
 116
 117 void lex_index_count::print(){
 118   printf("%i-vector: ", tag);
 119   printPairVector(tcountVector);
 120   printf("%i-vector: ", tag2);
 121   printPairVector(tcount2Vector);
 122 }
 123
 124 class VectorMergeJoin {
 125 public:
 126   xml_tree * tree;
 127   vector<int32_t> resultVector;
 128   void mergeJoin(vector<int32_t> v1, vector<int32_t> v2);
 129 };
 130
 131 void VectorMergeJoin::mergeJoin(vector<int32_t> v1, vector<int32_t> v2){
 132   int i1=0;
 133   int i2=0;
 134   int k;
 135   while((i1!=v1.size()) && (i2!=v2.size())){
 136     k = strcmp((const char*) tree->get_text(v1[i1]),
 137                (const char*) tree->get_text(v2[i2]));
 138     if (k==0)
 139       {
 140         resultVector.push_back(v1[i1]);
 141         i1++; //advance left
 142       }
 143     else if (k<0) i1++; //advance left
 144     else i2++; //advance right
 145   }
 146 }
 147
 148 class VectorCountMergeJoin {
 149 public:
 150   xml_tree * tree;
 151   vector<pair<int32_t,int32_t>> resultVector;
 152   void mergeJoin(vector<pair<int32_t,int32_t>> v1, vector<pair<int32_t,int32_t>> v2);
 153 };
 154
 155 void VectorCountMergeJoin::mergeJoin(vector<pair<int32_t,int32_t>> v1, vector<pair<int32_t,int32_t>> v2){
 156   int comp=0;
 157   int i1=0;
 158   int i2=0;
 159   int k,j;
 160   while((i1<v1.size()) && (i2<v2.size())){
 161     k = strcmp((const char*) tree->get_text(v1[i1].first),
 162                (const char*) tree->get_text(v2[i2].first));
 163     comp++;
 164     if (k==0)
 165       {
 166         for(j=0; j<v1[i1].second ; j++)
 167           resultVector.push_back(v1[i1+j]);
 168         i1=i1+j;
 169         //      i1++; //advance left
 170       }
 171     //    else if (k<0) i1++; //advance left
 172     else if (k<0) i1=i1+v1[i1].second; //advance left
 173     //    else i2++; //advance right
 174     else i2=i2+v2[i2].second; //advance right
 175
 176   }
 177   printf("Number of comparisons during MergeJoin: %i\n",comp);
 178 }
 179
 180 // class prefix_treeNode {
 181 // public:
 182   //  std::map<char, prefix_treeNode> Children;
 183 //  std::array<prefix_treeNode, 256> Children;
 184 //  uint32 textID;
 185 //};
 186
 187 using namespace SXSI;
 188
 189 static xml_tree*& XMLTREE(value v)
 190 {
 191   return Obj_val<xml_tree*>(v);
 192 }
 193
 194 static lex_index*& LEXINDEX(value v)
 195 {
 196   return Obj_val<lex_index*>(v);
 197 }
 198
 199 static lex_index_count*& LEXINDEXCOUNT(value v)
 200 {
 201   return Obj_val<lex_index_count*>(v);
 202 }
 203
 204 static xml_tree::node_t TREENODE(value i)
 205 {
 206   return static_cast<xml_tree::node_t>(Int_val(i));
 207 }
 208
 209 static xml_tree::tag_t TAG(value i)
 210 {
 211   return static_cast<xml_tree::tag_t>(Int_val(i));
 212 }
 213
 214 ML_BINDING value caml_build_lex_index(value vtree, value vtag, value vtag2)
 215 {
 216   if ((TAG(vtag)==-1) || (TAG(vtag2)==-1)) caml_failwith("<INVALID TAG>");
 217   CAMLparam2(vtree, vtag);
 218   CAMLlocal1(vindex);
 219   //  Version without count:
 220   //  vindex = sxsi_alloc_custom<lex_index*>();
 221   //  Version with counts:
 222   vindex = sxsi_alloc_custom<lex_index_count*>();
 223   xml_tree * tree = XMLTREE(vtree);
 224   myobject.tree = tree;
 225
 226   //  create the index
 227   //  Version without count:
 228   //  lex_index* mylindex = new lex_index();
 229   //  Version with count:
 230   lex_index_count* mylindex = new lex_index_count();
 231   mylindex->tag = TAG(vtag);
 232   mylindex->tag2 = TAG(vtag2);
 233   mylindex->createIndex(tree);
 234
 235   //  printf("%i-vector: ", mylindex->tag);
 236   //  printVector(mylindex->tagVector);
 237
 238   // Version with count:
 239   mylindex->createCounts(tree);
 240
 241   //do a join
 242   //  VectorMergeJoin* myVMJoin = new VectorMergeJoin();
 243   //  myVMJoin->tree = tree;
 244   //  myVMJoin->mergeJoin(mylindex->tagVector, mylindex->tag2Vector);
 245   //  printf("Result-vector: ");
 246   //  printVector(myVMJoin->resultVector);
 247
 248   VectorCountMergeJoin* myVMJoin = new VectorCountMergeJoin();
 249   myVMJoin->tree = tree;
 250   myVMJoin->mergeJoin(mylindex->tcountVector, mylindex->tcount2Vector);
 251   printf("Result-vector: ");
 252   printPairVector(myVMJoin->resultVector);
 253
 254   //  LEXINDEX(vindex)=mylindex;
 255   LEXINDEXCOUNT(vindex)=mylindex;
 256 }
 257
 258 ML_BINDING value caml_print_lex_index(value vindex)
 259 {
 260   CAMLparam1(vindex);
 261   //  Version without count:
 262   //  lex_index* index = LEXINDEX(vindex);
 263   //  Version without count:
 264   lex_index_count* index = LEXINDEXCOUNT(vindex);
 265
 266   //Print the index to the terminal
 267   //  caml_failwith("print_lex_index not implemented");
 268
 269   index->print();
 270   CAMLreturn (Val_unit);
 271 }