libcds/src/static_bitsequence/static_bitsequence.cpp

   1 /* static_bitsequence.cpp
   2  * Copyright (C) 2008, Francisco Claude, all rights reserved.
   3  *
   4  * static_bitsequence definition
   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 #include "static_bitsequence.h"
  23
  24 uint static_bitsequence::rank0(uint i) {
  25         return i+1-rank1(i);
  26 }
  27
  28 uint static_bitsequence::rank1(uint i) {
  29   if(i>=len) return ones;
  30   if(ones==0) return -1;
  31   uint ini = 1;
  32   uint fin = ones;
  33   while(ini<fin) {
  34     uint pos = (ini+fin)/2;
  35     uint bp = select1(pos);
  36     if(bp==i) return pos;
  37     if(bp<i)
  38       ini = pos+1;
  39     else
  40       fin = pos-1;
  41   }
  42         if(select1(ini)>i) return ini-1;
  43         return ini;
  44 }
  45
  46 uint static_bitsequence::select0(uint i) {
  47   if(i>len-ones) return len;
  48   if(i==0) return -1;
  49   uint ini = 0;
  50   uint fin = len-1;
  51   while(ini<fin) {
  52     uint pos = (ini+fin)/2;
  53     uint br = rank0(pos);
  54     if(br<i)
  55       ini = pos+1;
  56     else
  57       fin = pos;
  58   }
  59         return ini;
  60 }
  61
  62 uint static_bitsequence::select1(uint i) {
  63   if(i>ones) return len;
  64   if(i==0) return 0;
  65   uint ini = 0;
  66   uint fin = len-1;
  67   while(ini<fin) {
  68     uint pos = (ini+fin)/2;
  69     uint br = rank1(pos);
  70     if(br<i)
  71       ini = pos+1;
  72     else
  73       fin = pos;
  74   }
  75         return ini;
  76 }
  77
  78 bool static_bitsequence::access(uint i) {
  79   return (rank1(i)-(i!=0?rank1(i-1):0))>0;
  80 }
  81
  82 uint static_bitsequence::length() {
  83         return len;
  84 }
  85
  86 uint static_bitsequence::count_one() {
  87         return ones;
  88 }
  89
  90 uint static_bitsequence::count_zero() {
  91         return len-ones;
  92 }
  93
  94 static_bitsequence * static_bitsequence::load(FILE * fp) {
  95   uint r;
  96   if(fread(&r,sizeof(uint),1,fp)!=1) return NULL;
  97   fseek(fp,-1*sizeof(uint),SEEK_CUR);
  98   switch(r) {
  99     case RRR02_HDR: return static_bitsequence_rrr02::load(fp);
 100     case BRW32_HDR: return static_bitsequence_brw32::load(fp);
 101     case RRR02_LIGHT_HDR: return static_bitsequence_rrr02_light::load(fp);
 102   }
 103   return NULL;
 104 }