[Boost-commit] svn:boost r80625 - in trunk: boost/numeric/ublas libs/numeric/ublas/test

Subject: [Boost-commit] svn:boost r80625 - in trunk: boost/numeric/ublas libs/numeric/ublas/test
From: guwi17_at_[hidden]
Date: 2012-09-21 19:43:18

Author: guwi17
Date: 2012-09-21 19:43:16 EDT (Fri, 21 Sep 2012)
New Revision: 80625
URL: http://svn.boost.org/trac/boost/changeset/80625

Log:

* boost/numeric/ublas/vector_sparse.hpp, boost/numeric/ublas/matrix_sparse.hpp: see #7363, applied patch (added inplace_merge)

* libs/numeric/ublas/test/Jamfile.v2, libs/numeric/ublas/test/test_coordinate_vector_inplace_merge.cpp, libs/numeric/ublas/test/test_coordinate_matrix_inplace_merge.cpp: add test for COO::sort()

Added:
   trunk/libs/numeric/ublas/test/test_coordinate_matrix_inplace_merge.cpp   (contents, props changed)
   trunk/libs/numeric/ublas/test/test_coordinate_vector_inplace_merge.cpp   (contents, props changed)
Text files modified: 
   trunk/boost/numeric/ublas/matrix_sparse.hpp |    50 +++++++++++++++++++++++++++++++++++++++ 
   trunk/boost/numeric/ublas/vector_sparse.hpp |    46 +++++++++++++++++++++++++++++++++++-    
   trunk/libs/numeric/ublas/test/Jamfile.v2    |     4 +++                                     
   3 files changed, 97 insertions(+), 3 deletions(-)

Modified: trunk/boost/numeric/ublas/matrix_sparse.hpp
==============================================================================
--- trunk/boost/numeric/ublas/matrix_sparse.hpp	(original)
+++ trunk/boost/numeric/ublas/matrix_sparse.hpp	2012-09-21 19:43:16 EDT (Fri, 21 Sep 2012)
@@ -4391,6 +4391,54 @@
             m1.swap (m2);
         }
 
+        // replacement if STL lower bound algorithm for use of inplace_merge
+        array_size_type lower_bound (array_size_type beg, array_size_type end, array_size_type target) const {
+            while (end > beg) {
+                array_size_type mid = (beg + end) / 2;
+                if (((index1_data_[mid] < index1_data_[target]) ||
+                     ((index1_data_[mid] == index1_data_[target]) &&
+                      (index2_data_[mid] < index2_data_[target])))) {
+                    beg = mid + 1;
+                } else {
+                    end = mid;
+                }
+            }
+            return beg;
+        }
+
+        // specialized replacement of STL inplace_merge to avoid compilation
+        // problems with respect to the array_triple iterator
+        void inplace_merge (array_size_type beg, array_size_type mid, array_size_type end) const {
+            array_size_type len_lef = mid - beg;
+            array_size_type len_rig = end - mid;
+
+            if (len_lef == 1 && len_rig == 1) {
+                if ((index1_data_[mid] < index1_data_[beg]) ||
+                    ((index1_data_[mid] == index1_data_[beg]) && (index2_data_[mid] < index2_data_[beg])))
+                    {
+                        std::swap(index1_data_[beg], index1_data_[mid]);
+                        std::swap(index2_data_[beg], index2_data_[mid]);
+                        std::swap(value_data_[beg], value_data_[mid]);
+                    }
+            } else if (len_lef > 0 && len_rig > 0) {
+                array_size_type lef_mid, rig_mid;
+                if (len_lef >= len_rig) {
+                    lef_mid = (beg + mid) / 2;
+                    rig_mid = lower_bound(mid, end, lef_mid);
+                } else {
+                    rig_mid = (mid + end) / 2;
+                    lef_mid = lower_bound(beg, mid, rig_mid);
+                }
+                std::rotate(&index1_data_[0] + lef_mid, &index1_data_[0] + mid, &index1_data_[0] + rig_mid);
+                std::rotate(&index2_data_[0] + lef_mid, &index2_data_[0] + mid, &index2_data_[0] + rig_mid);
+                std::rotate(&value_data_[0] + lef_mid, &value_data_[0] + mid, &value_data_[0] + rig_mid);
+
+                array_size_type new_mid = lef_mid + rig_mid - mid;
+                inplace_merge(beg, lef_mid, new_mid);
+                inplace_merge(new_mid, rig_mid, end);
+            }
+        }
+
         // Sorting and summation of duplicates
         BOOST_UBLAS_INLINE
         void sort () const {
@@ -4401,7 +4449,7 @@
                 const typename array_triple::iterator iunsorted = ita.begin () + sorted_filled_;
                 // sort new elements and merge
                 std::sort (iunsorted, ita.end ());
-                std::inplace_merge (ita.begin (), iunsorted, ita.end ());
+                inplace_merge(0, sorted_filled_, filled_);
 #else
                 const typename array_triple::iterator iunsorted = ita.begin ();
                 std::sort (iunsorted, ita.end ());

Modified: trunk/boost/numeric/ublas/vector_sparse.hpp
==============================================================================
--- trunk/boost/numeric/ublas/vector_sparse.hpp	(original)
+++ trunk/boost/numeric/ublas/vector_sparse.hpp	2012-09-21 19:43:16 EDT (Fri, 21 Sep 2012)
@@ -1801,6 +1801,48 @@
             v1.swap (v2);
         }
 
+        // replacement if STL lower bound algorithm for use of inplace_merge
+        size_type lower_bound (size_type beg, size_type end, size_type target) const {
+            while (end > beg) {
+                size_type mid = (beg + end) / 2;
+                if (index_data_[mid] < index_data_[target]) {
+                    beg = mid + 1;
+                } else {
+                    end = mid;
+                }
+            }
+            return beg;
+        }
+
+        // specialized replacement of STL inplace_merge to avoid compilation
+        // problems with respect to the array_triple iterator
+        void inplace_merge (size_type beg, size_type mid, size_type end) const {
+            size_type len_lef = mid - beg;
+            size_type len_rig = end - mid;
+
+            if (len_lef == 1 && len_rig == 1) {
+                if (index_data_[mid] < index_data_[beg]) {
+                    std::swap(index_data_[beg], index_data_[mid]);
+                    std::swap(value_data_[beg], value_data_[mid]);
+                }
+            } else if (len_lef > 0 && len_rig > 0) {
+                size_type lef_mid, rig_mid;
+                if (len_lef >= len_rig) {
+                    lef_mid = (beg + mid) / 2;
+                    rig_mid = lower_bound(mid, end, lef_mid);
+                } else {
+                    rig_mid = (mid + end) / 2;
+                    lef_mid = lower_bound(beg, mid, rig_mid);
+                }
+                std::rotate(&index_data_[0] + lef_mid, &index_data_[0] + mid, &index_data_[0] + rig_mid);
+                std::rotate(&value_data_[0] + lef_mid, &value_data_[0] + mid, &value_data_[0] + rig_mid);
+
+                size_type new_mid = lef_mid + rig_mid - mid;
+                inplace_merge(beg, lef_mid, new_mid);
+                inplace_merge(new_mid, rig_mid, end);
+            }
+        }
+
         // Sorting and summation of duplicates
         BOOST_UBLAS_INLINE
         void sort () const {
@@ -1811,11 +1853,11 @@
                 const typename array_pair::iterator iunsorted = ipa.begin () + sorted_filled_;
                 // sort new elements and merge
                 std::sort (iunsorted, ipa.end ());
-                std::inplace_merge (ipa.begin (), iunsorted, ipa.end ());
+                inplace_merge(0, sorted_filled_, filled_);
 #else
                 const typename array_pair::iterator iunsorted = ipa.begin ();
                 std::sort (iunsorted, ipa.end ());
-#endif                
+#endif
 
                 // sum duplicates with += and remove
                 size_type filled = 0;

Modified: trunk/libs/numeric/ublas/test/Jamfile.v2
==============================================================================
--- trunk/libs/numeric/ublas/test/Jamfile.v2	(original)
+++ trunk/libs/numeric/ublas/test/Jamfile.v2	2012-09-21 19:43:16 EDT (Fri, 21 Sep 2012)
@@ -198,4 +198,8 @@
         : test_inplace_solve_mvov
         :
       ]
+      [ run test_coordinate_vector_inplace_merge.cpp 
+      ]
+      [ run test_coordinate_matrix_inplace_merge.cpp 
+      ]
     ;

Added: trunk/libs/numeric/ublas/test/test_coordinate_matrix_inplace_merge.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/numeric/ublas/test/test_coordinate_matrix_inplace_merge.cpp	2012-09-21 19:43:16 EDT (Fri, 21 Sep 2012)
@@ -0,0 +1,132 @@
+//  Copyright (c) 2011 David Bellot
+//
+//  Distributed under the Boost Software License, Version 1.0. (See
+//  accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UBLAS_NO_ELEMENT_PROXIES
+# define BOOST_UBLAS_NO_ELEMENT_PROXIES
+#endif
+
+#include <boost/numeric/ublas/assignment.hpp>
+#include <boost/numeric/ublas/matrix.hpp>
+#include <boost/numeric/ublas/matrix_sparse.hpp>
+#include <boost/numeric/ublas/matrix_expression.hpp>
+#include <boost/numeric/ublas/io.hpp>
+
+#include "libs/numeric/ublas/test/utils.hpp"
+
+using std::cout;
+using std::endl;
+
+const double TOL = 1e-15;
+
+template <class AE>
+typename AE::value_type mean_square(const boost::numeric::ublas::matrix_expression<AE> &me) {
+    typename AE::value_type s(0);
+    typename AE::size_type i, j;
+    for (i=0; i!= me().size1(); i++) {
+        for (j=0; j!= me().size2(); j++) {
+          s += boost::numeric::ublas::scalar_traits<typename AE::value_type>::type_abs(me()(i,j));
+        }
+    }
+    return s/me().size1()*me().size2();
+}
+
+template<typename T>
+bool check_sortedness(const boost::numeric::ublas::coordinate_matrix<T>& matrix) {
+  bool result = true;
+  typedef boost::numeric::ublas::coordinate_matrix<T> matrix_type;
+  typename matrix_type::index_array_type i1 = matrix.index1_data();
+  typename matrix_type::index_array_type i2 = matrix.index2_data();
+  typename matrix_type::array_size_type size = matrix.filled();
+
+  for (typename matrix_type::array_size_type i = 0; i + 1 < size && result; ++ i) {
+    result &= ( (i1[i] < i1[i + 1]) ||
+                ((i1[i] == i1[i]) &&
+                 (i2[i] < i2[i + 1])) );
+
+  }
+  return result;
+}
+
+void print_entries(size_t size_x, size_t size_y,
+                   const std::vector<std::pair<size_t, size_t> >& entries)
+{
+  std::cerr << "Error - Size:" << size_x << " x " << size_y << ". Entries: ";
+  for (size_t i = 0; i < entries.size(); ++ i) {
+    std::cerr << entries[i].first << ", " << entries[i].second << "; ";
+  }
+  std::cerr << "\n";
+}
+
+
+BOOST_UBLAS_TEST_DEF( test_coordinate_matrix_inplace_merge_random )
+{
+  const size_t max_repeats = 100;
+  const size_t max_size = 100;
+  const size_t dim_var = 10;
+  const size_t nr_entries = 10;
+
+  for (size_t repeats = 1; repeats < max_repeats; ++repeats ) {
+    for (size_t size = 1; size < max_size; size += 5) {
+      size_t size_x = size + rand() % dim_var;
+      size_t size_y = size + rand() % dim_var;
+
+      boost::numeric::ublas::coordinate_matrix<double> matrix_coord(size_x, size_y);
+      boost::numeric::ublas::matrix<double> matrix_dense(size_x, size_y, 0);
+
+      matrix_coord.sort();
+
+      std::vector<std::pair<size_t, size_t> > entries;
+      for (int entry = 0; entry < nr_entries; ++ entry) {
+        int x = rand() % size_x;
+        int y = rand() % size_y;
+        entries.push_back(std::make_pair(x, y));
+        matrix_coord.append_element(x, y, 1);
+        matrix_dense(x, y) += 1;
+      }
+      matrix_coord.sort();
+
+      {
+        bool sorted = check_sortedness(matrix_coord);
+        bool identical = mean_square(matrix_coord - matrix_dense) < TOL;
+        if (!(sorted && identical)) {
+          print_entries(size_x, size_y, entries);
+        }
+        BOOST_UBLAS_TEST_CHECK( check_sortedness(matrix_coord) );
+        BOOST_UBLAS_TEST_CHECK( mean_square(matrix_coord - matrix_dense) < TOL);
+      }
+
+      for (int entry = 0; entry < nr_entries; ++ entry) {
+        int x = rand() % size_x;
+        int y = rand() % size_y;
+        entries.push_back(std::make_pair(x, y));
+        matrix_coord(x, y) += 1;
+        matrix_dense(x, y) += 1;
+        matrix_coord.sort();
+      }
+
+      {
+        bool sorted = check_sortedness(matrix_coord);
+        bool identical = mean_square(matrix_coord - matrix_dense) < TOL;
+        if (!(sorted && identical)) {
+          print_entries(size_x, size_y, entries);
+        }
+        BOOST_UBLAS_TEST_CHECK( sorted );
+        BOOST_UBLAS_TEST_CHECK( identical );
+      }
+    }
+  }
+}
+
+int main()
+{
+    BOOST_UBLAS_TEST_BEGIN();
+
+    BOOST_UBLAS_TEST_DO( test_coordinate_matrix_inplace_merge_random );
+
+    BOOST_UBLAS_TEST_END();
+
+    return EXIT_SUCCESS;;
+}

Added: trunk/libs/numeric/ublas/test/test_coordinate_vector_inplace_merge.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/numeric/ublas/test/test_coordinate_vector_inplace_merge.cpp	2012-09-21 19:43:16 EDT (Fri, 21 Sep 2012)
@@ -0,0 +1,120 @@
+//  Copyright (c) 2011 David Bellot
+//
+//  Distributed under the Boost Software License, Version 1.0. (See
+//  accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UBLAS_NO_ELEMENT_PROXIES
+# define BOOST_UBLAS_NO_ELEMENT_PROXIES
+#endif
+
+#include <boost/numeric/ublas/assignment.hpp>
+#include <boost/numeric/ublas/vector.hpp>
+#include <boost/numeric/ublas/vector_sparse.hpp>
+#include <boost/numeric/ublas/vector_expression.hpp>
+#include <boost/numeric/ublas/io.hpp>
+
+#include "libs/numeric/ublas/test/utils.hpp"
+
+const double TOL = 1e-15;
+
+
+template <class AE>
+typename AE::value_type mean_square(const boost::numeric::ublas::vector_expression<AE> &me) {
+    typename AE::value_type s(0);
+    typename AE::size_type i;
+    for (i=0; i!= me().size(); i++) {
+      s += boost::numeric::ublas::scalar_traits<typename AE::value_type>::type_abs(me()(i));
+    }
+    return s/me().size();
+}
+
+template<typename T>
+bool check_sortedness(const boost::numeric::ublas::coordinate_vector<T>& vector) {
+  bool result = true;
+  typedef boost::numeric::ublas::coordinate_vector<T> vector_type;
+  typename vector_type::index_array_type idx = vector.index_data();
+  typename vector_type::size_type size = vector.filled();
+
+  for (typename vector_type::size_type i = 0; i + 1 < size && result; ++ i) {
+    result &= (idx[i] < idx[i + 1]);
+  }
+  return result;
+}
+
+void print_entries(size_t size,
+                   const std::vector<size_t>& entries)
+{
+  std::cerr << "Error entries - Size:" << size << ". Entries: ";
+  for (size_t i = 0; i < entries.size(); ++ i) {
+    std::cerr << entries[i] << "; ";
+  }
+  std::cerr << "\n";
+}
+
+BOOST_UBLAS_TEST_DEF( test_coordinate_vector_inplace_merge_random )
+{
+  const size_t max_repeats = 100;
+  const size_t max_size = 100;
+  const size_t dim_var = 10;
+  const size_t nr_entries = 10;
+
+  for (size_t repeats = 1; repeats < max_repeats; ++repeats ) {
+    for (size_t size = 1; size < max_size; size += 5) {
+      size_t size_vec = size + rand() % dim_var;
+
+      boost::numeric::ublas::coordinate_vector<double> vector_coord(size_vec);
+      boost::numeric::ublas::vector<double> vector_dense(size_vec, 0);
+
+      vector_coord.sort();
+
+      std::vector<size_t> entries;
+      for (int entry = 0; entry < nr_entries; ++ entry) {
+        int x = rand() % size_vec;
+        entries.push_back(x);
+        vector_coord.append_element(x, 1);
+        vector_dense(x) += 1;
+      }
+      vector_coord.sort();
+
+      {
+        bool sorted = check_sortedness(vector_coord);
+        bool identical = mean_square(vector_coord - vector_dense) < TOL;
+        if (!(sorted && identical)) {
+          print_entries(size_vec, entries);
+        }
+        BOOST_UBLAS_TEST_CHECK( check_sortedness(vector_coord) );
+        BOOST_UBLAS_TEST_CHECK( mean_square(vector_coord - vector_dense) < TOL);
+      }
+
+      for (int entry = 0; entry < nr_entries; ++ entry) {
+        int x = rand() % size_vec;
+        entries.push_back(x);
+        vector_coord(x) += 1;
+        vector_dense(x) += 1;
+        vector_coord.sort();
+      }
+
+      {
+        bool sorted = check_sortedness(vector_coord);
+        bool identical = mean_square(vector_coord - vector_dense) < TOL;
+        if (!(sorted && identical)) {
+          print_entries(size_vec, entries);
+        }
+        BOOST_UBLAS_TEST_CHECK( sorted );
+        BOOST_UBLAS_TEST_CHECK( identical );
+      }
+    }
+  }
+}
+
+int main()
+{
+    BOOST_UBLAS_TEST_BEGIN();
+
+    BOOST_UBLAS_TEST_DO( test_coordinate_vector_inplace_merge_random );
+
+    BOOST_UBLAS_TEST_END();
+
+    return EXIT_SUCCESS;;
+}