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 static_bitsequence_sdarray::static_bitsequence_sdarray() {make___selecttbl();}
  22
  23 static_bitsequence_sdarray::~static_bitsequence_sdarray() {
  24         if(ones)
  25                 selects3_free(&sd);
  26 }
  27
  28 uint static_bitsequence_sdarray::rank1(uint i) {
  29         if(i>=len) return -1;
  30         if(ones)
  31                 return selects3_rank(&sd,i);
  32         else
  33                 return 0;
  34 }
  35
  36 uint static_bitsequence_sdarray::select1(uint i) {
  37         if(i>ones || i==0) return -1;
  38         if(ones)
  39                 return selects3_select(&sd,i);
  40         else
  41                 return (uint)-1;
  42 }
  43
  44 uint static_bitsequence_sdarray::size() {
  45         return sizeof(static_bitsequence_sdarray)+(ones?(sd.size + sd.sd0->size + sd.sd1->size):0);
  46 }
  47
  48 int static_bitsequence_sdarray::save(FILE * fp) {
  49         uint wr = SDARRAY_HDR;
  50         wr = fwrite(&wr,sizeof(uint),1,fp);
  51         wr += fwrite(&len,sizeof(uint),1,fp);
  52         wr += fwrite(&ones,sizeof(uint),1,fp);
  53         if(wr!=3 || (ones?(selects3_save(&sd,fp)):false))
  54                 return 1;
  55         return 0;
  56 }
  57
  58 static_bitsequence_sdarray * static_bitsequence_sdarray::load(FILE * fp) {
  59         uint id;
  60         if(fread(&id,sizeof(uint),1,fp)!=1) return NULL;
  61         if(id!=SDARRAY_HDR) return NULL;
  62         static_bitsequence_sdarray * ret = new static_bitsequence_sdarray();
  63         id = fread(&ret->len,sizeof(uint),1,fp);
  64         id += fread(&ret->ones,sizeof(uint),1,fp);
  65         if(ret->ones && selects3_load(&ret->sd,fp)) {
  66                 delete ret;
  67                 return NULL;
  68         }
  69         return ret;
  70 }
  71