namespace libstick {
-/** The base class of BooleanColMatrix and BooleanColRowMatrix which implements
+/** The base class of boolean_colmatrix and boolean_colrowmatrix which implements
* the common logic of both. */
template<class IT, class D>
-class BooleanColMatrix_base {
+class boolean_colmatrix_base {
public:
typedef IT index_type;
typedef std::vector<index_type> column_type;
typedef D derived;
+ protected:
/** Create a matrix with 'width' columns, initalized with zero entries. */
- BooleanColMatrix_base(size_t width) :
+ boolean_colmatrix_base(size_t width) :
cols(width) {
}
+ public:
/** 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);
+ const column_type &col = get_column(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_derived()->_set(r, c, value);
+ }
+
+ /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific value. */
+ void set_all(index_type indices[][2], size_t count, bool value) {
+ for (unsigned i=0; i < count; ++i)
+ set(indices[i][0], indices[i][1], value);
}
/** Get the c-th column. */
- const column_type& getColumn(index_type c) const {
+ const column_type& get_column(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 addColumn(index_type c, const column_type &col) {
+ void add_column(index_type c, const column_type &col) {
assert(c < width());
// Flip all entries that are set in 'col'.
}
/** Two matrices are equal iff they have the same entries */
- bool operator==(const BooleanColMatrix_base<IT, D> &m) const {
+ bool operator==(const boolean_colmatrix_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 {
+ bool operator!=(const boolean_colmatrix_base<IT, D> &m) const {
return !(*this == m);
}
- protected:
-
+ /** Print index pairs of the 1s as { {r, c}, {r, c}, {r, c} } */
+ void print_indexpairs(std::ostream &os) const {
+ bool first=true;
+
+ os << "{";
+ for (unsigned c=0; c < width(); ++c) {
+ const column_type &col = get_column(c);
+ for (typename column_type::const_iterator it = col.begin(); it != col.end(); ++it) {
+ if (first)
+ first = false;
+ else
+ os << ",";
+ os << " {" << *it << ", " << c << "}";
+ }
+ }
+ os << " }";
+ }
+ protected:
/** Set the matrix entry at row 'r' and column 'c'. */
void _set(index_type r, index_type c, bool value) {
assert(c < width());
std::vector<column_type> cols;
/** A cast to the derived type */
- derived* getDerived() {
+ derived* get_derived() {
return static_cast<derived*>(this);
}
};
* 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> > {
+class boolean_colmatrix : public boolean_colmatrix_base<IT, boolean_colmatrix<IT> > {
public:
typedef IT index_type;
- typedef BooleanColMatrix_base<IT, BooleanColMatrix<IT> > base;
+ typedef boolean_colmatrix_base<IT, boolean_colmatrix<IT> > base;
/** Create a matrix with 'width' columns, initalized with zero entries. */
- BooleanColMatrix(size_t columns) :
+ boolean_colmatrix(size_t columns) :
base(columns) {
}
};
-/** The base class of BooleanRowMatrix and BooleanColRowMatrix which implements
+/** The base class of boolean_rowmatrix and boolean_colrowmatrix which implements
* the common logic of both. */
template<class IT, class D>
-class BooleanRowMatrix_base {
+class boolean_rowmatrix_base {
public:
typedef IT index_type;
typedef std::vector<index_type> row_type;
typedef D derived;
+ protected:
/** Create a matrix with 'height' rows, initalized with zero entries.
* */
- BooleanRowMatrix_base(size_t height) :
+ boolean_rowmatrix_base(size_t height) :
rows(height) {
}
+ public:
/** 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);
+ const row_type &row = get_row(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_derived()->_set(r, c, value);
+ }
+
+ /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific value. */
+ void set_all(index_type indices[][2], size_t count, bool value) {
+ for (unsigned i=0; i < count; ++i)
+ set(indices[i][0], indices[i][1], value);
}
/** Get the r-th row. */
- const row_type& getRow(index_type r) const {
+ const row_type& get_row(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 addRow(index_type r, const row_type &row) {
+ void add_row(index_type r, const row_type &row) {
assert(r < height());
// Flip all entries that are set in 'row'.
}
/** Two matrices are equal iff they have the same entries */
- bool operator==(const BooleanRowMatrix_base<IT, D> &m) const {
+ bool operator==(const boolean_rowmatrix_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 {
+ bool operator!=(const boolean_rowmatrix_base<IT, D> &m) const {
return !(*this == m);
}
}
private:
- derived* getDerived() {
+ derived* get_derived() {
return static_cast<derived*>(this);
}
* 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> > {
+class boolean_rowmatrix : public boolean_rowmatrix_base<IT, boolean_rowmatrix<IT> > {
public:
typedef IT index_type;
- typedef BooleanRowMatrix_base<IT, BooleanRowMatrix<IT> > base;
+ typedef boolean_rowmatrix_base<IT, boolean_rowmatrix<IT> > base;
/** Create a matrix with 'height' rows, initalized with zero entries. */
- BooleanRowMatrix(size_t height) :
+ boolean_rowmatrix(size_t height) :
base(height) {
}
/** 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> > {
+class boolean_colrowmatrix : public boolean_colmatrix_base<IT, boolean_colrowmatrix<IT> >,
+ public boolean_rowmatrix_base<IT, boolean_colrowmatrix<IT> > {
public:
- typedef BooleanColMatrix_base<IT, BooleanColRowMatrix<IT> > colbase;
- typedef BooleanRowMatrix_base<IT, BooleanColRowMatrix<IT> > rowbase;
+ typedef boolean_colmatrix_base<IT, boolean_colrowmatrix<IT> > colbase;
+ typedef boolean_rowmatrix_base<IT, boolean_colrowmatrix<IT> > rowbase;
public:
typedef IT index_type;
/** Create a size x size matrix, initialized with zeros. */
- BooleanColRowMatrix(size_t size) :
+ boolean_colrowmatrix(size_t size) :
colbase(size),
rowbase(size) {
}
colbase::set(r, c, value);
}
+ /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific value. */
+ void set_all(index_type indices[][2], size_t count, bool value) {
+ colbase::set_all(indices, count, 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));
}
/** Two matrices are equal iff they have the same entries */
- bool operator==(const BooleanColRowMatrix<IT> &m) const {
+ bool operator==(const boolean_colrowmatrix<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 {
+ bool operator!=(const boolean_colrowmatrix<IT> &m) const {
return !(*this == m);
}
/** Multiply with matrix b from the right */
template<class D>
- BooleanColRowMatrix<IT> operator*(const BooleanColMatrix_base<IT, D> &b) {
- BooleanColRowMatrix<IT> c(size());
+ boolean_colrowmatrix<IT> operator*(const boolean_colmatrix_base<IT, D> &b) const {
+ boolean_colrowmatrix<IT> c(size());
multiply_matrix(c, *this, b);
return c;
}
}
/** Multiply a*b and save the product in 'result'. It is assumed that 'result' is intially empty and has appropriate size. */
-template<class IT, class D, class RT>
-void multiply_matrix(RT &result, const BooleanRowMatrix_base<IT, D> &a, const BooleanColMatrix_base<IT, D> &b) {
+template<class IT, class D1, class D2, class RT>
+void multiply_matrix(RT &result, const boolean_rowmatrix_base<IT, D1> &a, const boolean_colmatrix_base<IT, D2> &b) {
assert(a.height() == b.width());
for (unsigned r=0; r < a.height(); ++r) {
- const typename BooleanRowMatrix_base<IT, D>::row_type &row = a.getRow(r);
+ const typename boolean_rowmatrix_base<IT, D1>::row_type &row = a.get_row(r);
for (unsigned c=0; c < b.width(); ++c) {
- const typename BooleanColMatrix_base<IT, D>::column_type &col = b.getColumn(c);
+ const typename boolean_colmatrix_base<IT, D2>::column_type &col = b.get_column(c);
if (count_set_intersection(row.begin(), row.end(), col.begin(), col.end()) % 2 == 1)
result.set(r, c, true);
}
}
template<class MT>
-MT unitMatrix(size_t size) {
+MT create_unit_matrix(size_t size) {
MT mat(size);
for (unsigned i=0; i < size; ++i)
mat.set(i, i, true);
}
template<class IT>
-std::ostream& operator<<(std::ostream &os, const BooleanColRowMatrix<IT> &mat) {
+std::ostream& operator<<(std::ostream &os, const boolean_colrowmatrix<IT> &mat) {
+
+ os << " ";
+ for (unsigned c=0; c < mat.size(); ++c) {
+ const unsigned d = (c % 10);
+ if (d > 0)
+ os << d;
+ else
+ os << " ";
+ }
+ os << std::endl;
+
for (unsigned r=0; r < mat.size(); ++r) {
+ const unsigned d = (r % 10);
+ if (d > 0)
+ os << d;
+ else
+ os << " ";
+
for (unsigned c=0; c < mat.size(); ++c)
os << (mat.get(r,c) ? "X" : ".");
}
template<class IT>
-std::ostream& operator<<(std::ostream &os, BooleanColRowMatrix<IT> &mat) {
- const BooleanColRowMatrix<IT> &m = mat;
+std::ostream& operator<<(std::ostream &os, boolean_colrowmatrix<IT> &mat) {
+ const boolean_colrowmatrix<IT> &m = mat;
return os << m;
}
template<class IT, class D>
-std::ostream& operator<<(std::ostream &os, const BooleanRowMatrix_base<IT, D> &mat) {
+std::ostream& operator<<(std::ostream &os, const boolean_rowmatrix_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());
+ std::list<IT> row(mat.get_row(r).size());
+ copy(mat.get_row(r).begin(), mat.get_row(r).end(), row.begin());
os << "|";
// Print the elements, and remove them
}
template<class IT, class D>
-std::ostream& operator<<(std::ostream &os, BooleanRowMatrix_base<IT, D> &mat) {
- const BooleanRowMatrix_base<IT, D> &m = mat;
+std::ostream& operator<<(std::ostream &os, boolean_rowmatrix_base<IT, D> &mat) {
+ const boolean_rowmatrix_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) {
+std::ostream& operator<<(std::ostream &os, const boolean_colmatrix_base<IT, D> &mat) {
// The sorted columns
std::vector<std::list<IT> > cols;
// The max height (max. value) of all columns
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());
+ std::list<IT> col(mat.get_column(c).size());
+ copy(mat.get_column(c).begin(), mat.get_column(c).end(), col.begin());
cols.push_back(col);
os << "-";
}
template<class IT, class D>
-std::ostream& operator<<(std::ostream &os, BooleanColMatrix_base<IT, D> &mat) {
- const BooleanColMatrix_base<IT, D> &m = mat;
+std::ostream& operator<<(std::ostream &os, boolean_colmatrix_base<IT, D> &mat) {
+ const boolean_colmatrix_base<IT, D> &m = mat;
return os << m;
}