shithub: mc

ref: ae222f2157fa57dd27ff23bcb13c78adc08627b2
dir: /libstd/bitset.myr/

use "alloc.use"
use "extremum.use"
use "mk.use"
use "slfill.use"
use "types.use"

pkg std =
	type bitset = struct
		bits : size[:]
	;;

	const mkbs	: (-> bitset#)
	const bsdup	: (bs : bitset# -> bitset#)
	const bsfree	: (bs : bitset# -> void)

	generic bsput	: (bs : bitset#, v : @a::(integral,numeric) -> void)
	generic bsdel	: (bs : bitset#, v : @a::(integral,numeric) -> void)
	generic bshas	: (bs : bitset#, v : @a::(integral,numeric) -> bool)

	const bsdiff	: (a : bitset#, b : bitset# -> void)
	const bsintersect	: (a : bitset#, b : bitset# -> void)
	const bsunion	: (a : bitset#, b : bitset# -> void)
	const bseq	: (a : bitset#, b : bitset# -> bool)
	const bsissubset	: (a : bitset#, b : bitset# -> bool)

	const bsclear	: (bs : bitset# -> bitset#)
;;

const mkbs = {
	-> zalloc()
}

const bsdup = {bs
	-> mk([.bits=bs.bits])
}

const bsfree = {bs
	slfree(bs.bits)
	free(bs)
}

const bsclear = {bs
	slfill(bs.bits, 0)
	-> bs
}

generic bsput = {bs, v
	var idx
	var off

	idx = (v castto(size)) / (8*sizeof(size))
	off = (v castto(size)) % (8*sizeof(size))
	ensurespace(bs, idx)
	bs.bits[idx] |= (1 << off)
}

generic bsdel = {bs, v
	var idx
	var off

	idx = (v castto(size)) / (8*sizeof(size))
	off = (v castto(size)) % (8*sizeof(size))
	ensurespace(bs, idx)
	bs.bits[idx] &= ~(1 << off)
}

generic bshas = {bs, v
	var idx
	var off

	idx = (v castto(size)) / (8*sizeof(size))
	off = (v castto(size)) % (8*sizeof(size))
	ensurespace(bs, idx)
	-> (bs.bits[idx] & (1 << off)) != 0
}

const bsunion = {a, b
	var i

	eqsz(a, b)
	for i = 0; i < b.bits.len; i++
		a.bits[i] |= b.bits[i]
	;;
}

const bsintersect = {a, b
	var i, n

	n = min(a.bits.len, b.bits.len)
	for i = 0; i < n; i++
		a.bits[i] &= b.bits[i]
	;;
}

const bsdiff = {a, b
	var i

	ensurespace(b, a.bits.len)
	for i = 0; i < a.bits.len; i++
		a.bits[i] &= ~b.bits[i]
	;;
}

const bsissubset = {a, b
	var i

	eqsz(a, b);
	for i = 0; i < a.bits.len; i++
		if (b.bits[i] & a.bits[i]) != b.bits[i]
			-> false
		;;
	;;
	-> true
}

const bseq = {a, b
	var i

	eqsz(a, b)
	for i = 0; i < a.bits.len; i++
		if a.bits[i] != b.bits[i]
			-> false
		;;
	;;
	-> true
}

const ensurespace = {bs, v
	if bs.bits.len <= v
		bs.bits = slzgrow(bs.bits, v + 1)
	;;
}

const eqsz = {a, b
	var sz

	sz = max(a.bits.len, b.bits.len)
	ensurespace(a, sz)
	ensurespace(b, sz)
}