1 #ifndef booleanmatrix_h_AechohNgakoghahV
2 #define booleanmatrix_h_AechohNgakoghahV
18 /** The base class of boolean_colmatrix and boolean_colrowmatrix which implements
19 * the common logic of both. */
20 template<class IT
, class D
>
21 class boolean_colmatrix_base
{
24 typedef IT index_type
;
25 typedef std::vector
<index_type
> column_type
;
29 /** Create a matrix with 'width' columns, initalized with zero entries. */
30 boolean_colmatrix_base(size_t width
) :
35 /** Get height resp. width of the matrix. */
36 size_t width() const {
40 /** Get the matrix entry at row 'r' and column 'c'. */
41 bool get(index_type r
, index_type c
) const {
43 const column_type
&col
= get_column(c
);
44 return binary_search(col
.begin(), col
.end(), r
);
47 /** Set the matrix entry at row 'r' and column 'c'. */
48 void set(index_type r
, index_type c
, bool value
) {
49 get_derived()->_set(r
, c
, value
);
52 /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific value. */
53 void set_all(index_type indices
[][2], size_t count
, bool value
) {
54 for (unsigned i
=0; i
< count
; ++i
)
55 set(indices
[i
][0], indices
[i
][1], value
);
58 /** Get the c-th column. */
59 const column_type
& get_column(index_type c
) const {
64 /** Add the column-vector 'col' to the c-th column. Note that 'col'
65 * actually contains the list of row-indices that are 1. */
66 void add_column(index_type c
, const column_type
&col
) {
69 // Flip all entries that are set in 'col'.
70 for (typename
column_type::const_iterator it
= col
.begin(); it
!= col
.end(); ++it
)
71 set(*it
, c
, !get(*it
, c
));
74 /** Two matrices are equal iff they have the same entries */
75 bool operator==(const boolean_colmatrix_base
<IT
, D
> &m
) const {
76 return cols
== m
.cols
;
79 /** Two matrices are equal iff they have the same entries */
80 bool operator!=(const boolean_colmatrix_base
<IT
, D
> &m
) const {
84 /** Print index pairs of the 1s as { {r, c}, {r, c}, {r, c} } */
85 void print_indexpairs(std::ostream
&os
) const {
89 for (unsigned c
=0; c
< width(); ++c
) {
90 const column_type
&col
= get_column(c
);
91 for (typename
column_type::const_iterator it
= col
.begin(); it
!= col
.end(); ++it
) {
96 os
<< " {" << *it
<< ", " << c
<< "}";
103 /** Set the matrix entry at row 'r' and column 'c'. */
104 void _set(index_type r
, index_type c
, bool value
) {
107 column_type
&col
= cols
.at(c
);
108 // Let us see where to insert the new element
109 typename
column_type::iterator it
= lower_bound(col
.begin(), col
.end(), r
);
110 bool exists
= (it
!= col
.end() && *it
== r
);
111 assert(get(r
,c
) == exists
);
113 // Add 'r' to c-th column
115 // r is new, insert it
120 // Remove the element
128 // C++11 would have is_sorted
129 for (unsigned i
=1; i
< col
.size(); i
++)
130 assert(col
[i
-1] < col
[i
]);
135 /** The matrix is the set of columns. */
136 std::vector
<column_type
> cols
;
138 /** A cast to the derived type */
139 derived
* get_derived() {
140 return static_cast<derived
*>(this);
145 /** This is boolean matrix that is a std::vector of column-vectors and in each
146 * column-vector we save the row-indices of the 1s. It is designed to handle a
147 * few 1s and column-wise operations well. */
148 template<class IT
=uint32_t>
149 class boolean_colmatrix
: public boolean_colmatrix_base
<IT
, boolean_colmatrix
<IT
> > {
152 typedef IT index_type
;
153 typedef boolean_colmatrix_base
<IT
, boolean_colmatrix
<IT
> > base
;
155 /** Create a matrix with 'width' columns, initalized with zero entries. */
156 boolean_colmatrix(size_t columns
) :
160 /** Set the matrix entry at row 'r' and column 'c'. */
161 void _set(index_type r
, index_type c
, bool value
) {
162 base::_set(r
, c
, value
);
167 /** The base class of boolean_rowmatrix and boolean_colrowmatrix which implements
168 * the common logic of both. */
169 template<class IT
, class D
>
170 class boolean_rowmatrix_base
{
173 typedef IT index_type
;
174 typedef std::vector
<index_type
> row_type
;
178 /** Create a matrix with 'height' rows, initalized with zero entries.
180 boolean_rowmatrix_base(size_t height
) :
185 /** Get height resp. width of the matrix. */
186 size_t height() const {
190 /** Get the matrix entry at row 'r' and column 'c'. */
191 bool get(index_type r
, index_type c
) const {
192 assert(r
< height());
193 const row_type
&row
= get_row(r
);
194 return binary_search(row
.begin(), row
.end(), c
);
197 /** Set the matrix entry at row 'r' and column 'c'. */
198 void set(index_type r
, index_type c
, bool value
) {
199 get_derived()->_set(r
, c
, value
);
202 /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific value. */
203 void set_all(index_type indices
[][2], size_t count
, bool value
) {
204 for (unsigned i
=0; i
< count
; ++i
)
205 set(indices
[i
][0], indices
[i
][1], value
);
208 /** Get the r-th row. */
209 const row_type
& get_row(index_type r
) const {
210 assert(r
< height());
214 /** Add the row-vector 'row' to the r-th row. Note that 'row'
215 * actually contains the list of column-indices that are 1. */
216 void add_row(index_type r
, const row_type
&row
) {
217 assert(r
< height());
219 // Flip all entries that are set in 'row'.
220 for (typename
row_type::const_iterator it
= row
.begin(); it
!= row
.end(); ++it
)
221 set(r
, *it
, !get(r
, *it
));
224 /** Two matrices are equal iff they have the same entries */
225 bool operator==(const boolean_rowmatrix_base
<IT
, D
> &m
) const {
226 return rows
== m
.rows
;
229 /** Two matrices are equal iff they have the same entries */
230 bool operator!=(const boolean_rowmatrix_base
<IT
, D
> &m
) const {
231 return !(*this == m
);
235 /** Set the matrix entry at row 'r' and column 'c'. */
236 void _set(index_type r
, index_type c
, bool value
) {
237 assert(r
< height());
239 row_type
&row
= rows
.at(r
);
240 // Let us see where to insert/remove the new element
241 typename
row_type::iterator it
= lower_bound(row
.begin(), row
.end(), c
);
242 bool exists
= (it
!= row
.end() && *it
== c
);
243 assert(get(r
,c
) == exists
);
245 // Add 'r' to c-th column
247 // r is new, insert it
252 // Remove the element
260 // C++11 would have is_sorted
261 for (unsigned i
=1; i
< row
.size(); i
++)
262 assert(row
[i
-1] < row
[i
]);
267 derived
* get_derived() {
268 return static_cast<derived
*>(this);
271 /** The matrix is the set of columns. */
272 std::vector
<row_type
> rows
;
276 /** This is boolean matrix that is a std::vector of row-vectors and in each
277 * row-vector we save the column-indices of the 1s. It is designed to handle a
278 * few 1s and row-wise operations well. */
279 template<class IT
=uint32_t>
280 class boolean_rowmatrix
: public boolean_rowmatrix_base
<IT
, boolean_rowmatrix
<IT
> > {
283 typedef IT index_type
;
284 typedef boolean_rowmatrix_base
<IT
, boolean_rowmatrix
<IT
> > base
;
286 /** Create a matrix with 'height' rows, initalized with zero entries. */
287 boolean_rowmatrix(size_t height
) :
291 /** Set the matrix entry at row 'r' and column 'c'. */
292 void _set(index_type r
, index_type c
, bool value
) {
293 base::_set(r
, c
, value
);
298 /** This is a boolean matrix that supports. It is designed to handle a
299 * few 1s and row- and column-wise operations well. */
300 template<class IT
=uint32_t>
301 class boolean_colrowmatrix
: public boolean_colmatrix_base
<IT
, boolean_colrowmatrix
<IT
> >,
302 public boolean_rowmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > {
305 typedef boolean_colmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > colbase
;
306 typedef boolean_rowmatrix_base
<IT
, boolean_colrowmatrix
<IT
> > rowbase
;
309 typedef IT index_type
;
311 /** Create a size x size matrix, initialized with zeros. */
312 boolean_colrowmatrix(size_t size
) :
317 /** Override implementation. */
318 void _set(index_type r
, index_type c
, bool value
) {
319 colbase::_set(r
, c
, value
);
320 rowbase::_set(r
, c
, value
);
324 /** Get height resp. width of the matrix. */
325 size_t size() const {
326 assert(colbase::width() == rowbase::height());
327 return colbase::width();
330 /** Set the matrix entry at row 'r' and column 'c'. */
331 void set(index_type r
, index_type c
, bool value
) {
332 //Calling set() for one base suffices, static polymorphism
333 //calls _set() anyhow.
334 //rowbase::set(r, c, value);
335 colbase::set(r
, c
, value
);
338 /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific value. */
339 void set_all(index_type indices
[][2], size_t count
, bool value
) {
340 colbase::set_all(indices
, count
, value
);
343 /** Get the matrix entry at row 'r' and column 'c'. */
344 bool get(index_type r
, index_type c
) const {
345 assert(colbase::get(r
, c
) == rowbase::get(r
, c
));
346 return colbase::get(r
, c
);
349 /** Two matrices are equal iff they have the same entries */
350 bool operator==(const boolean_colrowmatrix
<IT
> &m
) const {
351 assert(rowbase::operator==(m
) == colbase::operator==(m
));
352 return colbase::operator==(m
);
355 /** Two matrices are equal iff they have the same entries */
356 bool operator!=(const boolean_colrowmatrix
<IT
> &m
) const {
357 return !(*this == m
);
360 /** Multiply with matrix b from the right */
362 boolean_colrowmatrix
<IT
> operator*(const boolean_colmatrix_base
<IT
, D
> &b
) const {
363 boolean_colrowmatrix
<IT
> c(size());
364 multiply_matrix(c
, *this, b
);
370 /** Counts the number of common elements in two sorted vectors. Equal to
371 * counting the number of elements given by std::set_intersection. */
372 template <class InputIterator1
, class InputIterator2
>
373 size_t count_set_intersection (InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
)
377 // As long as we did not either end, look for common elements
378 while (first1
!=last1
&& first2
!=last2
)
380 if (*first1
< *first2
)
382 else if (*first2
< *first1
)
384 // Element is common to both
394 /** Multiply a*b and save the product in 'result'. It is assumed that 'result' is intially empty and has appropriate size. */
395 template<class IT
, class D1
, class D2
, class RT
>
396 void multiply_matrix(RT
&result
, const boolean_rowmatrix_base
<IT
, D1
> &a
, const boolean_colmatrix_base
<IT
, D2
> &b
) {
397 assert(a
.height() == b
.width());
399 for (unsigned r
=0; r
< a
.height(); ++r
) {
400 const typename boolean_rowmatrix_base
<IT
, D1
>::row_type
&row
= a
.get_row(r
);
401 for (unsigned c
=0; c
< b
.width(); ++c
) {
402 const typename boolean_colmatrix_base
<IT
, D2
>::column_type
&col
= b
.get_column(c
);
403 if (count_set_intersection(row
.begin(), row
.end(), col
.begin(), col
.end()) % 2 == 1)
404 result
.set(r
, c
, true);
410 MT
create_unit_matrix(size_t size
) {
412 for (unsigned i
=0; i
< size
; ++i
)
418 std::ostream
& operator<<(std::ostream
&os
, const boolean_colrowmatrix
<IT
> &mat
) {
421 for (unsigned c
=0; c
< mat
.size(); ++c
) {
422 const unsigned d
= (c
% 10);
430 for (unsigned r
=0; r
< mat
.size(); ++r
) {
431 const unsigned d
= (r
% 10);
437 for (unsigned c
=0; c
< mat
.size(); ++c
)
438 os
<< (mat
.get(r
,c
) ? "X" : ".");
440 if (r
< mat
.size() - 1)
447 std::ostream
& operator<<(std::ostream
&os
, boolean_colrowmatrix
<IT
> &mat
) {
448 const boolean_colrowmatrix
<IT
> &m
= mat
;
452 template<class IT
, class D
>
453 std::ostream
& operator<<(std::ostream
&os
, const boolean_rowmatrix_base
<IT
, D
> &mat
) {
454 for (unsigned r
=0; r
< mat
.height(); ++r
) {
455 // Get the sorted r-th row
456 std::list
<IT
> row(mat
.get_row(r
).size());
457 copy(mat
.get_row(r
).begin(), mat
.get_row(r
).end(), row
.begin());
460 // Print the elements, and remove them
461 for (unsigned c
=0; row
.size() > 0; ++c
) {
462 if (row
.front() == c
) {
469 if (r
< mat
.height() - 1)
475 template<class IT
, class D
>
476 std::ostream
& operator<<(std::ostream
&os
, boolean_rowmatrix_base
<IT
, D
> &mat
) {
477 const boolean_rowmatrix_base
<IT
, D
> &m
= mat
;
481 template<class IT
, class D
>
482 std::ostream
& operator<<(std::ostream
&os
, const boolean_colmatrix_base
<IT
, D
> &mat
) {
483 // The sorted columns
484 std::vector
<std::list
<IT
> > cols
;
485 // The max height (max. value) of all columns
488 for (unsigned c
=0; c
< mat
.width(); ++c
) {
489 // Get the sorted c-th column
490 std::list
<IT
> col(mat
.get_column(c
).size());
491 copy(mat
.get_column(c
).begin(), mat
.get_column(c
).end(), col
.begin());
497 height
= std::max(height
, col
.back());
502 for (unsigned r
=0; r
<= height
; ++r
) {
503 // Print the elements, and remove them
504 for (unsigned c
=0; c
< mat
.width(); ++c
) {
505 std::list
<IT
> &col
= cols
.at(c
);
506 // This column is already empty
509 else if (col
.front() == r
) {
521 template<class IT
, class D
>
522 std::ostream
& operator<<(std::ostream
&os
, boolean_colmatrix_base
<IT
, D
> &mat
) {
523 const boolean_colmatrix_base
<IT
, D
> &m
= mat
;