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