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     @property bool empty() const @safe pure nothrow @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 nothrow @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 nothrow @safe @nogc
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         static immutable err = new Error("buffer.length < repeat");
82         throw err;
83     }
84 }
85 
86 @safe pure nothrow @nogc unittest
87 {
88     int[2] items = [1, 2];
89     const n = 4;
90     int[n] buf;
91     import std.algorithm.comparison : equal;
92     assert(items.cartesianPower!false(n, buf)
93                 .equal([[1, 1, 1, 1].s[],
94                         [1, 1, 1, 2].s[],
95                         [1, 1, 2, 1].s[],
96                         [1, 1, 2, 2].s[],
97                         [1, 2, 1, 1].s[],
98                         [1, 2, 1, 2].s[],
99                         [1, 2, 2, 1].s[],
100                         [1, 2, 2, 2].s[],
101                         [2, 1, 1, 1].s[],
102                         [2, 1, 1, 2].s[],
103                         [2, 1, 2, 1].s[],
104                         [2, 1, 2, 2].s[],
105                         [2, 2, 1, 1].s[],
106                         [2, 2, 1, 2].s[],
107                         [2, 2, 2, 1].s[],
108                         [2, 2, 2, 2].s[]].s[]));
109 }