csalib/sparsearray2.h at master · sadakane/csalib · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
   Copyright 2010, Kunihiko Sadakane, all rights reserved.

   This software may be used freely for any purpose.
   No warranty is given regarding the quality of this software.
*/
#ifndef _SPARSEARRAY2_H_
#define _SPARSEARRAY2_H_

#include "densearray2.h"
#include "mman.h"

#define logD 6

#define PBS (sizeof(bitvec_t)*8)
//#define D (1<<logD)

#ifndef min
 #define min(x,y) ((x)<(y)?(x):(y))
#endif

typedef struct {
  i64 n;
  i64 m;
  i64 d;
  bitvec_t *hi;
  bitvec_t *low;
  densearray_sb *sd0,*sd1;
} sparsearray_sb;

i64 sparsearray_sb_construct(sparsearray_sb *sa, i64 n, bitvec_t *buf, int opt);
int sparsearray_sb_construct_init(sparsearray_sb *sa, i64 n, i64 m);
int sparsearray_sb_construct_set(sparsearray_sb *sa, i64 i, i64 x);
i64 sparsearray_sb_construct_end(sparsearray_sb *sa, int opt);
i64 sparsearray_sb_write(sparsearray_sb *sa, int opt, FILE *f);
i64 sparsearray_sb_read(sparsearray_sb *sa, int opt, uchar **map);

i64 sparsearray_sb_select(sparsearray_sb *sa, i64 i);
i64 sparsearray_sb_rank(sparsearray_sb *sa, i64 i);
i64 sparsearray_sb_rank0(sparsearray_sb *sa, i64 i);
int sparsearray_sb_getbit(sparsearray_sb *sa, i64 i);
i64 sparsearray_sb_rank_bit(sparsearray_sb *sa, i64 i, int *c);

typedef struct {
  i64 n,m,d,k;
  i64 size;
//  i64 *s;
  uchar *s;
  sparsearray_sb *sa;
  bitvec_t *hi, *low;
  int opt;

} sparsearray4;

i64 sparsearray4_construct(sparsearray4 *sa, i64 n, bitvec_t *buf, int opt);
int sparsearray4_construct_init(sparsearray4 *sa, i64 n, i64 m);
int sparsearray4_construct_set(sparsearray4 *sa, i64 i, i64 x);
i64 sparsearray4_construct_end(sparsearray4 *sa, ushort L, int opt);
i64 sparsearray4_write(sparsearray4 *sa, FILE *f);
i64 sparsearray4_read(sparsearray4 *sa, uchar **map);

i64 sparsearray4_select(sparsearray4 *sa, i64 i);
i64 sparsearray4_rank(sparsearray4 *sa, i64 i);
i64 sparsearray4_rank0(sparsearray4 *sa, i64 i);
int sparsearray4_getbit(sparsearray4 *sa, i64 i);
i64 sparsearray4_rank_and_bit(sparsearray4 *sa, i64 i, int *c);


#endif // _SPARSEARRAY2_H_