1 #ifndef booleanmatrix_h_AechohNgakoghahV
2 #define booleanmatrix_h_AechohNgakoghahV
19 std::ostream
& operator<<(std::ostream
&, const std::vector
<T
> &);
22 /** The base class of boolean_colmatrix and boolean_colrowmatrix which implements
23 * the common logic of both. */
24 template<class IT
, class D
>
25 class boolean_colmatrix_base
{
28 typedef IT index_type
;
29 typedef std::vector
<index_type
> column_type
;
33 /** Create a matrix with 'width' columns, initalized with zero entries. */
34 boolean_colmatrix_base(size_t width
) :
39 /** A casting constructor for any colmatrix with same entries type. */
41 boolean_colmatrix_base(const boolean_colmatrix_base
<IT
, D2
> &mat
) :
42 cols(mat
.get_columns()) {
45 /** Get width of the matrix. */
46 size_t width() const {
50 /** Get height of the matrix, i.e. maximum row-index + 1 among all columns. */
51 size_t height() const {
53 for (unsigned c
=0; c
< width(); ++c
)
54 if (cols
[c
].size() > 0)
55 h
= std::max(h
, cols
[c
].back());
59 /** Get the matrix entry at row 'r' and column 'c'. */
60 bool get(index_type r
, index_type c
) const {
62 const column_type
&col
= get_column(c
);
63 return binary_search(col
.begin(), col
.end(), r
);
66 /** Set the matrix entry at row 'r' and column 'c'. */
67 void set(index_type r
, index_type c
, bool value
) {
68 get_derived()->_set(r
, c
, value
);
71 /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific value. */
72 void set_all(index_type indices
[][2], size_t count
, bool value
) {
73 for (unsigned i
=0; i
< count
; ++i
)
74 set(indices
[i
][0], indices
[i
][1], value
);
77 /** Get the c-th column. */
78 const column_type
& get_column(index_type c
) const {
83 /** Get all columns */
84 const std::vector
<column_type
>& get_columns() const {
88 /** Add the column-vector 'col' to the c-th column. Note that 'col'
89 * actually contains the list of row-indices that are 1. */
90 void add_column(index_type c
, const column_type
&col
) {
93 // Flip all entries that are set in 'col'.
94 for (typename
column_type::const_iterator it
= col
.begin(); it
!= col
.end(); ++it
)
95 set(*it
, c
, !get(*it
, c
));
98 /** Two matrices are equal iff they have the same entries */
100 bool operator==(const boolean_colmatrix_base
<IT
, D2
> &m
) const {
101 return cols
== m
.get_columns();
104 /** Two matrices are equal iff they have the same entries */
106 bool operator!=(const boolean_colmatrix_base
<IT
, D2
> &m
) const {
107 return !(*this == m
);
110 /** Print index pairs of the 1s as { {r, c}, {r, c}, {r, c} } */
111 void print_indexpairs(std::ostream
&os
) const {
115 for (unsigned c
=0; c
< width(); ++c
) {
116 const column_type
&col
= get_column(c
);
117 for (typename
column_type::const_iterator it
= col
.begin(); it
!= col
.end(); ++it
) {
122 os
<< " {" << *it
<< ", " << c
<< "}";
129 /** Set the matrix entry at row 'r' and column 'c'. */
130 void _set(index_type r
, index_type c
, bool value
) {
133 column_type
&col
= cols
.at(c
);
134 // Let us see where to insert the new element
135 typename
column_type::iterator it
= lower_bound(col
.begin(), col
.end(), r
);
136 bool exists
= (it
!= col
.end() && *it
== r
);
137 assert(get(r
,c
) == exists
);
139 // Add 'r' to c-th column
141 // r is new, insert it
146 // Remove the element
154 // C++11 would have is_sorted
155 for (unsigned i
=1; i
< col
.size(); i
++)
156 assert(col
[i
-1] < col
[i
]);
161 /** The matrix is the set of columns. */
162 std::vector
<column_type
> cols
;
164 /** A cast to the derived type */
165 derived
* get_derived() {
166 return static_cast<derived
*>(this);
171 /** This is boolean matrix that is a std::vector of column-vectors and in each
172 * column-vector we save the row-indices of the 1s. It is designed to handle a
173 * few 1s and column-wise operations well. */
174 template<class IT
=uint32_t>
175 class boolean_colmatrix
: public boolean_colmatrix_base
<IT
, boolean_colmatrix
<IT
> > {
178 typedef IT index_type
;
179 typedef boolean_colmatrix_base
<IT
, boolean_colmatrix
<IT
> > base
;
180 typedef typename
base::column_type column_type
;
182 /** Create a matrix with 'width' columns, initalized with zero entries. */
183 boolean_colmatrix(size_t columns
) :
187 /** Set the matrix entry at row 'r' and column 'c'. */
188 void _set(index_type r
, index_type c
, bool value
) {
189 base::_set(r
, c
, value
);
192 /** A faster implementation of boolean_colmatrix_base::add_column().
193 * Assumes that 'col' is sorted. */
194 void add_column(index_type c
, const column_type
&col
) {
195 assert(c
< base::width());
198 for (unsigned i
=1; i
< col
.size(); ++i
)
199 assert(col
[i
-1] < col
[i
]);
202 // The original column
203 column_type
&orig_col
= base::cols
[c
];
205 // Make target column large enough
206 const size_t maxsize
= orig_col
.size() + col
.size();
207 if (tcol
.size() < maxsize
)
208 tcol
.resize(maxsize
);
210 // Compute symmetric difference
211 typename
column_type::iterator it
= std::set_symmetric_difference(
212 orig_col
.begin(), orig_col
.end(), col
.begin(), col
.end(), tcol
.begin());
214 // Copy back to the original column
215 orig_col
.resize(it
- tcol
.begin());
216 std::copy(tcol
.begin(), it
, orig_col
.begin());
220 /** A temporary container to speed up add_column() */
225 /** The base class of boolean_rowmatrix and boolean_colrowmatrix which implements
226 * the common logic of both. */
227 template<class IT
, class D
>
228 class boolean_rowmatrix_base
{
231 typedef IT index_type
;
232 typedef std::vector
<index_type
> row_type
;
236 /** Create a matrix with 'height' rows, initalized with zero entries.
238 boolean_rowmatrix_base(size_t height
) :
243 /** Get height of the matrix. */
244 size_t height() const {
248 /** Get the matrix entry at row 'r' and column 'c'. */
249 bool get(index_type r
, index_type c
) const {
250 assert(r
< height());
251 const row_type
&row
= get_row(r
);
252 return binary_search(row
.begin(), row
.end(), c
);
255 /** Set the matrix entry at row 'r' and column 'c'. */
256 void set(index_type r
, index_type c
, bool value
) {
257 get_derived()->_set(r
, c
, value
);
260 /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific value. */
261 void set_all(index_type indices
[][2], size_t count
, bool value
) {
262 for (unsigned i
=0; i
< count
; ++i
)
263 set(indices
[i
][0], indices
[i
][1], value
);
266 /** Get the r-th row. */
267 const row_type
& get_row(index_type r
) const {
268 assert(r
< height());
272 /** Add the row-vector 'row' to the r-th row. Note that 'row'
273 * actually contains the list of column-indices that are 1. */
274 void add_row(index_type r
, const row_type
&row
) {
275 assert(r
< height());
277 // Flip all entries that are set in 'row'.
278 for (typename
row_type::const_iterator it
= row
.begin(); it
!= row
.end(); ++it
)
279 set(r
, *it
, !get(r
, *it
));
282 /** Two matrices are equal iff they have the same entries */
283 bool operator==(const boolean_rowmatrix_base
<IT
, D
> &m
) const {
284 return rows
== m
.rows
;
287 /** Two matrices are equal iff they have the same entries */
288 bool operator!=(const boolean_rowmatrix_base
<IT
, D
> &m
) const {
289 return !(*this == m
);
293 /** Set the matrix entry at row 'r' and column 'c'. */
294 void _set(index_type r
, index_type c
, bool value
) {
295 assert(r
< height());
297 row_type
&row
= rows
.at(r
);
298 // Let us see where to insert/remove the new element
299 typename
row_type::iterator it
= lower_bound(row
.begin(), row
.end(), c
);
300 bool exists
= (it
!= row
.end() && *it
== c
);
301 assert(get(r
,c
) == exists
);
303 // Add 'r' to c-th column
305 // r is new, insert it
310 // Remove the element
318 // C++11 would have is_sorted
319 for (unsigned i
=1; i
< row
.size(); i
++)
320 assert(row
[i
-1] < row
[i
]);
325 derived
* get_derived() {
326 return static_cast<derived
*>(this);
329 /** The matrix is the set of columns. */
330 std::vector
<row_type
> rows
;
334 /** This is boolean matrix that is a std::vector of row-vectors and in each
335 * row-vector we save the column-indices of the 1s. It is designed to handle a
336 * few 1s and row-wise operations well. */
337 template<class IT
=uint32_t>
338 class boolean_rowmatrix
: public boolean_rowmatrix_base
<IT
, boolean_rowmatrix
<IT
> > {
341 typedef IT index_type
;
342 typedef boolean_rowmatrix_base
<IT
, boolean_rowmatrix
<IT
> > base
;
344 /** Create a matrix with 'height' rows, initalized with zero entries. */
345 boolean_rowmatrix(size_t height
) :
349 /** Set the matrix entry at row 'r' and column 'c'. */
350 void _set(index_type r
, index_type c
, bool value
) {
351 base::_set(r
, c
, value
);
356 /** This is a boolean matrix that supports. It is designed to handle a
357 * few 1s and row- and column-wise operations well. */
358 template<class IT
=uint32_t>
359 class boolean_colrowmatrix
: public boolean_colmatrix_base
<IT
, boolean_colrowmatrix
<IT
> >,
360 public boolean_rowmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > {
363 typedef boolean_colmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > colbase
;
364 typedef boolean_rowmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > rowbase
;
367 typedef IT index_type
;
369 /** Create a size x size matrix, initialized with zeros. */
370 boolean_colrowmatrix(size_t size
) :
375 /** Casting a colmatrix into a colrow matrix */
377 boolean_colrowmatrix(const boolean_colmatrix_base
<IT
, D
>& mat
) :
378 colbase(std::max(mat
.width(), mat
.height())),
379 rowbase(std::max(mat
.width(), mat
.height())) {
380 for (unsigned c
=0; c
< mat
.width(); ++c
) {
381 const typename
colbase::column_type
&col
= mat
.get_column(c
);
382 for (unsigned i
=0; i
< col
.size(); ++i
)
383 set(col
[i
], c
, true);
385 for (unsigned r
=0; r
< size(); ++r
) {
386 const typename
rowbase::row_type
&row
= rowbase::get_row(r
);
387 for (unsigned i
=0; i
< row
.size(); ++i
)
388 assert(get(r
, row
[i
]) == true);
392 /** Override implementation. */
393 void _set(index_type r
, index_type c
, bool value
) {
394 colbase::_set(r
, c
, value
);
395 rowbase::_set(r
, c
, value
);
399 /** Get height resp. width of the matrix. */
400 size_t size() const {
401 assert(colbase::width() == rowbase::height());
402 return colbase::width();
405 /** Set the matrix entry at row 'r' and column 'c'. */
406 void set(index_type r
, index_type c
, bool value
) {
407 //Calling set() for one base suffices, static polymorphism
408 //calls _set() anyhow.
409 //rowbase::set(r, c, value);
410 colbase::set(r
, c
, value
);
413 /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific value. */
414 void set_all(index_type indices
[][2], size_t count
, bool value
) {
415 colbase::set_all(indices
, count
, value
);
418 /** Get the matrix entry at row 'r' and column 'c'. */
419 bool get(index_type r
, index_type c
) const {
420 assert(colbase::get(r
, c
) == rowbase::get(r
, c
));
421 return colbase::get(r
, c
);
424 /** Two matrices are equal iff they have the same entries */
425 bool operator==(const boolean_colrowmatrix
<IT
> &m
) const {
426 assert(rowbase::operator==(m
) == colbase::operator==(m
));
427 return colbase::operator==(m
);
430 /** Two matrices are equal iff they have the same entries */
432 bool operator==(const boolean_colmatrix_base
<IT
, D
> &m
) const {
433 return colbase::operator==(m
);
436 /** Two matrices are equal iff they have the same entries */
437 bool operator!=(const boolean_colrowmatrix
<IT
> &m
) const {
438 return !(*this == m
);
441 /** Multiply with matrix b from the right */
443 boolean_colrowmatrix
<IT
> operator*(const boolean_colmatrix_base
<IT
, D
> &b
) const {
444 boolean_colrowmatrix
<IT
> c(size());
445 multiply_matrix(c
, *this, b
);
451 /** Counts the number of common elements in two sorted vectors. Equal to
452 * counting the number of elements given by std::set_intersection. */
453 template <class InputIterator1
, class InputIterator2
>
454 size_t count_set_intersection (InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
)
458 // As long as we did not either end, look for common elements
459 while (first1
!= last1
&& first2
!= last2
)
461 if (*first1
< *first2
)
463 else if (*first2
< *first1
)
465 // Element is common to both
475 /** Multiply a*b and save the product in 'result'. It is assumed that 'result' is intially empty and has appropriate size. */
476 template<class IT
, class D1
, class D2
, class RT
>
477 void multiply_matrix(RT
&result
, const boolean_rowmatrix_base
<IT
, D1
> &a
, const boolean_colmatrix_base
<IT
, D2
> &b
) {
478 assert(a
.height() == b
.width());
480 for (unsigned r
=0; r
< a
.height(); ++r
) {
481 const typename boolean_rowmatrix_base
<IT
, D1
>::row_type
&row
= a
.get_row(r
);
482 for (unsigned c
=0; c
< b
.width(); ++c
) {
483 const typename boolean_colmatrix_base
<IT
, D2
>::column_type
&col
= b
.get_column(c
);
484 if (count_set_intersection(row
.begin(), row
.end(), col
.begin(), col
.end()) % 2 == 1)
485 result
.set(r
, c
, true);
491 MT
create_unit_matrix(size_t size
) {
493 for (unsigned i
=0; i
< size
; ++i
)
499 std::ostream
& operator<<(std::ostream
&os
, const boolean_colrowmatrix
<IT
> &mat
) {
502 for (unsigned c
=0; c
< mat
.size(); ++c
) {
503 const unsigned d
= (c
% 10);
511 for (unsigned r
=0; r
< mat
.size(); ++r
) {
512 const unsigned d
= (r
% 10);
518 for (unsigned c
=0; c
< mat
.size(); ++c
)
519 os
<< (mat
.get(r
,c
) ? "X" : ".");
521 if (r
< mat
.size() - 1)
528 std::ostream
& operator<<(std::ostream
&os
, boolean_colrowmatrix
<IT
> &mat
) {
529 const boolean_colrowmatrix
<IT
> &m
= mat
;
533 template<class IT
, class D
>
534 std::ostream
& operator<<(std::ostream
&os
, const boolean_rowmatrix_base
<IT
, D
> &mat
) {
535 for (unsigned r
=0; r
< mat
.height(); ++r
) {
536 // Get the sorted r-th row
537 std::list
<IT
> row(mat
.get_row(r
).size());
538 copy(mat
.get_row(r
).begin(), mat
.get_row(r
).end(), row
.begin());
541 // Print the elements, and remove them
542 for (unsigned c
=0; row
.size() > 0; ++c
) {
543 if (row
.front() == c
) {
550 if (r
< mat
.height() - 1)
556 template<class IT
, class D
>
557 std::ostream
& operator<<(std::ostream
&os
, boolean_rowmatrix_base
<IT
, D
> &mat
) {
558 const boolean_rowmatrix_base
<IT
, D
> &m
= mat
;
562 template<class IT
, class D
>
563 std::ostream
& operator<<(std::ostream
&os
, const boolean_colmatrix_base
<IT
, D
> &mat
) {
564 // The sorted columns
565 std::vector
<std::list
<IT
> > cols
;
566 // The max height (max. value) of all columns
569 for (unsigned c
=0; c
< mat
.width(); ++c
) {
570 // Get the sorted c-th column
571 std::list
<IT
> col(mat
.get_column(c
).size());
572 copy(mat
.get_column(c
).begin(), mat
.get_column(c
).end(), col
.begin());
578 height
= std::max(height
, col
.back());
583 for (unsigned r
=0; r
<= height
; ++r
) {
584 // Print the elements, and remove them
585 for (unsigned c
=0; c
< mat
.width(); ++c
) {
586 std::list
<IT
> &col
= cols
.at(c
);
587 // This column is already empty
590 else if (col
.front() == r
) {
602 template<class IT
, class D
>
603 std::ostream
& operator<<(std::ostream
&os
, boolean_colmatrix_base
<IT
, D
> &mat
) {
604 const boolean_colmatrix_base
<IT
, D
> &m
= mat
;
609 std::ostream
& operator<<(std::ostream
& os
, const std::vector
<T
> &vec
) {
612 typename
std::vector
<T
>::const_iterator it
= vec
.begin();
613 while ( it
!= vec
.end()) {
615 if (++it
!= vec
.end())