#include <ostream>
#include <iterator>
+#include "booleanvector.h"
namespace libstick {
public:
typedef IT index_type;
- typedef std::vector<index_type> column_type;
+ typedef sorted_boolean_vector<IT> column_type;
typedef D derived;
protected:
return cols.size();
}
- /** Get height of the matrix, i.e. maximum row-index + 1 among all columns. */
+ /** 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)
/** 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 = get_column(c);
- return binary_search(col.begin(), col.end(), r);
+ return get_column(c).get(r);
}
/** Set the matrix entry at row 'r' and column 'c'. */
get_derived()->_set(r, c, value);
}
- /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific 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);
assert(c < width());
// Flip all entries that are set in 'col'.
- for (typename column_type::const_iterator it = col.begin(); it != col.end(); ++it)
+ for (typename column_type::indexarray::const_iterator it = col.get_ones().begin();
+ it != col.get_ones().end(); ++it)
set(*it, c, !get(*it, c));
}
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) {
+ const typename column_type::indexarray &ones = col.get_ones();
+ typename column_type::indexarray::iterator it = ones.begin();
+
+ for (typename column_type::indexarray::iterator it = ones.begin();
+ it != ones.end(); ++it) {
if (first)
first = false;
else
/** 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
- // C++11 would have is_sorted
- for (unsigned i=1; i < col.size(); i++)
- assert(col[i-1] < col[i]);
-#endif
+ cols.at(c).set(r, value);
}
protected:
base::_set(r, c, value);
}
- /** A faster implementation of boolean_colmatrix_base::add_column().
- * Assumes that 'col' is sorted. */
+ /** A faster implementation of boolean_colmatrix_base::add_column(). */
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());
+ base::cols[c].add(col);
}
private:
- /** A temporary container to speed up add_column() */
- column_type tcol;
};
public:
typedef IT index_type;
- typedef std::vector<index_type> row_type;
+ typedef sorted_boolean_vector<IT> row_type;
typedef D derived;
protected:
/** 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 = get_row(r);
- return binary_search(row.begin(), row.end(), c);
+ return get_row(r).get(c);
}
/** Set the matrix entry at row 'r' and column 'c'. */
get_derived()->_set(r, c, value);
}
- /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific 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);
assert(r < height());
// Flip all entries that are set in 'row'.
- for (typename row_type::const_iterator it = row.begin(); it != row.end(); ++it)
+ for (typename row_type::indexarray::const_iterator it = row.get_ones().begin();
+ it != row.get_ones().end(); ++it)
set(r, *it, !get(r, *it));
}
/** 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
- // C++11 would have is_sorted
- for (unsigned i=1; i < row.size(); i++)
- assert(row[i-1] < row[i]);
-#endif
+ rows.at(r).set(c, value);
}
protected:
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);
+ set(col.get_ones()[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);
+ assert(get(r, row.get_ones()[i]) == true);
}
}
colbase::set(r, c, value);
}
- /** For each of the 'count'-many (row-index, column-pair) pair in 'indices', set the specific 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);
}
/** Counts the number of common elements in two sorted vectors. Equal to
* counting the number of elements given by std::set_intersection. */
template <class InputIterator1, class InputIterator2>
-size_t count_set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
+size_t count_set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
{
size_t count = 0;
return count;
}
-/** Multiply a*b and save the product in 'result'. It is assumed that 'result' is intially empty and has appropriate size. */
+/** 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 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());
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, D2>::column_type &col = b.get_column(c);
- if (count_set_intersection(row.begin(), row.end(), col.begin(), col.end()) % 2 == 1)
+ if (count_set_intersection(
+ row.get_ones().begin(), row.get_ones().end(),
+ col.get_ones().begin(), col.get_ones().end()) % 2 == 1)
result.set(r, c, true);
}
}
projects / libstick.git / blobdiff