1 /* static_bitsequence_tester.cpp
2 * Copyright (C) 2008, Francisco Claude, all rights reserved.
4 * static_bitsequence_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
26 #include <static_bitsequence.h>
31 double ticks= (double)sysconf(_SC_CLK_TCK);
41 return (t2.tms_utime-t1.tms_utime)/ticks;
43 /* end Time meassuring */
45 uint NQUERIES=10000000;
48 void load(char *fname, uint ** text, uint * n) {
49 FILE * fp = fopen(fname,"r");
51 cout << "could not open " << fname << endl;
54 if(fread(n,sizeof(uint),1,fp)!=1) {
55 cout << "Error reading file " << fname << endl;
58 *text = new uint[uint_len(*n,1)];
60 if(fread(*text,sizeof(uint),uint_len(*n,1),fp)!=uint_len(*n,1)) {
61 cout << "Error reading file " << fname << endl;
66 void test_bitsequence(uint * bitseq, uint len, static_bitsequence * bs) {
69 for(uint i=0;i<len && !error;i++) {
70 //cout << "i="<<i<< endl;
72 if(i%max((uint)1,(bs->length()/100))==0) { cout << "."; cout.flush(); }
73 if(i%max((uint)1,(bs->length()/10))==0) { cout << endl; cout.flush(); }
75 if(bitget(bitseq,i)) ones++;
76 if(bs->access(i) != (bitget(bitseq,i)!=0)) {
77 cout << "Access error for position " << i << endl;
78 cout << " got: " << bs->access(i) << " expected: " << (bitget(bitseq,i)!=0) << endl;
81 if(bs->rank1(i) != ones) {
82 cout << "Rank1 error for position " << i << endl;
83 cout << " got: " << bs->rank1(i) << " expected: " << ones << endl;
86 if(bitget(bitseq,i) && bs->select1(ones) != i) {
87 cout << "Select1 error for position " << i << " ones:" << ones << endl;
88 cout << " got: " << bs->select1(ones) << " expected: " << i << endl;
91 if(bs->rank0(i) != i+1-ones) {
92 cout << "Rank0 error for position " << i << endl;
93 cout << " got: " << bs->rank0(i) << " expected: " << ones << endl;
96 if(!bitget(bitseq,i) && bs->select0(i+1-ones) != i) {
97 cout << "Select0 error for position " << i << endl;
98 cout << " got: " << bs->select0(i+1-ones) << " expected: " << i << endl;
105 void speed_access(static_bitsequence * ss, uint * bitseq, uint n) {
110 for(uint i=0;i<NQUERIES;i++) {
112 acc += ss->access(pos);
114 double t = stop_clock();
115 cout << " * Time for " << NQUERIES << " accesses: " << t << " secs" << endl;
116 cout << " * Time per access: " << 1000*t/NQUERIES << " msecs" << endl;
117 cout << " - Check sum: " << acc << endl;
120 void speed_rank0(static_bitsequence * ss, uint * bitseq, uint n) {
125 for(uint i=0;i<NQUERIES;i++) {
127 acc += ss->rank0(pos);
129 double t = stop_clock();
130 cout << " * Time for " << NQUERIES << " rank0s: " << t << " secs" << endl;
131 cout << " * Time per rank0: " << 1000*t/NQUERIES << " msecs" << endl;
132 cout << " - Check sum: " << acc << endl;
135 void speed_rank1(static_bitsequence * ss, uint * bitseq, uint n) {
140 for(uint i=0;i<NQUERIES;i++) {
142 acc += ss->rank1(pos);
144 double t = stop_clock();
145 cout << " * Time for " << NQUERIES << " rank1s: " << t << " secs" << endl;
146 cout << " * Time per rank1: " << 1000*t/NQUERIES << " msecs" << endl;
147 cout << " - Check sum: " << acc << endl;
150 void speed_select0(static_bitsequence * ss, uint * bitseq, uint n) {
152 uint ones=ss->rank0(n-1);
156 for(uint i=0;i<NQUERIES;i++) {
157 uint pos = rand()%ones+1;
158 acc += ss->select0(pos);
160 double t = stop_clock();
161 cout << " * Time for " << NQUERIES << " select0s: " << t << " secs" << endl;
162 cout << " * Time per select0: " << 1000*t/NQUERIES << " msecs" << endl;
163 cout << " - Check sum: " << acc << endl;
166 void speed_select1(static_bitsequence * ss, uint * bitseq, uint n) {
168 uint ones=ss->rank1(n-1);
172 for(uint i=0;i<NQUERIES;i++) {
173 uint pos = rand()%ones+1;
174 acc += ss->select1(pos);
176 double t = stop_clock();
177 cout << " * Time for " << NQUERIES << " select1s: " << t << " secs" << endl;
178 cout << " * Time per select1: " << 1000*t/NQUERIES << " msecs" << endl;
179 cout << " - Check sum: " << acc << endl;