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 }