1 module nxt.container.static_modarray;
2
3 version = useModulo;
4
5 /** Statically allocated `Mod`-array of fixed pre-allocated length `capacity` of
6 * `Mod`-elements in chunks of `elementLength`. `ElementType` is
7 * `Mod[elementLength]`.
8 */
9 struct StaticModArray(uint capacity,
10 uint elementLength,
11 uint span,
12 bool useModuloFlag)
13 if (capacity*elementLength >= 2) // no use storing less than 2 bytes
14 {
15 private enum radix = 2^^span;
16
17 /// Index modulo `radix` type.
18 static if (useModuloFlag)
19 {
20 import nxt.modulo : Mod;
21 alias Ix = Mod!(radix, ubyte);
22 }
23 else
24 alias Ix = ubyte;
25
26 enum L = elementLength;
27
28 /// ElementType type `T`.
29 static if (L == 1)
30 alias T = Ix;
31 else
32 alias T = Ix[L];
33
34 /** Construct with `rhsCapacity`. */
35 this(uint rhsCapacity)(in StaticModArray!(rhsCapacity,
36 elementLength,
37 span, useModuloFlag) rhs)
38 {
39 static if (capacity < rhsCapacity)
40 assert(rhs.length <= capacity);
41 foreach (immutable i, const ix; rhs)
42 _store[i] = ix;
43 _length = rhs.length;
44 }
45
46 /** Construct with elements `es`. */
47 this(Es...)(Es es)
48 if (Es.length >= 1 &&
49 Es.length <= capacity)
50 {
51 foreach (immutable i, ix; es)
52 _store[i] = ix;
53 _length = es.length;
54 }
55
56 static if (L == 1)
57 {
58 /** Construct with elements in `es`. */
59 this(const Ix[] es)
60 {
61 assert(es.length <= capacity);
62 _store[0 .. es.length] = es;
63 _length = cast(typeof(_length))es.length;
64 }
65 }
66
67 /** Default key separator in printing. */
68 enum keySeparator = ',';
69
70 @property auto toString()(char separator = keySeparator) const /* template-lazy */
71 {
72 string s;
73 foreach (immutable i, const ix; chunks)
74 {
75 if (i != 0) { s ~= separator; }
76 import std.string : format;
77 static if (elementLength == 1)
78 s ~= format("%.2X", ix); // in hexadecimal
79 else
80 {
81 foreach (const j, const subIx; ix[])
82 {
83 if (j != 0) { s ~= '_'; } // separator
84 s ~= format("%.2X", subIx); // in hexadecimal
85 }
86 }
87 }
88 return s;
89 }
90
91 @safe pure nothrow @nogc:
92
93 /** Returns: `true` if `this` is empty, `false` otherwise. */
94 pragma(inline, true)
95 bool empty() const @property => _length == 0;
96
97 /** Get first element. */
98 pragma(inline, true)
99 auto front() inout in(!empty) => _store[0];
100
101 /** Get last element. */
102 pragma(inline, true)
103 auto back() inout in(!empty) => _store[_length - 1];
104
105 /** Returns: `true` if `this` is full, `false` otherwise. */
106 pragma(inline, true)
107 bool full() const => _length == capacity;
108
109 /** Pop first (front) element. */
110 auto ref popFront() in(!empty)
111 {
112 // TODO: is there a reusable Phobos function for this?
113 foreach (immutable i; 0 .. _length - 1)
114 _store[i] = _store[i + 1]; // like `_store[i] = _store[i + 1];` but more generic
115 _length = cast(typeof(_length))(_length - 1);
116 return this;
117 }
118
119 /** Pop `n` front elements. */
120 auto ref popFrontN(size_t n) in(length >= n)
121 {
122 // TODO: is there a reusable Phobos function for this?
123 foreach (immutable i; 0 .. _length - n)
124 _store[i] = _store[i + n];
125 _length = cast(typeof(_length))(_length - n);
126 return this;
127 }
128
129 /** Pop last (back) element. */
130 auto ref popBack() in(!empty)
131 {
132 version(LDC) pragma(inline, true);
133 _length = cast(typeof(_length))(_length - 1); // TODO: better?
134 return this;
135 }
136
137 /** Push/Add elements `es` at back.
138 NOTE Doesn't invalidate any borrow.
139 */
140 auto ref pushBack(Es...)(Es es)
141 if (Es.length <= capacity)
142 in(length + Es.length <= capacity)
143 {
144 foreach (immutable i, const e; es)
145 _store[_length + i] = e;
146 _length = cast(typeof(_length))(_length + Es.length);
147 return this;
148 }
149
150 /** Returns: `true` if `key` is contained in `this`. */
151 bool contains(in Ix[] key) const @nogc
152 {
153 import std.algorithm.searching : canFind;
154 if (key.length != L) { return false; }
155 return chunks.canFind(key); // TODO: use binarySearch instead
156 }
157
158 static if (L == 1)
159 {
160 import std.traits : isUnsigned;
161
162 /** Returns: `true` if `ix` is contained in `this`. */
163 static if (useModuloFlag)
164 {
165 pragma(inline, true)
166 bool contains(ModUInt)(in Mod!(radix, ModUInt) ix) const @nogc
167 if (isUnsigned!ModUInt)
168 {
169 import std.algorithm.searching : canFind;
170 return chunks.canFind(ix); // TODO: use binarySearch
171 }
172 }
173 else
174 {
175 pragma(inline, true)
176 bool contains(UInt)(in UInt ix) const @nogc
177 if (isUnsigned!UInt)
178 {
179 import std.algorithm.searching : canFind;
180 return chunks.canFind(cast(T)ix); // TODO: use binarySearch
181 }
182 }
183 }
184
185 /** Returns: elements as a slice. */
186 pragma(inline, true)
187 auto chunks() inout => _store[0 .. _length];
188 alias chunks this;
189
190 /** Variant of `opIndex` with compile-time range checking. */
191 pragma(inline, true)
192 auto ref at(uint ix)() inout @trusted if (ix < capacity)
193 in(ix < _length) // assert accessing initialized elements
194 => _store.ptr[ix]; // uses `.ptr` because `ix` known at compile-time to be within bounds; `ix < capacity`
195
196 /** Get length. */
197 pragma(inline, true)
198 auto length() const => _length;
199
200 /** Get remaining space available.
201 Name taken from the same member of https://docs.rs/fixedvec/0.2.3/fixedvec/
202 */
203 pragma(inline, true)
204 auto available() const => capacity - _length;
205
206 enum typeBits = 4; // number of bits in enclosing type used for representing type
207
208 private:
209 static if (L == 1)
210 T[capacity] _store = void; // byte indexes
211 else
212 T[capacity] _store = void; // byte indexes
213 static if (_store.sizeof == 6)
214 ubyte _padding;
215 import nxt.dip_traits : hasPreviewBitfields;
216 static if (hasPreviewBitfields) // when -preview=bitfields is passed
217 {
218 mixin("ubyte _length : 8-typeBits;"); // maximum length of 15
219 mixin("ubyte _mustBeIgnored : typeBits;");
220 }
221 else
222 {
223 import std.bitmanip : bitfields;
224 mixin(bitfields!(size_t, "_length", 4, // maximum length of 15
225 ubyte, "_mustBeIgnored", typeBits)); // must be here and ignored because it contains `WordVariant` type of `Node`
226 }
227 }
228
229 version(unittest)
230 {
231 static assert(StaticModArray!(3, 1, 8, false).sizeof == 4);
232 static assert(StaticModArray!(7, 1, 8, false).sizeof == 8);
233 static assert(StaticModArray!(3, 2, 8, false).sizeof == 8);
234 static assert(StaticModArray!(2, 3, 8, false).sizeof == 8);
235 }
236
237 ///
238 @safe pure nothrow @nogc unittest
239 {
240 import std.algorithm : equal;
241
242 version(useModulo)
243 {
244 enum span = 8;
245 enum radix = 2^^span;
246 import nxt.modulo : Mod, mod;
247 alias Ix = Mod!(radix, ubyte);
248 static Mod!radix mk(ubyte value) => mod!radix(value);
249 }
250 else
251 {
252 alias Ix = ubyte;
253 static ubyte mk(ubyte value) => value;
254 }
255
256 const ixs = [mk(11), mk(22), mk(33), mk(44)].s;
257 enum capacity = 7;
258
259 auto x = StaticModArray!(capacity, 1, 8, true)(ixs);
260 auto y = StaticModArray!(capacity, 1, 8, true)(mk(11), mk(22), mk(33), mk(44));
261
262 assert(x == y);
263
264 assert(x.length == 4);
265 assert(x.available == 3);
266 assert(!x.empty);
267
268 assert(!x.contains([mk(10)].s));
269 assert(x.contains([mk(11)].s));
270 assert(x.contains([mk(22)].s));
271 assert(x.contains([mk(33)].s));
272 assert(x.contains([mk(44)].s));
273 assert(!x.contains([mk(45)].s));
274
275 assert(!x.contains(mk(10)));
276 assert(x.contains(mk(11)));
277 assert(x.contains(mk(22)));
278 assert(x.contains(mk(33)));
279 assert(x.contains(mk(44)));
280 assert(!x.contains(mk(45)));
281
282 assert(x.equal([11, 22, 33, 44].s[]));
283 assert(x.front == 11);
284 assert(x.back == 44);
285 assert(!x.full);
286 x.popFront();
287 assert(x.equal([22, 33, 44].s[]));
288 assert(x.front == 22);
289 assert(x.back == 44);
290 assert(!x.full);
291 x.popBack();
292 assert(x.equal([22, 33].s[]));
293 assert(x.front == 22);
294 assert(x.back == 33);
295 assert(!x.full);
296 x.popFront();
297 assert(x.equal([33].s[]));
298 assert(x.front == 33);
299 assert(x.back == 33);
300 assert(!x.full);
301 x.popFront();
302 assert(x.empty);
303 assert(!x.full);
304 assert(x.length == 0);
305
306 x.pushBack(mk(11), mk(22), mk(33), mk(44), mk(55), mk(66), mk(77));
307 assert(x.equal([11, 22, 33, 44, 55, 66, 77].s[]));
308 assert(!x.empty);
309 assert(x.full);
310
311 x.popFrontN(3);
312 assert(x.equal([44, 55, 66, 77].s[]));
313
314 x.popFrontN(2);
315 assert(x.equal([66, 77].s[]));
316
317 x.popFrontN(1);
318 assert(x.equal([77].s[]));
319
320 x.popFrontN(1);
321 assert(x.empty);
322
323 x.pushBack(mk(1)).pushBack(mk(2)).equal([1, 2].s[]);
324 assert(x.equal([1, 2].s[]));
325 assert(x.length == 2);
326 }
327
328 @safe pure nothrow unittest
329 {
330 import std.algorithm : equal;
331
332 version(useModulo)
333 {
334 enum span = 8;
335 enum radix = 2^^span;
336 import nxt.modulo : Mod, mod;
337 alias Ix = Mod!(radix, ubyte);
338 static Mod!radix mk(ubyte value) => mod!radix(value);
339 }
340 else
341 {
342 alias Ix = ubyte;
343 static ubyte mk(ubyte value) => value;
344 }
345
346 const ixs = [mk(11), mk(22), mk(33), mk(44)].s;
347 enum capacity = 7;
348 auto z = StaticModArray!(capacity, 1, 8, true)(ixs);
349 assert(z.sizeof == 8);
350 try
351 {
352 assert(z.toString == `0B,16,21,2C`);
353 }
354 catch (Exception e) {}
355 }
356
357 version(unittest)
358 {
359 import nxt.array_help : s;
360 }