nxt.permutations source code

1 module nxt.permutations;
2 
3 import std.range.primitives: isInputRange;
4 
5 /** Cartesian power.
6    See_Also: http://forum.dlang.org/thread/mailman.1434.1339436657.24740.digitalmars-d-learn@puremagic.com#post-uftixibnvfffugjwsdbl:40forum.dlang.org
7  */
8 struct CartesianPower(bool doCopy = true, T)
9 {
10 	T[] items;
11 	ulong repeat;
12 	T[] row;
13 	ulong i, maxN;
14 
15 	this(T[] items_, in uint repeat_, T[] buffer)
16 	{
17 		this.items = items_;
18 		this.repeat = repeat_;
19 		row = buffer[0 .. repeat];
20 		row[] = items[0];
21 		maxN = items.length ^^ repeat;
22 	}
23 
24 	static if (doCopy)
25 	{
26 		@property T[] front()
27 		{
28 			return row.dup;
29 		}
30 	}
31 	else
32 	{
33 		@property T[] front()
34 		{
35 			return row;
36 		}
37 	}
38 
39 	bool empty() const @property pure nothrow @safe @nogc
40 	{
41 		return i >= maxN;
42 	}
43 
44 	void popFront()
45 	{
46 		i++;
47 		if (empty) { return; }
48 		ulong n = i;
49 		size_t count = repeat - 1;
50 		while (n)
51 		{
52 			row[count] = items[n % items.length];
53 			count--;
54 			n /= items.length;
55 		}
56 	}
57 }
58 
59 version (unittest)
60 {
61 	import nxt.array_help : s;
62 	static assert(isInputRange!(typeof([1, 2].s[].cartesianPower!false(4))));
63 }
64 
65 auto cartesianPower(bool doCopy = true, T)(T[] items, in uint repeat)
66 	pure @safe
67 {
68 	return CartesianPower!(doCopy, T)(items, repeat, new T[repeat]);
69 }
70 
71 auto cartesianPower(bool doCopy = true, T)(T[] items, in uint repeat, T[] buffer)
72 	pure @safe
73 {
74 	if (buffer.length >= repeat)
75 	{
76 		return CartesianPower!(doCopy, T)(items, repeat, buffer);
77 	}
78 	else
79 	{
80 		// Is this correct in presence of chaining?
81 		throw new Error("buffer.length < repeat");
82 	}
83 }
84 
85 pure @safe unittest {
86 	int[2] items = [1, 2];
87 	const n = 4;
88 	int[n] buf;
89 	import std.algorithm.comparison : equal;
90 	assert(items.cartesianPower!false(n, buf)
91 				.equal([[1, 1, 1, 1].s[],
92 						[1, 1, 1, 2].s[],
93 						[1, 1, 2, 1].s[],
94 						[1, 1, 2, 2].s[],
95 						[1, 2, 1, 1].s[],
96 						[1, 2, 1, 2].s[],
97 						[1, 2, 2, 1].s[],
98 						[1, 2, 2, 2].s[],
99 						[2, 1, 1, 1].s[],
100 						[2, 1, 1, 2].s[],
101 						[2, 1, 2, 1].s[],
102 						[2, 1, 2, 2].s[],
103 						[2, 2, 1, 1].s[],
104 						[2, 2, 1, 2].s[],
105 						[2, 2, 2, 1].s[],
106 						[2, 2, 2, 2].s[]].s[]));
107 }