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 BooleanColMatrix and BooleanColRowMatrix which implements
  19  * the common logic of both. */
  20 template<class IT, class D>
  21 class BooleanColMatrix_base {
  22
  23     public:
  24         typedef IT index_type;
  25         typedef std::vector<index_type> column_type;
  26         typedef D derived;
  27
  28         /** Create a matrix with 'width' columns, initalized with zero entries. */
  29         BooleanColMatrix_base(size_t width) :
  30             cols(width) {
  31         }
  32
  33         /** Get height resp. width of the matrix. */
  34         size_t width() const {
  35             return cols.size();
  36         }
  37
  38         /** Get the matrix entry at row 'r' and column 'c'. */
  39         bool get(index_type r, index_type c) const {
  40             assert(c < width());
  41             const column_type &col = getColumn(c);
  42             return binary_search(col.begin(), col.end(), r);
  43         }
  44
  45         /** Set the matrix entry at row 'r' and column 'c'. */
  46         void set(index_type r, index_type c, bool value) {
  47             getDerived()->_set(r, c, value);
  48         }
  49
  50         /** Get the c-th column. */
  51         const column_type& getColumn(index_type c) const {
  52             assert(c < width());
  53             return cols[c];
  54         }
  55
  56         /** Add the column-vector 'col' to the c-th column. Note that 'col'
  57          * actually contains the list of row-indices that are 1. */
  58         void addColumn(index_type c, const column_type &col) {
  59             assert(c < width());
  60
  61             // Flip all entries that are set in 'col'.
  62             for (typename column_type::const_iterator it = col.begin(); it != col.end(); ++it)
  63                 set(*it, c, !get(*it, c));
  64         }
  65
  66         /** Two matrices are equal iff they have the same entries */
  67         bool operator==(const BooleanColMatrix_base<IT, D> &m) const {
  68             return cols == m.cols;
  69         }
  70
  71         /** Two matrices are equal iff they have the same entries */
  72         bool operator!=(const BooleanColMatrix_base<IT, D> &m) const {
  73             return !(*this == m);
  74         }
  75
  76     protected:
  77
  78
  79         /** Set the matrix entry at row 'r' and column 'c'. */
  80         void _set(index_type r, index_type c, bool value) {
  81             assert(c < width());
  82
  83             column_type &col = cols.at(c);
  84             // Let us see where to insert the new element
  85             typename column_type::iterator it = lower_bound(col.begin(), col.end(), r);
  86             bool exists = (it != col.end() && *it == r);
  87             assert(get(r,c) == exists);
  88
  89             // Add 'r' to c-th column
  90             if (value) {
  91                 // r is new, insert it
  92                 if (!exists)
  93                     col.insert(it, r);
  94                 assert(get(r,c));
  95             }
  96             // Remove the element
  97             else {
  98                 if (exists)
  99                     col.erase(it);
 100                 assert(!get(r,c));
 101             }
 102
 103 #ifndef NDEBUG
 104             // C++11 would have is_sorted
 105             for (unsigned i=1; i < col.size(); i++)
 106                 assert(col[i-1] < col[i]);
 107 #endif
 108         }
 109
 110     private:
 111         /** The matrix is the set of columns. */
 112         std::vector<column_type> cols;
 113
 114         /** A cast to the derived type */
 115         derived* getDerived() {
 116             return static_cast<derived*>(this);
 117         }
 118 };
 119
 120
 121 /** This is boolean matrix that is a std::vector of column-vectors and in each
 122  * column-vector we save the row-indices of the 1s. It is designed to handle a
 123  * few 1s and column-wise operations well. */
 124 template<class IT=uint32_t>
 125 class BooleanColMatrix : public BooleanColMatrix_base<IT, BooleanColMatrix<IT> > {
 126
 127     public:
 128         typedef IT index_type;
 129         typedef BooleanColMatrix_base<IT, BooleanColMatrix<IT> > base;
 130
 131         /** Create a matrix with 'width' columns, initalized with zero entries. */
 132         BooleanColMatrix(size_t columns) :
 133             base(columns) {
 134         }
 135
 136         /** Set the matrix entry at row 'r' and column 'c'. */
 137         void _set(index_type r, index_type c, bool value) {
 138             base::_set(r, c, value);
 139         }
 140 };
 141
 142
 143 /** The base class of BooleanRowMatrix and BooleanColRowMatrix which implements
 144  * the common logic of both. */
 145 template<class IT, class D>
 146 class BooleanRowMatrix_base {
 147
 148     public:
 149         typedef IT index_type;
 150         typedef std::vector<index_type> row_type;
 151         typedef D derived;
 152
 153         /** Create a matrix with 'height' rows, initalized with zero entries.
 154          * */
 155         BooleanRowMatrix_base(size_t height) :
 156             rows(height) {
 157         }
 158
 159         /** Get height resp. width of the matrix. */
 160         size_t height() const {
 161             return rows.size();
 162         }
 163
 164         /** Get the matrix entry at row 'r' and column 'c'. */
 165         bool get(index_type r, index_type c) const {
 166             assert(r < height());
 167             const row_type &row = getRow(r);
 168             return binary_search(row.begin(), row.end(), c);
 169         }
 170
 171         /** Set the matrix entry at row 'r' and column 'c'. */
 172         void set(index_type r, index_type c, bool value) {
 173             getDerived()->_set(r, c, value);
 174         }
 175
 176         /** Get the r-th row. */
 177         const row_type& getRow(index_type r) const {
 178             assert(r < height());
 179             return rows[r];
 180         }
 181
 182         /** Add the row-vector 'row' to the r-th row. Note that 'row'
 183          * actually contains the list of column-indices that are 1. */
 184         void addRow(index_type r, const row_type &row) {
 185             assert(r < height());
 186
 187             // Flip all entries that are set in 'row'.
 188             for (typename row_type::const_iterator it = row.begin(); it != row.end(); ++it)
 189                 set(r, *it, !get(r, *it));
 190         }
 191
 192         /** Two matrices are equal iff they have the same entries */
 193         bool operator==(const BooleanRowMatrix_base<IT, D> &m) const {
 194             return rows == m.rows;
 195         }
 196
 197         /** Two matrices are equal iff they have the same entries */
 198         bool operator!=(const BooleanRowMatrix_base<IT, D> &m) const {
 199             return !(*this == m);
 200         }
 201
 202     protected:
 203         /** Set the matrix entry at row 'r' and column 'c'. */
 204         void _set(index_type r, index_type c, bool value) {
 205             assert(r < height());
 206
 207             row_type &row = rows.at(r);
 208             // Let us see where to insert/remove the new element
 209             typename row_type::iterator it = lower_bound(row.begin(), row.end(), c);
 210             bool exists = (it != row.end() && *it == c);
 211             assert(get(r,c) == exists);
 212
 213             // Add 'r' to c-th column
 214             if (value) {
 215                 // r is new, insert it
 216                 if (!exists)
 217                     row.insert(it, c);
 218                 assert(get(r,c));
 219             }
 220             // Remove the element
 221             else {
 222                 if (exists)
 223                     row.erase(it);
 224                 assert(!get(r,c));
 225             }
 226
 227 #ifndef NDEBUG
 228             // C++11 would have is_sorted
 229             for (unsigned i=1; i < row.size(); i++)
 230                 assert(row[i-1] < row[i]);
 231 #endif
 232         }
 233
 234     private:
 235         derived* getDerived() {
 236             return static_cast<derived*>(this);
 237         }
 238
 239         /** The matrix is the set of columns. */
 240         std::vector<row_type> rows;
 241 };
 242
 243
 244 /** This is boolean matrix that is a std::vector of row-vectors and in each
 245  * row-vector we save the column-indices of the 1s. It is designed to handle a
 246  * few 1s and row-wise operations well. */
 247 template<class IT=uint32_t>
 248 class BooleanRowMatrix : public BooleanRowMatrix_base<IT, BooleanRowMatrix<IT> > {
 249
 250     public:
 251         typedef IT index_type;
 252         typedef BooleanRowMatrix_base<IT, BooleanRowMatrix<IT> > base;
 253
 254         /** Create a matrix with 'height' rows, initalized with zero entries. */
 255         BooleanRowMatrix(size_t height) :
 256             base(height) {
 257         }
 258
 259         /** Set the matrix entry at row 'r' and column 'c'. */
 260         void _set(index_type r, index_type c, bool value) {
 261             base::_set(r, c, value);
 262         }
 263 };
 264
 265
 266 /** This is a boolean matrix that supports. It is designed to handle a
 267  * few 1s and row- and column-wise operations well. */
 268 template<class IT=uint32_t>
 269 class BooleanColRowMatrix : public BooleanColMatrix_base<IT, BooleanColRowMatrix<IT> >,
 270                             public BooleanRowMatrix_base<IT, BooleanColRowMatrix<IT> > {
 271
 272     public:
 273         typedef BooleanColMatrix_base<IT, BooleanColRowMatrix<IT> > colbase;
 274         typedef BooleanRowMatrix_base<IT, BooleanColRowMatrix<IT> > rowbase;
 275
 276     public:
 277         typedef IT index_type;
 278
 279         /** Create a size x size matrix, initialized with zeros. */
 280         BooleanColRowMatrix(size_t size) :
 281             colbase(size),
 282             rowbase(size) {
 283         }
 284
 285         /** Override implementation. */
 286         void _set(index_type r, index_type c, bool value) {
 287             colbase::_set(r, c, value);
 288             rowbase::_set(r, c, value);
 289         }
 290
 291     public:
 292         /** Get height resp. width of the matrix. */
 293         size_t size() const {
 294             assert(colbase::width() == rowbase::height());
 295             return colbase::width();
 296         }
 297
 298         /** Set the matrix entry at row 'r' and column 'c'. */
 299         void set(index_type r, index_type c, bool value) {
 300             //Calling set() for one base suffices, static polymorphism
 301             //calls _set() anyhow.
 302             //rowbase::set(r, c, value);
 303             colbase::set(r, c, value);
 304         }
 305
 306         /** Get the matrix entry at row 'r' and column 'c'. */
 307         bool get(index_type r, index_type c) const {
 308             assert(colbase::get(r, c) == rowbase::get(r, c));
 309             return colbase::get(r, c);
 310         }
 311
 312         /** Two matrices are equal iff they have the same entries */
 313         bool operator==(const BooleanColRowMatrix<IT> &m) const {
 314             assert(rowbase::operator==(m) == colbase::operator==(m));
 315             return colbase::operator==(m);
 316         }
 317
 318         /** Two matrices are equal iff they have the same entries */
 319         bool operator!=(const BooleanColRowMatrix<IT> &m) const {
 320             return !(*this == m);
 321         }
 322
 323         /** Multiply with matrix b from the right */
 324         template<class D>
 325         BooleanColRowMatrix<IT> operator*(const BooleanColMatrix_base<IT, D> &b) {
 326             BooleanColRowMatrix<IT> c(size());
 327             multiply_matrix(c, *this, b);
 328             return c;
 329         }
 330 };
 331
 332
 333 /** Counts the number of common elements in two sorted vectors. Equal to
 334  * counting the number of elements given by std::set_intersection. */
 335 template <class InputIterator1, class InputIterator2>
 336 size_t count_set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
 337 {
 338     size_t count = 0;
 339
 340     // As long as we did not either end, look for common elements
 341     while (first1!=last1 && first2!=last2)
 342     {
 343         if (*first1 < *first2)
 344             ++first1;
 345         else if (*first2 < *first1)
 346             ++first2;
 347         // Element is common to both
 348         else {
 349             ++count;
 350             ++first1;
 351             ++first2;
 352         }
 353     }
 354     return count;
 355 }
 356
 357 /** Multiply a*b and save the product in 'result'. It is assumed that 'result' is intially empty and has appropriate size. */
 358 template<class IT, class D, class RT>
 359 void multiply_matrix(RT &result, const BooleanRowMatrix_base<IT, D> &a, const BooleanColMatrix_base<IT, D> &b) {
 360     assert(a.height() == b.width());
 361
 362     for (unsigned r=0; r < a.height(); ++r) {
 363         const typename BooleanRowMatrix_base<IT, D>::row_type &row = a.getRow(r);
 364         for (unsigned c=0; c < b.width(); ++c) {
 365             const typename BooleanColMatrix_base<IT, D>::column_type &col = b.getColumn(c);
 366             if (count_set_intersection(row.begin(), row.end(), col.begin(), col.end()) % 2 == 1)
 367                 result.set(r, c, true);
 368         }
 369     }
 370 }
 371
 372 template<class MT>
 373 MT unitMatrix(size_t size) {
 374     MT mat(size);
 375     for (unsigned i=0; i < size; ++i)
 376         mat.set(i, i, true);
 377     return mat;
 378 }
 379
 380 template<class IT>
 381 std::ostream& operator<<(std::ostream &os, const BooleanColRowMatrix<IT> &mat) {
 382     for (unsigned r=0; r < mat.size(); ++r) {
 383         for (unsigned c=0; c < mat.size(); ++c)
 384             os << (mat.get(r,c) ? "X" : ".");
 385
 386         if (r < mat.size() - 1)
 387             os << std::endl;
 388     }
 389     return os;
 390 }
 391
 392 template<class IT>
 393 std::ostream& operator<<(std::ostream &os, BooleanColRowMatrix<IT> &mat) {
 394     const BooleanColRowMatrix<IT> &m = mat;
 395     return os << m;
 396 }
 397
 398 template<class IT, class D>
 399 std::ostream& operator<<(std::ostream &os, const BooleanRowMatrix_base<IT, D> &mat) {
 400     for (unsigned r=0; r < mat.height(); ++r) {
 401         // Get the sorted r-th row
 402         std::list<IT> row(mat.getRow(r).size());
 403         copy(mat.getRow(r).begin(), mat.getRow(r).end(), row.begin());
 404
 405         os << "|";
 406         // Print the elements, and remove them
 407         for (unsigned c=0; row.size() > 0; ++c) {
 408             if (row.front() == c) {
 409                 os << "X";
 410                 row.pop_front();
 411             } else
 412                 os << ".";
 413         }
 414
 415         if (r < mat.height() - 1)
 416             os << std::endl;
 417     }
 418     return os;
 419 }
 420
 421 template<class IT, class D>
 422 std::ostream& operator<<(std::ostream &os, BooleanRowMatrix_base<IT, D> &mat) {
 423     const BooleanRowMatrix_base<IT, D> &m = mat;
 424     return os << m;
 425 }
 426
 427 template<class IT, class D>
 428 std::ostream& operator<<(std::ostream &os, const BooleanColMatrix_base<IT, D> &mat) {
 429     // The sorted columns
 430     std::vector<std::list<IT> > cols;
 431     // The max height (max. value) of all columns
 432     IT height = 0;
 433
 434     for (unsigned c=0; c < mat.width(); ++c) {
 435         // Get the sorted c-th column
 436         std::list<IT> col(mat.getColumn(c).size());
 437         copy(mat.getColumn(c).begin(), mat.getColumn(c).end(), col.begin());
 438         cols.push_back(col);
 439
 440         os << "-";
 441
 442         if (col.size() != 0)
 443             height = std::max(height, col.back());
 444     }
 445
 446     os << std::endl;
 447
 448     for (unsigned r=0; r <= height; ++r) {
 449         // Print the elements, and remove them
 450         for (unsigned c=0; c < mat.width(); ++c) {
 451             std::list<IT> &col = cols.at(c);
 452             // This column is already empty
 453             if (col.size() == 0)
 454                 os << " ";
 455             else if (col.front() == r) {
 456                 os << "X";
 457                 col.pop_front();
 458             } else
 459                 os << ".";
 460         }
 461
 462         os << std::endl;
 463     }
 464     return os;
 465 }
 466
 467 template<class IT, class D>
 468 std::ostream& operator<<(std::ostream &os, BooleanColMatrix_base<IT, D> &mat) {
 469     const BooleanColMatrix_base<IT, D> &m = mat;
 470     return os << m;
 471 }
 472
 473 }
 474
 475 #endif