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 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 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             for (unsigned i=1; i < col.size(); i++)
 105                 assert(col[i-1] < col[i]);
 106 #endif
 107         }
 108
 109     private:
 110         /** The matrix is the set of columns. */
 111         std::vector<column_type> cols;
 112
 113         /** A cast to the derived type */
 114         derived* getDerived() {
 115             return static_cast<derived*>(this);
 116         }
 117 };
 118
 119
 120 /** This is boolean matrix that is a std::vector of column-vectors and in each
 121  * column-vector we save the row-indices of the 1s. It is designed to handle a
 122  * few 1s and column-wise operations well. */
 123 template<class IT=uint32_t>
 124 class BooleanColMatrix : public BooleanColMatrix_base<IT, BooleanColMatrix<IT> > {
 125
 126     public:
 127         typedef IT index_type;
 128         typedef BooleanColMatrix_base<IT, BooleanColMatrix<IT> > base;
 129
 130         /** Create a matrix with 'width' columns, initalized with zero entries. */
 131         BooleanColMatrix(size_t columns) :
 132             base(columns) {
 133         }
 134
 135         /** Set the matrix entry at row 'r' and column 'c'. */
 136         void _set(index_type r, index_type c, bool value) {
 137             base::_set(r, c, value);
 138         }
 139 };
 140
 141
 142 /** The base class of BooleanRowMatrix and BooleanColRowMatrix which implements
 143  * the common logic of both. */
 144 template<class IT, class D>
 145 class BooleanRowMatrix_base {
 146
 147     public:
 148         typedef IT index_type;
 149         typedef std::vector<index_type> row_type;
 150         typedef D derived;
 151
 152         /** Create a matrix with 'height' rows, initalized with zero entries.
 153          * */
 154         BooleanRowMatrix_base(size_t height) :
 155             rows(height) {
 156         }
 157
 158         /** Get height resp. width of the matrix. */
 159         size_t height() const {
 160             return rows.size();
 161         }
 162
 163         /** Get the matrix entry at row 'r' and column 'c'. */
 164         bool get(index_type r, index_type c) const {
 165             assert(r < height());
 166             const row_type &row = getRow(r);
 167             return binary_search(row.begin(), row.end(), c);
 168         }
 169
 170         /** Set the matrix entry at row 'r' and column 'c'. */
 171         void set(index_type r, index_type c, bool value) {
 172             getDerived()->_set(r, c, value);
 173         }
 174
 175         /** Get the r-th row. */
 176         const row_type& getRow(index_type r) const {
 177             assert(r < height());
 178             return rows[r];
 179         }
 180
 181         /** Add the row-vector 'row' to the r-th row. Note that 'row'
 182          * actually contains the list of column-indices that are 1. */
 183         void add_row(index_type r, const row_type &row) {
 184             assert(r < height());
 185
 186             // Flip all entries that are set in 'row'.
 187             for (typename row_type::const_iterator it = row.begin(); it != row.end(); ++it)
 188                 set(r, *it, !get(r, *it));
 189         }
 190
 191         /** Two matrices are equal iff they have the same entries */
 192         bool operator==(const BooleanRowMatrix_base<IT, D> &m) const {
 193             return rows == m.rows;
 194         }
 195
 196         /** Two matrices are equal iff they have the same entries */
 197         bool operator!=(const BooleanRowMatrix_base<IT, D> &m) const {
 198             return !(*this == m);
 199         }
 200
 201     protected:
 202         /** Set the matrix entry at row 'r' and column 'c'. */
 203         void _set(index_type r, index_type c, bool value) {
 204             assert(r < height());
 205
 206             row_type &row = rows.at(r);
 207             // Let us see where to insert/remove the new element
 208             typename row_type::iterator it = lower_bound(row.begin(), row.end(), c);
 209             bool exists = (it != row.end() && *it == c);
 210             assert(get(r,c) == exists);
 211
 212             // Add 'r' to c-th column
 213             if (value) {
 214                 // r is new, insert it
 215                 if (!exists)
 216                     row.insert(it, c);
 217                 assert(get(r,c));
 218             }
 219             // Remove the element
 220             else {
 221                 if (exists)
 222                     row.erase(it);
 223                 assert(!get(r,c));
 224             }
 225
 226 #ifndef NDEBUG
 227             for (unsigned i=1; i < row.size(); i++)
 228                 assert(row[i-1] < row[i]);
 229 #endif
 230         }
 231
 232     private:
 233         derived* getDerived() {
 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 BooleanRowMatrix : public BooleanRowMatrix_base<IT, BooleanRowMatrix<IT> > {
 247
 248     public:
 249         typedef IT index_type;
 250         typedef BooleanRowMatrix_base<IT, BooleanRowMatrix<IT> > base;
 251
 252         /** Create a matrix with 'height' rows, initalized with zero entries. */
 253         BooleanRowMatrix(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 BooleanColRowMatrix : public BooleanColMatrix_base<IT, BooleanColRowMatrix<IT> >,
 268                             public BooleanRowMatrix_base<IT, BooleanColRowMatrix<IT> > {
 269
 270     public:
 271         typedef BooleanColMatrix_base<IT, BooleanColRowMatrix<IT> > colbase;
 272         typedef BooleanRowMatrix_base<IT, BooleanColRowMatrix<IT> > rowbase;
 273
 274     public:
 275         typedef IT index_type;
 276
 277         /** Create a size x size matrix, initialized with zeros. */
 278         BooleanColRowMatrix(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 BooleanColRowMatrix<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 BooleanColRowMatrix<IT> &m) const {
 318             return !(*this == m);
 319         }
 320 };
 321
 322 template<class IT>
 323 std::ostream& operator<<(std::ostream &os, const BooleanColRowMatrix<IT> &mat) {
 324     for (unsigned r=0; r < mat.size(); ++r) {
 325         for (unsigned c=0; c < mat.size(); ++c)
 326             os << (mat.get(r,c) ? "X" : ".");
 327
 328         if (r < mat.size() - 1)
 329             os << std::endl;
 330     }
 331     return os;
 332 }
 333
 334 template<class IT>
 335 std::ostream& operator<<(std::ostream &os, BooleanColRowMatrix<IT> &mat) {
 336     const BooleanColRowMatrix<IT> &m = mat;
 337     return os << m;
 338 }
 339
 340 template<class IT, class D>
 341 std::ostream& operator<<(std::ostream &os, const BooleanRowMatrix_base<IT, D> &mat) {
 342     for (unsigned r=0; r < mat.height(); ++r) {
 343         // Get the sorted r-th row
 344         std::list<IT> row(mat.getRow(r).size());
 345         copy(mat.getRow(r).begin(), mat.getRow(r).end(), row.begin());
 346
 347         os << "|";
 348         // Print the elements, and remove them
 349         for (unsigned c=0; row.size() > 0; ++c) {
 350             if (row.front() == c) {
 351                 os << "X";
 352                 row.pop_front();
 353             } else
 354                 os << ".";
 355         }
 356
 357         if (r < mat.height() - 1)
 358             os << std::endl;
 359     }
 360     return os;
 361 }
 362
 363 template<class IT, class D>
 364 std::ostream& operator<<(std::ostream &os, BooleanRowMatrix_base<IT, D> &mat) {
 365     const BooleanRowMatrix_base<IT, D> &m = mat;
 366     return os << m;
 367 }
 368
 369 template<class IT, class D>
 370 std::ostream& operator<<(std::ostream &os, const BooleanColMatrix_base<IT, D> &mat) {
 371     // The sorted columns
 372     std::vector<std::list<IT> > cols;
 373     // The max height (max. value) of all columns
 374     IT height = 0;
 375
 376     for (unsigned c=0; c < mat.width(); ++c) {
 377         // Get the sorted c-th column
 378         std::list<IT> col(mat.getColumn(c).size());
 379         copy(mat.getColumn(c).begin(), mat.getColumn(c).end(), col.begin());
 380         cols.push_back(col);
 381
 382         os << "-";
 383
 384         if (col.size() != 0)
 385             height = std::max(height, col.back());
 386     }
 387
 388     os << std::endl;
 389
 390     for (unsigned r=0; r <= height; ++r) {
 391         // Print the elements, and remove them
 392         for (unsigned c=0; c < mat.width(); ++c) {
 393             std::list<IT> &col = cols.at(c);
 394             // This column is already empty
 395             if (col.size() == 0)
 396                 os << " ";
 397             else if (col.front() == r) {
 398                 os << "X";
 399                 col.pop_front();
 400             } else
 401                 os << ".";
 402         }
 403
 404         os << std::endl;
 405     }
 406     return os;
 407 }
 408
 409 template<class IT, class D>
 410 std::ostream& operator<<(std::ostream &os, BooleanColMatrix_base<IT, D> &mat) {
 411     const BooleanColMatrix_base<IT, D> &m = mat;
 412     return os << m;
 413 }
 414
 415 }
 416
 417 #endif