From 54836e4fa90f52c9682c7918c47b28177e6f4170 Mon Sep 17 00:00:00 2001
From: Stefan Huber <shuber@sthu.org>
Date: Thu, 9 Jan 2014 21:25:09 +0100
Subject: [PATCH] Use boolean_vector in boolean_matrix

---
 include/libstick-0.1/booleanmatrix.h | 114 ++++++---------------------
 include/libstick-0.1/booleanvector.h |  10 +++
 tests/booleanmatrix.h                |  16 ++--
 3 files changed, 42 insertions(+), 98 deletions(-)

diff --git a/include/libstick-0.1/booleanmatrix.h b/include/libstick-0.1/booleanmatrix.h
index d98e7b5..594eb92 100644
--- a/include/libstick-0.1/booleanmatrix.h
+++ b/include/libstick-0.1/booleanmatrix.h
@@ -11,6 +11,7 @@
 #include <ostream>
 #include <iterator>
 
+#include "booleanvector.h"
 
 namespace libstick {
 
@@ -26,7 +27,7 @@ class boolean_colmatrix_base {
 
     public:
         typedef IT index_type;
-        typedef std::vector<index_type> column_type;
+        typedef sorted_boolean_vector<IT> column_type;
         typedef D derived;
 
     protected:
@@ -60,8 +61,7 @@ class boolean_colmatrix_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 = 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'. */
@@ -93,7 +93,8 @@ class boolean_colmatrix_base {
             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));
         }
 
@@ -116,7 +117,11 @@ class boolean_colmatrix_base {
             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
@@ -131,32 +136,7 @@ class boolean_colmatrix_base {
         /** 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:
@@ -191,36 +171,13 @@ class boolean_colmatrix : public boolean_colmatrix_base<IT, boolean_colmatrix<IT
             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;
 };
 
 
@@ -231,7 +188,7 @@ class boolean_rowmatrix_base {
 
     public:
         typedef IT index_type;
-        typedef std::vector<index_type> row_type;
+        typedef sorted_boolean_vector<IT> row_type;
         typedef D derived;
 
     protected:
@@ -250,8 +207,7 @@ class boolean_rowmatrix_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 = 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'. */
@@ -278,7 +234,8 @@ class boolean_rowmatrix_base {
             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));
         }
 
@@ -296,32 +253,7 @@ class boolean_rowmatrix_base {
         /** 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:
@@ -383,12 +315,12 @@ class boolean_colrowmatrix : public boolean_colmatrix_base<IT, boolean_colrowmat
             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);
             }
         }
 
@@ -455,7 +387,7 @@ class boolean_colrowmatrix : public boolean_colmatrix_base<IT, boolean_colrowmat
 /** 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;
 
@@ -486,7 +418,9 @@ void multiply_matrix(RT &result, const boolean_rowmatrix_base<IT, D1> &a, const
         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);
         }
     }
diff --git a/include/libstick-0.1/booleanvector.h b/include/libstick-0.1/booleanvector.h
index 5bfd7e3..d7eb41b 100644
--- a/include/libstick-0.1/booleanvector.h
+++ b/include/libstick-0.1/booleanvector.h
@@ -47,6 +47,11 @@ class sorted_boolean_vector {
             return array;
         }
 
+        /** Count the number of 1s. */
+        size_t size() const {
+            return get_ones().size();
+        }
+
         /** Two vectors are equal if they contain the same indices. */
         bool operator==(const sorted_boolean_vector<IT> &vec) const {
             return get_ones() == vec.get_ones();
@@ -173,6 +178,11 @@ class heapsorted_boolean_vector {
             return array;
         }
 
+        /** Count the number of 1s. */
+        size_t size() const {
+            return get_ones().size();
+        }
+
         /** Two vectors are equal if they contain the same indices. */
         bool operator==(const heapsorted_boolean_vector<IT> &vec) const {
             return get_ones() == vec.get_ones();
diff --git a/tests/booleanmatrix.h b/tests/booleanmatrix.h
index 6cbf538..9e33ee0 100644
--- a/tests/booleanmatrix.h
+++ b/tests/booleanmatrix.h
@@ -63,10 +63,10 @@ class boolean_matrix_TestSuite: public Test::Suite {
             for (unsigned c=0; c < size; ++c)
                 TEST_ASSERT(mat.get_column(c).size() == 0);
 
-            col.push_back(0);
-            col.push_back(3);
-            col.push_back(8);
-            col.push_back(14);
+            col.set(0, true);
+            col.set(3, true);
+            col.set(8, true);
+            col.set(14, true);
 
             // Add column and test for values
             mat.add_column(5, col);
@@ -90,10 +90,10 @@ class boolean_matrix_TestSuite: public Test::Suite {
             for (unsigned r=0; r < size; ++r)
                 TEST_ASSERT(mat.get_row(r).size() == 0);
 
-            row.push_back(0);
-            row.push_back(8);
-            row.push_back(14);
-            row.push_back(3);
+            row.set(0, true);
+            row.set(8, true);
+            row.set(14, true);
+            row.set(3, true);
 
             // Add row and test for values
             mat.add_row(5, row);
-- 
2.30.2