1 /* static_bitsequence_brw32.h
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 #ifndef _STATIC_BITSEQUENCE_BRW32_H
23 #define _STATIC_BITSEQUENCE_BRW32_H
26 #include <static_bitsequence.h>
30 //_factor = 0 => s=W*lgn
31 //_factor = P => s=W*P
32 //Is interesting to notice
33 //factor=2 => overhead 50%
34 //factor=3 => overhead 33%
35 //factor=4 => overhead 25%
36 //factor=20=> overhead 5%
38 /** Implementation of Rodrigo Gonzalez et al. practical rank/select solution [1].
39 * The interface was adapted.
41 * [1] Rodrigo Gonzalez, Szymon Grabowski, Veli Makinen, and Gonzalo Navarro.
42 * Practical Implementation of Rank and Select Queries. WEA05.
44 * @author Rodrigo Gonzalez
46 class static_bitsequence_brw32 : public static_bitsequence {
52 uint *Rs; //superblock array
54 uint BuildRankSub(uint ini,uint fin); //uso interno para contruir el indice rank
55 void BuildRank(); //crea indice para rank
56 static_bitsequence_brw32();
59 static_bitsequence_brw32(uint *bitarray, uint n, uint factor);
60 ~static_bitsequence_brw32(); //destructor
61 virtual bool access(uint i);
62 virtual uint rank1(uint i); //Nivel 1 bin, nivel 2 sec-pop y nivel 3 sec-bit
64 uint prev(uint start); // gives the largest index i<=start such that IsBitSet(i)=true
65 uint prev2(uint start); // gives the largest index i<=start such that IsBitSet(i)=true
66 uint next(uint start); // gives the smallest index i>=start such that IsBitSet(i)=true
67 virtual uint select0(uint x); // gives the position of the x:th 1.
68 virtual uint select1(uint x); // gives the position of the x:th 1.
69 uint SpaceRequirementInBits();
70 uint SpaceRequirement();
73 /*load-save functions*/
74 virtual int save(FILE *f);
75 static static_bitsequence_brw32 * load(FILE * fp);