[algorithm-bit-xs.git] / XS.xs

#define PERL_NO_GET_CONTEXT
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

#include "ppport.h"

typedef struct {
	IV n;
	IV* t;
} bit;

bit* bit_create(IV len) {
	if(len < 1){
		croak("Length less than 1");
		return 0;
	}
	len++;
	bit *ret;
	Newx(ret, 1, bit);
	ret->n = len;
	Newxz(ret->t, len, IV);
	return ret;
}

void bit_free(bit *b) {
	Safefree(b->t);
	Safefree(b);
}

IV bit_query(bit *b, IV idx) {
	if(idx > b->n || idx < 1){
		croak("Index not in range [1," IVdf "]", b->n);
		return 0;
	}
	IV ret = 0;
	while(idx)
		ret += b->t[idx], idx -= idx & -idx;
	return ret;
}

void bit_update(bit *b, IV idx, IV value) {
	if(idx > b->n || idx < 1){
		croak("Index not in range [1," IVdf "]", b->n);
		return;
	}
	while(idx < b->n)
		b->t[idx] += value, idx += idx & -idx;
}

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_

PROTOTYPES: ENABLE

Algorithm::BIT::XS bit_create(IV len);

void bit_free(Algorithm::BIT::XS b);

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);
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)
	92	ret += b->t[i1 * b->n + i2], i2 -= i2 & -i2;
	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)
	111	b->t[i1 * b->n + i2] += value, i2 += i2 & -i2;
	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);