X-Git-Url: https://git.sthu.org/?p=libstick.git;a=blobdiff_plain;f=include%2Flibstick-0.1%2Fbooleanmatrix.h;h=774aeb73095c6abb2738d49d9f6d8ad63f88ddbc;hp=894892f0f3f4a0fc7e38d118a609f4a2701b8a3c;hb=88ea14f1e9079c9b8c4af7aff01a3fe960e9472b;hpb=929c696bfb48aa0f96ce2b70b1b926b5f2b2dede diff --git a/include/libstick-0.1/booleanmatrix.h b/include/libstick-0.1/booleanmatrix.h index 894892f..774aeb7 100644 --- a/include/libstick-0.1/booleanmatrix.h +++ b/include/libstick-0.1/booleanmatrix.h @@ -15,10 +15,10 @@ 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 BooleanColMatrix_base { +class boolean_colmatrix_base { public: typedef IT index_type; @@ -26,7 +26,7 @@ class BooleanColMatrix_base { typedef D derived; /** Create a matrix with 'width' columns, initalized with zero entries. */ - BooleanColMatrix_base(size_t width) : + boolean_colmatrix_base(size_t width) : cols(width) { } @@ -38,24 +38,24 @@ class BooleanColMatrix_base { /** 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); } /** 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'. @@ -64,18 +64,16 @@ class BooleanColMatrix_base { } /** Two matrices are equal iff they have the same entries */ - bool operator==(const BooleanColMatrix_base &m) const { + bool operator==(const boolean_colmatrix_base &m) const { return cols == m.cols; } /** Two matrices are equal iff they have the same entries */ - bool operator!=(const BooleanColMatrix_base &m) const { + bool operator!=(const boolean_colmatrix_base &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()); @@ -112,7 +110,7 @@ class BooleanColMatrix_base { std::vector cols; /** A cast to the derived type */ - derived* getDerived() { + derived* get_derived() { return static_cast(this); } }; @@ -122,14 +120,14 @@ class BooleanColMatrix_base { * 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 BooleanColMatrix : public BooleanColMatrix_base > { +class boolean_colmatrix : public boolean_colmatrix_base > { public: typedef IT index_type; - typedef BooleanColMatrix_base > base; + typedef boolean_colmatrix_base > base; /** Create a matrix with 'width' columns, initalized with zero entries. */ - BooleanColMatrix(size_t columns) : + boolean_colmatrix(size_t columns) : base(columns) { } @@ -140,10 +138,10 @@ class BooleanColMatrix : public BooleanColMatrix_base > }; -/** 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 BooleanRowMatrix_base { +class boolean_rowmatrix_base { public: typedef IT index_type; @@ -152,7 +150,7 @@ class BooleanRowMatrix_base { /** Create a matrix with 'height' rows, initalized with zero entries. * */ - BooleanRowMatrix_base(size_t height) : + boolean_rowmatrix_base(size_t height) : rows(height) { } @@ -164,24 +162,24 @@ class BooleanRowMatrix_base { /** 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); } /** 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'. @@ -190,12 +188,12 @@ class BooleanRowMatrix_base { } /** Two matrices are equal iff they have the same entries */ - bool operator==(const BooleanRowMatrix_base &m) const { + bool operator==(const boolean_rowmatrix_base &m) const { return rows == m.rows; } /** Two matrices are equal iff they have the same entries */ - bool operator!=(const BooleanRowMatrix_base &m) const { + bool operator!=(const boolean_rowmatrix_base &m) const { return !(*this == m); } @@ -232,7 +230,7 @@ class BooleanRowMatrix_base { } private: - derived* getDerived() { + derived* get_derived() { return static_cast(this); } @@ -245,14 +243,14 @@ class BooleanRowMatrix_base { * 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 BooleanRowMatrix : public BooleanRowMatrix_base > { +class boolean_rowmatrix : public boolean_rowmatrix_base > { public: typedef IT index_type; - typedef BooleanRowMatrix_base > base; + typedef boolean_rowmatrix_base > base; /** Create a matrix with 'height' rows, initalized with zero entries. */ - BooleanRowMatrix(size_t height) : + boolean_rowmatrix(size_t height) : base(height) { } @@ -266,18 +264,18 @@ class BooleanRowMatrix : public BooleanRowMatrix_base > /** This is a boolean matrix that supports. It is designed to handle a * few 1s and row- and column-wise operations well. */ template -class BooleanColRowMatrix : public BooleanColMatrix_base >, - public BooleanRowMatrix_base > { +class boolean_colrowmatrix : public boolean_colmatrix_base >, + public boolean_rowmatrix_base > { public: - typedef BooleanColMatrix_base > colbase; - typedef BooleanRowMatrix_base > rowbase; + typedef boolean_colmatrix_base > colbase; + typedef boolean_rowmatrix_base > 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) { } @@ -310,20 +308,20 @@ class BooleanColRowMatrix : public BooleanColMatrix_base &m) const { + bool operator==(const boolean_colrowmatrix &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 &m) const { + bool operator!=(const boolean_colrowmatrix &m) const { return !(*this == m); } /** Multiply with matrix b from the right */ template - BooleanColRowMatrix operator*(const BooleanColMatrix_base &b) { - BooleanColRowMatrix c(size()); + boolean_colrowmatrix operator*(const boolean_colmatrix_base &b) { + boolean_colrowmatrix c(size()); multiply_matrix(c, *this, b); return c; } @@ -356,13 +354,13 @@ size_t count_set_intersection (InputIterator1 first1, InputIterator1 last1, Inpu /** Multiply a*b and save the product in 'result'. It is assumed that 'result' is intially empty and has appropriate size. */ template -void multiply_matrix(RT &result, const BooleanRowMatrix_base &a, const BooleanColMatrix_base &b) { +void multiply_matrix(RT &result, const boolean_rowmatrix_base &a, const boolean_colmatrix_base &b) { assert(a.height() == b.width()); for (unsigned r=0; r < a.height(); ++r) { - const typename BooleanRowMatrix_base::row_type &row = a.getRow(r); + const typename boolean_rowmatrix_base::row_type &row = a.get_row(r); for (unsigned c=0; c < b.width(); ++c) { - const typename BooleanColMatrix_base::column_type &col = b.getColumn(c); + const typename boolean_colmatrix_base::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); } @@ -370,7 +368,7 @@ void multiply_matrix(RT &result, const BooleanRowMatrix_base &a, const Bo } template -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); @@ -378,7 +376,7 @@ MT unitMatrix(size_t size) { } template -std::ostream& operator<<(std::ostream &os, const BooleanColRowMatrix &mat) { +std::ostream& operator<<(std::ostream &os, const boolean_colrowmatrix &mat) { for (unsigned r=0; r < mat.size(); ++r) { for (unsigned c=0; c < mat.size(); ++c) os << (mat.get(r,c) ? "X" : "."); @@ -390,17 +388,17 @@ std::ostream& operator<<(std::ostream &os, const BooleanColRowMatrix &mat) { } template -std::ostream& operator<<(std::ostream &os, BooleanColRowMatrix &mat) { - const BooleanColRowMatrix &m = mat; +std::ostream& operator<<(std::ostream &os, boolean_colrowmatrix &mat) { + const boolean_colrowmatrix &m = mat; return os << m; } template -std::ostream& operator<<(std::ostream &os, const BooleanRowMatrix_base &mat) { +std::ostream& operator<<(std::ostream &os, const boolean_rowmatrix_base &mat) { for (unsigned r=0; r < mat.height(); ++r) { // Get the sorted r-th row - std::list row(mat.getRow(r).size()); - copy(mat.getRow(r).begin(), mat.getRow(r).end(), row.begin()); + std::list 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 @@ -419,13 +417,13 @@ std::ostream& operator<<(std::ostream &os, const BooleanRowMatrix_base &m } template -std::ostream& operator<<(std::ostream &os, BooleanRowMatrix_base &mat) { - const BooleanRowMatrix_base &m = mat; +std::ostream& operator<<(std::ostream &os, boolean_rowmatrix_base &mat) { + const boolean_rowmatrix_base &m = mat; return os << m; } template -std::ostream& operator<<(std::ostream &os, const BooleanColMatrix_base &mat) { +std::ostream& operator<<(std::ostream &os, const boolean_colmatrix_base &mat) { // The sorted columns std::vector > cols; // The max height (max. value) of all columns @@ -433,8 +431,8 @@ std::ostream& operator<<(std::ostream &os, const BooleanColMatrix_base &m for (unsigned c=0; c < mat.width(); ++c) { // Get the sorted c-th column - std::list col(mat.getColumn(c).size()); - copy(mat.getColumn(c).begin(), mat.getColumn(c).end(), col.begin()); + std::list col(mat.get_column(c).size()); + copy(mat.get_column(c).begin(), mat.get_column(c).end(), col.begin()); cols.push_back(col); os << "-"; @@ -465,8 +463,8 @@ std::ostream& operator<<(std::ostream &os, const BooleanColMatrix_base &m } template -std::ostream& operator<<(std::ostream &os, BooleanColMatrix_base &mat) { - const BooleanColMatrix_base &m = mat; +std::ostream& operator<<(std::ostream &os, boolean_colmatrix_base &mat) { + const boolean_colmatrix_base &m = mat; return os << m; }