3 /*****************************************************************************
4 * Copyright (C) 2005, Rodrigo Gonzalez, all rights reserved. *
6 * New RANK, SELECT, SELECT-NEXT and SPARSE RANK implementations. *
8 * This library is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU Lesser General Public *
10 * License as published by the Free Software Foundation; either *
11 * version 2.1 of the License, or (at your option) any later version. *
13 * This library is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
16 * Lesser General Public License for more details. *
18 * You should have received a copy of the GNU Lesser General Public *
19 * License along with this library; if not, write to the Free Software *
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA *
21 ****************************************************************************/
23 // Modified by Niko Välimäki
28 //This Class use a superblock size of 256-512 bits
29 //and a block size of 32-64 bits also
32 const unsigned char __popcount_tab[] =
34 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
35 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
36 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
37 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
38 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
39 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
40 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
41 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
44 const unsigned char select_tab[] =
46 0,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
48 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
50 7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
52 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
54 8,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
56 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
58 7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
60 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
64 // bits needed to represent a number between 0 and n
65 inline ulong bits (ulong n){
67 while (n) { b++; n >>= 1; }
73 inline unsigned popcount (register ulong x){
74 return __popcount_tab[(x >> 0) & 0xff] + __popcount_tab[(x >> 8) & 0xff] + __popcount_tab[(x >> 16) & 0xff] + __popcount_tab[(x >> 24) & 0xff];
78 inline unsigned popcount (register ulong x){
79 return __popcount_tab[(x >> 0) & 0xff] + __popcount_tab[(x >> 8) & 0xff] + __popcount_tab[(x >> 16) & 0xff] + __popcount_tab[(x >> 24) & 0xff] + __popcount_tab[(x >> 32) & 0xff] + __popcount_tab[(x >> 40) & 0xff] + __popcount_tab[(x >> 48) & 0xff] + __popcount_tab[(x >> 56) & 0xff];
83 inline unsigned popcount16 (register int x){
84 return __popcount_tab[x & 0xff] + __popcount_tab[(x >> 8) & 0xff];
87 inline unsigned popcount8 (register int x){
88 return __popcount_tab[x & 0xff];
91 BitRank::BitRank(ulong *bitarray, ulong n, bool owner) {
94 this->n=n; // length of bitarray in bits
103 BitRank::~BitRank() {
106 if (owner) delete [] data;
109 //Build the rank (blocks and superblocks)
110 void BitRank::BuildRank()
112 ulong num_sblock = n/s;
113 ulong num_block = n/W;
114 Rs = new BlockArray(num_sblock+1, Tools::CeilLog2(n));//+1 we add the 0 pos
115 Rb = new uchar[num_block+1];//+1 we add the 0 pos
120 for (j=1;j<=num_sblock;j++)
122 (*Rs)[j]=BuildRankSub((j-1)*superFactor,superFactor)+(*Rs)[j-1];
126 for (ulong k=1;k<=num_block;k++) {
128 Rb[k]=BuildRankSub(j*superFactor, k%superFactor);
132 ulong BitRank::BuildRankSub(ulong ini, ulong bloques){
136 for(ulong i=ini;i<ini+bloques;i++) {
142 return rank; //return the numbers of 1's in the interval
146 //this rank ask from 0 to n-1
147 ulong BitRank::rank(ulong i) {
148 ++i; // the following gives sum of 1s before i
149 return (*Rs)[i>>8]+Rb[i>>wordShift]
150 +popcount(data[i >> wordShift] & ((1lu << (i & Wminusone))-1));
153 ulong BitRank::select(ulong x) {
154 // returns i such that x=rank(i) && rank(i-1)<x or n if that i not exist
155 // first binary search over first level rank structure
156 // then sequential search using popcount over a int
157 // then sequential search using popcount over a char
158 // then sequential search bit a bit
160 //binary search over first level rank structure
166 ulong rankmid = (*Rs)[mid];
173 rankmid = (*Rs)[mid];
175 //sequential search using popcount over a int
177 left=mid*superFactor;
179 ulong j = data[left];
181 unsigned ones = popcount(j);
191 //sequential search using popcount over a char
193 rankmid = popcount8(j);
198 rankmid = popcount8(j);
203 rankmid = popcount8(j);
212 // then sequential search bit a bit
221 ulong BitRank::select0(ulong x) {
222 // returns i such that x=rank0(i) && rank0(i-1)<x or n if that i not exist
223 // first binary search over first level rank structure
224 // then sequential search using popcount over a int
225 // then sequential search using popcount over a char
226 // then sequential search bit a bit
228 //binary search over first level rank structure
234 ulong rankmid = mid * s - (*Rs)[mid];
241 rankmid = mid * s - (*Rs)[mid];
244 //sequential search using popcount over a int
246 left=mid*superFactor;
248 ulong j = data[left];
250 unsigned zeros = W - popcount(j);
258 zeros = W - popcount(j);
261 //sequential search using popcount over a char
263 rankmid = 8 - popcount8(j);
268 rankmid = 8 - popcount8(j);
273 rankmid = 8 - popcount8(j);
282 // then sequential search bit a bit
292 bool BitRank::IsBitSet(ulong i) {
293 return (1lu << (i % W)) & data[i/W];
296 ulong BitRank::NumberOfBits() {
301 * Saving data fields:
304 ulong *data; //here is the bit-arra
306 void BitRank::Save(FILE *file)
308 if (std::fwrite(&(this->n), sizeof(ulong), 1, file) != 1)
309 throw std::runtime_error("BitRank::Save(): file write error (n).");
311 for (ulong offset = 0; offset < integers; ++offset)
312 if (std::fwrite(this->data + offset, sizeof(ulong), 1, file) != 1)
313 throw std::runtime_error("BitRank::Save(): file write error (data).");
316 BitRank::BitRank(FILE *file)
319 if (std::fread(&(this->n), sizeof(ulong), 1, file) != 1)
320 throw std::runtime_error("BitRank::Load(): file read error (n).");
324 integers = (n+1)/W+1;
328 data = new ulong[integers];
329 for (ulong offset = 0; offset < integers; ++offset)
330 if (std::fread(this->data + offset, sizeof(ulong), 1, file) != 1)
331 throw std::runtime_error("BitRank::Load(): file read error (data).");