libcds/src/static_bitsequence/static_bitsequence_brw32.h

   1 /* static_bitsequence_brw32.h
   2    Copyright (C) 2005, Rodrigo Gonzalez, all rights reserved.
   3
   4    New RANK, SELECT, SELECT-NEXT and SPARSE RANK implementations.
   5
   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.
  10
  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.
  15
  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
  19
  20 */
  21
  22 #ifndef _STATIC_BITSEQUENCE_BRW32_H
  23 #define _STATIC_BITSEQUENCE_BRW32_H
  24
  25 #include <basics.h>
  26 #include <static_bitsequence.h>
  27 /////////////
  28 //Rank(B,i)//
  29 /////////////
  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%
  37
  38 /** Implementation of Rodrigo Gonzalez et al. practical rank/select solution [1].
  39  *  The interface was adapted.
  40  *
  41  *  [1] Rodrigo Gonzalez, Szymon Grabowski, Veli Makinen, and Gonzalo Navarro.
  42  *      Practical Implementation of Rank and Select Queries. WEA05.
  43  *
  44  *  @author Rodrigo Gonzalez
  45  */
  46 class static_bitsequence_brw32 : public static_bitsequence {
  47 private:
  48         uint *data;
  49   //bool owner;
  50         uint n,integers;
  51   uint factor,b,s;
  52   uint *Rs; //superblock array
  53
  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();
  57
  58 public:
  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
  63
  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();
  71   virtual uint size();
  72
  73   /*load-save functions*/
  74   virtual int save(FILE *f);
  75   static static_bitsequence_brw32 * load(FILE * fp);
  76 };
  77
  78 #endif