Commit | Line | Data |
---|---|---|
0e4f7002 MG |
1 | #define PERL_NO_GET_CONTEXT |
2 | #include "EXTERN.h" | |
3 | #include "perl.h" | |
4 | #include "XSUB.h" | |
5 | ||
6 | #include "ppport.h" | |
7 | ||
8 | typedef struct { | |
9 | IV n; | |
10 | IV* t; | |
11 | } bit; | |
12 | ||
13 | bit* bit_create(IV len) { | |
14 | if(len < 1){ | |
15 | croak("Length less than 1"); | |
16 | return 0; | |
17 | } | |
18 | len++; | |
19 | bit *ret; | |
20 | Newx(ret, 1, bit); | |
21 | ret->n = len; | |
22 | Newxz(ret->t, len, IV); | |
23 | return ret; | |
24 | } | |
25 | ||
26 | void bit_free(bit *b) { | |
27 | Safefree(b->t); | |
28 | Safefree(b); | |
29 | } | |
30 | ||
31 | IV bit_query(bit *b, IV idx) { | |
32 | if(idx > b->n || idx < 1){ | |
33 | croak("Index not in range [1," IVdf "]", b->n); | |
34 | return 0; | |
35 | } | |
36 | IV ret = 0; | |
37 | while(idx) | |
38 | ret += b->t[idx], idx -= idx & -idx; | |
39 | return ret; | |
40 | } | |
41 | ||
42 | void bit_update(bit *b, IV idx, IV value) { | |
43 | if(idx > b->n || idx < 1){ | |
44 | croak("Index not in range [1," IVdf "]", b->n); | |
45 | return; | |
46 | } | |
47 | while(idx < b->n) | |
48 | b->t[idx] += value, idx += idx & -idx; | |
49 | } | |
50 | ||
51 | void bit_clear(bit *b) { | |
52 | Zero(b->t, b->n, IV); | |
53 | } | |
54 | ||
0c7cf8e9 MG |
55 | typedef struct { |
56 | IV n, m; | |
57 | IV* t; | |
58 | } bit2d; | |
59 | ||
60 | bit2d* bit2d_create(IV n, IV m) { | |
61 | if(n < 1 || m < 1){ | |
62 | croak("A dimension is less than 1"); | |
63 | return 0; | |
64 | } | |
65 | n++, m++; | |
66 | bit2d *ret; | |
67 | Newx(ret, 1, bit2d); | |
68 | ret->n = n; | |
69 | ret->m = m; | |
70 | Newxz(ret->t, n * m, IV); | |
71 | return ret; | |
72 | } | |
73 | ||
74 | void bit2d_free(bit2d *b) { | |
75 | Safefree(b->t); | |
76 | Safefree(b); | |
77 | } | |
78 | ||
79 | IV bit2d_query(bit2d *b, IV i1, IV i2) { | |
80 | if(i1 > b->n || i1 < 1) { | |
81 | croak("Index 1 not in range [1," IVdf "]", b->n); | |
82 | return 0; | |
83 | } | |
84 | if(i2 > b->m || i2 < 1) { | |
85 | croak("Index 2 not in range [1," IVdf "]", b->m); | |
86 | return 0; | |
87 | } | |
88 | IV ret = 0, i2c = i2; | |
89 | while(i1) { | |
90 | i2 = i2c; | |
91 | while(i2) | |
926e0865 | 92 | ret += b->t[i1 * b->m + i2], i2 -= i2 & -i2; |
0c7cf8e9 MG |
93 | i1 -= i1 & -i1; |
94 | } | |
95 | return ret; | |
96 | } | |
97 | ||
98 | void bit2d_update(bit2d *b, IV i1, IV i2, IV value) { | |
99 | if(i1 > b->n || i1 < 1) { | |
100 | croak("Index 1 not in range [1," IVdf "]", b->n); | |
101 | return; | |
102 | } | |
103 | if(i2 > b->m || i2 < 1) { | |
104 | croak("Index 2 not in range [1," IVdf "]", b->m); | |
105 | return; | |
106 | } | |
107 | IV i2c = i2; | |
108 | while(i1 < b->n) { | |
109 | i2 = i2c; | |
110 | while(i2 < b->m) | |
926e0865 | 111 | b->t[i1 * b->m + i2] += value, i2 += i2 & -i2; |
0c7cf8e9 MG |
112 | i1 += i1 & -i1; |
113 | } | |
114 | } | |
115 | ||
116 | void bit2d_clear(bit2d *b) { | |
117 | Zero(b->t, b->n * b->m, IV); | |
118 | } | |
119 | ||
0e4f7002 | 120 | typedef bit *Algorithm__BIT__XS; |
0c7cf8e9 | 121 | typedef bit2d *Algorithm__BIT2D__XS; |
0e4f7002 MG |
122 | |
123 | MODULE = Algorithm::BIT::XS PACKAGE = Algorithm::BIT::XS PREFIX = bit_ | |
124 | ||
125 | PROTOTYPES: ENABLE | |
126 | ||
127 | Algorithm::BIT::XS bit_create(IV len); | |
128 | ||
129 | void bit_free(Algorithm::BIT::XS b); | |
130 | ||
131 | IV bit_query(Algorithm::BIT::XS b, IV idx); | |
132 | ||
133 | void bit_update(Algorithm::BIT::XS b, IV idx, IV value); | |
134 | ||
135 | void bit_clear(Algorithm::BIT::XS b); | |
0c7cf8e9 MG |
136 | |
137 | MODULE = Algorithm::BIT::XS PACKAGE = Algorithm::BIT2D::XS PREFIX = bit2d_ | |
138 | ||
139 | PROTOTYPES: ENABLE | |
140 | ||
141 | Algorithm::BIT2D::XS bit2d_create(IV n, IV m); | |
142 | ||
143 | void bit2d_free(Algorithm::BIT2D::XS b); | |
144 | ||
145 | IV bit2d_query(Algorithm::BIT2D::XS b, IV i1, IV i2); | |
146 | ||
147 | void bit2d_update(Algorithm::BIT2D::XS b, IV i1, IV i2, IV value); | |
148 | ||
149 | void bit2d_clear(Algorithm::BIT2D::XS b); |