libcds/tests/test_wvtree02.cpp

   1
   2 #include <sys/stat.h>
   3 #include <iostream>
   4 #include <sstream>
   5 #include <basics.h>
   6 #include <static_bitsequence.h>
   7 #include <alphabet_mapper.h>
   8 #include <static_sequence.h>
   9
  10 using namespace std;
  11
  12 void test_static_sequence(uint * symbols, uint n, static_sequence * ss) {
  13   cout << "Size: " << ss->size() << endl;
  14   uint max_v=0;
  15   for(uint i=0;i<n;i++)
  16     max_v = max(max_v,symbols[i]);
  17   uint * occ = new uint[max_v+1];
  18   for(uint i=0;i<=max_v;i++)
  19     occ[i] = 0;
  20   bool error = false;
  21   for(uint i=0;i<n && !error;i++) {
  22     if(i!=0 && i%max(1,(n-1)/100)==0) { cout << "."; cout.flush(); }
  23     if(i!=0 && i%max(1,(n-1)/10)==0) cout << endl;
  24     occ[symbols[i]]++;
  25     uint a = ss->access(i);
  26     uint r = ss->rank(symbols[i],i);
  27     uint s = ss->select(symbols[i],occ[symbols[i]]);
  28     uint rM1 = (i==0)?0:ss->rank(symbols[i],i-1);
  29     if(r!=occ[symbols[i]]) {
  30       cout << "Error in rank for symbol " << symbols[i] << " at position " << i << endl;
  31       cout << "value: " << r << endl;
  32       cout << "Expected: " << occ[symbols[i]] << endl;
  33       error = true;
  34     }
  35     if(s!=i) {
  36       cout << "Error in select for symbol " << symbols[i] << " at position " << occ[symbols[i]] << endl;
  37       cout << "value: " << s << endl;
  38       cout << "Expected: " << i << endl;
  39       error = true;
  40     }
  41     if(a!=symbols[i]) {
  42       cout << "Error in access at position " << i << endl;
  43       cout << "value: " << a << endl;
  44       cout << "Expected: " << symbols[i] << endl;
  45       error = true;
  46     }
  47     if(rM1!=occ[symbols[i]]-1) {
  48       cout << "Error in rankM1 for symbol " << symbols[i] << " at position " << i-1 << endl;
  49       cout << "value: " << rM1 << endl;
  50       cout << "Expected: " << occ[symbols[i]]-1 << endl;
  51       error = true;
  52     }
  53   }
  54   if(!error)
  55     cout << "Test OK! It works :)" << endl;
  56   delete [] occ;
  57 }
  58
  59 int main(int argc, char ** argv) {
  60   if(argc!=3) {
  61     cout << "usage: " << argv[0] << " <file> <samp>" << endl;
  62     return 0;
  63   }
  64   struct stat text_info;
  65   if(stat(argv[1],&text_info)<0) {
  66     cout << "could not stat: " << argv[1] << endl;
  67     return -1;
  68   }
  69
  70   uint samp;
  71   {
  72     stringstream ss;
  73     ss << string(argv[2]);
  74
  75     ss >> samp;
  76   }
  77
  78   uint n= (uint)text_info.st_size;
  79   uint * text = new uint[n+1];
  80   FILE * fp = fopen(argv[1],"r");
  81   if(fp==NULL) {
  82     cout << "could not open " << argv[1] << endl;
  83     return -1;
  84   }
  85
  86   cout << "File: " << argv[1] << endl;
  87   cout << "Length: " << n << endl;
  88
  89   uint max_symbol = 0;
  90   for(uint i=0;i<n;i++) {
  91     uchar c;
  92     uint read=fread(&c,sizeof(uchar),1,fp);
  93     //assert(read==1);
  94     text[i] = (uint)c;
  95     c += read;
  96     max_symbol = max(max_symbol,text[i]);
  97   }
  98   max_symbol++;
  99
 100   fclose(fp);
 101
 102   /*uint *occ = new uint[max_symbol];
 103   for(uint i=0;i<max_symbol;i++)
 104     occ[i] = 0;
 105   for(uint i=0;i<n;i++)
 106     occ[text[i]]++;*/
 107
 108   alphabet_mapper * am = new alphabet_mapper_none();
 109   static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(samp);
 110         cout << "Building Huffman table..."; cout.flush();
 111         wt_coder * wtc = new wt_coder_huff(text,n,am);
 112         cout << "done" << endl; cout.flush();
 113   cout << "Building static_sequence..."; cout.flush();
 114   static_sequence * wt = new static_sequence_wvtree(text,n,wtc,bmb,am);
 115   cout << "done" << endl; cout.flush();
 116   delete bmb;
 117
 118   char * fname = new char[10+string(argv[1]).length()];
 119   sprintf(fname,"%s.wt",argv[1]);
 120   fp = fopen(fname,"w");
 121   cout << "save: " << wt->save(fp) << endl;
 122   fclose(fp);
 123   delete wt;
 124   fp = fopen(fname,"r");
 125   wt = static_sequence::load(fp);
 126   fclose(fp);
 127   delete [] fname;
 128
 129   test_static_sequence(text,n,wt);
 130
 131   cout << "WT Size: " << wt->size() << endl;
 132   cout << "ft = " << 1.*wt->size()/n << endl;
 133
 134   fname = new char[10+string(argv[1]).length()];
 135   sprintf(fname,"%s.wt",argv[1]);
 136   fp = fopen(fname,"w");
 137   cout << "save: " << wt->save(fp) << endl;
 138   fclose(fp);
 139   delete [] fname;
 140
 141   delete [] text;
 142   delete wt;
 143
 144 }