1 #ifndef booleanmatrix_h_AechohNgakoghahV
2 #define booleanmatrix_h_AechohNgakoghahV
14 #include "booleanvector.h"
20 std::ostream
& operator<<(std::ostream
&, const std::vector
<T
> &);
23 /** The base class of boolean_colmatrix and boolean_colrowmatrix which implements
24 * the common logic of both. */
25 template<class IT
, class D
>
26 class boolean_colmatrix_base
{
29 typedef IT index_type
;
30 typedef sorted_boolean_vector
<IT
> column_type
;
34 /** Create a matrix with 'width' columns, initalized with zero entries. */
35 boolean_colmatrix_base(size_t width
) :
40 /** A casting constructor for any colmatrix with same entries type. */
42 boolean_colmatrix_base(const boolean_colmatrix_base
<IT
, D2
> &mat
) :
43 cols(mat
.get_columns()) {
46 /** Get width of the matrix. */
47 size_t width() const {
51 /** Get height of the matrix, i.e. maximum row-index + 1 among all
53 size_t height() const {
55 for (unsigned c
=0; c
< width(); ++c
)
56 if (!cols
[c
].isempty())
57 h
= std::max(h
, cols
[c
].back());
61 /** Get the matrix entry at row 'r' and column 'c'. */
62 bool get(index_type r
, index_type c
) const {
64 return get_column(c
).get(r
);
67 /** Set the matrix entry at row 'r' and column 'c'. */
68 void set(index_type r
, index_type c
, bool value
) {
69 get_derived()->_set(r
, c
, value
);
72 /** For each of the 'count'-many (row-index, column-pair) pair in
73 * 'indices', set the specific value. */
74 void set_all(index_type indices
[][2], size_t count
, bool value
) {
75 for (unsigned i
=0; i
< count
; ++i
)
76 set(indices
[i
][0], indices
[i
][1], value
);
79 /** Get the c-th column. */
80 const column_type
& get_column(index_type c
) const {
85 /** Get all columns */
86 const std::vector
<column_type
>& get_columns() const {
90 /** Add the column-vector 'col' to the c-th column. Note that 'col'
91 * actually contains the list of row-indices that are 1. */
92 void add_column(index_type c
, const column_type
&col
) {
95 // Flip all entries that are set in 'col'.
96 for (typename
column_type::indexarray::const_iterator it
= col
.get_ones().begin();
97 it
!= col
.get_ones().end(); ++it
)
98 set(*it
, c
, !get(*it
, c
));
101 /** Two matrices are equal iff they have the same entries */
103 bool operator==(const boolean_colmatrix_base
<IT
, D2
> &m
) const {
104 return cols
== m
.get_columns();
107 /** Two matrices are equal iff they have the same entries */
109 bool operator!=(const boolean_colmatrix_base
<IT
, D2
> &m
) const {
110 return !(*this == m
);
113 /** Print index pairs of the 1s as { {r, c}, {r, c}, {r, c} } */
114 void print_indexpairs(std::ostream
&os
) const {
118 for (unsigned c
=0; c
< width(); ++c
) {
119 const column_type
&col
= get_column(c
);
120 const typename
column_type::indexarray
&ones
= col
.get_ones();
121 typename
column_type::indexarray::iterator it
= ones
.begin();
123 for (typename
column_type::indexarray::iterator it
= ones
.begin();
124 it
!= ones
.end(); ++it
) {
129 os
<< " {" << *it
<< ", " << c
<< "}";
136 /** Set the matrix entry at row 'r' and column 'c'. */
137 void _set(index_type r
, index_type c
, bool value
) {
139 cols
.at(c
).set(r
, value
);
143 /** The matrix is the set of columns. */
144 std::vector
<column_type
> cols
;
146 /** A cast to the derived type */
147 derived
* get_derived() {
148 return static_cast<derived
*>(this);
153 /** This is boolean matrix that is a std::vector of column-vectors and in each
154 * column-vector we save the row-indices of the 1s. It is designed to handle a
155 * few 1s and column-wise operations well. */
156 template<class IT
=uint32_t>
157 class boolean_colmatrix
: public boolean_colmatrix_base
<IT
, boolean_colmatrix
<IT
> > {
160 typedef IT index_type
;
161 typedef boolean_colmatrix_base
<IT
, boolean_colmatrix
<IT
> > base
;
162 typedef typename
base::column_type column_type
;
164 /** Create a matrix with 'width' columns, initalized with zero entries. */
165 boolean_colmatrix(size_t columns
) :
169 /** Set the matrix entry at row 'r' and column 'c'. */
170 void _set(index_type r
, index_type c
, bool value
) {
171 base::_set(r
, c
, value
);
174 /** A faster implementation of boolean_colmatrix_base::add_column(). */
175 void add_column(index_type c
, const column_type
&col
) {
176 assert(c
< base::width());
177 base::cols
[c
].add(col
);
184 /** The base class of boolean_rowmatrix and boolean_colrowmatrix which implements
185 * the common logic of both. */
186 template<class IT
, class D
>
187 class boolean_rowmatrix_base
{
190 typedef IT index_type
;
191 typedef sorted_boolean_vector
<IT
> row_type
;
195 /** Create a matrix with 'height' rows, initalized with zero entries.
197 boolean_rowmatrix_base(size_t height
) :
202 /** Get height of the matrix. */
203 size_t height() const {
207 /** Get the matrix entry at row 'r' and column 'c'. */
208 bool get(index_type r
, index_type c
) const {
209 assert(r
< height());
210 return get_row(r
).get(c
);
213 /** Set the matrix entry at row 'r' and column 'c'. */
214 void set(index_type r
, index_type c
, bool value
) {
215 get_derived()->_set(r
, c
, value
);
218 /** For each of the 'count'-many (row-index, column-pair) pair in
219 * 'indices', set the specific value. */
220 void set_all(index_type indices
[][2], size_t count
, bool value
) {
221 for (unsigned i
=0; i
< count
; ++i
)
222 set(indices
[i
][0], indices
[i
][1], value
);
225 /** Get the r-th row. */
226 const row_type
& get_row(index_type r
) const {
227 assert(r
< height());
231 /** Add the row-vector 'row' to the r-th row. Note that 'row'
232 * actually contains the list of column-indices that are 1. */
233 void add_row(index_type r
, const row_type
&row
) {
234 assert(r
< height());
236 // Flip all entries that are set in 'row'.
237 for (typename
row_type::indexarray::const_iterator it
= row
.get_ones().begin();
238 it
!= row
.get_ones().end(); ++it
)
239 set(r
, *it
, !get(r
, *it
));
242 /** Two matrices are equal iff they have the same entries */
243 bool operator==(const boolean_rowmatrix_base
<IT
, D
> &m
) const {
244 return rows
== m
.rows
;
247 /** Two matrices are equal iff they have the same entries */
248 bool operator!=(const boolean_rowmatrix_base
<IT
, D
> &m
) const {
249 return !(*this == m
);
253 /** Set the matrix entry at row 'r' and column 'c'. */
254 void _set(index_type r
, index_type c
, bool value
) {
255 assert(r
< height());
256 rows
.at(r
).set(c
, value
);
260 derived
* get_derived() {
261 return static_cast<derived
*>(this);
264 /** The matrix is the set of columns. */
265 std::vector
<row_type
> rows
;
269 /** This is boolean matrix that is a std::vector of row-vectors and in each
270 * row-vector we save the column-indices of the 1s. It is designed to handle a
271 * few 1s and row-wise operations well. */
272 template<class IT
=uint32_t>
273 class boolean_rowmatrix
: public boolean_rowmatrix_base
<IT
, boolean_rowmatrix
<IT
> > {
276 typedef IT index_type
;
277 typedef boolean_rowmatrix_base
<IT
, boolean_rowmatrix
<IT
> > base
;
279 /** Create a matrix with 'height' rows, initalized with zero entries. */
280 boolean_rowmatrix(size_t height
) :
284 /** Set the matrix entry at row 'r' and column 'c'. */
285 void _set(index_type r
, index_type c
, bool value
) {
286 base::_set(r
, c
, value
);
291 /** This is a boolean matrix that supports. It is designed to handle a
292 * few 1s and row- and column-wise operations well. */
293 template<class IT
=uint32_t>
294 class boolean_colrowmatrix
: public boolean_colmatrix_base
<IT
, boolean_colrowmatrix
<IT
> >,
295 public boolean_rowmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > {
298 typedef boolean_colmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > colbase
;
299 typedef boolean_rowmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > rowbase
;
302 typedef IT index_type
;
304 /** Create a size x size matrix, initialized with zeros. */
305 boolean_colrowmatrix(size_t size
) :
310 /** Casting a colmatrix into a colrow matrix */
312 boolean_colrowmatrix(const boolean_colmatrix_base
<IT
, D
>& mat
) :
313 colbase(std::max(mat
.width(), mat
.height())),
314 rowbase(std::max(mat
.width(), mat
.height())) {
315 for (unsigned c
=0; c
< mat
.width(); ++c
) {
316 const typename
colbase::column_type
&col
= mat
.get_column(c
);
317 for (unsigned i
=0; i
< col
.size(); ++i
)
318 set(col
.get_ones()[i
], c
, true);
320 for (unsigned r
=0; r
< size(); ++r
) {
321 const typename
rowbase::row_type
&row
= rowbase::get_row(r
);
322 for (unsigned i
=0; i
< row
.size(); ++i
)
323 assert(get(r
, row
.get_ones()[i
]) == true);
327 /** Override implementation. */
328 void _set(index_type r
, index_type c
, bool value
) {
329 colbase::_set(r
, c
, value
);
330 rowbase::_set(r
, c
, value
);
334 /** Get height resp. width of the matrix. */
335 size_t size() const {
336 assert(colbase::width() == rowbase::height());
337 return colbase::width();
340 /** Set the matrix entry at row 'r' and column 'c'. */
341 void set(index_type r
, index_type c
, bool value
) {
342 //Calling set() for one base suffices, static polymorphism
343 //calls _set() anyhow.
344 //rowbase::set(r, c, value);
345 colbase::set(r
, c
, value
);
348 /** For each of the 'count'-many (row-index, column-pair) pair in
349 * 'indices', set the specific value. */
350 void set_all(index_type indices
[][2], size_t count
, bool value
) {
351 colbase::set_all(indices
, count
, value
);
354 /** Get the matrix entry at row 'r' and column 'c'. */
355 bool get(index_type r
, index_type c
) const {
356 assert(colbase::get(r
, c
) == rowbase::get(r
, c
));
357 return colbase::get(r
, c
);
360 /** Two matrices are equal iff they have the same entries */
361 bool operator==(const boolean_colrowmatrix
<IT
> &m
) const {
362 assert(rowbase::operator==(m
) == colbase::operator==(m
));
363 return colbase::operator==(m
);
366 /** Two matrices are equal iff they have the same entries */
368 bool operator==(const boolean_colmatrix_base
<IT
, D
> &m
) const {
369 return colbase::operator==(m
);
372 /** Two matrices are equal iff they have the same entries */
373 bool operator!=(const boolean_colrowmatrix
<IT
> &m
) const {
374 return !(*this == m
);
377 /** Multiply with matrix b from the right */
379 boolean_colrowmatrix
<IT
> operator*(const boolean_colmatrix_base
<IT
, D
> &b
) const {
380 boolean_colrowmatrix
<IT
> c(size());
381 multiply_matrix(c
, *this, b
);
387 /** Counts the number of common elements in two sorted vectors. Equal to
388 * counting the number of elements given by std::set_intersection. */
389 template <class InputIterator1
, class InputIterator2
>
390 size_t count_set_intersection(InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
)
394 // As long as we did not either end, look for common elements
395 while (first1
!= last1
&& first2
!= last2
)
397 if (*first1
< *first2
)
399 else if (*first2
< *first1
)
401 // Element is common to both
411 /** Multiply a*b and save the product in 'result'. It is assumed that 'result'
412 * is intially empty and has appropriate size. */
413 template<class IT
, class D1
, class D2
, class RT
>
414 void multiply_matrix(RT
&result
, const boolean_rowmatrix_base
<IT
, D1
> &a
, const boolean_colmatrix_base
<IT
, D2
> &b
) {
415 assert(a
.height() == b
.width());
417 for (unsigned r
=0; r
< a
.height(); ++r
) {
418 const typename boolean_rowmatrix_base
<IT
, D1
>::row_type
&row
= a
.get_row(r
);
419 for (unsigned c
=0; c
< b
.width(); ++c
) {
420 const typename boolean_colmatrix_base
<IT
, D2
>::column_type
&col
= b
.get_column(c
);
421 if (count_set_intersection(
422 row
.get_ones().begin(), row
.get_ones().end(),
423 col
.get_ones().begin(), col
.get_ones().end()) % 2 == 1)
424 result
.set(r
, c
, true);
430 MT
create_unit_matrix(size_t size
) {
432 for (unsigned i
=0; i
< size
; ++i
)
438 std::ostream
& operator<<(std::ostream
&os
, const boolean_colrowmatrix
<IT
> &mat
) {
441 for (unsigned c
=0; c
< mat
.size(); ++c
) {
442 const unsigned d
= (c
% 10);
450 for (unsigned r
=0; r
< mat
.size(); ++r
) {
451 const unsigned d
= (r
% 10);
457 for (unsigned c
=0; c
< mat
.size(); ++c
)
458 os
<< (mat
.get(r
,c
) ? "X" : ".");
460 if (r
< mat
.size() - 1)
467 std::ostream
& operator<<(std::ostream
&os
, boolean_colrowmatrix
<IT
> &mat
) {
468 const boolean_colrowmatrix
<IT
> &m
= mat
;
472 template<class IT
, class D
>
473 std::ostream
& operator<<(std::ostream
&os
, const boolean_rowmatrix_base
<IT
, D
> &mat
) {
474 for (unsigned r
=0; r
< mat
.height(); ++r
) {
475 // Get the sorted r-th row
476 std::list
<IT
> row(mat
.get_row(r
).size());
477 copy(mat
.get_row(r
).begin(), mat
.get_row(r
).end(), row
.begin());
480 // Print the elements, and remove them
481 for (unsigned c
=0; row
.size() > 0; ++c
) {
482 if (row
.front() == c
) {
489 if (r
< mat
.height() - 1)
495 template<class IT
, class D
>
496 std::ostream
& operator<<(std::ostream
&os
, boolean_rowmatrix_base
<IT
, D
> &mat
) {
497 const boolean_rowmatrix_base
<IT
, D
> &m
= mat
;
501 template<class IT
, class D
>
502 std::ostream
& operator<<(std::ostream
&os
, const boolean_colmatrix_base
<IT
, D
> &mat
) {
503 // The sorted columns
504 std::vector
<std::list
<IT
> > cols
;
505 // The max height (max. value) of all columns
508 for (unsigned c
=0; c
< mat
.width(); ++c
) {
509 // Get the sorted c-th column
510 std::list
<IT
> col(mat
.get_column(c
).size());
511 copy(mat
.get_column(c
).begin(), mat
.get_column(c
).end(), col
.begin());
517 height
= std::max(height
, col
.back());
522 for (unsigned r
=0; r
<= height
; ++r
) {
523 // Print the elements, and remove them
524 for (unsigned c
=0; c
< mat
.width(); ++c
) {
525 std::list
<IT
> &col
= cols
.at(c
);
526 // This column is already empty
529 else if (col
.front() == r
) {
541 template<class IT
, class D
>
542 std::ostream
& operator<<(std::ostream
&os
, boolean_colmatrix_base
<IT
, D
> &mat
) {
543 const boolean_colmatrix_base
<IT
, D
> &m
= mat
;
548 std::ostream
& operator<<(std::ostream
& os
, const std::vector
<T
> &vec
) {
551 typename
std::vector
<T
>::const_iterator it
= vec
.begin();
552 while ( it
!= vec
.end()) {
554 if (++it
!= vec
.end())