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     {
96         return x = ui;
97     }
98     else
99     {
100         ui -= 0xD800;
101         ui += 0xE000;
102 
103         // skip undefined
104         if (ui < 0xFFFE)
105             return x = ui;
106         else
107             ui += 2;
108 
109         assert(ui < 0x110000);
110         return x = ui;
111     }
112 }
113 
114 unittest
115 {
116     auto x = randomized!dchar;
117     dstring d = "alphaalphaalphaalphaalphaalphaalphaalphaalphaalpha";
118     auto r = d.randomize; // TODO: Use Phobos function to check if string is legally coded.
119 }
120 
121 /** Randomize value of $(D x). */
122 dstring randInPlace(dstring x) @trusted
123 {
124     typeof(x) y;
125     foreach (ix; 0 .. x.length)
126         y ~= randomized!dchar; // TODO: How to do this in a better way?
127     x = y;
128     return x;
129 }
130 
131 /** Randomize value of $(D x).
132  */
133 R randInPlace(R)(R x)
134 if (isIterable!R &&
135     hasAssignableElements!R)
136 {
137     import core.lifetime : move;
138     foreach (ref e; x)
139     {
140         e.randInPlace();
141     }
142     return move(x);             // TODO: remove when compiler does this for us
143 }
144 
145 /** Randomize all elements of $(D x).
146     Each element is randomized within range `[elementLow, elementHigh]`.
147  */
148 R randInPlaceWithElementRange(R, E)(R x,
149                                     E elementLow,
150                                     E elementHigh)
151 if (isIterable!R &&
152     hasAssignableElements!R &&
153     is(ElementType!R == E))
154 {
155     import core.lifetime : move;
156     foreach (ref e; x)
157     {
158         e.randInPlaceWithRange(elementLow, elementHigh);
159     }
160     return move(x);
161 }
162 
163 @safe unittest
164 {
165     void testDynamic(T)()
166     {
167         auto x = new T[testLength];
168         auto y = x.dup;
169         x.randInPlace();
170         y.randInPlace();
171         assert(y != x);
172     }
173     testDynamic!int;
174     testDynamic!float;
175     testDynamic!bool;
176 }
177 
178 /** Randomize elements of $(D x).
179  */
180 ref T randInPlace(T)(return ref T x)
181 if (isStaticArray!T)
182 {
183     foreach (ref e; x)
184     {
185         e.randInPlace();
186     }
187     return x;
188 }
189 
190 @safe unittest
191 {
192     void testStatic(T)()
193     {
194         T[testLength] x;
195         auto y = x;
196         x.randInPlace();
197         y.randInPlace();
198         assert(y != x);
199     }
200     testStatic!bool;
201     testStatic!int;
202     testStatic!real;
203     enum E { a, b, c, d, e, f, g, h,
204              i, j, k, l, m, n, o, p }
205     testStatic!E;
206 }
207 
208 /** Blockwise-randomize elements of $(D x) of array type $(D A).
209     Randomizes in array blocks of type $(D B).
210  */
211 ref A randInPlaceBlockwise(B = size_t, A)(ref A x)
212 if (isArray!A &&
213     isIntegral!(ElementType!A))
214 {
215     alias E = ElementType!A;
216     static assert(E.sizeof < B.sizeof);
217     enum mult = B.sizeof / E.sizeof; // block multiplicity
218 
219     immutable n = x.length;
220 
221     // beginning unaligned bytes
222     auto p = cast(size_t)x.ptr;
223     immutable size_t mask = B.sizeof - 1;
224     immutable r = (p & mask) / E.sizeof; // element-offset from B-aligned address before x
225     size_t k = 0; // E-index to first B-block
226     if (r)
227     {
228         import std.algorithm.comparison : min;
229         k = min(n, mult - r); // at first aligned B-block
230         foreach (i, ref e; x[0 .. k])
231         {
232             e.randInPlace();
233         }
234     }
235 
236     // mid blocks of type B
237     auto bp = cast(B*)(x.ptr + k); // block pointer
238     immutable nB = (n - k) / mult; // number of B-blocks
239     foreach (ref b; 0 .. nB) // for each block index
240     {
241         bp[b].randInPlace();
242     }
243 
244     // ending unaligned bytes
245     foreach (i, ref e; x[k + nB*mult .. $])
246     {
247         e.randInPlace();
248     }
249 
250     return x;
251 }
252 
253 unittest
254 {
255     static void test(B = size_t, T)()
256     {
257         enum n = 1024;
258 
259         // dynamic array
260         for (size_t i = 0; i < n; i++)
261         {
262             T[] da = new T[i];
263             da.randInPlaceBlockwise!B;
264             size_t j = randomInstanceOf!(typeof(i))(0, n/2);
265             da.randInPlaceBlockwise!B;
266         }
267 
268         // static array
269         T[n] sa;
270         auto sa2 = sa[1 .. $];
271         sa2.randInPlaceBlockwise!B;
272     }
273 
274     import std.meta : AliasSeq;
275     foreach (T; AliasSeq!(byte, short, int, ubyte, ushort, uint))
276     {
277         test!(size_t, T);
278     }
279 }
280 
281 /** Randomize members of $(D x).
282  */
283 auto ref randInPlace(T)(return ref T x)
284 if (is(T == struct))
285 {
286     foreach (ref e; x.tupleof)
287     {
288         e.randInPlace();
289     }
290     return x;
291 }
292 
293 @safe unittest
294 {
295     struct T { ubyte a, b, c, d; }
296     T[testLength] x;
297     auto y = x;
298     x.randInPlace();
299     y.randInPlace();
300     assert(y != x);
301 }
302 
303 /** Randomize members of $(D x).
304  */
305 auto ref randInPlace(T)(T x)
306 if (is(T == class))
307 {
308     foreach (ref e; x.tupleof)
309     {
310         e.randInPlace();
311     }
312     return x;
313 }
314 
315 alias randomize = randInPlace;
316 
317 unittest
318 {
319     void testClass(E)()
320     {
321         class T { E a, b; }
322         auto x = new T;
323         auto y = new T;
324         x.randInPlace();
325         y.randInPlace();
326         assert(y != x);
327     }
328     testClass!bool;
329     testClass!int;
330     testClass!float;
331 }
332 
333 /** Returns: randomized instance of type $(D T).
334  */
335 T randomInstanceOf(T)()
336 {
337     /* TODO: recursively only void-initialize parts of T that are POD, not
338      reference types */
339     static if (hasIndirections!T)
340         T x;
341     else
342         /* don't init - randInPlace below fills in everything safely */
343         T x = void;
344     x.randInPlace();
345     return x;
346 }
347 
348 /** Returns: randomized instance of type $(D T).
349  */
350 T randomInstanceOf(T)(T low = T.min,
351                       T high = T.max)
352 if (isNumeric!T)
353 {
354     /* TODO: recursively only void-initialize parts of T that are POD, not
355        reference types */
356     static if (hasIndirections!T)
357         T x;
358     else
359         /* don't init - `randInPlace()` below fills in everything safely */
360         T x = void;
361     return x.randInPlaceWithRange(low, high);
362 }
363 
364 alias randomized = randomInstanceOf;
365 
366 /** Random number generator xoroshiro128+
367 
368     See_Also: http://xoroshiro.di.unimi.it/
369     See_Also: http://forum.dlang.org/post/kdobdorqztlsomweftmi@forum.dlang.org
370     See_Also: https://www.reddit.com/r/programming/comments/4gtlfz/xoroshiro128_the_fastest_fullperiod_pseudorandom/
371  */
372 struct Xoroshiro128plus
373 {
374 @safe pure nothrow @nogc:
375     public:
376 
377     enum ulong min = ulong.min;
378     enum ulong max = ulong.max;
379 
380     enum bool isUniformRandom = true;
381 
382     /// Range primitives
383     enum bool empty = false;
384 
385     /// ditto
386     ulong front() @property
387     {
388         return s[0] + s[1];
389     }
390 
391     /// ditto
392     void popFront()
393     {
394         immutable ulong s1 = s[1] ^ s[0];
395         s[0] = rotateLeft(s[0], 55) ^ s1 ^ (s1 << 14);
396         s[1] = rotateLeft(s1, 36);
397     }
398 
399     void seed(ulong s0, ulong s1)
400     in
401     {
402         // seeds are not both 0
403         assert(!(!s0 && !s1));
404     }
405     do
406     {
407         s[0] = s0;
408         s[1] = s1;
409     }
410 
411     void seed(ulong[2] s01)
412     in
413     {
414         // seeds are not both 0
415         assert(!(!s01[0] && !s01[1]));
416     }
417     do
418     {
419         s[] = s01[];
420     }
421 
422 private:
423     ulong[2] s;
424 
425     static ulong rotateLeft(ulong x, int k)
426     in
427     {
428         assert(k <= 64);
429     }
430     do
431     {
432         return (x << k) | (x >> (64 - k));
433     }
434 }
435 
436 @safe pure nothrow unittest
437 {
438     Xoroshiro128plus gen;
439     gen.seed(150078950, 1313143614);
440     import std.random : uniform;
441     import std.range : generate, take;
442     auto x = generate!(() => uniform!int(gen)).take(103);
443 }