bp-darray.h

   1 #ifndef BP_DARRAY_H_
   2 #define BP_DARRAY_H_
   3
   4 #ifdef __cplusplus
   5 extern "C" {
   6 #endif
   7 #include "bp-utils.h"
   8
   9 typedef unsigned char byte;
  10 typedef unsigned short word;
  11 typedef unsigned int dword;
  12
  13 #define OPT_NO_RANK (1<<30)
  14
  15
  16 typedef dword pb;
  17
  18
  19 typedef struct {
  20   int n,m;
  21   int size;
  22   pb *buf;
  23   dword *lp;
  24   dword *sl;
  25   word *ss;
  26   dword *p;
  27
  28   dword *rl;
  29   word *rm;
  30   byte *rs;
  31
  32   int idx_size;
  33 } darray;
  34
  35
  36 darray * bp_darray_construct(int n, pb *buf,int opt);
  37 void bp_darray_free(darray *da);
  38
  39 int bp_darray_select(darray *da, int i,int f);
  40 static int bp_darray_rank(darray *da, int i)
  41 {
  42   int r,j,i_rr, i_rrr;
  43   pb *p;
  44   i_rr = i >> logRR;
  45   i_rrr = i >> logRRR;
  46   r = da->rl[i>>logR] + da->rm[i_rr];
  47
  48   j = (i_rrr) & (RR/RRR-1);
  49   while (j > 0) {
  50     r += da->rs[((i_rr)<<(logRR-logRRR))+j-1];
  51     j--;
  52   }
  53
  54   p = da->buf + ((i_rrr)<<(logRRR-logD));
  55   j = i & (RRR-1);
  56   while (j >= D) {
  57     r += popcount(*p++);
  58     j -= D;
  59   }
  60   r += popcount(*p >> (D-1-j));
  61
  62   return r;
  63 }
  64
  65 darray * bp_darray_pat_construct(int n, pb *buf, int k, pb pat, int opt);
  66 int bp_darray_pat_select(darray *da, int i, pb (*getpat)(pb *));
  67 int bp_darray_pat_rank(darray *da, int i, pb (*getpat)(pb *));
  68
  69 int bp_darray_select_bsearch(darray *da, int i, pb (*getpat)(pb *));
  70
  71
  72
  73 #ifdef __cplusplus
  74 }
  75 #endif
  76
  77
  78 #endif