1 #ifndef booleanmatrix_h_AechohNgakoghahV
2 #define booleanmatrix_h_AechohNgakoghahV
18 /** The base class of BooleanColMatrix and BooleanColRowMatrix which implements
19 * the common logic of both. */
20 template<class IT
, class D
>
21 class BooleanColMatrix_base
{
24 typedef IT index_type
;
25 typedef std::vector
<index_type
> column_type
;
28 /** Create a matrix with 'width' columns, initalized with zero entries. */
29 BooleanColMatrix_base(size_t width
) :
33 /** Get height resp. width of the matrix. */
34 size_t width() const {
38 /** Get the matrix entry at row 'r' and column 'c'. */
39 bool get(index_type r
, index_type c
) const {
41 const column_type
&col
= getColumn(c
);
42 return binary_search(col
.begin(), col
.end(), r
);
45 /** Set the matrix entry at row 'r' and column 'c'. */
46 void set(index_type r
, index_type c
, bool value
) {
47 getDerived()->_set(r
, c
, value
);
50 /** Get the c-th column. */
51 const column_type
& getColumn(index_type c
) const {
56 /** Add the column-vector 'col' to the c-th column. Note that 'col'
57 * actually contains the list of row-indices that are 1. */
58 void addColumn(index_type c
, const column_type
&col
) {
61 // Flip all entries that are set in 'col'.
62 for (typename
column_type::const_iterator it
= col
.begin(); it
!= col
.end(); ++it
)
63 set(*it
, c
, !get(*it
, c
));
66 /** Two matrices are equal iff they have the same entries */
67 bool operator==(const BooleanColMatrix_base
<IT
, D
> &m
) const {
68 return cols
== m
.cols
;
71 /** Two matrices are equal iff they have the same entries */
72 bool operator!=(const BooleanColMatrix_base
<IT
, D
> &m
) const {
79 /** Set the matrix entry at row 'r' and column 'c'. */
80 void _set(index_type r
, index_type c
, bool value
) {
83 column_type
&col
= cols
.at(c
);
84 // Let us see where to insert the new element
85 typename
column_type::iterator it
= lower_bound(col
.begin(), col
.end(), r
);
86 bool exists
= (it
!= col
.end() && *it
== r
);
87 assert(get(r
,c
) == exists
);
89 // Add 'r' to c-th column
91 // r is new, insert it
104 // C++11 would have is_sorted
105 for (unsigned i
=1; i
< col
.size(); i
++)
106 assert(col
[i
-1] < col
[i
]);
111 /** The matrix is the set of columns. */
112 std::vector
<column_type
> cols
;
114 /** A cast to the derived type */
115 derived
* getDerived() {
116 return static_cast<derived
*>(this);
121 /** This is boolean matrix that is a std::vector of column-vectors and in each
122 * column-vector we save the row-indices of the 1s. It is designed to handle a
123 * few 1s and column-wise operations well. */
124 template<class IT
=uint32_t>
125 class BooleanColMatrix
: public BooleanColMatrix_base
<IT
, BooleanColMatrix
<IT
> > {
128 typedef IT index_type
;
129 typedef BooleanColMatrix_base
<IT
, BooleanColMatrix
<IT
> > base
;
131 /** Create a matrix with 'width' columns, initalized with zero entries. */
132 BooleanColMatrix(size_t columns
) :
136 /** Set the matrix entry at row 'r' and column 'c'. */
137 void _set(index_type r
, index_type c
, bool value
) {
138 base::_set(r
, c
, value
);
143 /** The base class of BooleanRowMatrix and BooleanColRowMatrix which implements
144 * the common logic of both. */
145 template<class IT
, class D
>
146 class BooleanRowMatrix_base
{
149 typedef IT index_type
;
150 typedef std::vector
<index_type
> row_type
;
153 /** Create a matrix with 'height' rows, initalized with zero entries.
155 BooleanRowMatrix_base(size_t height
) :
159 /** Get height resp. width of the matrix. */
160 size_t height() const {
164 /** Get the matrix entry at row 'r' and column 'c'. */
165 bool get(index_type r
, index_type c
) const {
166 assert(r
< height());
167 const row_type
&row
= getRow(r
);
168 return binary_search(row
.begin(), row
.end(), c
);
171 /** Set the matrix entry at row 'r' and column 'c'. */
172 void set(index_type r
, index_type c
, bool value
) {
173 getDerived()->_set(r
, c
, value
);
176 /** Get the r-th row. */
177 const row_type
& getRow(index_type r
) const {
178 assert(r
< height());
182 /** Add the row-vector 'row' to the r-th row. Note that 'row'
183 * actually contains the list of column-indices that are 1. */
184 void addRow(index_type r
, const row_type
&row
) {
185 assert(r
< height());
187 // Flip all entries that are set in 'row'.
188 for (typename
row_type::const_iterator it
= row
.begin(); it
!= row
.end(); ++it
)
189 set(r
, *it
, !get(r
, *it
));
192 /** Two matrices are equal iff they have the same entries */
193 bool operator==(const BooleanRowMatrix_base
<IT
, D
> &m
) const {
194 return rows
== m
.rows
;
197 /** Two matrices are equal iff they have the same entries */
198 bool operator!=(const BooleanRowMatrix_base
<IT
, D
> &m
) const {
199 return !(*this == m
);
203 /** Set the matrix entry at row 'r' and column 'c'. */
204 void _set(index_type r
, index_type c
, bool value
) {
205 assert(r
< height());
207 row_type
&row
= rows
.at(r
);
208 // Let us see where to insert/remove the new element
209 typename
row_type::iterator it
= lower_bound(row
.begin(), row
.end(), c
);
210 bool exists
= (it
!= row
.end() && *it
== c
);
211 assert(get(r
,c
) == exists
);
213 // Add 'r' to c-th column
215 // r is new, insert it
220 // Remove the element
228 // C++11 would have is_sorted
229 for (unsigned i
=1; i
< row
.size(); i
++)
230 assert(row
[i
-1] < row
[i
]);
235 derived
* getDerived() {
236 return static_cast<derived
*>(this);
239 /** The matrix is the set of columns. */
240 std::vector
<row_type
> rows
;
244 /** This is boolean matrix that is a std::vector of row-vectors and in each
245 * row-vector we save the column-indices of the 1s. It is designed to handle a
246 * few 1s and row-wise operations well. */
247 template<class IT
=uint32_t>
248 class BooleanRowMatrix
: public BooleanRowMatrix_base
<IT
, BooleanRowMatrix
<IT
> > {
251 typedef IT index_type
;
252 typedef BooleanRowMatrix_base
<IT
, BooleanRowMatrix
<IT
> > base
;
254 /** Create a matrix with 'height' rows, initalized with zero entries. */
255 BooleanRowMatrix(size_t height
) :
259 /** Set the matrix entry at row 'r' and column 'c'. */
260 void _set(index_type r
, index_type c
, bool value
) {
261 base::_set(r
, c
, value
);
266 /** This is a boolean matrix that supports. It is designed to handle a
267 * few 1s and row- and column-wise operations well. */
268 template<class IT
=uint32_t>
269 class BooleanColRowMatrix
: public BooleanColMatrix_base
<IT
, BooleanColRowMatrix
<IT
> >,
270 public BooleanRowMatrix_base
<IT
, BooleanColRowMatrix
<IT
> > {
273 typedef BooleanColMatrix_base
<IT
, BooleanColRowMatrix
<IT
> > colbase
;
274 typedef BooleanRowMatrix_base
<IT
, BooleanColRowMatrix
<IT
> > rowbase
;
277 typedef IT index_type
;
279 /** Create a size x size matrix, initialized with zeros. */
280 BooleanColRowMatrix(size_t size
) :
285 /** Override implementation. */
286 void _set(index_type r
, index_type c
, bool value
) {
287 colbase::_set(r
, c
, value
);
288 rowbase::_set(r
, c
, value
);
292 /** Get height resp. width of the matrix. */
293 size_t size() const {
294 assert(colbase::width() == rowbase::height());
295 return colbase::width();
298 /** Set the matrix entry at row 'r' and column 'c'. */
299 void set(index_type r
, index_type c
, bool value
) {
300 //Calling set() for one base suffices, static polymorphism
301 //calls _set() anyhow.
302 //rowbase::set(r, c, value);
303 colbase::set(r
, c
, value
);
306 /** Get the matrix entry at row 'r' and column 'c'. */
307 bool get(index_type r
, index_type c
) const {
308 assert(colbase::get(r
, c
) == rowbase::get(r
, c
));
309 return colbase::get(r
, c
);
312 /** Two matrices are equal iff they have the same entries */
313 bool operator==(const BooleanColRowMatrix
<IT
> &m
) const {
314 assert(rowbase::operator==(m
) == colbase::operator==(m
));
315 return colbase::operator==(m
);
318 /** Two matrices are equal iff they have the same entries */
319 bool operator!=(const BooleanColRowMatrix
<IT
> &m
) const {
320 return !(*this == m
);
323 /** Multiply with matrix b from the right */
325 BooleanColRowMatrix
<IT
> operator*(const BooleanColMatrix_base
<IT
, D
> &b
) {
326 BooleanColRowMatrix
<IT
> c(size());
327 multiply_matrix(c
, *this, b
);
333 /** Counts the number of common elements in two sorted vectors. Equal to
334 * counting the number of elements given by std::set_intersection. */
335 template <class InputIterator1
, class InputIterator2
>
336 size_t count_set_intersection (InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
)
340 // As long as we did not either end, look for common elements
341 while (first1
!=last1
&& first2
!=last2
)
343 if (*first1
< *first2
)
345 else if (*first2
< *first1
)
347 // Element is common to both
357 /** Multiply a*b and save the product in 'result'. It is assumed that 'result' is intially empty and has appropriate size. */
358 template<class IT
, class D
, class RT
>
359 void multiply_matrix(RT
&result
, const BooleanRowMatrix_base
<IT
, D
> &a
, const BooleanColMatrix_base
<IT
, D
> &b
) {
360 assert(a
.height() == b
.width());
362 for (unsigned r
=0; r
< a
.height(); ++r
) {
363 const typename BooleanRowMatrix_base
<IT
, D
>::row_type
&row
= a
.getRow(r
);
364 for (unsigned c
=0; c
< b
.width(); ++c
) {
365 const typename BooleanColMatrix_base
<IT
, D
>::column_type
&col
= b
.getColumn(c
);
366 if (count_set_intersection(row
.begin(), row
.end(), col
.begin(), col
.end()) % 2 == 1)
367 result
.set(r
, c
, true);
373 MT
unitMatrix(size_t size
) {
375 for (unsigned i
=0; i
< size
; ++i
)
381 std::ostream
& operator<<(std::ostream
&os
, const BooleanColRowMatrix
<IT
> &mat
) {
382 for (unsigned r
=0; r
< mat
.size(); ++r
) {
383 for (unsigned c
=0; c
< mat
.size(); ++c
)
384 os
<< (mat
.get(r
,c
) ? "X" : ".");
386 if (r
< mat
.size() - 1)
393 std::ostream
& operator<<(std::ostream
&os
, BooleanColRowMatrix
<IT
> &mat
) {
394 const BooleanColRowMatrix
<IT
> &m
= mat
;
398 template<class IT
, class D
>
399 std::ostream
& operator<<(std::ostream
&os
, const BooleanRowMatrix_base
<IT
, D
> &mat
) {
400 for (unsigned r
=0; r
< mat
.height(); ++r
) {
401 // Get the sorted r-th row
402 std::list
<IT
> row(mat
.getRow(r
).size());
403 copy(mat
.getRow(r
).begin(), mat
.getRow(r
).end(), row
.begin());
406 // Print the elements, and remove them
407 for (unsigned c
=0; row
.size() > 0; ++c
) {
408 if (row
.front() == c
) {
415 if (r
< mat
.height() - 1)
421 template<class IT
, class D
>
422 std::ostream
& operator<<(std::ostream
&os
, BooleanRowMatrix_base
<IT
, D
> &mat
) {
423 const BooleanRowMatrix_base
<IT
, D
> &m
= mat
;
427 template<class IT
, class D
>
428 std::ostream
& operator<<(std::ostream
&os
, const BooleanColMatrix_base
<IT
, D
> &mat
) {
429 // The sorted columns
430 std::vector
<std::list
<IT
> > cols
;
431 // The max height (max. value) of all columns
434 for (unsigned c
=0; c
< mat
.width(); ++c
) {
435 // Get the sorted c-th column
436 std::list
<IT
> col(mat
.getColumn(c
).size());
437 copy(mat
.getColumn(c
).begin(), mat
.getColumn(c
).end(), col
.begin());
443 height
= std::max(height
, col
.back());
448 for (unsigned r
=0; r
<= height
; ++r
) {
449 // Print the elements, and remove them
450 for (unsigned c
=0; c
< mat
.width(); ++c
) {
451 std::list
<IT
> &col
= cols
.at(c
);
452 // This column is already empty
455 else if (col
.front() == r
) {
467 template<class IT
, class D
>
468 std::ostream
& operator<<(std::ostream
&os
, BooleanColMatrix_base
<IT
, D
> &mat
) {
469 const BooleanColMatrix_base
<IT
, D
> &m
= mat
;