nxt.random_ex source code

1 /** Randomize existing instances and generate randomized instances of a given type.
2 
3     Copyright: Per Nordlöw 2018-.
4     License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
5     Authors: $(WEB Per Nordlöw)
6 
7     See_Also: http://forum.dlang.org/thread/byonwfghdqgcirdjyboh@forum.dlang.org
8 
9     TODO: Can these be tagged with @nogc? Currently std.random.uniform may allocate.
10 
11     TODO: Tags as nothrow when std.random gets there.
12 
13     TODO: How to handle possibly null reference (class, dynamic types) types?
14     Answer relates to how to randomize empty/null variable length structures
15     (arrays, strings, etc).
16 
17     - Maybe some kind of length randomization?
18  */
19 module nxt.random_ex;
20 
21 import std.traits: isIntegral, isFloatingPoint, isNumeric, isIterable, isStaticArray, isArray, hasIndirections, isSomeString, isScalarType, isBoolean;
22 import std.range: ElementType, hasAssignableElements;
23 import std.random: uniform;
24 
25 version(unittest) private enum testLength = 64;
26 
27 /** Randomize value $(D x). */
28 ref E randInPlace(E)(return ref E x)
29 if (isBoolean!E)
30 {
31     return x = cast(bool)uniform(0, 2);
32 }
33 
34 /** Randomize value $(D x), optionally in range [$(D low), $(D high)]. */
35 ref E randInPlace(E)(return ref E x)
36 if (isIntegral!E)
37 {
38     return x = uniform(E.min, E.max);    // BUG: Never assigns the value E.max
39 }
40 
41 /** Randomize value $(D x), optional in range [$(D low), $(D high)]. */
42 ref E randInPlace(E)(return ref E x)
43 if (isFloatingPoint!E)
44 {
45     return x = uniform(cast(E)0, cast(E)1);
46 }
47 
48 /** Randomize value $(D x), optionally in range [$(D low), $(D high)]. */
49 ref E randInPlaceWithRange(E)(return ref E x,
50                               E low,
51                               E high)
52 if (isIntegral!E)
53 {
54     return x = uniform(low, high);    // BUG: Never assigns the value E.max
55 }
56 
57 /** Randomize value of $(D x), optional in range [$(D low), $(D high)]. */
58 ref E randInPlaceWithRange(E)(return ref E x,
59                               E low /* E.min_normal */,
60                               E high /* E.max */)
61 if (isFloatingPoint!E)
62 {
63     return x = uniform(low, high);
64 }
65 
66 version(unittest)
67 {
68     import nxt.rational: Rational, rational;
69 }
70 
71 /** Randomize value of $(D x). */
72 ref Rational!E randInPlace(Rational, E)(return ref Rational!E x) @trusted
73 if (isIntegral!E)
74 {
75     return x = rational(uniform(E.min, E.max),
76                         uniform(1, E.max));
77 }
78 
79 @safe unittest
80 {
81     Rational!int x;
82     x.randInPlace();
83 }
84 
85 /** Generate random value of $(D x).
86     See_Also: http://forum.dlang.org/thread/emlgflxpgecxsqweauhc@forum.dlang.org
87  */
88 ref dchar randInPlace(return ref dchar x) @trusted
89 {
90     auto ui = uniform(0,
91                       0xD800 +
92                       (0x110000 - 0xE000) - 2 // minus two for U+FFFE and U+FFFF
93         );
94     if (ui < 0xD800)
95         return x = ui;
96     else
97     {
98         ui -= 0xD800;
99         ui += 0xE000;
100 
101         // skip undefined
102         if (ui < 0xFFFE)
103             return x = ui;
104         else
105             ui += 2;
106 
107         assert(ui < 0x110000);
108         return x = ui;
109     }
110 }
111 
112 unittest
113 {
114     dstring d = "alphaalphaalphaalphaalphaalphaalphaalphaalphaalpha";
115     auto r = d.randomize; // TODO: Use Phobos function to check if string is legally coded.
116 }
117 
118 /** Randomize value of $(D x). */
119 dstring randInPlace(dstring x) @trusted
120 {
121     typeof(x) y;
122     foreach (ix; 0 .. x.length)
123         y ~= randomized!dchar; // TODO: How to do this in a better way?
124     x = y;
125     return x;
126 }
127 
128 /** Randomize value of $(D x).
129  */
130 R randInPlace(R)(R x)
131 if (isIterable!R &&
132     hasAssignableElements!R)
133 {
134     import core.lifetime : move;
135     foreach (ref e; x)
136         e.randInPlace();
137     return move(x);             // TODO: remove when compiler does this for us
138 }
139 
140 /** Randomize all elements of $(D x).
141     Each element is randomized within range `[elementLow, elementHigh]`.
142  */
143 R randInPlaceWithElementRange(R, E)(R x,
144                                     E elementLow,
145                                     E elementHigh)
146 if (isIterable!R &&
147     hasAssignableElements!R &&
148     is(ElementType!R == E))
149 {
150     import core.lifetime : move;
151     foreach (ref e; x)
152         e.randInPlaceWithRange(elementLow, elementHigh);
153     return move(x);
154 }
155 
156 @safe unittest
157 {
158     void testDynamic(T)()
159     {
160         auto x = new T[testLength];
161         auto y = x.dup;
162         x.randInPlace();
163         y.randInPlace();
164         assert(y != x);
165     }
166     testDynamic!int;
167     testDynamic!float;
168     testDynamic!bool;
169 }
170 
171 /** Randomize elements of $(D x).
172  */
173 ref T randInPlace(T)(return ref T x)
174 if (isStaticArray!T)
175 {
176     foreach (ref e; x)
177         e.randInPlace();
178     return x;
179 }
180 
181 @safe unittest
182 {
183     void testStatic(T)()
184     {
185         T[testLength] x;
186         auto y = x;
187         x.randInPlace();
188         y.randInPlace();
189         assert(y != x);
190     }
191     testStatic!bool;
192     testStatic!int;
193     testStatic!real;
194     enum E { a, b, c, d, e, f, g, h,
195              i, j, k, l, m, n, o, p }
196     testStatic!E;
197 }
198 
199 /** Blockwise-randomize elements of $(D x) of array type $(D A).
200     Randomizes in array blocks of type $(D B).
201  */
202 ref A randInPlaceBlockwise(B = size_t, A)(ref A x)
203 if (isArray!A &&
204     isIntegral!(ElementType!A))
205 {
206     alias E = ElementType!A;
207     static assert(E.sizeof < B.sizeof);
208     enum mult = B.sizeof / E.sizeof; // block multiplicity
209 
210     immutable n = x.length;
211 
212     // beginning unaligned bytes
213     auto p = cast(size_t)x.ptr;
214     immutable size_t mask = B.sizeof - 1;
215     immutable r = (p & mask) / E.sizeof; // element-offset from B-aligned address before x
216     size_t k = 0; // E-index to first B-block
217     if (r)
218     {
219         import std.algorithm.comparison : min;
220         k = min(n, mult - r); // at first aligned B-block
221         foreach (i, ref e; x[0 .. k])
222             e.randInPlace();
223     }
224 
225     // mid blocks of type B
226     auto bp = cast(B*)(x.ptr + k); // block pointer
227     immutable nB = (n - k) / mult; // number of B-blocks
228     foreach (ref b; 0 .. nB) // for each block index
229         bp[b].randInPlace();
230 
231     // ending unaligned bytes
232     foreach (i, ref e; x[k + nB*mult .. $])
233         e.randInPlace();
234 
235     return x;
236 }
237 
238 unittest
239 {
240     static void test(B = size_t, T)()
241     {
242         enum n = 1024;
243 
244         // dynamic array
245         for (size_t i = 0; i < n; i++)
246         {
247             T[] da = new T[i];
248             da.randInPlaceBlockwise!B;
249             size_t j = randomInstanceOf!(typeof(i))(0, n/2);
250             da.randInPlaceBlockwise!B;
251         }
252 
253         // static array
254         T[n] sa;
255         auto sa2 = sa[1 .. $];
256         sa2.randInPlaceBlockwise!B;
257     }
258 
259     import std.meta : AliasSeq;
260     foreach (T; AliasSeq!(byte, short, int, ubyte, ushort, uint))
261         test!(size_t, T);
262 }
263 
264 /** Randomize members of $(D x).
265  */
266 auto ref randInPlace(T)(return ref T x)
267 if (is(T == struct))
268 {
269     foreach (ref e; x.tupleof)
270         e.randInPlace();
271     return x;
272 }
273 
274 @safe unittest
275 {
276     struct T { ubyte a, b, c, d; }
277     T[testLength] x;
278     auto y = x;
279     x.randInPlace();
280     y.randInPlace();
281     assert(y != x);
282 }
283 
284 /** Randomize members of $(D x).
285  */
286 auto ref randInPlace(T)(T x)
287 if (is(T == class))
288 {
289     foreach (ref e; x.tupleof)
290         e.randInPlace();
291     return x;
292 }
293 
294 alias randomize = randInPlace;
295 
296 unittest
297 {
298     void testClass(E)()
299     {
300         class T { E a, b; }
301         auto x = new T;
302         auto y = new T;
303         x.randInPlace();
304         y.randInPlace();
305         assert(y != x);
306     }
307     testClass!bool;
308     testClass!int;
309     testClass!float;
310 }
311 
312 /** Returns: randomized instance of type $(D T).
313  */
314 T randomInstanceOf(T)()
315 {
316     /* TODO: recursively only void-initialize parts of T that are POD, not
317      reference types */
318     static if (hasIndirections!T)
319         T x;
320     else
321         /* don't init - randInPlace below fills in everything safely */
322         T x = void;
323     x.randInPlace();
324     return x;
325 }
326 
327 /** Returns: randomized instance of type $(D T).
328  */
329 T randomInstanceOf(T)(T low = T.min,
330                       T high = T.max)
331 if (isNumeric!T)
332 {
333     /* TODO: recursively only void-initialize parts of T that are POD, not
334        reference types */
335     static if (hasIndirections!T)
336         T x;
337     else
338         /* don't init - `randInPlace()` below fills in everything safely */
339         T x = void;
340     return x.randInPlaceWithRange(low, high);
341 }
342 
343 alias randomized = randomInstanceOf;
344 
345 unittest
346 {
347     auto x = randomized!dchar;
348 	assert(x == x);
349 }
350 
351 /** Random number generator xoroshiro128+
352 
353     See_Also: http://xoroshiro.di.unimi.it/
354     See_Also: http://forum.dlang.org/post/kdobdorqztlsomweftmi@forum.dlang.org
355     See_Also: https://www.reddit.com/r/programming/comments/4gtlfz/xoroshiro128_the_fastest_fullperiod_pseudorandom/
356  */
357 struct Xoroshiro128plus
358 {
359 @safe pure nothrow @nogc:
360     public:
361 
362     enum ulong min = ulong.min;
363     enum ulong max = ulong.max;
364 
365     enum bool isUniformRandom = true;
366 
367     /// Range primitives
368     enum bool empty = false;
369 
370     /// ditto
371     ulong front() @property
372     {
373         return s[0] + s[1];
374     }
375 
376     /// ditto
377     void popFront()
378     {
379 		import core.bitop : rol;
380         immutable ulong s1 = s[1] ^ s[0];
381         s[0] = rol(s[0], 55) ^ s1 ^ (s1 << 14);
382         s[1] = rol(s1, 36);
383     }
384 
385     void seed(ulong s0, ulong s1)
386     in
387     {
388         // seeds are not both 0
389         assert(!(!s0 && !s1));
390     }
391     do
392     {
393         s[0] = s0;
394         s[1] = s1;
395     }
396 
397     void seed(ulong[2] s01)
398     in
399     {
400         // seeds are not both 0
401         assert(!(!s01[0] && !s01[1]));
402     }
403     do
404     {
405         s[] = s01[];
406     }
407 
408 private:
409     ulong[2] s;
410 }
411 
412 @safe pure nothrow unittest
413 {
414     Xoroshiro128plus gen;
415     gen.seed(150078950, 1313143614);
416     import std.random : uniform;
417     import std.range : generate, take;
418     auto x = generate!(() => uniform!int(gen)).take(103);
419 }