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
  15 namespace libstick {
  16
  17
  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 {
  22
  23     public:
  24         typedef IT index_type;
  25         typedef std::vector<index_type> column_type;
  26         typedef D derived;
  27
  28     protected:
  29         /** Create a matrix with 'width' columns, initalized with zero entries. */
  30         boolean_colmatrix_base(size_t width) :
  31             cols(width) {
  32         }
  33
  34     public:
  35         /** Get height resp. width of the matrix. */
  36         size_t width() const {
  37             return cols.size();
  38         }
  39
  40         /** Get the matrix entry at row 'r' and column 'c'. */
  41         bool get(index_type r, index_type c) const {
  42             assert(c < width());
  43             const column_type &col = get_column(c);
  44             return binary_search(col.begin(), col.end(), r);
  45         }
  46
  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);
  50         }
  51
  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);
  56         }
  57
  58         /** Get the c-th column. */
  59         const column_type& get_column(index_type c) const {
  60             assert(c < width());
  61             return cols[c];
  62         }
  63
  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) {
  67             assert(c < width());
  68
  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));
  72         }
  73
  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;
  77         }
  78
  79         /** Two matrices are equal iff they have the same entries */
  80         bool operator!=(const boolean_colmatrix_base<IT, D> &m) const {
  81             return !(*this == m);
  82         }
  83
  84         /** Print index pairs of the 1s as { {r, c}, {r, c}, {r, c} } */
  85         void print_indexpairs(std::ostream &os) const {
  86             bool first=true;
  87
  88             os << "{";
  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) {
  92                     if (first)
  93                         first = false;
  94                     else
  95                         os << ",";
  96                     os << " {" << *it << ", " << c << "}";
  97                 }
  98             }
  99             os << " }";
 100         }
 101
 102     protected:
 103         /** Set the matrix entry at row 'r' and column 'c'. */
 104         void _set(index_type r, index_type c, bool value) {
 105             assert(c < width());
 106
 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);
 112
 113             // Add 'r' to c-th column
 114             if (value) {
 115                 // r is new, insert it
 116                 if (!exists)
 117                     col.insert(it, r);
 118                 assert(get(r,c));
 119             }
 120             // Remove the element
 121             else {
 122                 if (exists)
 123                     col.erase(it);
 124                 assert(!get(r,c));
 125             }
 126
 127 #ifndef NDEBUG
 128             // C++11 would have is_sorted
 129             for (unsigned i=1; i < col.size(); i++)
 130                 assert(col[i-1] < col[i]);
 131 #endif
 132         }
 133
 134     private:
 135         /** The matrix is the set of columns. */
 136         std::vector<column_type> cols;
 137
 138         /** A cast to the derived type */
 139         derived* get_derived() {
 140             return static_cast<derived*>(this);
 141         }
 142 };
 143
 144
 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> > {
 150
 151     public:
 152         typedef IT index_type;
 153         typedef boolean_colmatrix_base<IT, boolean_colmatrix<IT> > base;
 154
 155         /** Create a matrix with 'width' columns, initalized with zero entries. */
 156         boolean_colmatrix(size_t columns) :
 157             base(columns) {
 158         }
 159
 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);
 163         }
 164 };
 165
 166
 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 {
 171
 172     public:
 173         typedef IT index_type;
 174         typedef std::vector<index_type> row_type;
 175         typedef D derived;
 176
 177     protected:
 178         /** Create a matrix with 'height' rows, initalized with zero entries.
 179          * */
 180         boolean_rowmatrix_base(size_t height) :
 181             rows(height) {
 182         }
 183
 184     public:
 185         /** Get height resp. width of the matrix. */
 186         size_t height() const {
 187             return rows.size();
 188         }
 189
 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);
 195         }
 196
 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);
 200         }
 201
 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);
 206         }
 207
 208         /** Get the r-th row. */
 209         const row_type& get_row(index_type r) const {
 210             assert(r < height());
 211             return rows[r];
 212         }
 213
 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());
 218
 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));
 222         }
 223
 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;
 227         }
 228
 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);
 232         }
 233
 234     protected:
 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());
 238
 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);
 244
 245             // Add 'r' to c-th column
 246             if (value) {
 247                 // r is new, insert it
 248                 if (!exists)
 249                     row.insert(it, c);
 250                 assert(get(r,c));
 251             }
 252             // Remove the element
 253             else {
 254                 if (exists)
 255                     row.erase(it);
 256                 assert(!get(r,c));
 257             }
 258
 259 #ifndef NDEBUG
 260             // C++11 would have is_sorted
 261             for (unsigned i=1; i < row.size(); i++)
 262                 assert(row[i-1] < row[i]);
 263 #endif
 264         }
 265
 266     private:
 267         derived* get_derived() {
 268             return static_cast<derived*>(this);
 269         }
 270
 271         /** The matrix is the set of columns. */
 272         std::vector<row_type> rows;
 273 };
 274
 275
 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> > {
 281
 282     public:
 283         typedef IT index_type;
 284         typedef boolean_rowmatrix_base<IT, boolean_rowmatrix<IT> > base;
 285
 286         /** Create a matrix with 'height' rows, initalized with zero entries. */
 287         boolean_rowmatrix(size_t height) :
 288             base(height) {
 289         }
 290
 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);
 294         }
 295 };
 296
 297
 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> > {
 303
 304     public:
 305         typedef boolean_colmatrix_base<IT, boolean_colrowmatrix<IT> > colbase;
 306         typedef boolean_rowmatrix_base<IT, boolean_colrowmatrix<IT> > rowbase;
 307
 308     public:
 309         typedef IT index_type;
 310
 311         /** Create a size x size matrix, initialized with zeros. */
 312         boolean_colrowmatrix(size_t size) :
 313             colbase(size),
 314             rowbase(size) {
 315         }
 316
 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);
 321         }
 322
 323     public:
 324         /** Get height resp. width of the matrix. */
 325         size_t size() const {
 326             assert(colbase::width() == rowbase::height());
 327             return colbase::width();
 328         }
 329
 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);
 336         }
 337
 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);
 341         }
 342
 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);
 347         }
 348
 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);
 353         }
 354
 355         /** Two matrices are equal iff they have the same entries */
 356         bool operator!=(const boolean_colrowmatrix<IT> &m) const {
 357             return !(*this == m);
 358         }
 359
 360         /** Multiply with matrix b from the right */
 361         template<class D>
 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);
 365             return c;
 366         }
 367 };
 368
 369
 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)
 374 {
 375     size_t count = 0;
 376
 377     // As long as we did not either end, look for common elements
 378     while (first1 != last1 && first2 != last2)
 379     {
 380         if (*first1 < *first2)
 381             ++first1;
 382         else if (*first2 < *first1)
 383             ++first2;
 384         // Element is common to both
 385         else {
 386             ++count;
 387             ++first1;
 388             ++first2;
 389         }
 390     }
 391     return count;
 392 }
 393
 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());
 398
 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);
 405         }
 406     }
 407 }
 408
 409 template<class MT>
 410 MT create_unit_matrix(size_t size) {
 411     MT mat(size);
 412     for (unsigned i=0; i < size; ++i)
 413         mat.set(i, i, true);
 414     return mat;
 415 }
 416
 417 template<class IT>
 418 std::ostream& operator<<(std::ostream &os, const boolean_colrowmatrix<IT> &mat) {
 419
 420     os << " ";
 421     for (unsigned c=0; c < mat.size(); ++c) {
 422         const unsigned d = (c % 10);
 423         if (d > 0)
 424             os << d;
 425         else
 426             os << " ";
 427     }
 428     os << std::endl;
 429
 430     for (unsigned r=0; r < mat.size(); ++r) {
 431         const unsigned d = (r % 10);
 432         if (d > 0)
 433             os << d;
 434         else
 435             os << " ";
 436
 437         for (unsigned c=0; c < mat.size(); ++c)
 438             os << (mat.get(r,c) ? "X" : ".");
 439
 440         if (r < mat.size() - 1)
 441             os << std::endl;
 442     }
 443     return os;
 444 }
 445
 446 template<class IT>
 447 std::ostream& operator<<(std::ostream &os, boolean_colrowmatrix<IT> &mat) {
 448     const boolean_colrowmatrix<IT> &m = mat;
 449     return os << m;
 450 }
 451
 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());
 458
 459         os << "|";
 460         // Print the elements, and remove them
 461         for (unsigned c=0; row.size() > 0; ++c) {
 462             if (row.front() == c) {
 463                 os << "X";
 464                 row.pop_front();
 465             } else
 466                 os << ".";
 467         }
 468
 469         if (r < mat.height() - 1)
 470             os << std::endl;
 471     }
 472     return os;
 473 }
 474
 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;
 478     return os << m;
 479 }
 480
 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
 486     IT height = 0;
 487
 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());
 492         cols.push_back(col);
 493
 494         os << "-";
 495
 496         if (col.size() != 0)
 497             height = std::max(height, col.back());
 498     }
 499
 500     os << std::endl;
 501
 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
 507             if (col.size() == 0)
 508                 os << " ";
 509             else if (col.front() == r) {
 510                 os << "X";
 511                 col.pop_front();
 512             } else
 513                 os << ".";
 514         }
 515
 516         os << std::endl;
 517     }
 518     return os;
 519 }
 520
 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;
 524     return os << m;
 525 }
 526
 527 }
 528
 529 #endif