X-Git-Url: http://git.ieval.ro/?a=blobdiff_plain;f=XS.xs;fp=XS.xs;h=940807b509e110ac8e6f9bdf7b32aeccf36d908e;hb=0c7cf8e9cf7b3714bc5fc9e2625d6e4016b8812a;hp=d395dca861e16b88106a6df98cca485e8e792dc3;hpb=0e4f70024573e1a6be0c53b0c51474eb1d975d43;p=algorithm-bit-xs.git

diff --git a/XS.xs b/XS.xs
index d395dca..940807b 100644
--- a/XS.xs
+++ b/XS.xs
@@ -52,7 +52,73 @@ void bit_clear(bit *b) {
 	Zero(b->t, b->n, IV);
 }
 
+typedef struct {
+	IV n, m;
+	IV* t;
+} bit2d;
+
+bit2d* bit2d_create(IV n, IV m) {
+	if(n < 1 || m < 1){
+		croak("A dimension is less than 1");
+		return 0;
+	}
+	n++, m++;
+	bit2d *ret;
+	Newx(ret, 1, bit2d);
+	ret->n = n;
+	ret->m = m;
+	Newxz(ret->t, n * m, IV);
+	return ret;
+}
+
+void bit2d_free(bit2d *b) {
+	Safefree(b->t);
+	Safefree(b);
+}
+
+IV bit2d_query(bit2d *b, IV i1, IV i2) {
+	if(i1 > b->n || i1 < 1) {
+		croak("Index 1 not in range [1," IVdf "]", b->n);
+		return 0;
+	}
+	if(i2 > b->m || i2 < 1) {
+		croak("Index 2 not in range [1," IVdf "]", b->m);
+		return 0;
+	}
+	IV ret = 0, i2c = i2;
+	while(i1) {
+		i2 = i2c;
+		while(i2)
+			ret += b->t[i1 * b->n + i2], i2 -= i2 & -i2;
+		i1 -= i1 & -i1;
+	}
+	return ret;
+}
+
+void bit2d_update(bit2d *b, IV i1, IV i2, IV value) {
+	if(i1 > b->n || i1 < 1) {
+		croak("Index 1 not in range [1," IVdf "]", b->n);
+		return;
+	}
+	if(i2 > b->m || i2 < 1) {
+		croak("Index 2 not in range [1," IVdf "]", b->m);
+		return;
+	}
+	IV i2c = i2;
+	while(i1 < b->n) {
+		i2 = i2c;
+		while(i2 < b->m)
+			b->t[i1 * b->n + i2] += value, i2 += i2 & -i2;
+		i1 += i1 & -i1;
+	}
+}
+
+void bit2d_clear(bit2d *b) {
+	Zero(b->t, b->n * b->m, IV);
+}
+
 typedef bit *Algorithm__BIT__XS;
+typedef bit2d *Algorithm__BIT2D__XS;
 
 MODULE = Algorithm::BIT::XS		PACKAGE = Algorithm::BIT::XS		PREFIX = bit_
 
@@ -67,3 +133,17 @@ IV bit_query(Algorithm::BIT::XS b, IV idx);
 void bit_update(Algorithm::BIT::XS b, IV idx, IV value);
 
 void bit_clear(Algorithm::BIT::XS b);
+
+MODULE = Algorithm::BIT::XS		PACKAGE = Algorithm::BIT2D::XS		PREFIX = bit2d_
+
+PROTOTYPES: ENABLE
+
+Algorithm::BIT2D::XS bit2d_create(IV n, IV m);
+
+void bit2d_free(Algorithm::BIT2D::XS b);
+
+IV bit2d_query(Algorithm::BIT2D::XS b, IV i1, IV i2);
+
+void bit2d_update(Algorithm::BIT2D::XS b, IV i1, IV i2, IV value);
+
+void bit2d_clear(Algorithm::BIT2D::XS b);