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 (uint)-1;
  30   if(ones==0) return 0;
  31         if(ones==len) return i+1;
  32   uint ini = 1;
  33   uint fin = ones;
  34   while(ini<fin) {
  35     uint pos = (ini+fin)/2;
  36     uint bp = select1(pos);
  37     if(bp==i) return pos;
  38     if(bp<i)
  39       ini = pos+1;
  40     else
  41       fin = pos-1;
  42   }
  43         if(select1(ini)>i) return ini-1;
  44         return ini;
  45 }
  46
  47 uint static_bitsequence::select0(uint i) {
  48   if(i>len-ones) return -1;
  49   if(i==0) return -1;
  50         if(ones==0) return i-1;
  51   uint ini = 0;
  52   uint fin = len-1;
  53   while(ini<fin) {
  54     uint pos = (ini+fin)/2;
  55     uint br = rank0(pos);
  56     if(br<i)
  57       ini = pos+1;
  58     else
  59       fin = pos;
  60   }
  61         return ini;
  62 }
  63
  64 uint static_bitsequence::select1(uint i) {
  65   if(i>ones) return -1;
  66   if(i==0) return -1;
  67         if(ones==len) return i-1;
  68   uint ini = 0;
  69   uint fin = len-1;
  70   while(ini<fin) {
  71     uint pos = (ini+fin)/2;
  72     uint br = rank1(pos);
  73     if(br<i)
  74       ini = pos+1;
  75     else
  76       fin = pos;
  77   }
  78         return ini;
  79 }
  80
  81 uint static_bitsequence::select_next1(uint i) {
  82         return select1(rank1(i)+1);
  83 }
  84
  85 uint static_bitsequence::select_next0(uint i) {
  86         return select0(rank0(i)+1);
  87 }
  88
  89 bool static_bitsequence::access(uint i) {
  90   return (rank1(i)-(i!=0?rank1(i-1):0))>0;
  91 }
  92
  93 uint static_bitsequence::length() {
  94         return len;
  95 }
  96
  97 uint static_bitsequence::count_one() {
  98         return ones;
  99 }
 100
 101 uint static_bitsequence::count_zero() {
 102         return len-ones;
 103 }
 104
 105 static_bitsequence * static_bitsequence::load(FILE * fp) {
 106   uint r;
 107   if(fread(&r,sizeof(uint),1,fp)!=1) return NULL;
 108   fseek(fp,-1*sizeof(uint),SEEK_CUR);
 109   switch(r) {
 110     case RRR02_HDR: return static_bitsequence_rrr02::load(fp);
 111     case BRW32_HDR: return static_bitsequence_brw32::load(fp);
 112     case RRR02_LIGHT_HDR: return static_bitsequence_rrr02_light::load(fp);
 113     case SDARRAY_HDR: return static_bitsequence_sdarray::load(fp);
 114   }
 115   return NULL;
 116 }