libcds/src/static_bitsequence/static_bitsequence_sdarray.cpp

   1
   2 #include <static_bitsequence_sdarray.h>
   3
   4 static_bitsequence_sdarray::static_bitsequence_sdarray(uint * buff, uint len) {
   5   uint * tmp_seq = new uint[uint_len(len,1)+1];
   6   ones = 0;
   7   for(uint i=0;i<uint_len(len,1)+1;i++)
   8     tmp_seq[i] = 0;
   9   for(uint i=0;i<len;i++)
  10   if(bitget(buff,i)) {
  11     __setbit(tmp_seq,i,1);
  12     ones++;
  13   }
  14   if(ones)
  15     selects3_construct(&sd,len,tmp_seq);
  16   this->len = len;
  17   //this->ones = sd.m;
  18   delete [] tmp_seq;
  19 }
  20
  21
  22 static_bitsequence_sdarray::static_bitsequence_sdarray() {make___selecttbl();}
  23
  24 static_bitsequence_sdarray::~static_bitsequence_sdarray() {
  25   if(ones)
  26     selects3_free(&sd);
  27 }
  28
  29
  30 uint static_bitsequence_sdarray::rank1(uint i) {
  31   if(i>=len) return -1;
  32   if(ones)
  33     return selects3_rank(&sd,i);
  34   else
  35     return 0;
  36 }
  37
  38
  39 uint static_bitsequence_sdarray::select1(uint i) {
  40   if(i>ones || i==0) return -1;
  41   if(ones)
  42     return selects3_select(&sd,i);
  43   else
  44     return (uint)-1;
  45 }
  46
  47
  48 uint static_bitsequence_sdarray::select_next1(uint i) {
  49   return selects3_selectnext(&sd,i);
  50 }
  51
  52
  53 uint static_bitsequence_sdarray::size() {
  54   return sizeof(static_bitsequence_sdarray)+(ones?(sd.size + sd.sd0->size + sd.sd1->size):0);
  55 }
  56
  57
  58 int static_bitsequence_sdarray::save(FILE * fp) {
  59   uint wr = SDARRAY_HDR;
  60   wr = fwrite(&wr,sizeof(uint),1,fp);
  61   wr += fwrite(&len,sizeof(uint),1,fp);
  62   wr += fwrite(&ones,sizeof(uint),1,fp);
  63   if(wr!=3 || (ones?(selects3_save(&sd,fp)):false))
  64     return 1;
  65   return 0;
  66 }
  67
  68
  69 static_bitsequence_sdarray * static_bitsequence_sdarray::load(FILE * fp) {
  70   uint id;
  71   if(fread(&id,sizeof(uint),1,fp)!=1) return NULL;
  72   if(id!=SDARRAY_HDR) return NULL;
  73   static_bitsequence_sdarray * ret = new static_bitsequence_sdarray();
  74   id = fread(&ret->len,sizeof(uint),1,fp);
  75   id += fread(&ret->ones,sizeof(uint),1,fp);
  76   if(ret->ones && selects3_load(&ret->sd,fp)) {
  77     delete ret;
  78     return NULL;
  79   }
  80   return ret;
  81 }