1
2
3
4
5
6 using System;
7
8 namespace System.Collections
9 {
10 public class Bitset
11 {
12 public Bitset() : numBits(0), bits()
13 {
14 bits.Add(0u);
15 }
16 public Bitset(long numBits_) : numBits(0), bits()
17 {
18 Resize(numBits_);
19 }
20 public Bitset(const string& bits_) : numBits(0), bits()
21 {
22 Resize(bits_.Length());
23 for (long i = 0; i < numBits; ++i;)
24 {
25 if (bits_[i] == '1')
26 {
27 Set(i);
28 }
29 }
30 }
31 public default Bitset(const Bitset&);
32 public default void operator=(const Bitset&);
33 public default Bitset(Bitset&&);
34 public default void operator=(Bitset&&);
35 public default ~Bitset();
36 public void Clear()
37 {
38 numBits = 0;
39 bits.Clear();
40 }
41 public inline long Count() const
42 {
43 return numBits;
44 }
45 public void Resize(long numBits_)
46 {
47 numBits = numBits_;
48 #assert(numBits >= 0);
49 if (numBits > 0)
50 {
51 bits.Resize(1 + NumFullBlocks());
52 }
53 else
54 {
55 bits.Resize(1);
56 }
57 }
58 public void Set()
59 {
60 long n = bits.Count();
61 for (long i = 0; i < n; ++i;)
62 {
63 bits[i] = allOne;
64 }
65 }
66 public void Reset()
67 {
68 long n = bits.Count();
69 for (long i = 0; i < n; ++i;)
70 {
71 bits[i] = cast<ulong>(0u);
72 }
73 }
74 public void CheckPos(long pos)
75 {
76 #assert(pos >= 0 && pos < numBits);
77 }
78 public inline void Set(long pos)
79 {
80 CheckPos(pos);
81 ulong& b = bits[pos / blockSize];
82 b = b | (1u << (cast<ulong>(pos) & blockMask));
83 }
84 public inline void Reset(long pos)
85 {
86 CheckPos(pos);
87 ulong& b = bits[pos / blockSize];
88 b = b & ~(1u << (cast<ulong>(pos) & blockMask));
89 }
90 public void Set(long pos, bool bit)
91 {
92 if (bit)
93 {
94 Set(pos);
95 }
96 else
97 {
98 Reset(pos);
99 }
100 }
101 public void Flip()
102 {
103 long n = bits.Count();
104 for (long i = 0; i < n; ++i;)
105 {
106 bits[i] = ~(bits[i]);
107 }
108 }
109 public inline void Flip(long pos)
110 {
111 CheckPos(pos);
112 ulong& b = bits[pos / blockSize];
113 b = b ^ (1u << (cast<ulong>(pos) & blockMask));
114 }
115 public inline bool operator[](long index) const
116 {
117 return Test(index);
118 }
119 public inline bool Test(long pos) const
120 {
121 CheckPos(pos);
122 ulong b = bits[pos / blockSize];
123 return (b & (1u << (cast<ulong>(pos) & blockMask))) != 0u;
124 }
125 public bool All() const
126 {
127 long n = NumFullBlocks();
128 for (long i = 0; i < n; ++i;)
129 {
130 if (bits[i] != allOne)
131 {
132 return false;
133 }
134 }
135 for (long i = LastBlockStartIndex(); i < numBits; ++i;)
136 {
137 if (!Test(i))
138 {
139 return false;
140 }
141 }
142 return true;
143 }
144 public bool Any() const
145 {
146 long n = NumFullBlocks();
147 for (long i = 0; i < n; ++i;)
148 {
149 if (bits[i] != 0u)
150 {
151 return true;
152 }
153 }
154 for (long i = LastBlockStartIndex(); i < numBits; ++i;)
155 {
156 if (Test(i))
157 {
158 return true;
159 }
160 }
161 return false;
162 }
163 public bool None() const
164 {
165 long n = NumFullBlocks();
166 for (long i = 0; i < n; ++i;)
167 {
168 if (bits[i] != 0u)
169 {
170 return false;
171 }
172 }
173 for (long i = LastBlockStartIndex(); i < numBits; ++i;)
174 {
175 if (Test(i))
176 {
177 return false;
178 }
179 }
180 return true;
181 }
182 public string ToString() const
183 {
184 string s;
185 s.Reserve(numBits);
186 for (long i = 0; i < numBits; ++i;)
187 {
188 if (Test(i))
189 {
190 s.Append('1');
191 }
192 else
193 {
194 s.Append('0');
195 }
196 }
197 return s;
198 }
199 public inline long NumBits() const
200 {
201 return numBits;
202 }
203 public inline List<ulong>& Bits() const
204 {
205 return bits;
206 }
207 public inline long NumFullBlocks() const
208 {
209 if (numBits == 0)
210 {
211 return 0;
212 }
213 return (numBits - 1) / blockSize;
214 }
215 public inline long LastBlockStartIndex() const
216 {
217 return NumFullBlocks() * blockSize;
218 }
219 private const long blockSize = 64;
220 private const ulong blockMask = 63u;
221 private const ulong allOne = cast<ulong>(-1);
222 private long numBits;
223 private List<ulong> bits;
224 }
225
226 public bool operator==(const Bitset& left, const Bitset& right)
227 {
228 long numBits = left.NumBits();
229 if (numBits != right.NumBits())
230 {
231 return false;
232 }
233 long n = left.NumFullBlocks();
234 for (long i = 0; i < n; ++i;)
235 {
236 if (left.Bits()[i] != right.Bits()[i])
237 {
238 return false;
239 }
240 }
241 for (long i = left.LastBlockStartIndex(); i < numBits; ++i;)
242 {
243 if (left.Test(i) != right.Test(i))
244 {
245 return false;
246 }
247 }
248 return true;
249 }