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