nxt.static_modarray source code

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