--- /dev/null
+#ifndef booleanmatrix_h_AechohNgakoghahV
+#define booleanmatrix_h_AechohNgakoghahV
+
+#include <stdint.h>
+#include <cassert>
+#include <cstdlib>
+#include <algorithm>
+#include <vector>
+#include <list>
+#include <set>
+#include <ostream>
+#include <iterator>
+
+
+namespace libstick {
+
+
+/** The base class of BooleanColMatrix and BooleanColRowMatrix which implements
+ * the common logic of both. */
+template<class IT, class D>
+class BooleanColMatrix_base {
+
+ public:
+ typedef IT index_type;
+ typedef std::vector<index_type> column_type;
+ typedef D derived;
+
+ /** Create a matrix with 'width' columns, initalized with zero entries. */
+ BooleanColMatrix_base(size_t width) :
+ cols(width) {
+ }
+
+ /** Get height resp. width of the matrix. */
+ size_t width() const {
+ return cols.size();
+ }
+
+ /** Get the matrix entry at row 'r' and column 'c'. */
+ bool get(index_type r, index_type c) const {
+ assert(c < width());
+ const column_type &col = getColumn(c);
+ return binary_search(col.begin(), col.end(), r);
+ }
+
+ /** Set the matrix entry at row 'r' and column 'c'. */
+ void set(index_type r, index_type c, bool value) {
+ getDerived()->_set(r, c, value);
+ }
+
+ /** Get the c-th column. */
+ const column_type& getColumn(index_type c) const {
+ assert(c < width());
+ return cols[c];
+ }
+
+ /** Add the column-vector 'col' to the c-th column. Note that 'col'
+ * actually contains the list of row-indices that are 1. */
+ void add_column(index_type c, const column_type &col) {
+ assert(c < width());
+
+ // Flip all entries that are set in 'col'.
+ for (typename column_type::const_iterator it = col.begin(); it != col.end(); ++it)
+ set(*it, c, !get(*it, c));
+ }
+
+ /** Two matrices are equal iff they have the same entries */
+ bool operator==(const BooleanColMatrix_base<IT, D> &m) const {
+ return cols == m.cols;
+ }
+
+ /** Two matrices are equal iff they have the same entries */
+ bool operator!=(const BooleanColMatrix_base<IT, D> &m) const {
+ return !(*this == m);
+ }
+
+ protected:
+
+
+ /** Set the matrix entry at row 'r' and column 'c'. */
+ void _set(index_type r, index_type c, bool value) {
+ assert(c < width());
+
+ column_type &col = cols.at(c);
+ // Let us see where to insert the new element
+ typename column_type::iterator it = lower_bound(col.begin(), col.end(), r);
+ bool exists = (it != col.end() && *it == r);
+ assert(get(r,c) == exists);
+
+ // Add 'r' to c-th column
+ if (value) {
+ // r is new, insert it
+ if (!exists)
+ col.insert(it, r);
+ assert(get(r,c));
+ }
+ // Remove the element
+ else {
+ if (exists)
+ col.erase(it);
+ assert(!get(r,c));
+ }
+
+#ifndef NDEBUG
+ for (unsigned i=1; i < col.size(); i++)
+ assert(col[i-1] < col[i]);
+#endif
+ }
+
+ private:
+ /** The matrix is the set of columns. */
+ std::vector<column_type> cols;
+
+ /** A cast to the derived type */
+ derived* getDerived() {
+ return static_cast<derived*>(this);
+ }
+};
+
+
+/** This is boolean matrix that is a std::vector of column-vectors and in each
+ * column-vector we save the row-indices of the 1s. It is designed to handle a
+ * few 1s and column-wise operations well. */
+template<class IT=uint32_t>
+class BooleanColMatrix : public BooleanColMatrix_base<IT, BooleanColMatrix<IT> > {
+
+ public:
+ typedef IT index_type;
+ typedef BooleanColMatrix_base<IT, BooleanColMatrix<IT> > base;
+
+ /** Create a matrix with 'width' columns, initalized with zero entries. */
+ BooleanColMatrix(size_t columns) :
+ base(columns) {
+ }
+
+ /** Set the matrix entry at row 'r' and column 'c'. */
+ void _set(index_type r, index_type c, bool value) {
+ base::_set(r, c, value);
+ }
+};
+
+
+/** The base class of BooleanRowMatrix and BooleanColRowMatrix which implements
+ * the common logic of both. */
+template<class IT, class D>
+class BooleanRowMatrix_base {
+
+ public:
+ typedef IT index_type;
+ typedef std::vector<index_type> row_type;
+ typedef D derived;
+
+ /** Create a matrix with 'height' rows, initalized with zero entries.
+ * */
+ BooleanRowMatrix_base(size_t height) :
+ rows(height) {
+ }
+
+ /** Get height resp. width of the matrix. */
+ size_t height() const {
+ return rows.size();
+ }
+
+ /** Get the matrix entry at row 'r' and column 'c'. */
+ bool get(index_type r, index_type c) const {
+ assert(r < height());
+ const row_type &row = getRow(r);
+ return binary_search(row.begin(), row.end(), c);
+ }
+
+ /** Set the matrix entry at row 'r' and column 'c'. */
+ void set(index_type r, index_type c, bool value) {
+ getDerived()->_set(r, c, value);
+ }
+
+ /** Get the r-th row. */
+ const row_type& getRow(index_type r) const {
+ assert(r < height());
+ return rows[r];
+ }
+
+ /** Add the row-vector 'row' to the r-th row. Note that 'row'
+ * actually contains the list of column-indices that are 1. */
+ void add_row(index_type r, const row_type &row) {
+ assert(r < height());
+
+ // Flip all entries that are set in 'row'.
+ for (typename row_type::const_iterator it = row.begin(); it != row.end(); ++it)
+ set(r, *it, !get(r, *it));
+ }
+
+ /** Two matrices are equal iff they have the same entries */
+ bool operator==(const BooleanRowMatrix_base<IT, D> &m) const {
+ return rows == m.rows;
+ }
+
+ /** Two matrices are equal iff they have the same entries */
+ bool operator!=(const BooleanRowMatrix_base<IT, D> &m) const {
+ return !(*this == m);
+ }
+
+ protected:
+ /** Set the matrix entry at row 'r' and column 'c'. */
+ void _set(index_type r, index_type c, bool value) {
+ assert(r < height());
+
+ row_type &row = rows.at(r);
+ // Let us see where to insert/remove the new element
+ typename row_type::iterator it = lower_bound(row.begin(), row.end(), c);
+ bool exists = (it != row.end() && *it == c);
+ assert(get(r,c) == exists);
+
+ // Add 'r' to c-th column
+ if (value) {
+ // r is new, insert it
+ if (!exists)
+ row.insert(it, c);
+ assert(get(r,c));
+ }
+ // Remove the element
+ else {
+ if (exists)
+ row.erase(it);
+ assert(!get(r,c));
+ }
+
+#ifndef NDEBUG
+ for (unsigned i=1; i < row.size(); i++)
+ assert(row[i-1] < row[i]);
+#endif
+ }
+
+ private:
+ derived* getDerived() {
+ return static_cast<derived*>(this);
+ }
+
+ /** The matrix is the set of columns. */
+ std::vector<row_type> rows;
+};
+
+
+/** This is boolean matrix that is a std::vector of row-vectors and in each
+ * row-vector we save the column-indices of the 1s. It is designed to handle a
+ * few 1s and row-wise operations well. */
+template<class IT=uint32_t>
+class BooleanRowMatrix : public BooleanRowMatrix_base<IT, BooleanRowMatrix<IT> > {
+
+ public:
+ typedef IT index_type;
+ typedef BooleanRowMatrix_base<IT, BooleanRowMatrix<IT> > base;
+
+ /** Create a matrix with 'height' rows, initalized with zero entries. */
+ BooleanRowMatrix(size_t height) :
+ base(height) {
+ }
+
+ /** Set the matrix entry at row 'r' and column 'c'. */
+ void _set(index_type r, index_type c, bool value) {
+ base::_set(r, c, value);
+ }
+};
+
+
+/** This is a boolean matrix that supports. It is designed to handle a
+ * few 1s and row- and column-wise operations well. */
+template<class IT=uint32_t>
+class BooleanColRowMatrix : public BooleanColMatrix_base<IT, BooleanColRowMatrix<IT> >,
+ public BooleanRowMatrix_base<IT, BooleanColRowMatrix<IT> > {
+
+ public:
+ typedef BooleanColMatrix_base<IT, BooleanColRowMatrix<IT> > colbase;
+ typedef BooleanRowMatrix_base<IT, BooleanColRowMatrix<IT> > rowbase;
+
+ public:
+ typedef IT index_type;
+
+ /** Create a size x size matrix, initialized with zeros. */
+ BooleanColRowMatrix(size_t size) :
+ colbase(size),
+ rowbase(size) {
+ }
+
+ /** Override implementation. */
+ void _set(index_type r, index_type c, bool value) {
+ colbase::_set(r, c, value);
+ rowbase::_set(r, c, value);
+ }
+
+ public:
+ /** Get height resp. width of the matrix. */
+ size_t size() const {
+ assert(colbase::width() == rowbase::height());
+ return colbase::width();
+ }
+
+ /** Set the matrix entry at row 'r' and column 'c'. */
+ void set(index_type r, index_type c, bool value) {
+ //Calling set() for one base suffices, static polymorphism
+ //calls _set() anyhow.
+ //rowbase::set(r, c, value);
+ colbase::set(r, c, value);
+ }
+
+ /** Get the matrix entry at row 'r' and column 'c'. */
+ bool get(index_type r, index_type c) const {
+ assert(colbase::get(r, c) == rowbase::get(r, c));
+ return colbase::get(r, c);
+ }
+
+ /** Two matrices are equal iff they have the same entries */
+ bool operator==(const BooleanColRowMatrix<IT> &m) const {
+ assert(rowbase::operator==(m) == colbase::operator==(m));
+ return colbase::operator==(m);
+ }
+
+ /** Two matrices are equal iff they have the same entries */
+ bool operator!=(const BooleanColRowMatrix<IT> &m) const {
+ return !(*this == m);
+ }
+};
+
+template<class IT>
+std::ostream& operator<<(std::ostream &os, const BooleanColRowMatrix<IT> &mat) {
+ for (unsigned r=0; r < mat.size(); ++r) {
+ for (unsigned c=0; c < mat.size(); ++c)
+ os << (mat.get(r,c) ? "X" : ".");
+
+ if (r < mat.size() - 1)
+ os << std::endl;
+ }
+ return os;
+}
+
+template<class IT>
+std::ostream& operator<<(std::ostream &os, BooleanColRowMatrix<IT> &mat) {
+ const BooleanColRowMatrix<IT> &m = mat;
+ return os << m;
+}
+
+template<class IT, class D>
+std::ostream& operator<<(std::ostream &os, const BooleanRowMatrix_base<IT, D> &mat) {
+ for (unsigned r=0; r < mat.height(); ++r) {
+ // Get the sorted r-th row
+ std::list<IT> row(mat.getRow(r).size());
+ copy(mat.getRow(r).begin(), mat.getRow(r).end(), row.begin());
+
+ os << "|";
+ // Print the elements, and remove them
+ for (unsigned c=0; row.size() > 0; ++c) {
+ if (row.front() == c) {
+ os << "X";
+ row.pop_front();
+ } else
+ os << ".";
+ }
+
+ if (r < mat.height() - 1)
+ os << std::endl;
+ }
+ return os;
+}
+
+template<class IT, class D>
+std::ostream& operator<<(std::ostream &os, BooleanRowMatrix_base<IT, D> &mat) {
+ const BooleanRowMatrix_base<IT, D> &m = mat;
+ return os << m;
+}
+
+template<class IT, class D>
+std::ostream& operator<<(std::ostream &os, const BooleanColMatrix_base<IT, D> &mat) {
+ // The sorted columns
+ std::vector<std::list<IT> > cols;
+ // The max height (max. value) of all columns
+ IT height = 0;
+
+ for (unsigned c=0; c < mat.width(); ++c) {
+ // Get the sorted c-th column
+ std::list<IT> col(mat.getColumn(c).size());
+ copy(mat.getColumn(c).begin(), mat.getColumn(c).end(), col.begin());
+ cols.push_back(col);
+
+ os << "-";
+
+ if (col.size() != 0)
+ height = std::max(height, col.back());
+ }
+
+ os << std::endl;
+
+ for (unsigned r=0; r <= height; ++r) {
+ // Print the elements, and remove them
+ for (unsigned c=0; c < mat.width(); ++c) {
+ std::list<IT> &col = cols.at(c);
+ // This column is already empty
+ if (col.size() == 0)
+ os << " ";
+ else if (col.front() == r) {
+ os << "X";
+ col.pop_front();
+ } else
+ os << ".";
+ }
+
+ os << std::endl;
+ }
+ return os;
+}
+
+template<class IT, class D>
+std::ostream& operator<<(std::ostream &os, BooleanColMatrix_base<IT, D> &mat) {
+ const BooleanColMatrix_base<IT, D> &m = mat;
+ return os << m;
+}
+
+}
+
+#endif
projects / libstick.git / blobdiff