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
105 BitRank::~BitRank() {
108 if (owner) delete [] data;
111 //Build the rank (blocks and superblocks)
112 void BitRank::BuildRank()
114 ulong num_sblock = n/s;
115 ulong num_block = n/b;
116 Rs = new ulong[num_sblock+1];//+1 we add the 0 pos
117 Rb = new uchar[num_block+1];//+1 we add the 0 pos
122 for (j=1;j<=num_sblock;j++)
124 Rs[j]=BuildRankSub((j-1)*superFactor,superFactor)+Rs[j-1];
128 for (ulong k=1;k<=num_block;k++) {
130 Rb[k]=BuildRankSub(j*superFactor, k%superFactor);
134 ulong BitRank::BuildRankSub(ulong ini, ulong bloques){
138 for(ulong i=ini;i<ini+bloques;i++) {
144 return rank; //return the numbers of 1's in the interval
148 //this rank ask from 0 to n-1
149 ulong BitRank::rank(ulong i) {
150 ++i; // the following gives sum of 1s before i
151 return Rs[i>>8]+Rb[i>>wordShift]
152 +popcount(data[i >> wordShift] & ((1lu << (i & Wminusone))-1));
155 ulong BitRank::select(ulong x) {
156 // returns i such that x=rank(i) && rank(i-1)<x or n if that i not exist
157 // first binary search over first level rank structure
158 // then sequential search using popcount over a int
159 // then sequential search using popcount over a char
160 // then sequential search bit a bit
162 //binary search over first level rank structure
168 ulong rankmid = Rs[mid];
177 //sequential search using popcount over a int
179 left=mid*superFactor;
181 ulong j = data[left];
183 unsigned ones = popcount(j);
193 //sequential search using popcount over a char
195 rankmid = popcount8(j);
200 rankmid = popcount8(j);
205 rankmid = popcount8(j);
214 // then sequential search bit a bit
223 ulong BitRank::select0(ulong x) {
224 // returns i such that x=rank0(i) && rank0(i-1)<x or n if that i not exist
225 // first binary search over first level rank structure
226 // then sequential search using popcount over a int
227 // then sequential search using popcount over a char
228 // then sequential search bit a bit
230 //binary search over first level rank structure
236 ulong rankmid = mid * s - Rs[mid];
243 rankmid = mid * s - Rs[mid];
246 //sequential search using popcount over a int
248 left=mid*superFactor;
250 ulong j = data[left];
252 unsigned zeros = W - popcount(j);
260 zeros = W - popcount(j);
263 //sequential search using popcount over a char
265 rankmid = 8 - popcount8(j);
270 rankmid = 8 - popcount8(j);
275 rankmid = 8 - popcount8(j);
284 // then sequential search bit a bit
294 bool BitRank::IsBitSet(ulong i) {
295 return (1lu << (i % W)) & data[i/W];
298 ulong BitRank::NumberOfBits() {