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