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
  41 static int bp_darray_rank(darray *da, int i)
  42 {
  43   int r,j,i_rr, i_rrr;
  44   pb *p;
  45   i_rr = i >> logRR;
  46   i_rrr = i >> logRRR;
  47   r = da->rl[i>>logR] + da->rm[i_rr];
  48
  49   j = (i_rrr) & (RR/RRR-1);
  50   while (j > 0) {
  51     r += da->rs[((i_rr)<<(logRR-logRRR))+j-1];
  52     j--;
  53   }
  54
  55   p = da->buf + ((i_rrr)<<(logRRR-logD));
  56   j = i & (RRR-1);
  57   while (j >= D) {
  58     r += popcount(*p++);
  59     j -= D;
  60   }
  61   r += popcount(*p >> (D-1-j));
  62
  63   return r;
  64 }
  65
  66 darray * bp_darray_pat_construct(int n, pb *buf, int k, pb pat, int opt);
  67 int bp_darray_pat_select(darray *da, int i, pb (*getpat)(pb *));
  68 int bp_darray_pat_rank(darray *da, int i, pb (*getpat)(pb *));
  69
  70 int bp_darray_select_bsearch(darray *da, int i, pb (*getpat)(pb *));
  71
  72
  73
  74 #ifdef __cplusplus
  75 }
  76 #endif
  77
  78
  79 #endif