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