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