X-Git-Url: https://git.sthu.org/?a=blobdiff_plain;f=include%2Flibstick-0.1%2Fbooleanmatrix.h;h=8626f53d58eca6c755737b29f16e37bebd316399;hb=4b8265e5bcfd2332a3333c4129352e10c2d59c2f;hp=894892f0f3f4a0fc7e38d118a609f4a2701b8a3c;hpb=929c696bfb48aa0f96ce2b70b1b926b5f2b2dede;p=libstick.git

diff --git a/include/libstick-0.1/booleanmatrix.h b/include/libstick-0.1/booleanmatrix.h
index 894892f..8626f53 100644
--- a/include/libstick-0.1/booleanmatrix.h
+++ b/include/libstick-0.1/booleanmatrix.h
@@ -15,21 +15,23 @@
 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();
@@ -38,24 +40,30 @@ 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);
+        }
+
+        /** 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'.
@@ -64,18 +72,34 @@ class BooleanColMatrix_base {
         }
 
         /** 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());
@@ -112,7 +136,7 @@ class BooleanColMatrix_base {
         std::vector<column_type> cols;
 
         /** A cast to the derived type */
-        derived* getDerived() {
+        derived* get_derived() {
             return static_cast<derived*>(this);
         }
 };
@@ -122,14 +146,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 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) {
         }
 
@@ -140,22 +164,24 @@ class BooleanColMatrix : public BooleanColMatrix_base<IT, BooleanColMatrix<IT> >
 };
 
 
-/** 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();
@@ -164,24 +190,30 @@ 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);
+        }
+
+        /** 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'.
@@ -190,12 +222,12 @@ class BooleanRowMatrix_base {
         }
 
         /** 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);
         }
 
@@ -232,7 +264,7 @@ class BooleanRowMatrix_base {
         }
 
     private:
-        derived* getDerived() {
+        derived* get_derived() {
             return static_cast<derived*>(this);
         }
 
@@ -245,14 +277,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 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) {
         }
 
@@ -266,18 +298,18 @@ class BooleanRowMatrix : public BooleanRowMatrix_base<IT, BooleanRowMatrix<IT> >
 /** 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) {
         }
@@ -303,6 +335,11 @@ class BooleanColRowMatrix : public BooleanColMatrix_base<IT, BooleanColRowMatrix
             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));
@@ -310,20 +347,20 @@ class BooleanColRowMatrix : public BooleanColMatrix_base<IT, BooleanColRowMatrix
         }
 
         /** 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;
         }
@@ -338,7 +375,7 @@ size_t count_set_intersection (InputIterator1 first1, InputIterator1 last1, Inpu
     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;
@@ -355,14 +392,14 @@ 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<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);
         }
@@ -370,7 +407,7 @@ void multiply_matrix(RT &result, const BooleanRowMatrix_base<IT, D> &a, const Bo
 }
 
 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);
@@ -378,8 +415,25 @@ MT unitMatrix(size_t size) {
 }
 
 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" : ".");
 
@@ -390,17 +444,17 @@ std::ostream& operator<<(std::ostream &os, const BooleanColRowMatrix<IT> &mat) {
 }
 
 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
@@ -419,13 +473,13 @@ std::ostream& operator<<(std::ostream &os, const BooleanRowMatrix_base<IT, D> &m
 }
 
 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
@@ -433,8 +487,8 @@ std::ostream& operator<<(std::ostream &os, const BooleanColMatrix_base<IT, D> &m
 
     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 << "-";
@@ -465,8 +519,8 @@ std::ostream& operator<<(std::ostream &os, const BooleanColMatrix_base<IT, D> &m
 }
 
 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;
 }