1 /* static_sequence_tester.cpp
2 * Copyright (C) 2008, Francisco Claude, all rights reserved.
4 * static_sequence_tester
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 #include "static_sequence_tester.h"
27 double ticks= (double)sysconf(_SC_CLK_TCK);
37 return (t2.tms_utime-t1.tms_utime)/ticks;
39 /* end Time meassuring */
44 void test_static_sequence(uint * symbols, uint n, static_sequence * ss) {
45 cout << "Size: " << ss->size() << endl;
48 max_v = max(max_v,symbols[i]);
49 uint * occ = new uint[max_v+1];
50 for(uint i=0;i<=max_v;i++)
53 for(uint i=0;i<n && !error;i++) {
54 if(i!=0 && i%max(1,(n-1)/100)==0) { cout << "."; cout.flush(); }
55 if(i!=0 && i%max(1,(n-1)/10)==0) cout << endl;
57 uint a = /*symbols[i]; /*/ss->access(i);
58 uint r = /*occ[symbols[i]];/*/ss->rank(symbols[i],i);
59 uint s = /*i; /*/ss->select(symbols[i],occ[symbols[i]]);
60 uint rM1 = (i==0)?0:ss->rank(symbols[i],i-1);
61 if(r!=occ[symbols[i]]) {
62 cout << "Error in rank for symbol " << symbols[i] << " at position " << i << endl;
63 cout << "value: " << r << endl;
64 cout << "Expected: " << occ[symbols[i]] << endl;
68 cout << "Error in select for symbol " << symbols[i] << " at position " << occ[symbols[i]] << endl;
69 cout << "value: " << s << endl;
70 cout << "Expected: " << i << endl;
74 cout << "Error in access at position " << i << endl;
75 cout << "value: " << a << endl;
76 cout << "Expected: " << symbols[i] << endl;
79 if(rM1!=occ[symbols[i]]-1) {
80 cout << "Error in rankM1 for symbol " << symbols[i] << " at position " << i-1 << endl;
81 cout << "value: " << rM1 << endl;
82 cout << "Expected: " << occ[symbols[i]]-1 << endl;
87 cout << "Test OK! It works :)" << endl;
91 void load(char *fname, uint ** text, uint * n) {
92 struct stat text_info;
93 if(stat(fname,&text_info)<0) {
94 cout << "could not stat: " << fname << endl;
98 *n= (uint)text_info.st_size/4;
99 *text = new uint[*n+1];
100 FILE * fp = fopen(fname,"r");
102 cout << "could not open " << fname << endl;
106 cout << "File: " << fname << endl;
107 cout << "Length: " << *n << endl;
110 for(uint i=0;i<*n;i++) {
112 uint read=fread(&c,sizeof(uint),1,fp);
114 (*text)[i] = 1+(uint)c;
116 max_symbol = max(max_symbol,(*text)[i]);
121 /*static_sequence * ss = ssb->build(*text,*n);
123 char * fname2 = new char[10+string(fname).length()];
124 sprintf(fname2,"%s.wt",fname);
125 fp = fopen(fname2,"w");
129 fp = fopen(fname2,"r");
130 ss = static_sequence::load(fp);
136 static_sequence * savetest(char * bname, static_sequence * ss) {
137 char * fname = new char[10+string(bname).length()];
138 sprintf(fname,"%s.ss",bname);
139 FILE * fp = fopen(fname,"w");
140 cout << "Saving structure ... "; cout.flush();
142 cout << "done" << endl; cout.flush();
144 cout << "Deleting structure ... "; cout.flush();
146 cout << "done" << endl; cout.flush();
147 fp = fopen(fname,"r");
148 cout << "Loading structure ... "; cout.flush();
149 ss = static_sequence::load(fp);
150 cout << "done" << endl; cout.flush();
152 if(ss==NULL) cout << "Error loading static_sequence" << endl;
153 //cout << ss << endl;
158 void speed_rank(static_sequence * ss, uint * text, uint n) {
160 for(uint i=0;i<n;i++) {
161 max_symbol = max(max_symbol,text[i]);
164 uint *occ = new uint[max_symbol];
165 for(uint i=0;i<max_symbol;i++)
167 for(uint i=0;i<n;i++)
170 uint * valid_symbols = new uint[max_symbol]; uint c=0;
171 for(uint i=0;i<max_symbol;i++) {
173 valid_symbols[c++]=i;
180 for(uint i=0;i<NQUERIES;i++) {
181 uint symb = rand()%c;
183 acc += ss->rank(valid_symbols[symb],pos);
185 double t = stop_clock();
186 cout << " * Time for " << NQUERIES << " ranks: " << t << " secs" << endl;
187 cout << " * Time per rank: " << 1000*t/NQUERIES << " msecs" << endl;
188 cout << " - Check sum: " << acc << endl;
189 delete [] valid_symbols;
193 void speed_select(static_sequence * ss, uint * text, uint n) {
195 for(uint i=0;i<n;i++) {
196 max_symbol = max(max_symbol,text[i]);
199 uint *occ = new uint[max_symbol];
200 for(uint i=0;i<max_symbol;i++)
202 for(uint i=0;i<n;i++)
205 uint * valid_symbols = new uint[max_symbol]; uint c=0;
206 for(uint i=0;i<max_symbol;i++) {
208 valid_symbols[c++]=i;
215 for(uint i=0;i<NQUERIES;i++) {
216 uint symb = rand()%c;
217 uint pos = rand()%occ[valid_symbols[symb]]+1;
218 acc += ss->select(valid_symbols[symb],pos);
220 double t = stop_clock();
221 cout << " * Time for " << NQUERIES << " selects: " << t << " secs" << endl;
222 cout << " * Time per select: " << 1000*t/NQUERIES << " msecs" << endl;
223 cout << " - Check sum: " << acc << endl;
224 delete [] valid_symbols;
228 void speed_access(static_sequence * ss, uint * text, uint n) {
233 for(uint i=0;i<NQUERIES;i++) {
235 acc += ss->access(pos);
237 double t = stop_clock();
238 cout << " * Time for " << NQUERIES << " accesses: " << t << " secs" << endl;
239 cout << " * Time per access: " << 1000*t/NQUERIES << " msecs" << endl;
240 cout << " - Check sum: " << acc << endl;