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