namespace libstick {
+template<class T>
+std::ostream& operator<<(std::ostream &, const std::vector<T> &);
+
+
/** The base class of boolean_colmatrix and boolean_colrowmatrix which implements
* the common logic of both. */
template<class IT, class D>
typedef std::vector<index_type> column_type;
typedef D derived;
+ protected:
/** Create a matrix with 'width' columns, initalized with zero entries. */
boolean_colmatrix_base(size_t width) :
cols(width) {
}
- /** Get height resp. width of the matrix. */
+ public:
+ /** A casting constructor for any colmatrix with same entries type. */
+ template<class D2>
+ boolean_colmatrix_base(const boolean_colmatrix_base<IT, D2> &mat) :
+ cols(mat.get_columns()) {
+ }
+
+ /** Get width of the matrix. */
size_t width() const {
return cols.size();
}
+ /** Get height of the matrix, i.e. maximum row-index + 1 among all columns. */
+ size_t height() const {
+ IT h = 0;
+ for (unsigned c=0; c < width(); ++c)
+ if (cols[c].size() > 0)
+ h = std::max(h, cols[c].back());
+ return h+1;
+ }
+
/** Get the matrix entry at row 'r' and column 'c'. */
bool get(index_type r, index_type c) const {
assert(c < width());
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& get_column(index_type c) const {
assert(c < width());
return cols[c];
}
+ /** Get all columns */
+ const std::vector<column_type>& get_columns() const {
+ return cols;
+ }
+
/** 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) {
}
/** Two matrices are equal iff they have the same entries */
- bool operator==(const boolean_colmatrix_base<IT, D> &m) const {
- return cols == m.cols;
+ template<class D2>
+ bool operator==(const boolean_colmatrix_base<IT, D2> &m) const {
+ return cols == m.get_columns();
}
/** Two matrices are equal iff they have the same entries */
- bool operator!=(const boolean_colmatrix_base<IT, D> &m) const {
+ template<class D2>
+ bool operator!=(const boolean_colmatrix_base<IT, D2> &m) const {
return !(*this == m);
}
+ /** 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) {
#endif
}
- private:
+ protected:
/** The matrix is the set of columns. */
std::vector<column_type> cols;
public:
typedef IT index_type;
typedef boolean_colmatrix_base<IT, boolean_colmatrix<IT> > base;
+ typedef typename base::column_type column_type;
/** Create a matrix with 'width' columns, initalized with zero entries. */
boolean_colmatrix(size_t columns) :
void _set(index_type r, index_type c, bool value) {
base::_set(r, c, value);
}
+
+ /** A faster implementation of boolean_colmatrix_base::add_column().
+ * Assumes that 'col' is sorted. */
+ void add_column(index_type c, const column_type &col) {
+ assert(c < base::width());
+
+#ifndef NDEBUG
+ for (unsigned i=1; i < col.size(); ++i)
+ assert(col[i-1] < col[i]);
+#endif
+
+ // The original column
+ column_type &orig_col = base::cols[c];
+
+ // Make target column large enough
+ const size_t maxsize = orig_col.size() + col.size();
+ if (tcol.size() < maxsize)
+ tcol.resize(maxsize);
+
+ // Compute symmetric difference
+ typename column_type::iterator it = std::set_symmetric_difference(
+ orig_col.begin(), orig_col.end(), col.begin(), col.end(), tcol.begin());
+
+ // Copy back to the original column
+ orig_col.resize(it - tcol.begin());
+ std::copy(tcol.begin(), it, orig_col.begin());
+ }
+
+ private:
+ /** A temporary container to speed up add_column() */
+ column_type tcol;
};
typedef std::vector<index_type> row_type;
typedef D derived;
+ protected:
/** Create a matrix with 'height' rows, initalized with zero entries.
* */
boolean_rowmatrix_base(size_t height) :
rows(height) {
}
- /** Get height resp. width of the matrix. */
+ public:
+ /** Get height of the matrix. */
size_t height() const {
return rows.size();
}
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& get_row(index_type r) const {
assert(r < height());
#endif
}
- private:
+ protected:
derived* get_derived() {
return static_cast<derived*>(this);
}
rowbase(size) {
}
+ /** Casting a colmatrix into a colrow matrix */
+ template<class D>
+ boolean_colrowmatrix(const boolean_colmatrix_base<IT, D>& mat) :
+ colbase(std::max(mat.width(), mat.height())),
+ rowbase(std::max(mat.width(), mat.height())) {
+ for (unsigned c=0; c < mat.width(); ++c) {
+ const typename colbase::column_type &col = mat.get_column(c);
+ for (unsigned i=0; i < col.size(); ++i)
+ set(col[i], c, true);
+ }
+ for (unsigned r=0; r < size(); ++r) {
+ const typename rowbase::row_type &row = rowbase::get_row(r);
+ for (unsigned i=0; i < row.size(); ++i)
+ assert(get(r, row[i]) == true);
+ }
+ }
+
/** Override implementation. */
void _set(index_type r, index_type c, bool value) {
colbase::_set(r, c, value);
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));
return colbase::operator==(m);
}
+ /** Two matrices are equal iff they have the same entries */
+ template<class D>
+ bool operator==(const boolean_colmatrix_base<IT, D> &m) const {
+ return colbase::operator==(m);
+ }
+
/** Two matrices are equal iff they have the same entries */
bool operator!=(const boolean_colrowmatrix<IT> &m) const {
return !(*this == m);
/** Multiply with matrix b from the right */
template<class D>
- boolean_colrowmatrix<IT> operator*(const boolean_colmatrix_base<IT, D> &b) {
+ boolean_colrowmatrix<IT> operator*(const boolean_colmatrix_base<IT, D> &b) const {
boolean_colrowmatrix<IT> c(size());
multiply_matrix(c, *this, b);
return c;
size_t count = 0;
// As long as we did not either end, look for common elements
- while (first1!=last1 && first2!=last2)
+ while (first1 != last1 && first2 != last2)
{
if (*first1 < *first2)
++first1;
}
/** 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 boolean_rowmatrix_base<IT, D> &a, const boolean_colmatrix_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 boolean_rowmatrix_base<IT, D>::row_type &row = a.get_row(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 boolean_colmatrix_base<IT, D>::column_type &col = b.get_column(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 IT>
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" : ".");
return os << m;
}
+template<class T>
+std::ostream& operator<<(std::ostream& os, const std::vector<T> &vec) {
+ os << "[";
+
+ typename std::vector<T>::const_iterator it = vec.begin();
+ while ( it != vec.end()) {
+ os << *it;
+ if (++it != vec.end())
+ os << " ";
+ }
+
+ os << "]";
+ return os;
+}
+
}
#endif
projects / libstick.git / blobdiff