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 opMul()(in auto ref BSM!n matrix) const pure
16     {
17         import std.range : iota, transversal, zip;
18         import std.algorithm.searching : canFind;
19         import std.algorithm.mutation : copy;
20         import std.algorithm.iteration : map;
21 
22         BSM!n r;
23         foreach (i, ref row; r)
24         {
25             n.iota.map!(j => zip(s_mat[i][], matrix[].transversal(j))
26                 .canFind!"a[0]&&a[1]").copy(row[]);
27         }
28 
29         return r;
30     }
31 
32     auto opMul()(in auto ref BCV!n vector) const pure
33     {
34         import std.range : zip;
35         import std.algorithm.searching : canFind;
36         import std.algorithm.mutation : copy;
37         import std.algorithm.iteration : map;
38 
39         BCV!n r;
40         s_mat[].map!(row => zip(row[], vector[]).canFind!"a[0]&&a[1]")
41             .copy(r[]);
42 
43         return r;
44     }
45 }
46 
47 // boolean column vector
48 struct BCV(size_t n) if (n > 0)
49 {
50     bool[n] c_vec;
51     alias c_vec this;
52 }
53 
54 unittest
55 {
56     immutable a = BSM!3([[true, false, true], [true, true, false],
57         [false, false, true]]);
58     immutable b = BSM!3([[false, true, true], [true, false, false],
59         [false, false, true]]);
60     immutable c = BSM!3([[false, true, true], [true, true, true],
61         [false, false, true]]);
62 
63     assert(a * b == c);
64 }
65 
66 unittest
67 {
68     immutable a = BSM!3([[true, false, true], [true, true, false],
69         [false, false, true]]);
70     immutable b = BCV!3([true, false, false]);
71     immutable c = BCV!3([true, true, false]);
72 
73     assert(a * b == c);
74 }
75 
76 enum Identity(size_t n) = {
77     BSM!n id;
78     foreach (i; 0 .. n)
79     {
80         id[i][i] = true;
81     }
82     return id;
83 }();
84 
85 import std.traits : TemplateArgsOf, TemplateOf;
86 
87 auto transpose(M)(in M a) pure if (__traits(isSame, TemplateOf!M, BSM))
88 {
89     BSM!(TemplateArgsOf!M) ta;
90     foreach (i, row; a)
91     {
92         foreach (j, e; row)
93         {
94             ta[j][i] = e;
95         }
96     }
97     return ta;
98 }
99 
100 auto lowerRotator(size_t n)(size_t shift) @property pure
101 {
102     BSM!n r;
103     if (shift % n == 0)
104     {
105         r = Identity!n;
106     }
107     else
108     {
109         foreach (i, ref e; r)
110         {
111             e[(i + n - (shift % n)) % n] = true;
112         }
113     }
114     return r;
115 }
116 
117 auto upperRotator(size_t n)(size_t shift) @property pure
118 {
119     BSM!n r;
120     if (shift % n == 0)
121     {
122         r = Identity!n;
123     }
124     else
125     {
126         foreach (i, ref e; r)
127         {
128             e[(i + (shift % n)) % n] = true;
129         }
130     }
131     return r;
132 }
133 
134 auto permutation(size_t N)(in size_t[] substitution)
135 in
136 {
137     import std.algorithm.comparison : isPermutation;
138     import std.range : iota;
139 
140     assert(N.iota.isPermutation(substitution));
141 }
142 body
143 {
144     BSM!N p;
145     foreach (i, s; substitution)
146     {
147         p[s][i] = true;
148     }
149     return p;
150 }