/
BitSet.wurst
138 lines (106 loc) · 4.08 KB
/
BitSet.wurst
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
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()