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