BitRank.h

   1 /*****************************************************************************
   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 #ifndef _BITSTREAM_H_
  22 #define _BITSTREAM_H_
  23
  24 #include "Tools.h"
  25
  26 class BitRank {
  27 private:
  28     // Check word length
  29 #if W == 32
  30     static const unsigned wordShift = 5;
  31     static const unsigned superFactor = 8; // 256 bit blocks
  32 #else
  33     static const unsigned wordShift = 6;
  34     static const unsigned superFactor = 4; // 256 bit blocks
  35 #endif
  36
  37     ulong *data; //here is the bit-array
  38     bool owner;
  39     ulong n,integers;
  40     unsigned b,s;
  41     ulong *Rs; //superblock array
  42     uchar *Rb; //block array
  43     ulong BuildRankSub(ulong,  ulong); //internal use of BuildRank
  44     void BuildRank(); //crea indice para rank
  45 public:
  46     BitRank(ulong *, ulong, bool);
  47     ~BitRank(); //destructor
  48     ulong rank(ulong i); //Rank from 0 to n-1
  49     ulong select(ulong x); // gives the position of the x:th 1.
  50     ulong select0(ulong x); // gives the position of the x:th 0.
  51
  52     bool IsBitSet(ulong i);
  53     ulong NumberOfBits();
  54 };
  55
  56 #endif