1 /* static_bitsequence_brw32.cpp
2 Copyright (C) 2005, Rodrigo Gonzalez, all rights reserved.
4 New RANK, SELECT, SELECT-NEXT and SPARSE RANK implementations.
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_bitsequence_brw32.h"
25 // #include <sys/types.h>
31 //_factor = 0 => s=W*lgn
32 //_factor = P => s=W*P
33 //Is interesting to notice
34 //factor=2 => overhead 50%
35 //factor=3 => overhead 33%
36 //factor=4 => overhead 25%
37 //factor=20=> overhead 5%
39 static_bitsequence_brw32::static_bitsequence_brw32(){
41 // this->owner = true;
46 static_bitsequence_brw32::static_bitsequence_brw32( uint *bitarray, uint _n, uint _factor){
47 /*cout << "*****" << endl;
48 cout << bitarray << endl;
50 cout << _factor << endl; */
51 if(_factor==0) exit(-1);
52 data=new uint[_n/W+1];
53 for(uint i=0;i<uint_len(_n,1);i++)
54 data[i] = bitarray[i];
55 for(uint i=uint_len(_n,1);i<_n/W+1;i++)
61 if (_factor==0) this->factor=lgn;
62 else this->factor=_factor;
68 this->ones = rank1(n-1);
71 static_bitsequence_brw32::~static_bitsequence_brw32() {
76 //Metodo que realiza la busqueda d
77 void static_bitsequence_brw32::BuildRank(){
78 uint num_sblock = n/s;
79 Rs = new uint[num_sblock+5];// +1 pues sumo la pos cero
80 for(uint i=0;i<num_sblock+5;i++)
84 for (j=1;j<=num_sblock;j++) {
86 Rs[j]+=BuildRankSub((j-1)*factor,factor);
90 uint static_bitsequence_brw32::BuildRankSub(uint ini,uint bloques){
92 for(uint i=ini;i<ini+bloques;i++) {
98 return rank; //retorna el numero de 1's del intervalo
102 uint static_bitsequence_brw32::rank1(uint i) {
105 uint aux=(i/s)*factor;
106 for (uint a=aux;a<i/W;a++)
107 resp+=popcount(data[a]);
108 resp+=popcount(data[i/W] & ((1<<(i & mask31))-1));
112 bool static_bitsequence_brw32::access(uint i) {
113 return (1u << (i % W)) & data[i/W];
116 int static_bitsequence_brw32::save(FILE *f) {
118 if (f == NULL) return 20;
119 if( fwrite(&wr,sizeof(uint),1,f) != 1 ) return -1;
120 if (fwrite (&n,sizeof(uint),1,f) != 1) return 21;
121 if (fwrite (&factor,sizeof(uint),1,f) != 1) return 21;
122 if (fwrite (data,sizeof(uint),n/W+1,f) != n/W+1) return 21;
123 if (fwrite (Rs,sizeof(uint),n/s+1,f) != n/s+1) return 21;
127 static_bitsequence_brw32 * static_bitsequence_brw32::load(FILE *f) {
128 if (f == NULL) return NULL;
130 if(fread(&type,sizeof(uint),1,f)!=1) return NULL;
131 if(type!=BRW32_HDR) { cout << "type:"<<type<<endl; return NULL; }
132 static_bitsequence_brw32 * ret = new static_bitsequence_brw32();
133 if (fread (&ret->n,sizeof(uint),1,f) != 1) return NULL;
134 ret->b=32; // b is a word
135 if (fread (&ret->factor,sizeof(uint),1,f) != 1) return NULL;
136 ret->s=ret->b*ret->factor;
137 uint aux=(ret->n+1)%W;
139 ret->integers = (ret->n+1)/W+1;
141 ret->integers = (ret->n+1)/W;
142 ret->data = new uint[ret->n/W+1];
143 if (!ret->data) return NULL;
144 if (fread (ret->data,sizeof(uint),ret->n/W+1,f) != ret->n/W+1) return NULL;
145 ret->Rs= new uint[ret->n/ret->s+1];
146 if (!ret->Rs) return NULL;
147 if (fread (ret->Rs,sizeof(uint),ret->n/ret->s+1,f) != ret->n/ret->s+1) return NULL;
149 ret->ones = ret->rank1(ret->n-1);
153 uint static_bitsequence_brw32::SpaceRequirementInBits() {
154 return uint_len(n,1)*sizeof(uint)*8+(n/s)*sizeof(uint)*8 +sizeof(static_bitsequence_brw32)*8;
157 uint static_bitsequence_brw32::size() {
158 return sizeof(static_bitsequence_brw32)+SpaceRequirementInBits()/8;
161 uint static_bitsequence_brw32::SpaceRequirement() {
162 return n/8+(n/s)*sizeof(uint)+sizeof(static_bitsequence_brw32);
165 uint static_bitsequence_brw32::prev2(uint start) {
166 // returns the position of the previous 1 bit before and including start.
167 // tuned to 32 bit machine
170 int offset = (start % W);
172 uint val = data[i] << (Wminusone-offset);
174 if (!val) { val = data[--i]; answer -= 1+offset; }
176 while (!val) { val = data[--i]; answer -= W; }
178 if (!(val & 0xFFFF0000)) { val <<= 16; answer -= 16; }
179 if (!(val & 0xFF000000)) { val <<= 8; answer -= 8; }
181 while (!(val & 0x80000000)) { val <<= 1; answer--; }
185 uint static_bitsequence_brw32::prev(uint start) {
186 // returns the position of the previous 1 bit before and including start.
187 // tuned to 32 bit machine
190 int offset = (start % W);
191 uint aux2 = data[i] & (-1u >> (31-offset));
194 if ((aux2&0xFF000000) > 0) return i*W+23+prev_tab[(aux2>>24)&0xFF];
195 else if ((aux2&0xFF0000) > 0) return i*W+15+prev_tab[(aux2>>16)&0xFF];
196 else if ((aux2&0xFF00) > 0) return i*W+7+prev_tab[(aux2>>8)&0xFF];
197 else return i*W+prev_tab[aux2&0xFF]-1;
199 for (uint k=i-1;;k--) {
202 if ((aux2&0xFF000000) > 0) return k*W+23+prev_tab[(aux2>>24)&0xFF];
203 else if ((aux2&0xFF0000) > 0) return k*W+15+prev_tab[(aux2>>16)&0xFF];
204 else if ((aux2&0xFF00) > 0) return k*W+7+prev_tab[(aux2>>8)&0xFF];
205 else return k*W+prev_tab[aux2&0xFF]-1;
211 uint static_bitsequence_brw32::next(uint k) {
215 aux2= data[count/W] >> des;
217 if ((aux2&0xff) > 0) return count+select_tab[aux2&0xff]-1;
218 else if ((aux2&0xff00) > 0) return count+8+select_tab[(aux2>>8)&0xff]-1;
219 else if ((aux2&0xff0000) > 0) return count+16+select_tab[(aux2>>16)&0xff]-1;
220 else {return count+24+select_tab[(aux2>>24)&0xff]-1;}
223 for (uint i=count/W+1;i<integers;i++) {
226 if ((aux2&0xff) > 0) return i*W+select_tab[aux2&0xff]-1;
227 else if ((aux2&0xff00) > 0) return i*W+8+select_tab[(aux2>>8)&0xff]-1;
228 else if ((aux2&0xff0000) > 0) return i*W+16+select_tab[(aux2>>16)&0xff]-1;
229 else {return i*W+24+select_tab[(aux2>>24)&0xff]-1;}
235 uint static_bitsequence_brw32::select1(uint x) {
236 // returns i such that x=rank(i) && rank(i-1)<x or n if that i not exist
237 // first binary search over first level rank structure
238 // then sequential search using popcount over a int
239 // then sequential search using popcount over a char
240 // then sequential search bit a bit
241 if(x>ones) return (uint)(-1);
243 //binary search over first level rank structure
246 uint rankmid = Rs[mid];
255 //sequential search using popcount over a int
260 uint ones = popcount(j);
263 if (left > integers) return n;
267 //sequential search using popcount over a char
269 rankmid = popcount8(j);
274 rankmid = popcount8(j);
279 rankmid = popcount8(j);
288 // then sequential search bit a bit
297 uint static_bitsequence_brw32::select0(uint x) {
298 // returns i such that x=rank_0(i) && rank_0(i-1)<x or n if that i not exist
299 // first binary search over first level rank structure
300 // then sequential search using popcount over a int
301 // then sequential search using popcount over a char
302 // then sequential search bit a bit
303 if(x>n-ones) return (uint)(-1);
305 //binary search over first level rank structure
309 uint rankmid = mid*factor*W-Rs[mid];
316 rankmid = mid*factor*W-Rs[mid];
318 //sequential search using popcount over a int
323 uint zeros = W-popcount(j);
326 if (left > integers) return n;
328 zeros = W-popcount(j);
330 //sequential search using popcount over a char
332 rankmid = 8-popcount8(j);
337 rankmid = 8-popcount8(j);
342 rankmid = 8-popcount8(j);
351 // then sequential search bit a bit
358 if (left > n) return n;