package BitSet
import NoWurst
import Integer
import Wurstunit
import Annotations

public constant BITSET_SIZE = 32

int array pows
int array reversePows

@compiletime function initPows()
	pows[0] = 1
	var allPows = 1
	for i = 1 to BITSET_SIZE - 1
		pows[i] = pows[i - 1] * 2
		allPows = allPows.bitOr(pows[i])
	for i = 0 to BITSET_SIZE - 1
		reversePows[i] = allPows.bitXor(pows[i])

init
	initPows()

/** Bitset represents a fixed-size sequence of BITSET_SIZE bits. The bits are contained in a single int. */
public tuple bitset(int val)

/** Creates an empty bitset. */
public function emptyBitset() returns bitset
	return bitset(0)

/** Returns the value of the bit with the specified index. */
public function bitset.get(int index) returns bool
	return this.val.bitAnd(pows[index]) != 0

/** Sets the bit at the specified index to true. */
public function bitset.set(int index) returns bitset
	return bitset(this.val.bitOr(pows[index]))

/** Sets the bit at the specified index to false. */
public function bitset.reset(int index) returns bitset
	return bitset(this.val.bitAnd(reversePows[index]))

/** Sets the bit at the specified index to the specified value. */
public function bitset.set(int index, bool value) returns bitset
	return value ? this.set(index) : this.reset(index)

/** Sets the bit at the specified index to the complement of its current value. */
public function bitset.flip(int index) returns bitset
	return bitset(this.val.bitXor(pows[index]))

/** Returns true if this bitset contains no bits that are set to true. */
public function bitset.isEmpty() returns bool
	return this.val == 0

/** Returns true if the specified bitset has any bits set to true that are also set to true in this bitset. */
public function bitset.intersects(bitset other) returns bool
	return this.val.bitAnd(other.val) != 0

/** Performs a logical AND of this bit set with the bit set argument. */
public function bitset.bitAnd(bitset other) returns bitset
	return bitset(this.val.bitAnd(other.val))

/** Performs a logical OR of this bit set with the bit set argument. */
public function bitset.bitOr(bitset other) returns bitset
	return bitset(this.val.bitOr(other.val))

/** Performs a logical XOR of this bit set with the bit set argument. */
public function bitset.bitXor(bitset other) returns bitset
	return bitset(this.val.bitXor(other.val))

/** Returns an integer representation of the data. */
public function bitset.toInt() returns int
	return this.val

// Conversion methods for generics

public function bitsetToIndex(bitset object) returns int
	return object.toInt()

public function bitsetFromIndex(int index) returns bitset
	return bitset(index)

// Tests

@test function testGet()
	let set = bitset(45)
	set.get(0).assertTrue()
	set.get(1).assertFalse()
	set.get(2).assertTrue()
	set.get(3).assertTrue()
	set.get(4).assertFalse()
	set.get(5).assertTrue()

@test function testSet()
	emptyBitset().set(0).set(2).set(3).set(5).val.assertEquals(45)

@test function testReset()
	bitset(45).reset(3).val.assertEquals(37)

@test function testFlip()
	emptyBitset().set(3).flip(3).get(3).assertFalse()
	emptyBitset().flip(3).get(3).assertTrue()

@test function testHighestBit()
	let bit = BITSET_SIZE - 1
	emptyBitset().set(bit).get(bit).assertTrue()
	emptyBitset().set(bit).reset(bit).get(bit).assertFalse()
	emptyBitset().flip(bit).get(bit).assertTrue()
	emptyBitset().set(bit).flip(bit).get(bit).assertFalse()

@test function testIsEmpty()
	emptyBitset().isEmpty().assertTrue()
	emptyBitset().set(7).isEmpty().assertFalse()

@test function testIntersects()
	emptyBitset().set(2).set(5).set(7).intersects(emptyBitset().set(1).set(4).set(21)).assertFalse()
	emptyBitset().set(3).set(11).intersects(emptyBitset().set(5).set(11)).assertTrue()

@test function testOverall()
	var bitset = emptyBitset().set(0).set(3).set(8)

	for i = 0 to 8
		if i == 0 or i == 3 or i == 8
			bitset.get(i).assertTrue()
		else
			bitset.get(i).assertFalse()

	bitset = bitset.reset(8)
	.set(3) // should not change anything
	.reset(2) // should not change anything
	.flip(0)
	.flip(2)

	for i = 0 to 8
		if i == 2 or i == 3
			bitset.get(i).assertTrue()
		else
			bitset.get(i).assertFalse()