libcds/src/static_sequence/wt_node_internal.cpp

   1
   2 #include <wt_node_internal.h>
   3
   4
   5 wt_node_internal::wt_node_internal(uint * symbols, uint n, uint l, wt_coder * c, static_bitsequence_builder * bmb) {
   6         uint * ibitmap = new uint[n/W+1];
   7         for(uint i=0;i<n/W+1;i++)
   8                 ibitmap[i]=0;
   9         for(uint i=0;i<n;i++)
  10                 if(c->is_set(symbols[i],l))
  11                         bitset(ibitmap,i);
  12         bitmap = bmb->build(ibitmap, n);
  13   delete [] ibitmap;
  14         uint count_right = bitmap->rank1(n-1);
  15         uint count_left = n-count_right+1;
  16         uint * left = new uint[count_left+1];
  17         uint * right = new uint[count_right+1];
  18         count_right = count_left = 0;
  19         bool match_left = true, match_right = true;
  20         for(uint i=0;i<n;i++) {
  21                 if(bitmap->access(i)) {
  22                         right[count_right++]=symbols[i];
  23                         if(count_right>1)
  24                                 if(right[count_right-1]!=right[count_right-2])
  25                                         match_right = false;
  26                 }
  27                 else {
  28                         left[count_left++]=symbols[i];
  29                         if(count_left>1)
  30                                 if(left[count_left-1]!=left[count_left-2])
  31                                         match_left = false;
  32                 }
  33         }
  34         if(count_left>0) {
  35                 if(match_left)
  36                         left_child = new wt_node_leaf(left[0], count_left);
  37                 else
  38                         left_child = new wt_node_internal(left, count_left, l+1, c, bmb);
  39         } else {
  40                 left_child = NULL;
  41         }
  42         if(count_right>0) {
  43                 if(match_right)
  44                         right_child = new wt_node_leaf(right[0], count_right);
  45                 else
  46                         right_child = new wt_node_internal(right, count_right, l+1, c, bmb);
  47         } else {
  48                 right_child = NULL;
  49         }
  50         delete [] left;
  51         delete [] right;
  52 }
  53
  54 wt_node_internal::wt_node_internal() { }
  55
  56 wt_node_internal::~wt_node_internal() {
  57         delete bitmap;
  58         if(right_child!=NULL) delete right_child;
  59         if(left_child!=NULL) delete left_child;
  60 }
  61
  62 uint wt_node_internal::rank(uint symbol, uint pos, uint l, wt_coder * c) {
  63         bool is_set = c->is_set(symbol,l);
  64         if(!is_set) {
  65                 if(left_child==NULL) return 0;
  66                 return left_child->rank(symbol, bitmap->rank0(pos)-1,l+1,c);
  67         }
  68         else {
  69                 if(right_child==NULL) return 0;
  70                 return right_child->rank(symbol, bitmap->rank1(pos)-1,l+1,c);
  71         }
  72 }
  73
  74 uint wt_node_internal::select(uint symbol, uint pos, uint l, wt_coder * c) {
  75         bool is_set = c->is_set(symbol, l);
  76         if(!is_set) {
  77                 if(left_child==NULL)
  78                         return (uint)(-1);
  79                 uint new_pos = left_child->select(symbol, pos, l+1,c);
  80                 if(new_pos+1==0) return (uint)(-1);
  81                 return bitmap->select0(new_pos)+1;
  82         } else {
  83                 if(right_child==NULL)
  84                         return (uint)(-1);
  85                 uint new_pos = right_child->select(symbol, pos, l+1,c);
  86                 if(new_pos+1==0) return (uint)(-1);
  87                 return bitmap->select1(new_pos)+1;
  88         }
  89 }
  90
  91 uint wt_node_internal::access(uint pos) {
  92         bool is_set = bitmap->access(pos);
  93         if(!is_set) {
  94                 assert(left_child!=NULL);
  95                 return left_child->access(bitmap->rank0(pos)-1);
  96         } else {
  97                 assert(right_child!=NULL);
  98                 return right_child->access(bitmap->rank1(pos)-1);
  99         }
 100 }
 101
 102 uint wt_node_internal::size() {
 103         uint s = bitmap->size()+sizeof(wt_node_internal);
 104         if(left_child!=NULL)
 105                 s += left_child->size();
 106         if(right_child!=NULL)
 107                 s += right_child->size();
 108         return s;
 109 }
 110
 111 uint wt_node_internal::save(FILE *fp) {
 112   uint wr = WT_NODE_INTERNAL_HDR;
 113   wr = fwrite(&wr,sizeof(uint),1,fp);
 114   if(wr!=1) return 1;
 115   if(bitmap->save(fp)) return 1;
 116   if(left_child!=NULL) {
 117     if(left_child->save(fp)) return 1;
 118   } else {
 119     wr = WT_NODE_NULL_HDR;
 120     wr = fwrite(&wr,sizeof(uint),1,fp);
 121     if(wr!=1) return 1;
 122   }
 123   if(right_child!=NULL) {
 124     if(right_child->save(fp)) return 1;
 125   } else {
 126     wr = WT_NODE_NULL_HDR;
 127     wr = fwrite(&wr,sizeof(uint),1,fp);
 128     if(wr!=1) return 1;
 129   }
 130   return 0;
 131 }
 132
 133 wt_node_internal * wt_node_internal::load(FILE *fp) {
 134   uint rd;
 135   if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
 136   if(rd!=WT_NODE_INTERNAL_HDR) return NULL;
 137   wt_node_internal * ret = new wt_node_internal();
 138   ret->bitmap = static_bitsequence::load(fp);
 139   ret->left_child = wt_node::load(fp);
 140   ret->right_child = wt_node::load(fp);
 141   return ret;
 142 }