include/libstick-0.1/booleanmatrix.h

   1 #ifndef booleanmatrix_h_AechohNgakoghahV
   2 #define booleanmatrix_h_AechohNgakoghahV
   3
   4 #include <stdint.h>
   5 #include <cassert>
   6 #include <cstdlib>
   7 #include <algorithm>
   8 #include <vector>
   9 #include <list>
  10 #include <set>
  11 #include <ostream>
  12 #include <iterator>
  13
  14 #include "booleanvector.h"
  15
  16 namespace libstick {
  17
  18
  19 template<class T>
  20 std::ostream& operator<<(std::ostream &, const std::vector<T> &);
  21
  22
  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 {
  27
  28     public:
  29         typedef IT index_type;
  30         typedef sorted_boolean_vector<IT> column_type;
  31         typedef D derived;
  32
  33     protected:
  34         /** Create a matrix with 'width' columns, initalized with zero entries. */
  35         boolean_colmatrix_base(size_t width) :
  36             cols(width) {
  37         }
  38
  39     public:
  40         /** A casting constructor for any colmatrix with same entries type. */
  41         template<class D2>
  42         boolean_colmatrix_base(const boolean_colmatrix_base<IT, D2> &mat) :
  43             cols(mat.get_columns()) {
  44         }
  45
  46         /** Get width of the matrix. */
  47         size_t width() const {
  48             return cols.size();
  49         }
  50
  51         /** Get height of the matrix, i.e. maximum row-index + 1 among all
  52          * columns. */
  53         size_t height() const {
  54             IT h = 0;
  55             for (unsigned c=0; c < width(); ++c)
  56                 if (!cols[c].isempty())
  57                     h = std::max(h, cols[c].back());
  58             return h+1;
  59         }
  60
  61         /** Get the matrix entry at row 'r' and column 'c'. */
  62         bool get(index_type r, index_type c) const {
  63             assert(c < width());
  64             return get_column(c).get(r);
  65         }
  66
  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);
  70         }
  71
  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);
  77         }
  78
  79         /** Get the c-th column. */
  80         const column_type& get_column(index_type c) const {
  81             assert(c < width());
  82             return cols[c];
  83         }
  84
  85         /** Get all columns */
  86         const std::vector<column_type>& get_columns() const {
  87             return cols;
  88         }
  89
  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) {
  93             assert(c < width());
  94
  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));
  99         }
 100
 101         /** Two matrices are equal iff they have the same entries */
 102         template<class D2>
 103         bool operator==(const boolean_colmatrix_base<IT, D2> &m) const {
 104             return cols == m.get_columns();
 105         }
 106
 107         /** Two matrices are equal iff they have the same entries */
 108         template<class D2>
 109         bool operator!=(const boolean_colmatrix_base<IT, D2> &m) const {
 110             return !(*this == m);
 111         }
 112
 113         /** Print index pairs of the 1s as { {r, c}, {r, c}, {r, c} } */
 114         void print_indexpairs(std::ostream &os) const {
 115             bool first=true;
 116
 117             os << "{";
 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();
 122
 123                 for (typename column_type::indexarray::iterator it = ones.begin();
 124                         it != ones.end(); ++it) {
 125                     if (first)
 126                         first = false;
 127                     else
 128                         os << ",";
 129                     os << " {" << *it << ", " << c << "}";
 130                 }
 131             }
 132             os << " }";
 133         }
 134
 135     protected:
 136         /** Set the matrix entry at row 'r' and column 'c'. */
 137         void _set(index_type r, index_type c, bool value) {
 138             assert(c < width());
 139             cols.at(c).set(r, value);
 140         }
 141
 142     protected:
 143         /** The matrix is the set of columns. */
 144         std::vector<column_type> cols;
 145
 146         /** A cast to the derived type */
 147         derived* get_derived() {
 148             return static_cast<derived*>(this);
 149         }
 150 };
 151
 152
 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> > {
 158
 159     public:
 160         typedef IT index_type;
 161         typedef boolean_colmatrix_base<IT, boolean_colmatrix<IT> > base;
 162         typedef typename base::column_type column_type;
 163
 164         /** Create a matrix with 'width' columns, initalized with zero entries. */
 165         boolean_colmatrix(size_t columns) :
 166             base(columns) {
 167         }
 168
 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);
 172         }
 173
 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);
 178         }
 179
 180     private:
 181 };
 182
 183
 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 {
 188
 189     public:
 190         typedef IT index_type;
 191         typedef sorted_boolean_vector<IT> row_type;
 192         typedef D derived;
 193
 194     protected:
 195         /** Create a matrix with 'height' rows, initalized with zero entries.
 196          * */
 197         boolean_rowmatrix_base(size_t height) :
 198             rows(height) {
 199         }
 200
 201     public:
 202         /** Get height of the matrix. */
 203         size_t height() const {
 204             return rows.size();
 205         }
 206
 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);
 211         }
 212
 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);
 216         }
 217
 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);
 223         }
 224
 225         /** Get the r-th row. */
 226         const row_type& get_row(index_type r) const {
 227             assert(r < height());
 228             return rows[r];
 229         }
 230
 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());
 235
 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));
 240         }
 241
 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;
 245         }
 246
 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);
 250         }
 251
 252     protected:
 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);
 257         }
 258
 259     protected:
 260         derived* get_derived() {
 261             return static_cast<derived*>(this);
 262         }
 263
 264         /** The matrix is the set of columns. */
 265         std::vector<row_type> rows;
 266 };
 267
 268
 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> > {
 274
 275     public:
 276         typedef IT index_type;
 277         typedef boolean_rowmatrix_base<IT, boolean_rowmatrix<IT> > base;
 278
 279         /** Create a matrix with 'height' rows, initalized with zero entries. */
 280         boolean_rowmatrix(size_t height) :
 281             base(height) {
 282         }
 283
 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);
 287         }
 288 };
 289
 290
 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> > {
 296
 297     public:
 298         typedef boolean_colmatrix_base<IT, boolean_colrowmatrix<IT> > colbase;
 299         typedef boolean_rowmatrix_base<IT, boolean_colrowmatrix<IT> > rowbase;
 300
 301     public:
 302         typedef IT index_type;
 303
 304         /** Create a size x size matrix, initialized with zeros. */
 305         boolean_colrowmatrix(size_t size) :
 306             colbase(size),
 307             rowbase(size) {
 308         }
 309
 310         /** Casting a colmatrix into a colrow matrix */
 311         template<class D>
 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);
 319             }
 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);
 324             }
 325         }
 326
 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);
 331         }
 332
 333     public:
 334         /** Get height resp. width of the matrix. */
 335         size_t size() const {
 336             assert(colbase::width() == rowbase::height());
 337             return colbase::width();
 338         }
 339
 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);
 346         }
 347
 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);
 352         }
 353
 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);
 358         }
 359
 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);
 364         }
 365
 366         /** Two matrices are equal iff they have the same entries */
 367         template<class D>
 368         bool operator==(const boolean_colmatrix_base<IT, D> &m) const {
 369             return colbase::operator==(m);
 370         }
 371
 372         /** Two matrices are equal iff they have the same entries */
 373         bool operator!=(const boolean_colrowmatrix<IT> &m) const {
 374             return !(*this == m);
 375         }
 376
 377         /** Multiply with matrix b from the right */
 378         template<class D>
 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);
 382             return c;
 383         }
 384 };
 385
 386
 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)
 391 {
 392     size_t count = 0;
 393
 394     // As long as we did not either end, look for common elements
 395     while (first1 != last1 && first2 != last2)
 396     {
 397         if (*first1 < *first2)
 398             ++first1;
 399         else if (*first2 < *first1)
 400             ++first2;
 401         // Element is common to both
 402         else {
 403             ++count;
 404             ++first1;
 405             ++first2;
 406         }
 407     }
 408     return count;
 409 }
 410
 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());
 416
 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);
 425         }
 426     }
 427 }
 428
 429 template<class MT>
 430 MT create_unit_matrix(size_t size) {
 431     MT mat(size);
 432     for (unsigned i=0; i < size; ++i)
 433         mat.set(i, i, true);
 434     return mat;
 435 }
 436
 437 template<class IT>
 438 std::ostream& operator<<(std::ostream &os, const boolean_colrowmatrix<IT> &mat) {
 439
 440     os << " ";
 441     for (unsigned c=0; c < mat.size(); ++c) {
 442         const unsigned d = (c % 10);
 443         if (d > 0)
 444             os << d;
 445         else
 446             os << " ";
 447     }
 448     os << std::endl;
 449
 450     for (unsigned r=0; r < mat.size(); ++r) {
 451         const unsigned d = (r % 10);
 452         if (d > 0)
 453             os << d;
 454         else
 455             os << " ";
 456
 457         for (unsigned c=0; c < mat.size(); ++c)
 458             os << (mat.get(r,c) ? "X" : ".");
 459
 460         if (r < mat.size() - 1)
 461             os << std::endl;
 462     }
 463     return os;
 464 }
 465
 466 template<class IT>
 467 std::ostream& operator<<(std::ostream &os, boolean_colrowmatrix<IT> &mat) {
 468     const boolean_colrowmatrix<IT> &m = mat;
 469     return os << m;
 470 }
 471
 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());
 478
 479         os << "|";
 480         // Print the elements, and remove them
 481         for (unsigned c=0; row.size() > 0; ++c) {
 482             if (row.front() == c) {
 483                 os << "X";
 484                 row.pop_front();
 485             } else
 486                 os << ".";
 487         }
 488
 489         if (r < mat.height() - 1)
 490             os << std::endl;
 491     }
 492     return os;
 493 }
 494
 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;
 498     return os << m;
 499 }
 500
 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
 506     IT height = 0;
 507
 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());
 512         cols.push_back(col);
 513
 514         os << "-";
 515
 516         if (!col.isempty())
 517             height = std::max(height, col.back());
 518     }
 519
 520     os << std::endl;
 521
 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
 527             if (col.isempty())
 528                 os << " ";
 529             else if (col.front() == r) {
 530                 os << "X";
 531                 col.pop_front();
 532             } else
 533                 os << ".";
 534         }
 535
 536         os << std::endl;
 537     }
 538     return os;
 539 }
 540
 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;
 544     return os << m;
 545 }
 546
 547 template<class T>
 548 std::ostream& operator<<(std::ostream& os, const std::vector<T> &vec) {
 549     os << "[";
 550
 551     typename std::vector<T>::const_iterator it = vec.begin();
 552     while ( it != vec.end()) {
 553         os << *it;
 554         if (++it != vec.end())
 555             os << " ";
 556     }
 557
 558     os << "]";
 559     return os;
 560 }
 561
 562 }
 563
 564 #endif