boolean_matrix source code

1 /*
2 Copyright electrolysis 2016.
3 Distributed under the Boost Software License, Version 1.0.
4 (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5 */
6 
7 module boolean_matrix;
8 
9 // boolean square matrix
10 struct BSM(size_t n) if (n > 0)
11 {
12     bool[n][n] s_mat;
13     alias s_mat this;
14 
15     auto opBinary(string op)(in auto ref BSM!n matrix) const pure
16     {
17         static if (op == "*")
18         {
19             BSM!n r;
20 
21             foreach (i, ref row; s_mat)
22             {
23                 foreach (j, e; row)
24                 {
25                     if (e)
26                     {
27                         r[i][] |= matrix[j][];
28                     }
29                 }
30             }
31 
32             return r;
33         }
34         else
35         {
36             static assert(0, `Operator '` ~ op ~ `' is not implemented.`);
37         }
38     }
39 
40     auto opBinary(string op)(in auto ref BCV!n vector) const pure
41     {
42         static if (op == "*")
43         {
44             BCV!n r;
45 
46             foreach (i, ref row; s_mat)
47             {
48                 foreach (j, e; row)
49                 {
50                     if (e && vector[j])
51                     {
52                         r[i] = true;
53                         break;
54                     }
55                 }
56             }
57 
58             return r;
59         }
60         else
61         {
62             static assert(0, `Operator '` ~ op ~ `' is not implemented.`);
63         }
64     }
65 
66     static enum I = {
67         BSM!n id;
68         foreach (i, ref row; id)
69         {
70             row[i] = true;
71         }
72         return id;
73     }();
74 }
75 
76 // boolean column vector
77 struct BCV(size_t n) if (n > 0)
78 {
79     bool[n] c_vec;
80     alias c_vec this;
81 
82     static auto e(size_t k) pure
83     in
84     {
85         assert(k < n);
86     }
87     body
88     {
89         BCV!n v;
90         v[k] = true;
91         return v;
92     }
93 }
94 
95 unittest
96 {
97     immutable a = BSM!3([[true, false, true], [true, true, false],
98         [false, false, true]]);
99     immutable b = BSM!3([[false, true, true], [true, false, false],
100         [false, false, true]]);
101     immutable c = BSM!3([[false, true, true], [true, true, true],
102         [false, false, true]]);
103 
104     assert(a * b == c);
105 }
106 
107 unittest
108 {
109     immutable a = BSM!3([[true, false, true], [true, true, false],
110         [false, false, true]]);
111     immutable b = BCV!3([true, false, false]);
112     immutable c = BCV!3([true, true, false]);
113 
114     assert(a * b == c);
115 }
116 
117 unittest
118 {
119     immutable a = BCV!3([false, true, false]);
120 
121     assert(BCV!3.e(1) == a);
122 }
123 
124 import std.traits : isInstanceOf;
125 
126 auto transpose(M)(in M a) pure if (isInstanceOf!(BSM, M))
127 {
128     import std.traits : TemplateArgsOf;
129 
130     BSM!(TemplateArgsOf!M) ta;
131     foreach (i, row; a)
132     {
133         foreach (j, e; row)
134         {
135             ta[j][i] = e;
136         }
137     }
138     return ta;
139 }
140 
141 unittest
142 {
143     immutable a = BSM!3([[false, true, false], [false, true, true],
144         [true, false, false]]);
145     immutable b = BSM!3([[false, false, true], [true, true, false],
146         [false, true, false]]);
147 
148     assert(transpose(a) == b);
149 }
150 
151 auto isBijective(M)(in M a) pure if (isInstanceOf!(BSM, M))
152 {
153     foreach (i, ref row; a)
154     {
155         size_t k;
156 
157         foreach (j, e; row)
158         {
159             if (e)
160             {
161                 if (++k == 2)
162                 {
163                     return false;
164                 }
165                 else
166                 {
167                     foreach (ref row2; a[i + 1 .. $])
168                     {
169                         if (row2[j])
170                         {
171                             return false;
172                         }
173                     }
174                 }
175             }
176         }
177 
178         if (k == 0)
179         {
180             return false;
181         }
182     }
183 
184     return true;
185 }
186 
187 unittest
188 {
189     immutable a = BSM!3([[true, false, false], [false, false, true],
190         [false, true, false]]);
191     immutable b = BSM!3([[false, false, true], [false, false, true],
192         [true, true, false]]);
193     immutable c = BSM!3([[true, false, true], [false, true, false],
194         [false, false, false]]);
195     immutable d = BSM!3([[false, false, false], [false, true, false],
196         [false, false, false]]);
197 
198     assert(isBijective(a));
199     assert(!isBijective(b));
200     assert(!isBijective(c));
201     assert(!isBijective(d));
202 }
203 
204 auto isIrreflexive(M)(in M a) pure if (isInstanceOf!(BSM, M))
205 {
206     foreach (i, ref row; a)
207     {
208         if (row[i])
209         {
210             return false;
211         }
212     }
213 
214     return true;
215 }
216 
217 unittest
218 {
219     immutable a = BSM!3([[false, false, true], [false, false, true],
220         [true, true, false]]);
221     immutable b = BSM!3([[true, false, true], [false, false, true],
222         [true, false, false]]);
223 
224     assert(isIrreflexive(a));
225     assert(!isIrreflexive(b));
226 }
227 
228 auto isSymmetric(M)(in M a) pure if (isInstanceOf!(BSM, M))
229 {
230     foreach (i, ref row; a[0 .. $ - 1])
231     {
232         foreach (j, e; row[i + 1 .. $])
233         {
234             if (a[i + j + 1][i] != e)
235             {
236                 return false;
237             }
238         }
239     }
240 
241     return true;
242 }
243 
244 unittest
245 {
246     immutable a = BSM!3([[true, false, true], [false, false, true],
247         [true, true, false]]);
248     immutable b = BSM!3([[true, false, true], [false, false, true],
249         [true, false, false]]);
250 
251     assert(isSymmetric(a));
252     assert(!isSymmetric(b));
253 }
254 
255 auto cyclicPermutation(size_t n)(size_t shift) @property pure
256 {
257     BSM!n r;
258     if (shift % n == 0)
259     {
260         r = BSM!n.I;
261     }
262     else
263     {
264         foreach (i, ref e; r)
265         {
266             e[(i + (shift % n)) % n] = true;
267         }
268     }
269     return r;
270 }
271 
272 unittest
273 {
274     immutable a = BSM!3([[true, false, false], [false, true, false],
275         [false, false, true]]);
276     immutable b = BSM!3([[false, true, false], [false, false, true],
277         [true, false, false]]);
278 
279     assert(cyclicPermutation!3(0) == a);
280     assert(cyclicPermutation!3(21) == a);
281     assert(cyclicPermutation!3(1) == b);
282     assert(cyclicPermutation!3(22) == b);
283 }
284 
285 auto cyclicPermutationInv(size_t n)(size_t shift) @property pure
286 {
287     BSM!n r;
288     if (shift % n == 0)
289     {
290         r = BSM!n.I;
291     }
292     else
293     {
294         foreach (i, ref e; r)
295         {
296             e[(i + n - (shift % n)) % n] = true;
297         }
298     }
299     return r;
300 }
301 
302 unittest
303 {
304     immutable a = BSM!3([[true, false, false], [false, true, false],
305         [false, false, true]]);
306     immutable b = BSM!3([[false, false, true], [true, false, false],
307         [false, true, false]]);
308 
309     assert(cyclicPermutationInv!3(0) == a);
310     assert(cyclicPermutationInv!3(21) == a);
311     assert(cyclicPermutationInv!3(1) == b);
312     assert(cyclicPermutationInv!3(22) == b);
313 }
314 
315 auto permutation(size_t N)(in size_t[] substitution)
316 in
317 {
318     import std.algorithm.comparison : isPermutation;
319     import std.range : iota;
320 
321     assert(N.iota.isPermutation(substitution));
322 }
323 body
324 {
325     BSM!N p;
326     foreach (i, s; substitution)
327     {
328         p[s][i] = true;
329     }
330     return p;
331 }
332 
333 unittest
334 {
335     immutable a = BSM!3([[true, false, false], [false, true, false],
336         [false, false, true]]);
337     immutable b = BSM!3([[false, true, false], [false, false, true],
338         [true, false, false]]);
339     immutable c = BSM!3([[false, false, true], [false, true, false],
340         [true, false, false]]);
341 
342     assert(permutation!3([0, 1, 2]) == a);
343     assert(permutation!3([2, 0, 1]) == b);
344     assert(permutation!3([2, 1, 0]) == c);
345 }