This is an automated email from the git hooks/post-receive script. rene pushed a commit to branch master in repository mdds.
commit d3bd0aedf9420bda9692787b5e116201fdb7a49a Author: Rene Engelhard <[email protected]> Date: Thu Apr 21 14:50:47 2016 +0200 Imported Upstream version 0.5.3 --- Makefile.in | 25 +- NEWS | 9 + configure | 32 +- include/mdds/mixed_type_matrix.hpp | 10 +- include/mdds/mixed_type_matrix_def.inl | 25 +- include/mdds/mixed_type_matrix_storage.hpp | 765 +++------------------ .../mixed_type_matrix_storage_filled_linear.inl | 701 +++++++++++++++++++ ...xed_type_matrix_storage_filled_nested_array.inl | 374 ++++++++++ include/mdds/mixed_type_matrix_storage_sparse.inl | 376 ++++++++++ include/mdds/rectangle_set.hpp | 246 +------ .../{rectangle_set.hpp => rectangle_set_def.inl} | 225 +----- misc/mdds.spec.in | 4 +- src/array_creation_perf_test.cpp | 81 +++ src/mixed_type_matrix_test.cpp | 83 ++- src/test_global.hpp | 1 + 15 files changed, 1798 insertions(+), 1159 deletions(-) diff --git a/Makefile.in b/Makefile.in index de4c975..9a98933 100644 --- a/Makefile.in +++ b/Makefile.in @@ -18,18 +18,25 @@ EXECS= \ rectangle_set_test HEADERS= \ - $(INCDIR)/mdds/node.hpp \ - $(INCDIR)/mdds/quad_node.hpp \ - $(INCDIR)/mdds/global.hpp \ - $(INCDIR)/mdds/flat_segment_tree.hpp \ $(INCDIR)/mdds/flat_segment_tree_def.inl \ - $(INCDIR)/mdds/point_quad_tree.hpp \ - $(INCDIR)/mdds/segment_tree.hpp \ - $(INCDIR)/mdds/mixed_type_matrix.hpp \ + $(INCDIR)/mdds/flat_segment_tree.hpp \ + $(INCDIR)/mdds/flat_segment_tree_itr.hpp \ + $(INCDIR)/mdds/global.hpp \ + $(INCDIR)/mdds/hash_container/map.hpp \ $(INCDIR)/mdds/mixed_type_matrix_def.inl \ - $(INCDIR)/mdds/mixed_type_matrix_storage.hpp \ + $(INCDIR)/mdds/mixed_type_matrix_element.hpp \ $(INCDIR)/mdds/mixed_type_matrix_flag_storage.hpp \ - $(INCDIR)/mdds/rectangle_set.hpp + $(INCDIR)/mdds/mixed_type_matrix.hpp \ + $(INCDIR)/mdds/mixed_type_matrix_storage_filled_linear.inl \ + $(INCDIR)/mdds/mixed_type_matrix_storage_filled_nested_array.inl \ + $(INCDIR)/mdds/mixed_type_matrix_storage.hpp \ + $(INCDIR)/mdds/mixed_type_matrix_storage_sparse.inl \ + $(INCDIR)/mdds/node.hpp \ + $(INCDIR)/mdds/point_quad_tree.hpp \ + $(INCDIR)/mdds/quad_node.hpp \ + $(INCDIR)/mdds/rectangle_set_def.inl \ + $(INCDIR)/mdds/rectangle_set.hpp \ + $(INCDIR)/mdds/segment_tree.hpp DEPENDS= \ $(HEADERS) diff --git a/NEWS b/NEWS index d200527..7f9a224 100644 --- a/NEWS +++ b/NEWS @@ -1,3 +1,12 @@ +mdds 0.5.3 + +* mixed_type_matrix + + * re-implemented the filled storage for better performance, with two + separate implementations for zero and emtpy matrix types. The + newer implementation should improve object creation time + considerably. + mdds 0.5.2 * flat_segment_tree diff --git a/configure b/configure index 1352ca1..680db6a 100755 --- a/configure +++ b/configure @@ -1,6 +1,6 @@ #! /bin/sh # Guess values for system-dependent variables and create Makefiles. -# Generated by GNU Autoconf 2.68 for mdds 0.5.2. +# Generated by GNU Autoconf 2.68 for mdds 0.5.3. # # Report bugs to <[email protected]>. # @@ -559,8 +559,8 @@ MAKEFLAGS= # Identity of this package. PACKAGE_NAME='mdds' PACKAGE_TARNAME='mdds' -PACKAGE_VERSION='0.5.2' -PACKAGE_STRING='mdds 0.5.2' +PACKAGE_VERSION='0.5.3' +PACKAGE_STRING='mdds 0.5.3' PACKAGE_BUGREPORT='[email protected]' PACKAGE_URL='' @@ -1160,7 +1160,7 @@ if test "$ac_init_help" = "long"; then # Omit some internal or obsolete options to make the list less imposing. # This message is too long to be a string in the A/UX 3.1 sh. cat <<_ACEOF -\`configure' configures mdds 0.5.2 to adapt to many kinds of systems. +\`configure' configures mdds 0.5.3 to adapt to many kinds of systems. Usage: $0 [OPTION]... [VAR=VALUE]... @@ -1221,7 +1221,7 @@ fi if test -n "$ac_init_help"; then case $ac_init_help in - short | recursive ) echo "Configuration of mdds 0.5.2:";; + short | recursive ) echo "Configuration of mdds 0.5.3:";; esac cat <<\_ACEOF @@ -1305,7 +1305,7 @@ fi test -n "$ac_init_help" && exit $ac_status if $ac_init_version; then cat <<\_ACEOF -mdds configure 0.5.2 +mdds configure 0.5.3 generated by GNU Autoconf 2.68 Copyright (C) 2010 Free Software Foundation, Inc. @@ -1322,7 +1322,7 @@ cat >config.log <<_ACEOF This file contains any messages produced by compilers while running configure, to aid debugging if configure makes a mistake. -It was created by mdds $as_me 0.5.2, which was +It was created by mdds $as_me 0.5.3, which was generated by GNU Autoconf 2.68. Invocation command line was $ $0 $@ @@ -1671,7 +1671,7 @@ ac_compiler_gnu=$ac_cv_c_compiler_gnu -VERSION=0.5.2 +VERSION=0.5.3 PACKAGE_TARNAME=mdds @@ -2268,7 +2268,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.5.2, which was +This file was extended by mdds $as_me 0.5.3, which was generated by GNU Autoconf 2.68. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -2321,7 +2321,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.5.2 +mdds config.status 0.5.3 configured by $0, generated by GNU Autoconf 2.68, with options \\"\$ac_cs_config\\" @@ -3437,7 +3437,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.5.2, which was +This file was extended by mdds $as_me 0.5.3, which was generated by GNU Autoconf 2.68. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -3490,7 +3490,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.5.2 +mdds config.status 0.5.3 configured by $0, generated by GNU Autoconf 2.68, with options \\"\$ac_cs_config\\" @@ -4607,7 +4607,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.5.2, which was +This file was extended by mdds $as_me 0.5.3, which was generated by GNU Autoconf 2.68. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -4660,7 +4660,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.5.2 +mdds config.status 0.5.3 configured by $0, generated by GNU Autoconf 2.68, with options \\"\$ac_cs_config\\" @@ -5778,7 +5778,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.5.2, which was +This file was extended by mdds $as_me 0.5.3, which was generated by GNU Autoconf 2.68. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -5831,7 +5831,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.5.2 +mdds config.status 0.5.3 configured by $0, generated by GNU Autoconf 2.68, with options \\"\$ac_cs_config\\" diff --git a/include/mdds/mixed_type_matrix.hpp b/include/mdds/mixed_type_matrix.hpp index 758baff..4487b7f 100644 --- a/include/mdds/mixed_type_matrix.hpp +++ b/include/mdds/mixed_type_matrix.hpp @@ -81,7 +81,8 @@ private: public: typedef ::mdds::flag_storage<flag_type, size_pair_type, size_pair_type_hash> flag_storage; - typedef ::mdds::storage_filled<mixed_type_matrix> filled_storage_type; + typedef ::mdds::storage_filled_linear<mixed_type_matrix> filled_storage_type; + typedef ::mdds::storage_filled_linear_zero<mixed_type_matrix> filled_storage_zero_type; typedef ::mdds::storage_sparse<mixed_type_matrix> sparse_storage_type; typedef typename storage_base::const_iterator const_iterator; @@ -220,6 +221,13 @@ public: #endif private: + /** + * Storage classes have no vtable; the concrete class type must be + * specified when deleting the instance. + */ + void delete_storage(); + +private: storage_base* mp_storage; }; diff --git a/include/mdds/mixed_type_matrix_def.inl b/include/mdds/mixed_type_matrix_def.inl index 9d9cf54..264c039 100644 --- a/include/mdds/mixed_type_matrix_def.inl +++ b/include/mdds/mixed_type_matrix_def.inl @@ -34,7 +34,7 @@ mixed_type_matrix<_String,_Flag>::create_storage(size_t rows, size_t cols, matri switch (density) { case matrix_density_filled_zero: - return new filled_storage_type(rows, cols, matrix_init_element_zero); + return new filled_storage_zero_type(rows, cols, matrix_init_element_zero); case matrix_density_filled_empty: return new filled_storage_type(rows, cols, matrix_init_element_empty); case matrix_density_sparse_zero: @@ -77,7 +77,7 @@ mixed_type_matrix<_String,_Flag>::mixed_type_matrix(const mixed_type_matrix& r) template<typename _String, typename _Flag> mixed_type_matrix<_String,_Flag>::~mixed_type_matrix() { - delete mp_storage; + delete_storage(); } template<typename _String, typename _Flag> @@ -102,7 +102,7 @@ mixed_type_matrix<_String,_Flag>::operator= (const mixed_type_matrix& r) // self assignment. return *this; - delete mp_storage; + delete_storage(); mp_storage = r.mp_storage->clone(); return *this; } @@ -299,4 +299,23 @@ void mixed_type_matrix<_String,_Flag>::dump_flags() const } #endif +template<typename _String, typename _Flag> +void mixed_type_matrix<_String,_Flag>::delete_storage() +{ + switch (mp_storage->get_storage_type()) + { + case matrix_storage_filled: + delete static_cast<filled_storage_type*>(mp_storage); + break; + case matrix_storage_filled_zero: + delete static_cast<filled_storage_zero_type*>(mp_storage); + break; + case matrix_storage_sparse: + delete static_cast<sparse_storage_type*>(mp_storage); + break; + default: + assert(!"unknown storage type!"); + } +} + } diff --git a/include/mdds/mixed_type_matrix_storage.hpp b/include/mdds/mixed_type_matrix_storage.hpp index 2f95bf9..91456df 100644 --- a/include/mdds/mixed_type_matrix_storage.hpp +++ b/include/mdds/mixed_type_matrix_storage.hpp @@ -32,12 +32,14 @@ #include <boost/ptr_container/ptr_vector.hpp> #include <boost/ptr_container/ptr_map.hpp> +#include <boost/pool/object_pool.hpp> namespace mdds { enum matrix_storage_t { matrix_storage_filled, + matrix_storage_filled_zero, matrix_storage_sparse }; @@ -84,22 +86,6 @@ public: m_row_itr(r.m_row_itr), m_row_itr_end(r.m_row_itr_end) {} - /** - * Set the current iterator position to the end position. - */ - void set_to_end() - { - if (empty()) - return; - - m_rows_itr = m_rows_itr_end; - typename store_type::rows_type::const_iterator itr = m_rows_itr_end; - --itr; // Move to the last row. - - // They both need to be at the end position of the last row. - m_row_itr = m_row_itr_end = m_rows_wrap(itr).end(); - } - bool operator== (const const_itr_access& r) const { if (&m_db != &r.m_db) @@ -126,12 +112,6 @@ public: bool empty() const { return m_db.get_rows().begin() == m_rows_itr_end; } - void update_row_itr() - { - m_row_itr = m_rows_wrap(m_rows_itr).begin(); - m_row_itr_end = m_rows_wrap(m_rows_itr).end(); - } - const element& get() const { return m_wrap(m_row_itr); } bool inc() @@ -186,6 +166,30 @@ public: return true; } + /** + * Set the current iterator position to the end position. + */ + void set_to_end() + { + if (empty()) + return; + + m_rows_itr = m_rows_itr_end; + typename store_type::rows_type::const_iterator itr = m_rows_itr_end; + --itr; // Move to the last row. + + // They both need to be at the end position of the last row. + m_row_itr = m_row_itr_end = m_rows_wrap(itr).end(); + } + +private: + + void update_row_itr() + { + m_row_itr = m_rows_wrap(m_rows_itr).begin(); + m_row_itr_end = m_rows_wrap(m_rows_itr).end(); + } + private: const store_type& m_db; typename store_type::rows_type::const_iterator m_rows_itr; @@ -205,12 +209,15 @@ public: typedef typename _MatrixType::element element; typedef typename _MatrixType::flag_storage flag_storage; typedef typename _MatrixType::string_type string_type; - typedef typename _MatrixType::filled_storage_type filled_storage_type; - typedef typename _MatrixType::sparse_storage_type sparse_storage_type; + + typedef typename _MatrixType::filled_storage_type filled_storage_type; + typedef typename _MatrixType::filled_storage_zero_type filled_storage_zero_type; + typedef typename _MatrixType::sparse_storage_type sparse_storage_type; class const_iterator { typedef typename filled_storage_type::const_itr_access filled_access_type; + typedef typename filled_storage_zero_type::const_itr_access filled_zero_access_type; typedef typename sparse_storage_type::const_itr_access sparse_access_type; public: // iterator traits @@ -235,6 +242,9 @@ public: case matrix_storage_filled: get_filled_itr()->set_to_end(); break; + case matrix_storage_filled_zero: + get_filled_zero_itr()->set_to_end(); + break; case matrix_storage_sparse: get_sparse_itr()->set_to_end(); break; @@ -256,6 +266,9 @@ public: case matrix_storage_filled: m_const_itr_access = new filled_access_type(*r.get_filled_itr()); break; + case matrix_storage_filled_zero: + m_const_itr_access = new filled_zero_access_type(*r.get_filled_zero_itr()); + break; case matrix_storage_sparse: m_const_itr_access = new sparse_access_type(*r.get_sparse_itr()); break; @@ -271,6 +284,9 @@ public: case matrix_storage_filled: delete get_filled_itr(); break; + case matrix_storage_filled_zero: + delete get_filled_zero_itr(); + break; case matrix_storage_sparse: delete get_sparse_itr(); break; @@ -302,6 +318,8 @@ public: { case matrix_storage_filled: return get_filled_itr()->get(); + case matrix_storage_filled_zero: + return get_filled_zero_itr()->get(); case matrix_storage_sparse: return get_sparse_itr()->get(); default: @@ -316,6 +334,8 @@ public: { case matrix_storage_filled: return &get_filled_itr()->get(); + case matrix_storage_filled_zero: + return &get_filled_zero_itr()->get(); case matrix_storage_sparse: return &get_sparse_itr()->get(); default: @@ -332,6 +352,9 @@ public: case matrix_storage_filled: has_next = get_filled_itr()->inc(); break; + case matrix_storage_filled_zero: + has_next = get_filled_zero_itr()->inc(); + break; case matrix_storage_sparse: has_next = get_sparse_itr()->inc(); break; @@ -349,6 +372,9 @@ public: case matrix_storage_filled: has_next = get_filled_itr()->dec(); break; + case matrix_storage_filled_zero: + has_next = get_filled_zero_itr()->dec(); + break; case matrix_storage_sparse: has_next = get_sparse_itr()->dec(); break; @@ -375,6 +401,8 @@ public: { case matrix_storage_filled: return *get_filled_itr() == *r.get_filled_itr(); + case matrix_storage_filled_zero: + return *get_filled_zero_itr() == *r.get_filled_zero_itr(); case matrix_storage_sparse: return *get_sparse_itr() == *r.get_sparse_itr(); default: @@ -389,6 +417,7 @@ public: } private: + filled_access_type* get_filled_itr() { return static_cast<filled_access_type*>(m_const_itr_access); @@ -399,6 +428,16 @@ public: return static_cast<const filled_access_type*>(m_const_itr_access); } + filled_zero_access_type* get_filled_zero_itr() + { + return static_cast<filled_zero_access_type*>(m_const_itr_access); + } + + const filled_zero_access_type* get_filled_zero_itr() const + { + return static_cast<const filled_zero_access_type*>(m_const_itr_access); + } + sparse_access_type* get_sparse_itr() { return static_cast<sparse_access_type*>(m_const_itr_access); @@ -430,12 +469,11 @@ public: matrix_storage_t get_storage_type() const { return m_store_type; } - /** - * the destructor must remain virtual because the derived classes have - * different sizes. TODO: Figure out a way to remove the virtual-ness - * without leaking memory. - */ - virtual ~storage_base() {} + /** + * When deleting the storage object, the caller must explicitly specify + * the concrete class or else memory will leak. + */ + ~storage_base() {} const_iterator begin() const { @@ -447,6 +485,12 @@ public: return const_iterator(p, m_store_type); } break; + case matrix_storage_filled_zero: + { + void* p = static_cast<const filled_storage_zero_type*>(this)->get_const_itr_access(); + return const_iterator(p, m_store_type); + } + break; case matrix_storage_sparse: { void* p = static_cast<const sparse_storage_type*>(this)->get_const_itr_access(); @@ -469,6 +513,12 @@ public: return const_iterator(p, m_store_type, true); } break; + case matrix_storage_filled_zero: + { + void* p = static_cast<const filled_storage_zero_type*>(this)->get_const_itr_access(); + return const_iterator(p, m_store_type, true); + } + break; case matrix_storage_sparse: { void* p = static_cast<const sparse_storage_type*>(this)->get_const_itr_access(); @@ -487,6 +537,8 @@ public: { case matrix_storage_filled: return static_cast<filled_storage_type*>(this)->get_element(row, col); + case matrix_storage_filled_zero: + return static_cast<filled_storage_zero_type*>(this)->get_element(row, col); case matrix_storage_sparse: return static_cast<sparse_storage_type*>(this)->get_element(row, col); default: @@ -501,6 +553,8 @@ public: { case matrix_storage_filled: return static_cast<const filled_storage_type*>(this)->get_type(row, col); + case matrix_storage_filled_zero: + return static_cast<const filled_storage_zero_type*>(this)->get_type(row, col); case matrix_storage_sparse: return static_cast<const sparse_storage_type*>(this)->get_type(row, col); default: @@ -515,6 +569,8 @@ public: { case matrix_storage_filled: return static_cast<const filled_storage_type*>(this)->get_numeric(row, col); + case matrix_storage_filled_zero: + return static_cast<const filled_storage_zero_type*>(this)->get_numeric(row, col); case matrix_storage_sparse: return static_cast<const sparse_storage_type*>(this)->get_numeric(row, col); default: @@ -529,6 +585,8 @@ public: { case matrix_storage_filled: return static_cast<const filled_storage_type*>(this)->get_string(row, col); + case matrix_storage_filled_zero: + return static_cast<const filled_storage_zero_type*>(this)->get_string(row, col); case matrix_storage_sparse: return static_cast<const sparse_storage_type*>(this)->get_string(row, col); default: @@ -543,6 +601,8 @@ public: { case matrix_storage_filled: return static_cast<const filled_storage_type*>(this)->get_boolean(row, col); + case matrix_storage_filled_zero: + return static_cast<const filled_storage_zero_type*>(this)->get_boolean(row, col); case matrix_storage_sparse: return static_cast<const sparse_storage_type*>(this)->get_boolean(row, col); default: @@ -557,6 +617,8 @@ public: { case matrix_storage_filled: return static_cast<const filled_storage_type*>(this)->rows(); + case matrix_storage_filled_zero: + return static_cast<const filled_storage_zero_type*>(this)->rows(); case matrix_storage_sparse: return static_cast<const sparse_storage_type*>(this)->rows(); default: @@ -571,6 +633,8 @@ public: { case matrix_storage_filled: return static_cast<const filled_storage_type*>(this)->cols(); + case matrix_storage_filled_zero: + return static_cast<const filled_storage_zero_type*>(this)->cols(); case matrix_storage_sparse: return static_cast<const sparse_storage_type*>(this)->cols(); default: @@ -586,6 +650,9 @@ public: case matrix_storage_filled: static_cast<filled_storage_type*>(this)->transpose(); break; + case matrix_storage_filled_zero: + static_cast<filled_storage_zero_type*>(this)->transpose(); + break; case matrix_storage_sparse: static_cast<sparse_storage_type*>(this)->transpose(); break; @@ -601,6 +668,9 @@ public: case matrix_storage_filled: static_cast<filled_storage_type*>(this)->resize(row, col); break; + case matrix_storage_filled_zero: + static_cast<filled_storage_zero_type*>(this)->resize(row, col); + break; case matrix_storage_sparse: static_cast<sparse_storage_type*>(this)->resize(row, col); break; @@ -616,6 +686,9 @@ public: case matrix_storage_filled: static_cast<filled_storage_type*>(this)->clear(); break; + case matrix_storage_filled_zero: + static_cast<filled_storage_zero_type*>(this)->clear(); + break; case matrix_storage_sparse: static_cast<sparse_storage_type*>(this)->clear(); break; @@ -630,6 +703,8 @@ public: { case matrix_storage_filled: return static_cast<filled_storage_type*>(this)->numeric(); + case matrix_storage_filled_zero: + return static_cast<filled_storage_zero_type*>(this)->numeric(); case matrix_storage_sparse: return static_cast<sparse_storage_type*>(this)->numeric(); default: @@ -644,6 +719,8 @@ public: { case matrix_storage_filled: return static_cast<const filled_storage_type*>(this)->empty(); + case matrix_storage_filled_zero: + return static_cast<const filled_storage_zero_type*>(this)->empty(); case matrix_storage_sparse: return static_cast<const sparse_storage_type*>(this)->empty(); default: @@ -658,6 +735,8 @@ public: { case matrix_storage_filled: return static_cast<const filled_storage_type*>(this)->clone(); + case matrix_storage_filled_zero: + return static_cast<const filled_storage_zero_type*>(this)->clone(); case matrix_storage_sparse: return static_cast<const sparse_storage_type*>(this)->clone(); default: @@ -677,628 +756,10 @@ private: flag_storage m_flags; }; -/** - * This storage creates instance for every single element, even for the - * empty elements. - */ -template<typename _MatrixType> -class storage_filled : public ::mdds::storage_base<_MatrixType> -{ - typedef _MatrixType matrix_type; - typedef typename matrix_type::string_type string_type; - -public: - typedef typename matrix_type::element element; - typedef ::boost::ptr_vector<element> row_type; - typedef ::boost::ptr_vector<row_type> rows_type; - - struct elem_wrap - { - const element& operator() (const typename row_type::const_iterator& itr) const - { - return *itr; - } - }; - struct rows_wrap - { - const row_type& operator() (const typename rows_type::const_iterator& itr) const - { - return *itr; - } - }; - typedef ::mdds::const_itr_access<storage_filled, elem_wrap, rows_wrap> const_itr_access; - - storage_filled(size_t _rows, size_t _cols, matrix_init_element_t init_type) : - storage_base<matrix_type>(matrix_storage_filled, init_type), - m_numeric(false), - m_valid(false) - { - m_rows.reserve(_rows); - for (size_t i = 0; i < _rows; ++i) - { - m_rows.push_back(new row_type); - init_row(m_rows.back(), _cols); - } - } - - storage_filled(const storage_filled& r) : - storage_base<matrix_type>(r), - m_rows(r.m_rows), - m_numeric(r.m_numeric), - m_valid(r.m_valid) {} - - virtual ~storage_filled() {} - - const_itr_access* get_const_itr_access() const - { - return new const_itr_access(*this); - } - - element& get_element(size_t row, size_t col) - { - m_valid = false; - return m_rows.at(row).at(col); - } - - matrix_element_t get_type(size_t row, size_t col) const - { - return m_rows.at(row).at(col).m_type; - } - - double get_numeric(size_t row, size_t col) const - { - const element& elem = m_rows.at(row).at(col); - switch (elem.m_type) - { - case element_numeric: - return elem.m_numeric; - case element_boolean: - return static_cast<double>(elem.m_boolean); - case element_empty: - default: - ; - } - return 0.0; - } - - const string_type* get_string(size_t row, size_t col) const - { - const element& elem = m_rows.at(row).at(col); - if (elem.m_type != element_string) - throw matrix_storage_error("element type is not string."); - - return elem.mp_string; - } - - bool get_boolean(size_t row, size_t col) const - { - const element& elem = m_rows.at(row).at(col); - if (elem.m_type != element_boolean) - throw matrix_storage_error("element type is not boolean."); - - return elem.m_boolean; - } - - size_t rows() const - { - return m_rows.size(); - } - - size_t cols() const - { - return m_rows.empty() ? 0 : m_rows[0].size(); - } - - void transpose() - { - rows_type trans_mx; - size_t row_size = rows(), col_size = cols(); - trans_mx.reserve(col_size); - for (size_t col = 0; col < col_size; ++col) - { - trans_mx.push_back(new row_type); - row_type& trans_row = trans_mx.back(); - trans_row.reserve(row_size); - for (size_t row = 0; row < row_size; ++row) - trans_row.push_back(new element(m_rows[row][col])); - } - m_rows.swap(trans_mx); - } - - void resize(size_t row, size_t col) - { - m_valid = false; - if (!row || !col) - { - // Empty the matrix. - clear(); - return; - } - - size_t cur_rows = rows(), cur_cols = cols(); - - if (!cur_rows || !cur_cols) - { - // current matrix is empty. - rows_type new_rows; - new_rows.reserve(row); - for (size_t i = 0; i < row; ++i) - { - new_rows.push_back(new row_type); - init_row(new_rows.back(), col); - } - m_rows.swap(new_rows); - return; - } - - if (row > cur_rows) - { - // Insert extra rows... - size_t new_row_count = row - cur_rows; - m_rows.reserve(row); - for (size_t i = 0; i < new_row_count; ++i) - { - m_rows.push_back(new row_type); - init_row(m_rows.back(), col); - } - - resize_rows(cur_rows-1, cur_cols, col); - } - else if (cur_rows > row) - { - // Remove rows to new size. - m_rows.resize(row); - resize_rows(row-1, cur_cols, col); - } - else - { - assert(cur_rows == row); - resize_rows(cur_rows-1, cur_cols, col); - } - } - - void clear() - { - m_rows.clear(); - m_valid = true; - m_numeric = false; - } - - bool numeric() - { - if (m_valid) - return m_numeric; - - typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end(); - for (; itr_row != itr_row_end; ++itr_row) - { - typename row_type::const_iterator itr_col = itr_row->begin(), itr_col_end = itr_row->end(); - for (; itr_col != itr_col_end; ++itr_col) - { - matrix_element_t elem_type = itr_col->m_type; - if (elem_type != element_numeric && elem_type != element_boolean) - { - m_numeric = false; - m_valid = true; - return m_numeric; - } - } - } - - m_numeric = true; - m_valid = true; - return m_numeric; - } - - bool empty() const - { - return m_rows.empty(); - } - - ::mdds::storage_base<matrix_type>* clone() const - { - return new storage_filled(*this); - } - - const rows_type& get_rows() const { return m_rows; } - -private: - - /** - * Resize rows to a new column size, from row 0 up to specified upper - * row. - */ - void resize_rows(size_t upper_row, size_t cur_cols, size_t new_cols) - { - for (size_t i = 0; i <= upper_row; ++i) - { - // Resize pre-existing rows to new column size. - if (new_cols > cur_cols) - { - size_t new_col_count = new_cols - cur_cols; - for (size_t j = 0; j < new_col_count; ++j) - insert_new_elem(m_rows[i]); - } - else if (new_cols < cur_cols) - m_rows[i].resize(new_cols); - } - } - - void init_row(row_type& row, size_t col_size) - { - row.reserve(col_size); - for (size_t j = 0; j < col_size; ++j) - insert_new_elem(row); - } - - void insert_new_elem(row_type& row) - { - matrix_init_element_t init_type = storage_base<matrix_type>::get_init_type(); - switch (init_type) - { - case matrix_init_element_zero: - row.push_back(new element(static_cast<double>(0.0))); - break; - case matrix_init_element_empty: - row.push_back(new element); - break; - default: - throw matrix_storage_error("unknown init type."); - } - } - -private: - rows_type m_rows; - bool m_numeric:1; - bool m_valid:1; -}; - -/** - * This storage stores only non-empty elements. - */ -template<typename _MatrixType> -class storage_sparse : public storage_base<_MatrixType> -{ - typedef _MatrixType matrix_type; - - typedef typename matrix_type::string_type string_type; - -public: - typedef typename matrix_type::element element; - typedef ::boost::ptr_map<size_t, element> row_type; - typedef ::boost::ptr_map<size_t, row_type> rows_type; - struct elem_wrap - { - const element& operator() (const typename row_type::const_iterator& itr) const - { - return *itr->second; - } - }; - struct rows_wrap - { - const row_type& operator() (const typename rows_type::const_iterator& itr) const - { - return *itr->second; - } - }; - typedef ::mdds::const_itr_access<storage_sparse, elem_wrap, rows_wrap> const_itr_access; - - storage_sparse(size_t _rows, size_t _cols, matrix_init_element_t init_type) : - storage_base<matrix_type>(matrix_storage_sparse, init_type), - m_row_size(_rows), m_col_size(_cols), - m_numeric(_rows && _cols), m_valid(true) - { - switch (storage_base<matrix_type>::get_init_type()) - { - case matrix_init_element_zero: - m_empty_elem.m_type = element_numeric; - m_empty_elem.m_numeric = 0.0; - break; - default: - m_empty_elem.m_type = element_empty; - m_numeric = false; - } - } - - storage_sparse(const storage_sparse& r) : - storage_base<matrix_type>(r), - m_rows(r.m_rows), - m_empty_elem(r.m_empty_elem), - m_row_size(r.m_row_size), - m_col_size(r.m_col_size) {} - - virtual ~storage_sparse() {} - - const_itr_access* get_const_itr_access() const { return new const_itr_access(*this); } - - element & get_element(size_t row, size_t col) - { - if (row >= m_row_size || col >= m_col_size) - throw matrix_storage_error("specified element is out-of-bound."); - - m_valid = false; - - typename rows_type::iterator itr = m_rows.find(row); - if (itr == m_rows.end()) - { - // Insert a brand-new row. - ::std::pair<typename rows_type::iterator, bool> r = m_rows.insert(row, new row_type); - if (!r.second) - throw matrix_storage_error("failed to insert a new row instance into storage_sparse."); - itr = r.first; - } - - row_type& row_store = *itr->second; - typename row_type::iterator itr_elem = row_store.find(col); - if (itr_elem == row_store.end()) - { - // Insert a new element at this column position. - ::std::pair<typename row_type::iterator, bool> r = row_store.insert(col, new element); - if (!r.second) - throw matrix_storage_error("failed to insert a new element instance."); - itr_elem = r.first; - } - return *itr_elem->second; - } - - matrix_element_t get_type(size_t row, size_t col) const - { - typename rows_type::const_iterator itr = m_rows.find(row); - if (itr == m_rows.end()) - return m_empty_elem.m_type; - - const row_type& row_store = *itr->second; - typename row_type::const_iterator itr_elem = row_store.find(col); - if (itr_elem == row_store.end()) - return m_empty_elem.m_type; - - return itr_elem->second->m_type; - } - - double get_numeric(size_t row, size_t col) const - { - const element& elem = get_non_empty_element(row, col); - switch (elem.m_type) - { - case element_numeric: - return elem.m_numeric; - case element_boolean: - return static_cast<double>(elem.m_boolean); - case element_empty: - default: - ; - } - return 0.0; - } - - const string_type* get_string(size_t row, size_t col) const - { - matrix_element_t elem_type = get_type(row, col); - if (elem_type != element_string) - throw matrix_storage_error("element type is not string."); - - return get_non_empty_element(row, col).mp_string; - } - - bool get_boolean(size_t row, size_t col) const - { - matrix_element_t elem_type = get_type(row, col); - if (elem_type != element_boolean) - throw matrix_storage_error("element type is not string."); - - return get_non_empty_element(row, col).m_boolean; - } - - size_t rows() const - { - return m_row_size; - } - - size_t cols() const - { - return m_col_size; - } - - typedef ::std::pair<size_t, size_t> elem_pos_type; - - struct elem_pos_sorter : public ::std::binary_function<elem_pos_type, elem_pos_type, bool> - { - bool operator() (const elem_pos_type& left, const elem_pos_type& right) const - { - if (left.first != right.first) - return left.first < right.first; - return left.second < right.second; - } - }; - - void transpose() - { - using namespace std; - - rows_type trans; - - // First, pick up the positions of all non-empty elements. - vector<elem_pos_type> filled_elems; - { - typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end(); - for (; itr_row != itr_row_end; ++itr_row) - { - size_t row_idx = itr_row->first; - const row_type& row = *itr_row->second; - typename row_type::const_iterator itr_col = row.begin(), itr_col_end = row.end(); - for (; itr_col != itr_col_end; ++itr_col) - { - // Be sure to swap the row and column indices. - filled_elems.push_back(elem_pos_type(itr_col->first, row_idx)); - } - } - } - // Sort by row index first, then by column index. - sort(filled_elems.begin(), filled_elems.end(), elem_pos_sorter()); - - // Iterate through the non-empty element positions and perform - // transposition. - typename vector<elem_pos_type>::const_iterator - itr_pos = filled_elems.begin(), itr_pos_end = filled_elems.end(); - while (itr_pos != itr_pos_end) - { - // First item of the new row. - size_t row_idx = itr_pos->first; - size_t col_idx = itr_pos->second; - pair<typename rows_type::iterator, bool> r = trans.insert(row_idx, new row_type); - if (!r.second) - throw matrix_storage_error("failed to insert a new row instance during transposition."); - - typename rows_type::iterator itr_row = r.first; - row_type& row = *itr_row->second; - pair<typename row_type::iterator, bool> r2 = - row.insert(col_idx, new element(m_rows[col_idx][row_idx])); - if (!r2.second) - throw matrix_storage_error("afiled to insert a new element instance during transposition."); - - // Keep iterating until we get a different row index. - for (++itr_pos; itr_pos != itr_pos_end && itr_pos->first == row_idx; ++itr_pos) - { - col_idx = itr_pos->second; - r2 = row.insert(col_idx, new element(m_rows[col_idx][row_idx])); - if (!r2.second) - throw matrix_storage_error("afiled to insert a new element instance during transposition."); - } - } - - m_rows.swap(trans); - ::std::swap(m_row_size, m_col_size); - } - - void resize(size_t row, size_t col) - { - m_valid = false; - - if (!row || !col) - { - clear(); - return; - } - - // Resizing a sparse matrix need to modify the data only when - // shrinking. - - if (m_row_size > row) - { - // Remove all rows where the row index is greater than or - // equal to 'row'. - typename rows_type::iterator itr = m_rows.lower_bound(row); - m_rows.erase(itr, m_rows.end()); - } - - if (m_col_size > col) - { - typename rows_type::iterator itr = m_rows.begin(), itr_end = m_rows.end(); - for (; itr != itr_end; ++itr) - { - // Now, remove all columns where the column index is - // greater than or equal to 'col'. - row_type& row_container = *itr->second; - typename row_type::iterator itr_elem = row_container.lower_bound(col); - row_container.erase(itr_elem, row_container.end()); - } - } - - m_row_size = row; - m_col_size = col; - } - - void clear() - { - m_rows.clear(); - m_row_size = 0; - m_col_size = 0; - m_valid = true; - m_numeric = false; - } - - bool numeric() - { - using namespace std; - - if (m_valid) - return m_numeric; - - size_t non_empty_count = 0; - typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end(); - for (; itr_row != itr_row_end; ++itr_row) - { - const row_type& row = *itr_row->second; - non_empty_count += row.size(); - assert(row.size() <= m_col_size); - typename row_type::const_iterator itr_col = row.begin(), itr_col_end = row.end(); - for (; itr_col != itr_col_end; ++itr_col) - { - const element& elem = *itr_col->second; - if (elem.m_type != element_numeric && elem.m_type != element_boolean) - { - m_valid = true; - m_numeric = false; - return m_numeric; - } - } - } - - // All non-empty elements are numeric. - - matrix_init_element_t init_type = storage_base<matrix_type>::get_init_type(); - if (init_type == matrix_init_element_zero) - m_numeric = true; - else - { - size_t total_elem_count = m_row_size * m_col_size; - assert(non_empty_count <= total_elem_count); - m_numeric = total_elem_count == non_empty_count; - } - - m_valid = true; - return m_numeric; - } - - bool empty() const - { - // If one of row and column sizes are zero, the other size must be - // zero, and vise versa. - assert((!m_row_size && !m_col_size) || (m_row_size && m_col_size)); - - return m_row_size == 0 || m_col_size == 0; - } - - storage_base<matrix_type>* clone() const - { - return new storage_sparse(*this); - } - - const rows_type& get_rows() const { return m_rows; } - -private: - const element& get_non_empty_element(size_t row, size_t col) const - { - typename rows_type::const_iterator itr = m_rows.find(row); - if (itr == m_rows.end()) - return m_empty_elem; - - const row_type& row_store = *itr->second; - typename row_type::const_iterator itr_elem = row_store.find(col); - if (itr_elem == row_store.end()) - return m_empty_elem; - return *itr_elem->second; - } - -private: - rows_type m_rows; - element m_empty_elem; - size_t m_row_size; - size_t m_col_size; - bool m_numeric:1; - bool m_valid:1; -}; - } +#include "mixed_type_matrix_storage_filled_nested_array.inl" +#include "mixed_type_matrix_storage_filled_linear.inl" +#include "mixed_type_matrix_storage_sparse.inl" + #endif diff --git a/include/mdds/mixed_type_matrix_storage_filled_linear.inl b/include/mdds/mixed_type_matrix_storage_filled_linear.inl new file mode 100644 index 0000000..bd400ec --- /dev/null +++ b/include/mdds/mixed_type_matrix_storage_filled_linear.inl @@ -0,0 +1,701 @@ +/************************************************************************* + * + * Copyright (c) 2011 Kohei Yoshida + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + * + ************************************************************************/ + +namespace mdds { + +/** + * Iterator wrapper for storage whose data provides standard iterators. + */ +template<typename _StoreType, typename _ItrWrap> +class const_itr_access_linear +{ + typedef _StoreType store_type; + typedef _ItrWrap itr_wrap_type; +public: + typedef typename store_type::element element; + + const_itr_access_linear(const store_type& db) : + m_db(db), + m_itr(db.get_array().begin()), + m_itr_end(db.get_array().end()) {} + + const_itr_access_linear(const const_itr_access_linear& r) : + m_db(r.m_db), + m_itr(r.m_itr), + m_itr_end(r.m_itr_end) {} + + bool operator== (const const_itr_access_linear& r) const + { + if (&m_db != &r.m_db) + // different storage instances. + return false; + + return m_itr == r.m_itr; + } + + bool empty() const { return m_db.get_array().begin() == m_itr_end; } + + const element& get() const + { + assert(m_itr != m_itr_end); + return m_itr_wrap(m_itr); + } + + bool inc() + { + if (m_itr == m_itr_end) + return false; + + ++m_itr; + return m_itr != m_itr_end; + } + + bool dec() + { + if (m_itr == m_db.get_array().begin()) + // already on the first element. + return false; + + --m_itr; + return true; + } + + /** + * Set the current iterator position to the end position. + */ + void set_to_end() + { + if (empty()) + return; + + m_itr = m_itr_end; + } +private: + const store_type& m_db; + itr_wrap_type m_itr_wrap; + typename store_type::array_type::const_iterator m_itr; + typename store_type::array_type::const_iterator m_itr_end; +}; + +/** + * Iterator access wrapper whose storage type is a C-style array with no + * standard iterators. + */ +template<typename _StoreType> +class const_itr_access_array +{ + typedef _StoreType store_type; +public: + typedef typename store_type::element element; + + const_itr_access_array(const store_type& db) : + m_db(db), + m_array(db.get_array()), + m_size(db.rows()*db.cols()), + m_pos(0) {} + + const_itr_access_array(const const_itr_access_array& r) : + m_db(r.m_db), + m_array(r.m_array), + m_size(r.m_size), + m_pos(r.m_pos) {} + + bool operator== (const const_itr_access_array& r) const + { + if (&m_db != &r.m_db) + // different storage instances. + return false; + + return m_array == r.m_array && m_size == r.m_size && m_pos == r.m_pos; + } + + bool empty() const { return m_db.empty(); } + + const element& get() const + { + return m_array[m_pos]; + } + + bool inc() + { + if (m_pos == m_size) + return false; + + ++m_pos; + return m_pos != m_size; + } + + bool dec() + { + if (m_pos == 0) + // already on the first element. + return false; + + --m_pos; + return true; + } + + /** + * Set the current iterator position to the end position. + */ + void set_to_end() + { + if (empty()) + return; + + m_pos = m_size; + } +private: + const store_type& m_db; + const typename store_type::element* m_array; + const size_t m_size; + size_t m_pos; +}; + +/** + * This storage creates instance for every single element, even for the + * empty elements. + */ +template<typename _MatrixType> +class storage_filled_linear : public ::mdds::storage_base<_MatrixType> +{ + typedef _MatrixType matrix_type; + typedef typename matrix_type::string_type string_type; + +public: + typedef typename matrix_type::element element; + typedef ::std::vector<element*> array_type; + struct itr_wrap + { + const element& operator() (const typename array_type::const_iterator& itr) const + { + return *(*itr); + } + }; + typedef const_itr_access_linear<storage_filled_linear, itr_wrap> const_itr_access; + + storage_filled_linear(size_t _rows, size_t _cols, matrix_init_element_t init_type) : + storage_base<matrix_type>(matrix_storage_filled, init_type), + m_element_pool(new ::boost::object_pool<element>), + m_rows(_rows), + m_cols(_cols), + m_numeric(false), + m_valid(false) + { + if (init_type == matrix_init_element_zero) + m_init_elem.set_numeric(0.0); + + size_t n = m_rows * m_cols; + m_array.resize(n, &m_init_elem); + } + + storage_filled_linear(const storage_filled_linear& r) : + storage_base<matrix_type>(r), + m_element_pool(new ::boost::object_pool<element>), + m_init_elem(r.m_init_elem), + m_rows(r.m_rows), + m_cols(r.m_cols), + m_numeric(r.m_numeric), + m_valid(r.m_valid) + { + size_t n = r.m_array.size(); + if (!n) + return; + + // Populate the array with initial values first. + m_array.resize(n, &m_init_elem); + + for (size_t i = 0; i < n; ++i) + { + const element* p = r.m_array[i]; + if (p != &r.m_init_elem) + // non-default value. Duplicate the element instance. + m_array[i] = m_element_pool->construct(*p); + } + } + + ~storage_filled_linear() + { + delete m_element_pool; + } + + const_itr_access* get_const_itr_access() const + { + return new const_itr_access(*this); + } + + element& get_element(size_t row, size_t col) + { + m_valid = false; + size_t pos = get_pos(row, col); + if (m_array.at(pos) == &m_init_elem) + { + // Initial element. Instantiate a new element to take its place. + matrix_init_element_t init_type = storage_base<matrix_type>::get_init_type(); + switch (init_type) + { + case matrix_init_element_zero: + m_array[pos] = m_element_pool->construct(static_cast<double>(0.0)); + break; + case matrix_init_element_empty: + m_array[pos] = m_element_pool->construct(); + break; + default: + throw matrix_storage_error("unknown init type."); + } + } + return *m_array[pos]; + } + + matrix_element_t get_type(size_t row, size_t col) const + { + return m_array.at(get_pos(row, col))->m_type; + } + + double get_numeric(size_t row, size_t col) const + { + const element& elem = *m_array.at(get_pos(row, col)); + switch (elem.m_type) + { + case element_numeric: + return elem.m_numeric; + case element_boolean: + return static_cast<double>(elem.m_boolean); + case element_empty: + default: + ; + } + return 0.0; + } + + const string_type* get_string(size_t row, size_t col) const + { + const element& elem = *m_array.at(get_pos(row, col)); + if (elem.m_type != element_string) + throw matrix_storage_error("element type is not string."); + + return elem.mp_string; + } + + bool get_boolean(size_t row, size_t col) const + { + const element& elem = *m_array.at(get_pos(row, col)); + if (elem.m_type != element_boolean) + throw matrix_storage_error("element type is not boolean."); + + return elem.m_boolean; + } + + size_t rows() const + { + return m_rows; + } + + size_t cols() const + { + return m_cols; + } + + void transpose() + { + array_type trans_array(m_array.size(), &m_init_elem); + for (size_t i = 0; i < m_rows; ++i) + for (size_t j = 0; j < m_cols; ++j) + trans_array[m_rows*j+i] = m_array[get_pos(i,j)]; + + m_array.swap(trans_array); + ::std::swap(m_rows, m_cols); + } + + void resize(size_t row, size_t col) + { + m_valid = false; + if (!row || !col) + { + // Empty the matrix. + clear(); + m_rows = row; + m_cols = col; + return; + } + + size_t new_size = row * col; + if (m_array.empty()) + { + // Current matrix is empty. + m_array.resize(new_size, &m_init_elem); + m_rows = row; + m_cols = col; + return; + } + + array_type new_array(new_size, &m_init_elem); + size_t min_rows = ::std::min(row, m_rows); + size_t min_cols = ::std::min(col, m_cols); + for (size_t i = 0; i < min_rows; ++i) + { + for (size_t j = 0; j < min_cols; ++j) + new_array[col*i+j] = m_array[get_pos(i, j)]; + } + + if (row < m_rows) + { + // Delete all element instances that are in the rows being stripped off. + for (size_t i = row; i < m_rows; ++i) + { + for (size_t j = 0; j < m_cols; ++j) + { + element* p = m_array[get_pos(i, j)]; + if (p != &m_init_elem) + m_element_pool->destroy(p); + } + } + } + + if (col < m_cols) + { + // Delete all elements in the columns that are being stripped off. + for (size_t i = 0; i < min_rows; ++i) + { + for (size_t j = col; j < m_cols; ++j) + { + element* p = m_array[get_pos(i, j)]; + if (p != &m_init_elem) + m_element_pool->destroy(p); + } + } + } + + m_array.swap(new_array); + m_rows = row; + m_cols = col; + } + + void clear() + { + delete m_element_pool; + m_element_pool = new ::boost::object_pool<element>; + m_array.clear(); + m_valid = true; + m_numeric = false; + } + + bool numeric() + { + if (m_valid) + return m_numeric; + + typename array_type::const_iterator itr = m_array.begin(), itr_end = m_array.end(); + for (; itr != itr_end; ++itr) + { + const element* p = *itr; + matrix_element_t elem_type = p->m_type; + if (elem_type != element_numeric && elem_type != element_boolean) + { + m_numeric = false; + m_valid = true; + return m_numeric; + } + } + + m_numeric = true; + m_valid = true; + return m_numeric; + } + + bool empty() const + { + return m_array.empty(); + } + + ::mdds::storage_base<matrix_type>* clone() const + { + return new storage_filled_linear(*this); + } + + const array_type& get_array() const { return m_array; } + +private: + + /** + * Get an array position of the data referenced by the row and column + * indices. The array consists of multiple rows, the content of row 0 + * followded by the content of row 1, and so on. <b>Note that no + * boundary check is performed in this method.</b> + * + * @param row 0-based row index. + * @param col 0-based column index. + * @return position in the data array. + */ + size_t get_pos(size_t row, size_t col) const + { + return m_cols * row + col; + } + +private: + ::boost::object_pool<element>* m_element_pool; + array_type m_array; + element m_init_elem; + size_t m_rows; + size_t m_cols; + bool m_numeric:1; + bool m_valid:1; +}; + +/** + * All elements are filled with unique numeric element instances, with their + * initial values being zero. + */ +template<typename _MatrixType> +class storage_filled_linear_zero : public ::mdds::storage_base<_MatrixType> +{ + typedef _MatrixType matrix_type; + typedef typename matrix_type::string_type string_type; + +public: + typedef typename matrix_type::element element; + typedef ::std::vector<element> array_type; + struct itr_wrap + { + const element& operator() (const typename array_type::const_iterator& itr) const + { + return *itr; + } + }; + typedef const_itr_access_linear<storage_filled_linear_zero, itr_wrap> const_itr_access; + + storage_filled_linear_zero(size_t _rows, size_t _cols, matrix_init_element_t init_type) : + storage_base<matrix_type>(matrix_storage_filled_zero, init_type), + m_rows(_rows), + m_cols(_cols), + m_numeric(false), + m_valid(false) + { + assert(init_type == matrix_init_element_zero); + + size_t n = m_rows * m_cols; + if (!n) + return; + + m_array.resize(n, element(0.0)); + } + + storage_filled_linear_zero(const storage_filled_linear_zero& r) : + storage_base<matrix_type>(r), + m_array(r.m_array), + m_rows(r.m_rows), + m_cols(r.m_cols), + m_numeric(r.m_numeric), + m_valid(r.m_valid) {} + + ~storage_filled_linear_zero() {} + + const_itr_access* get_const_itr_access() const + { + return new const_itr_access(*this); + } + + element& get_element(size_t row, size_t col) + { + m_valid = false; + return m_array[get_pos(row,col)]; + } + + matrix_element_t get_type(size_t row, size_t col) const + { + return m_array[get_pos(row,col)].m_type; + } + + double get_numeric(size_t row, size_t col) const + { + const element& elem = m_array[get_pos(row,col)]; + switch (elem.m_type) + { + case element_numeric: + return elem.m_numeric; + case element_boolean: + return static_cast<double>(elem.m_boolean); + case element_empty: + default: + ; + } + return 0.0; + } + + const string_type* get_string(size_t row, size_t col) const + { + const element& elem = m_array[get_pos(row,col)]; + if (elem.m_type != element_string) + throw matrix_storage_error("element type is not string."); + + return elem.mp_string; + } + + bool get_boolean(size_t row, size_t col) const + { + const element& elem = m_array[get_pos(row,col)]; + if (elem.m_type != element_boolean) + throw matrix_storage_error("element type is not boolean."); + + return elem.m_boolean; + } + + size_t rows() const + { + return m_rows; + } + + size_t cols() const + { + return m_cols; + } + + void transpose() + { + if (!m_rows || !m_cols) + // empty matrix - nothing to do. + return; + + array_type trans_array(m_rows*m_cols, element(0.0)); + for (size_t i = 0; i < m_rows; ++i) + for (size_t j = 0; j < m_cols; ++j) + trans_array[m_rows*j+i] = m_array[get_pos(i,j)]; + + m_array.swap(trans_array); + ::std::swap(m_rows, m_cols); + } + + void resize(size_t row, size_t col) + { + m_valid = false; + if (!row || !col) + { + // Empty the matrix. + clear(); + m_rows = row; + m_cols = col; + return; + } + + size_t new_size = row * col; + if (empty()) + { + // Current matrix is empty. + m_array.resize(new_size, element(0.0)); + m_rows = row; + m_cols = col; + return; + } + + array_type new_array(new_size, element(0.0)); + size_t min_rows = ::std::min(row, m_rows); + size_t min_cols = ::std::min(col, m_cols); + for (size_t i = 0; i < min_rows; ++i) + { + for (size_t j = 0; j < min_cols; ++j) + new_array[col*i+j] = m_array[get_pos(i, j)]; + } + + m_array.swap(new_array); + m_rows = row; + m_cols = col; + } + + void clear() + { + m_array.clear(); + m_valid = true; + m_numeric = false; + } + + bool numeric() + { + if (m_valid) + return m_numeric; + + size_t n = m_array.size(); + if (!n) + { + // empty matrix is never considered numeric. + m_numeric = false; + return m_numeric; + } + + for (size_t i = 0; i < n; ++i) + { + matrix_element_t elem_type = m_array[i].m_type; + if (elem_type != element_numeric && elem_type != element_boolean) + { + m_numeric = false; + m_valid = true; + return m_numeric; + } + } + + m_numeric = true; + m_valid = true; + return m_numeric; + } + + bool empty() const + { + return m_array.empty(); + } + + ::mdds::storage_base<matrix_type>* clone() const + { + return new storage_filled_linear_zero(*this); + } + + const array_type& get_array() const { return m_array; } + +private: + + /** + * Get an array position of the data referenced by the row and column + * indices. The array consists of multiple rows, the content of row 0 + * followded by the content of row 1, and so on. <b>Note that no + * boundary check is performed in this method.</b> + * + * @param row 0-based row index. + * @param col 0-based column index. + * @return position in the data array. + */ + size_t get_pos(size_t row, size_t col) const + { + return m_cols * row + col; + } + +private: + array_type m_array; + size_t m_rows; + size_t m_cols; + bool m_numeric:1; + bool m_valid:1; +}; + +} diff --git a/include/mdds/mixed_type_matrix_storage_filled_nested_array.inl b/include/mdds/mixed_type_matrix_storage_filled_nested_array.inl new file mode 100644 index 0000000..acb8662 --- /dev/null +++ b/include/mdds/mixed_type_matrix_storage_filled_nested_array.inl @@ -0,0 +1,374 @@ +/************************************************************************* + * + * Copyright (c) 2011 Kohei Yoshida + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + * + ************************************************************************/ + +namespace mdds { + +/** + * This storage creates instance for every single element, even for the + * empty elements. + */ +template<typename _MatrixType> +class storage_filled_nested_array : public ::mdds::storage_base<_MatrixType> +{ + typedef _MatrixType matrix_type; + typedef typename matrix_type::string_type string_type; + +public: + typedef typename matrix_type::element element; + typedef ::std::vector<element*> row_type; + typedef ::std::vector<row_type*> rows_type; + + struct elem_wrap + { + const element& operator() (const typename row_type::const_iterator& itr) const + { + return *(*itr); + } + }; + struct rows_wrap + { + const row_type& operator() (const typename rows_type::const_iterator& itr) const + { + return *(*itr); + } + }; + typedef ::mdds::const_itr_access<storage_filled_nested_array, elem_wrap, rows_wrap> const_itr_access; + + storage_filled_nested_array(size_t _rows, size_t _cols, matrix_init_element_t init_type) : + storage_base<matrix_type>(matrix_storage_filled, init_type), + m_row_pool(new ::boost::object_pool<row_type>), + m_element_pool(new ::boost::object_pool<element>), + m_numeric(false), + m_valid(false) + { + if (init_type == matrix_init_element_zero) + m_init_elem.set_numeric(0.0); + + m_rows.reserve(_rows); + for (size_t i = 0; i < _rows; ++i) + m_rows.push_back(m_row_pool->construct(_cols, &m_init_elem)); + } + + storage_filled_nested_array(const storage_filled_nested_array& r) : + storage_base<matrix_type>(r), + m_row_pool(new ::boost::object_pool<row_type>), + m_element_pool(new ::boost::object_pool<element>), + m_init_elem(r.m_init_elem), + m_numeric(r.m_numeric), + m_valid(r.m_valid) + { + size_t n = r.m_rows.size(); + m_rows.reserve(n); + for (size_t i = 0; i < n; ++i) + { + const row_type& row_other = *r.m_rows[i]; + size_t col_size = row_other.size(); + m_rows.push_back(m_row_pool->construct(col_size, &m_init_elem)); + row_type& row = *m_rows.back(); + for (size_t j = 0; j < col_size; ++j) + { + if (row_other[j] != &r.m_init_elem) + row[j] = m_element_pool->construct(*row_other[j]); + } + } + } + + virtual ~storage_filled_nested_array() + { + delete m_row_pool; + delete m_element_pool; + } + + const_itr_access* get_const_itr_access() const + { + return new const_itr_access(*this); + } + + element& get_element(size_t row, size_t col) + { + m_valid = false; + if (m_rows.at(row)->at(col) == &m_init_elem) + { + // Initial element. Instantiate a new element to take its place. + matrix_init_element_t init_type = storage_base<matrix_type>::get_init_type(); + switch (init_type) + { + case matrix_init_element_zero: + (*m_rows[row])[col] = m_element_pool->construct(static_cast<double>(0.0)); + break; + case matrix_init_element_empty: + (*m_rows[row])[col] = m_element_pool->construct(); + break; + default: + throw matrix_storage_error("unknown init type."); + } + } + return *(*m_rows[row])[col]; + } + + matrix_element_t get_type(size_t row, size_t col) const + { + return m_rows.at(row)->at(col)->m_type; + } + + double get_numeric(size_t row, size_t col) const + { + const element& elem = *m_rows.at(row)->at(col); + switch (elem.m_type) + { + case element_numeric: + return elem.m_numeric; + case element_boolean: + return static_cast<double>(elem.m_boolean); + case element_empty: + default: + ; + } + return 0.0; + } + + const string_type* get_string(size_t row, size_t col) const + { + const element& elem = *m_rows.at(row)->at(col); + if (elem.m_type != element_string) + throw matrix_storage_error("element type is not string."); + + return elem.mp_string; + } + + bool get_boolean(size_t row, size_t col) const + { + const element& elem = *m_rows.at(row)->at(col); + if (elem.m_type != element_boolean) + throw matrix_storage_error("element type is not boolean."); + + return elem.m_boolean; + } + + size_t rows() const + { + return m_rows.size(); + } + + size_t cols() const + { + return m_rows.empty() ? 0 : m_rows[0]->size(); + } + + void transpose() + { + rows_type trans_mx; + size_t row_size = rows(), col_size = cols(); + trans_mx.reserve(col_size); + for (size_t col = 0; col < col_size; ++col) + { + trans_mx.push_back(m_row_pool->construct()); + row_type& trans_row = *trans_mx.back(); + trans_row.reserve(row_size); + for (size_t row = 0; row < row_size; ++row) + trans_row.push_back((*m_rows[row])[col]); + } + m_rows.swap(trans_mx); + + // Delete the row instances in the old container. + delete_rows(trans_mx, 0); + } + + void resize(size_t row, size_t col) + { + m_valid = false; + if (!row || !col) + { + // Empty the matrix. + clear(); + return; + } + + size_t cur_rows = rows(), cur_cols = cols(); + + if (!cur_rows || !cur_cols) + { + // current matrix is empty. + rows_type new_rows; + new_rows.reserve(row); + for (size_t i = 0; i < row; ++i) + new_rows.push_back(m_row_pool->construct(col, &m_init_elem)); + + m_rows.swap(new_rows); + return; + } + + if (row > cur_rows) + { + // Insert extra rows... + size_t new_row_count = row - cur_rows; + m_rows.reserve(row); + for (size_t i = 0; i < new_row_count; ++i) + m_rows.push_back(m_row_pool->construct(col, &m_init_elem)); + + resize_rows(cur_rows-1, cur_cols, col); + } + else if (cur_rows > row) + { + // Remove rows to new size. Delete the row instances that are to + // be stripped off. + delete_rows(m_rows, row); + m_rows.resize(row); + resize_rows(row-1, cur_cols, col); + } + else + { + assert(cur_rows == row); + resize_rows(cur_rows-1, cur_cols, col); + } + } + + void clear() + { + delete m_row_pool; + delete m_element_pool; + m_row_pool = new ::boost::object_pool<row_type>; + m_element_pool = new ::boost::object_pool<element>; + m_rows.clear(); + m_valid = true; + m_numeric = false; + } + + bool numeric() + { + if (m_valid) + return m_numeric; + + typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end(); + for (; itr_row != itr_row_end; ++itr_row) + { + typename row_type::const_iterator itr_col = (*itr_row)->begin(), itr_col_end = (*itr_row)->end(); + for (; itr_col != itr_col_end; ++itr_col) + { + const element* p = *itr_col; + matrix_element_t elem_type = p->m_type; + if (elem_type != element_numeric && elem_type != element_boolean) + { + m_numeric = false; + m_valid = true; + return m_numeric; + } + } + } + + m_numeric = true; + m_valid = true; + return m_numeric; + } + + bool empty() const + { + return m_rows.empty(); + } + + ::mdds::storage_base<matrix_type>* clone() const + { + return new storage_filled_nested_array(*this); + } + + const rows_type& get_rows() const { return m_rows; } + +private: + + /** + * Resize rows to a new column size, from row 0 up to specified upper + * row. + */ + void resize_rows(size_t upper_row, size_t cur_cols, size_t new_cols) + { + for (size_t i = 0; i <= upper_row; ++i) + { + // Resize pre-existing rows to new column size. + if (new_cols > cur_cols) + { + size_t new_col_count = new_cols - cur_cols; + for (size_t j = 0; j < new_col_count; ++j) + append_new_elem(*m_rows[i]); + } + else if (new_cols < cur_cols) + { + // Delete the instances being cast out. + delete_elems_from_row(*m_rows[i], new_cols); + m_rows[i]->resize(new_cols); + } + } + } + + void delete_rows(rows_type& row_array, size_t first_row) + { + typename rows_type::iterator itr = row_array.begin(), itr_end = row_array.end(); + ::std::advance(itr, first_row); + for (; itr != itr_end; ++itr) + { + row_type* p = *itr; + m_row_pool->destroy(p); + } + } + + void delete_elems_from_row(row_type& row, size_t new_cols) + { + typename row_type::iterator itr = row.begin(), itr_end = row.end(); + ::std::advance(itr, new_cols); + for (; itr != itr_end; ++itr) + { + element* p = *itr; + if (p != &m_init_elem) + m_element_pool->destroy(p); + } + } + + void append_new_elem(row_type& row) + { + matrix_init_element_t init_type = storage_base<matrix_type>::get_init_type(); + switch (init_type) + { + case matrix_init_element_zero: + row.push_back(m_element_pool->construct(static_cast<double>(0.0))); + break; + case matrix_init_element_empty: + row.push_back(m_element_pool->construct()); + break; + default: + throw matrix_storage_error("unknown init type."); + } + } + +private: + ::boost::object_pool<row_type>* m_row_pool; + ::boost::object_pool<element>* m_element_pool; + rows_type m_rows; + element m_init_elem; + bool m_numeric:1; + bool m_valid:1; +}; + +} diff --git a/include/mdds/mixed_type_matrix_storage_sparse.inl b/include/mdds/mixed_type_matrix_storage_sparse.inl new file mode 100644 index 0000000..cc30906 --- /dev/null +++ b/include/mdds/mixed_type_matrix_storage_sparse.inl @@ -0,0 +1,376 @@ +/************************************************************************* + * + * Copyright (c) 2011 Kohei Yoshida + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + * + ************************************************************************/ + +namespace mdds { + +/** + * This storage stores only non-empty elements. + */ +template<typename _MatrixType> +class storage_sparse : public storage_base<_MatrixType> +{ + typedef _MatrixType matrix_type; + + typedef typename matrix_type::string_type string_type; + +public: + typedef typename matrix_type::element element; + typedef ::boost::ptr_map<size_t, element> row_type; + typedef ::boost::ptr_map<size_t, row_type> rows_type; + struct elem_wrap + { + const element& operator() (const typename row_type::const_iterator& itr) const + { + return *itr->second; + } + }; + struct rows_wrap + { + const row_type& operator() (const typename rows_type::const_iterator& itr) const + { + return *itr->second; + } + }; + typedef ::mdds::const_itr_access<storage_sparse, elem_wrap, rows_wrap> const_itr_access; + + storage_sparse(size_t _rows, size_t _cols, matrix_init_element_t init_type) : + storage_base<matrix_type>(matrix_storage_sparse, init_type), + m_row_size(_rows), m_col_size(_cols), + m_numeric(_rows && _cols), m_valid(true) + { + switch (storage_base<matrix_type>::get_init_type()) + { + case matrix_init_element_zero: + m_empty_elem.m_type = element_numeric; + m_empty_elem.m_numeric = 0.0; + break; + default: + m_empty_elem.m_type = element_empty; + m_numeric = false; + } + } + + storage_sparse(const storage_sparse& r) : + storage_base<matrix_type>(r), + m_rows(r.m_rows), + m_empty_elem(r.m_empty_elem), + m_row_size(r.m_row_size), + m_col_size(r.m_col_size) {} + + ~storage_sparse() {} + + const_itr_access* get_const_itr_access() const { return new const_itr_access(*this); } + + element & get_element(size_t row, size_t col) + { + if (row >= m_row_size || col >= m_col_size) + throw matrix_storage_error("specified element is out-of-bound."); + + m_valid = false; + + typename rows_type::iterator itr = m_rows.find(row); + if (itr == m_rows.end()) + { + // Insert a brand-new row. + ::std::pair<typename rows_type::iterator, bool> r = m_rows.insert(row, new row_type); + if (!r.second) + throw matrix_storage_error("failed to insert a new row instance into storage_sparse."); + itr = r.first; + } + + row_type& row_store = *itr->second; + typename row_type::iterator itr_elem = row_store.find(col); + if (itr_elem == row_store.end()) + { + // Insert a new element at this column position. + ::std::pair<typename row_type::iterator, bool> r = row_store.insert(col, new element); + if (!r.second) + throw matrix_storage_error("failed to insert a new element instance."); + itr_elem = r.first; + } + return *itr_elem->second; + } + + matrix_element_t get_type(size_t row, size_t col) const + { + typename rows_type::const_iterator itr = m_rows.find(row); + if (itr == m_rows.end()) + return m_empty_elem.m_type; + + const row_type& row_store = *itr->second; + typename row_type::const_iterator itr_elem = row_store.find(col); + if (itr_elem == row_store.end()) + return m_empty_elem.m_type; + + return itr_elem->second->m_type; + } + + double get_numeric(size_t row, size_t col) const + { + const element& elem = get_non_empty_element(row, col); + switch (elem.m_type) + { + case element_numeric: + return elem.m_numeric; + case element_boolean: + return static_cast<double>(elem.m_boolean); + case element_empty: + default: + ; + } + return 0.0; + } + + const string_type* get_string(size_t row, size_t col) const + { + matrix_element_t elem_type = get_type(row, col); + if (elem_type != element_string) + throw matrix_storage_error("element type is not string."); + + return get_non_empty_element(row, col).mp_string; + } + + bool get_boolean(size_t row, size_t col) const + { + matrix_element_t elem_type = get_type(row, col); + if (elem_type != element_boolean) + throw matrix_storage_error("element type is not string."); + + return get_non_empty_element(row, col).m_boolean; + } + + size_t rows() const + { + return m_row_size; + } + + size_t cols() const + { + return m_col_size; + } + + typedef ::std::pair<size_t, size_t> elem_pos_type; + + struct elem_pos_sorter : public ::std::binary_function<elem_pos_type, elem_pos_type, bool> + { + bool operator() (const elem_pos_type& left, const elem_pos_type& right) const + { + if (left.first != right.first) + return left.first < right.first; + return left.second < right.second; + } + }; + + void transpose() + { + using namespace std; + + rows_type trans; + + // First, pick up the positions of all non-empty elements. + vector<elem_pos_type> filled_elems; + { + typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end(); + for (; itr_row != itr_row_end; ++itr_row) + { + size_t row_idx = itr_row->first; + const row_type& row = *itr_row->second; + typename row_type::const_iterator itr_col = row.begin(), itr_col_end = row.end(); + for (; itr_col != itr_col_end; ++itr_col) + { + // Be sure to swap the row and column indices. + filled_elems.push_back(elem_pos_type(itr_col->first, row_idx)); + } + } + } + // Sort by row index first, then by column index. + sort(filled_elems.begin(), filled_elems.end(), elem_pos_sorter()); + + // Iterate through the non-empty element positions and perform + // transposition. + typename vector<elem_pos_type>::const_iterator + itr_pos = filled_elems.begin(), itr_pos_end = filled_elems.end(); + while (itr_pos != itr_pos_end) + { + // First item of the new row. + size_t row_idx = itr_pos->first; + size_t col_idx = itr_pos->second; + pair<typename rows_type::iterator, bool> r = trans.insert(row_idx, new row_type); + if (!r.second) + throw matrix_storage_error("failed to insert a new row instance during transposition."); + + typename rows_type::iterator itr_row = r.first; + row_type& row = *itr_row->second; + pair<typename row_type::iterator, bool> r2 = + row.insert(col_idx, new element(m_rows[col_idx][row_idx])); + if (!r2.second) + throw matrix_storage_error("afiled to insert a new element instance during transposition."); + + // Keep iterating until we get a different row index. + for (++itr_pos; itr_pos != itr_pos_end && itr_pos->first == row_idx; ++itr_pos) + { + col_idx = itr_pos->second; + r2 = row.insert(col_idx, new element(m_rows[col_idx][row_idx])); + if (!r2.second) + throw matrix_storage_error("afiled to insert a new element instance during transposition."); + } + } + + m_rows.swap(trans); + ::std::swap(m_row_size, m_col_size); + } + + void resize(size_t row, size_t col) + { + m_valid = false; + + if (!row || !col) + { + clear(); + return; + } + + // Resizing a sparse matrix need to modify the data only when + // shrinking. + + if (m_row_size > row) + { + // Remove all rows where the row index is greater than or + // equal to 'row'. + typename rows_type::iterator itr = m_rows.lower_bound(row); + m_rows.erase(itr, m_rows.end()); + } + + if (m_col_size > col) + { + typename rows_type::iterator itr = m_rows.begin(), itr_end = m_rows.end(); + for (; itr != itr_end; ++itr) + { + // Now, remove all columns where the column index is + // greater than or equal to 'col'. + row_type& row_container = *itr->second; + typename row_type::iterator itr_elem = row_container.lower_bound(col); + row_container.erase(itr_elem, row_container.end()); + } + } + + m_row_size = row; + m_col_size = col; + } + + void clear() + { + m_rows.clear(); + m_row_size = 0; + m_col_size = 0; + m_valid = true; + m_numeric = false; + } + + bool numeric() + { + using namespace std; + + if (m_valid) + return m_numeric; + + size_t non_empty_count = 0; + typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end(); + for (; itr_row != itr_row_end; ++itr_row) + { + const row_type& row = *itr_row->second; + non_empty_count += row.size(); + assert(row.size() <= m_col_size); + typename row_type::const_iterator itr_col = row.begin(), itr_col_end = row.end(); + for (; itr_col != itr_col_end; ++itr_col) + { + const element& elem = *itr_col->second; + if (elem.m_type != element_numeric && elem.m_type != element_boolean) + { + m_valid = true; + m_numeric = false; + return m_numeric; + } + } + } + + // All non-empty elements are numeric. + + matrix_init_element_t init_type = storage_base<matrix_type>::get_init_type(); + if (init_type == matrix_init_element_zero) + m_numeric = true; + else + { + size_t total_elem_count = m_row_size * m_col_size; + assert(non_empty_count <= total_elem_count); + m_numeric = total_elem_count == non_empty_count; + } + + m_valid = true; + return m_numeric; + } + + bool empty() const + { + // If one of row and column sizes are zero, the other size must be + // zero, and vise versa. + assert((!m_row_size && !m_col_size) || (m_row_size && m_col_size)); + + return m_row_size == 0 || m_col_size == 0; + } + + storage_base<matrix_type>* clone() const + { + return new storage_sparse(*this); + } + + const rows_type& get_rows() const { return m_rows; } + +private: + const element& get_non_empty_element(size_t row, size_t col) const + { + typename rows_type::const_iterator itr = m_rows.find(row); + if (itr == m_rows.end()) + return m_empty_elem; + + const row_type& row_store = *itr->second; + typename row_type::const_iterator itr_elem = row_store.find(col); + if (itr_elem == row_store.end()) + return m_empty_elem; + return *itr_elem->second; + } + +private: + rows_type m_rows; + element m_empty_elem; + size_t m_row_size; + size_t m_col_size; + bool m_numeric:1; + bool m_valid:1; +}; + +} diff --git a/include/mdds/rectangle_set.hpp b/include/mdds/rectangle_set.hpp index 5cfd99e..82269a3 100644 --- a/include/mdds/rectangle_set.hpp +++ b/include/mdds/rectangle_set.hpp @@ -1,6 +1,6 @@ /************************************************************************* * - * Copyright (c) 2010 Kohei Yoshida + * Copyright (c) 2010, 2011 Kohei Yoshida * * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation @@ -248,250 +248,8 @@ private: dataset_type m_dataset; }; -template<typename _Key, typename _Data> -rectangle_set<_Key,_Data>::rectangle_set() -{ -} - -template<typename _Key, typename _Data> -rectangle_set<_Key,_Data>::rectangle_set(const rectangle_set& r) : - m_inner_map(r.m_inner_map), - m_dataset(r.m_dataset) -{ - build_outer_segment_tree(); } -template<typename _Key, typename _Data> -rectangle_set<_Key,_Data>::~rectangle_set() -{ -} - -template<typename _Key, typename _Data> -rectangle_set<_Key,_Data>& rectangle_set<_Key,_Data>::operator= (const rectangle_set& r) -{ - clear(); // Don't forget to clear the internal state beforehands. - - m_inner_map = r.m_inner_map; - m_dataset = r.m_dataset; - build_outer_segment_tree(); - return *this; -} - -template<typename _Key, typename _Data> -bool rectangle_set<_Key,_Data>::operator== (const rectangle_set& r) const -{ - if (m_dataset.size() != r.m_dataset.size()) - return false; - - typename dataset_type::const_iterator itr = m_dataset.begin(), itr_end = m_dataset.end(); - for (; itr != itr_end; ++itr) - { - typename dataset_type::const_iterator itr_rhs = r.m_dataset.find(itr->first); - if (itr_rhs == r.m_dataset.end()) - return false; - - if (itr->second != itr_rhs->second) - return false; - } - - return true; -} - -template<typename _Key, typename _Data> -bool rectangle_set<_Key,_Data>::insert(key_type x1, key_type y1, key_type x2, key_type y2, data_type* data) -{ - // Make sure this is not a duplicate. - if (m_dataset.find(data) != m_dataset.end()) - return false; - - // Check if interval x1 - x2 is already stored. - interval_type outer_interval = interval_type(x1, x2); - typename inner_segment_map_type::iterator itr = m_inner_map.find(outer_interval); - if (itr == m_inner_map.end()) - { - // this interval has not yet been stored. Create a new inner segment - // tree instance for this interval. - ::std::pair<typename inner_segment_map_type::iterator, bool> r = - m_inner_map.insert(outer_interval, new inner_type); - if (!r.second) - throw general_error("inner segment tree insertion failed."); - - itr = r.first; - - // Register the pointer to this inner segment tree instance with the - // outer segment tree. - if (!m_outer_segments.insert(x1, x2, itr->second)) - // This should never fail if my logic is correct. - throw general_error("failed to insert an inner segment tree pointer into the outer segment tree."); - } - - inner_type* inner_tree = itr->second; - inner_tree->insert(y1, y2, data); - m_dataset.insert(typename dataset_type::value_type(data, rectangle(x1, y1, x2, y2))); - - return true; -} - -template<typename _Key, typename _Data> -bool rectangle_set<_Key,_Data>::search(key_type x, key_type y, search_result_type& result) -{ - typename outer_type::search_result_type inner_trees; - if (!m_outer_segments.is_tree_valid()) - m_outer_segments.build_tree(); - - if (!m_outer_segments.search(x, inner_trees)) - return false; - - typename outer_type::search_result_type::iterator itr_tree = inner_trees.begin(), itr_tree_end = inner_trees.end(); - for (; itr_tree != itr_tree_end; ++itr_tree) - { - inner_type* inner_tree = *itr_tree; - if (!inner_tree->is_tree_valid()) - inner_tree->build_tree(); - - // Search all relevant inner trees and aggregate results. - if (!inner_tree->search(y, result)) - return false; - } - return true; -} - -template<typename _Key, typename _Data> -typename rectangle_set<_Key,_Data>::search_result -rectangle_set<_Key,_Data>::search(key_type x, key_type y) -{ - search_result result; - typename outer_type::search_result_type inner_trees; - if (!m_outer_segments.is_tree_valid()) - m_outer_segments.build_tree(); - - if (!m_outer_segments.search(x, inner_trees)) - return result; - - typename outer_type::search_result_type::iterator itr_tree = inner_trees.begin(), itr_tree_end = inner_trees.end(); - for (; itr_tree != itr_tree_end; ++itr_tree) - { - inner_type* inner_tree = *itr_tree; - if (!inner_tree->is_tree_valid()) - inner_tree->build_tree(); - - // Search all relevant inner trees and aggregate results. - inner_tree->search(y, result); - } - return result; -} - -template<typename _Key, typename _Data> -void rectangle_set<_Key,_Data>::remove(data_type* data) -{ - typename dataset_type::iterator itr_data = m_dataset.find(data); - if (itr_data == m_dataset.end()) - // The data is not stored in this data structure. - return; - - const rectangle& rect = itr_data->second; - - // Find the corresponding inner segment tree for this outer interval. - interval_type outer(rect.x1, rect.x2); - typename inner_segment_map_type::iterator itr_seg = m_inner_map.find(outer); - if (itr_seg == m_inner_map.end()) - throw general_error("inconsistent internal state: failed to find an internal segment tree for an existing interval."); - - // Remove data from the inner segment tree. - inner_type* inner_tree = itr_seg->second; - inner_tree->remove(data); - if (inner_tree->empty()) - { - // This inner tree is now empty. Erase it. - m_outer_segments.remove(inner_tree); - m_inner_map.erase(itr_seg); - } - - // Remove it from the data set as well. - m_dataset.erase(data); -} - -template<typename _Key, typename _Data> -void rectangle_set<_Key,_Data>::clear() -{ - m_outer_segments.clear(); - m_inner_map.clear(); - m_dataset.clear(); -} - -template<typename _Key, typename _Data> -size_t rectangle_set<_Key,_Data>::size() const -{ - return m_dataset.size(); -} - -template<typename _Key, typename _Data> -bool rectangle_set<_Key,_Data>::empty() const -{ - return m_dataset.empty(); -} - -template<typename _Key, typename _Data> -void rectangle_set<_Key,_Data>::build_outer_segment_tree() -{ - // Re-construct the outer segment tree from the authoritative inner tree - // map. - typename inner_segment_map_type::iterator itr = m_inner_map.begin(), itr_end = m_inner_map.end(); - for (; itr != itr_end; ++itr) - { - const interval_type& interval = itr->first; - inner_type* tree = itr->second; - m_outer_segments.insert(interval.first, interval.second, tree); - } -} - -#ifdef UNIT_TEST -template<typename _Key, typename _Data> -void rectangle_set<_Key,_Data>::dump_rectangles() const -{ - using namespace std; - cout << "dump rectangles ------------------------------------------------" << endl; - if (m_dataset.empty()) - { - cout << "No rectangles in the data set." << endl; - return; - } - - typename dataset_type::const_iterator itr = m_dataset.begin(), itr_end = m_dataset.end(); - for (; itr != itr_end; ++itr) - { - const rectangle& rect = itr->second; - cout << itr->first->name << ": (x1,y1,x2,y2) = " - << "(" << rect.x1 << "," << rect.y1 << "," << rect.x2 << "," << rect.y2 << ")" - << endl; - } -} - -template<typename _Key, typename _Data> -bool rectangle_set<_Key,_Data>::verify_rectangles(const dataset_type& expected) const -{ - if (m_dataset.size() != expected.size()) - // Data sizes differ. - return false; - - typename dataset_type::const_iterator itr_data = m_dataset.begin(), itr_data_end = m_dataset.end(); - for (; itr_data != itr_data_end; ++itr_data) - { - const data_type* data = itr_data->first; - typename dataset_type::const_iterator itr_test = expected.find(data); - if (itr_test == expected.end()) - // Pointer in one container but not in the other. - return false; - - if (itr_data->second != itr_test->second) - // Rectangle positions and/or sizes differ. - return false; - } - - return true; -} -#endif - -} +#include "rectangle_set_def.inl" #endif diff --git a/include/mdds/rectangle_set.hpp b/include/mdds/rectangle_set_def.inl similarity index 56% copy from include/mdds/rectangle_set.hpp copy to include/mdds/rectangle_set_def.inl index 5cfd99e..a2f40e1 100644 --- a/include/mdds/rectangle_set.hpp +++ b/include/mdds/rectangle_set_def.inl @@ -1,6 +1,6 @@ /************************************************************************* * - * Copyright (c) 2010 Kohei Yoshida + * Copyright (c) 2011 Kohei Yoshida * * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation @@ -25,230 +25,9 @@ * ************************************************************************/ -#ifndef __MDDS_RECTANGLE_SET_HPP__ -#define __MDDS_RECTANGLE_SET_HPP__ - -#include "segment_tree.hpp" -#include "global.hpp" -#include "hash_container/map.hpp" - -#include <vector> -#include <boost/ptr_container/ptr_map.hpp> - namespace mdds { template<typename _Key, typename _Data> -class rectangle_set -{ -public: - typedef _Key key_type; - typedef _Data data_type; - -#ifdef UNIT_TEST -public: -#else -private: -#endif - struct rectangle - { - key_type x1; - key_type y1; - key_type x2; - key_type y2; - - rectangle(key_type _x1, key_type _y1, key_type _x2, key_type _y2) : - x1(_x1), y1(_y1), x2(_x2), y2(_y2) {} - - rectangle(const rectangle& r) : - x1(r.x1), y1(r.y1), x2(r.x2), y2(r.y2) {} - - rectangle& operator= (const rectangle& r) - { - x1 = r.x1; - y1 = r.y1; - x2 = r.x2; - y2 = r.y2; - return *this; - } - - bool operator== (const rectangle& r) const - { - return x1 == r.x1 && y1 == r.y1 && x2 == r.x2 && y2 == r.y2; - } - - bool operator!= (const rectangle& r) const - { - return !operator==(r); - } - }; - typedef _mdds_unordered_map_type<data_type*, rectangle> dataset_type; -private: - typedef segment_tree<key_type, data_type> inner_type; - typedef segment_tree<key_type, inner_type> outer_type; - - typedef ::std::pair<key_type, key_type> interval_type; - typedef ::boost::ptr_map<interval_type, inner_type> inner_segment_map_type; - -public: - typedef typename inner_type::search_result_type search_result_type; - - /** - * Most of the implementation of search_result and its iterator is in - * segment_tree since the iteration logic is identical & depends on the - * segment_tree internals. - */ - class search_result : public inner_type::search_result_base - { - public: - typedef typename inner_type::search_result_base::res_chains_type res_chains_type; - typedef typename inner_type::search_result_base::res_chains_ptr res_chains_ptr; - typedef typename inner_type::data_chain_type data_chain_type; - - public: - - class iterator : public inner_type::iterator_base - { - friend class rectangle_set<_Key,_Data>::search_result; - private: - iterator(const res_chains_ptr& p) : inner_type::iterator_base(p) {} - public: - iterator() : inner_type::iterator_base() {} - }; - - search_result() : inner_type::search_result_base() {} - search_result(const search_result& r) : inner_type::search_result_base(r) {} - - typename search_result::iterator begin() - { - typename search_result::iterator itr( - inner_type::search_result_base::get_res_chains()); - itr.move_to_front(); - return itr; - } - - typename search_result::iterator end() - { - typename search_result::iterator itr( - inner_type::search_result_base::get_res_chains()); - itr.move_to_end(); - return itr; - } - }; - - rectangle_set(); - rectangle_set(const rectangle_set& r); - ~rectangle_set(); - - rectangle_set& operator= (const rectangle_set& r); - - /** - * Equality between two instances of rectangle_set is evaluated based on - * the stored rectangle instances; their pointer values and geometries. - */ - bool operator== (const rectangle_set& r) const; - - bool operator!= (const rectangle_set& r) const { return !operator==(r); } - - /** - * Insert a new rectangle (and data associated with it) into the set. - * Note that insertion of duplicate data instance is not allowed. A data - * is considered a duplicate if its pointer value is identical to one of - * the data instances already stored within. Also note that <i>the end - * point of a rectangle is non-inclusive; a rectangle of (x1,y1) - (x2,y2) - * means that the rectangle spans x1 <= x < x2 and y1 <= y < y2.</i> - * - * @param x1 lower x coordinate of the rectangle. Inclusive. - * @param y1 lower y coordinate of the rectangle. Inclusive. - * @param x2 upper x coordinate of the rectangle. Non-inclusive. - * @param y2 upper y coordinate of the rectangle. Non-inclusive. - * @param data pointer to data instance associated with this rectangle. - * <i>Note that the caller is responsible for managing the - * life cycle of the data instance</i>. - * - * @return true if a rectangle successfully inserted, false otherwise. - */ - bool insert(key_type x1, key_type y1, key_type x2, key_type y2, data_type* data); - - /** - * Search and collect all rectangles that contains a given point. - * - * @param x x coordinate of a query point. - * @param y y coordinate of a query point. - * @param result array of pointers to rectangle instances. - * - * @return true if the search is successful, false otherwise. - */ - bool search(key_type x, key_type y, search_result_type& result); - - /** - * Search and collect all rectangles containing a given point. - * - * @param x x coordinate of a query point. - * @param y y coordinate of a query point. - * - * @return object containing the result of the search, which can be - * accessed via iterator. - */ - search_result search(key_type x, key_type y); - - /** - * Remove a rectangle instance pointed to by a given pointer. - * - * @param data pointer that points to the rectangle instance you wish to - * remove from the set. - */ - void remove(data_type* data); - - /** - * Clear all rectangles stored in the set. - */ - void clear(); - - /** - * Return the number of rectangles currently stored in the set. - * - * @return number of stored rectangles. - */ - size_t size() const; - - /** - * Check whether or not the set is empty. - * - * @return true if the set is empty, false otherwise. - */ - bool empty() const; - -private: - void build_outer_segment_tree(); - -#ifdef UNIT_TEST -public: - void dump_rectangles() const; - bool verify_rectangles(const dataset_type& expected) const; -#endif - -private: - - /** - * This data member stores pointers to the inner segment tree instances - * associated with outer intervals. Used to speed up searches. - */ - outer_type m_outer_segments; - - /** - * This data member owns the inner segment_tree instances. - */ - inner_segment_map_type m_inner_map; - - /** - * Used to keep track of currently stored data instances, to prevent - * insertion of duplicates. Duplicates are defined as data objects having - * identical pointer value. - */ - dataset_type m_dataset; -}; - -template<typename _Key, typename _Data> rectangle_set<_Key,_Data>::rectangle_set() { } @@ -493,5 +272,3 @@ bool rectangle_set<_Key,_Data>::verify_rectangles(const dataset_type& expected) #endif } - -#endif diff --git a/misc/mdds.spec.in b/misc/mdds.spec.in index 31e5dd3..2b461f2 100644 --- a/misc/mdds.spec.in +++ b/misc/mdds.spec.in @@ -41,7 +41,7 @@ Authors: %setup -q -n %{name}_%{version} %build -%configure --docdir=%buildroot%{_docdir} +%configure --docdir=%{_docdir} %check #make check @@ -54,7 +54,7 @@ rm -rf %buildroot %files devel %defattr(-,root,root) -%doc %buildroot%{_docdir} +%doc %{_docdir} %{_includedir}/%{name} %changelog diff --git a/src/array_creation_perf_test.cpp b/src/array_creation_perf_test.cpp new file mode 100644 index 0000000..359c8f5 --- /dev/null +++ b/src/array_creation_perf_test.cpp @@ -0,0 +1,81 @@ + +#include <vector> +#include <boost/pool/object_pool.hpp> +#include <iostream> + +#include <stdio.h> +#include <string> +#include <sys/time.h> + +namespace { + +class StackPrinter +{ +public: + explicit StackPrinter(const char* msg) : + msMsg(msg) + { + fprintf(stdout, "%s: --begin\n", msMsg.c_str()); + mfStartTime = getTime(); + } + + ~StackPrinter() + { + double fEndTime = getTime(); + fprintf(stdout, "%s: --end (duration: %g sec)\n", msMsg.c_str(), (fEndTime-mfStartTime)); + } + + void printTime(int line) const + { + double fEndTime = getTime(); + fprintf(stdout, "%s: --(%d) (duration: %g sec)\n", msMsg.c_str(), line, (fEndTime-mfStartTime)); + } + +private: + double getTime() const + { + timeval tv; + gettimeofday(&tv, NULL); + return tv.tv_sec + tv.tv_usec / 1000000.0; + } + + ::std::string msMsg; + double mfStartTime; +}; + +} + +using namespace std; +using ::boost::object_pool; + +struct element +{ + double number; + element() : number(0.0) {} + element(double num) : number(num) {} +}; + +int main() +{ + size_t n = 100000000; + { + StackPrinter __stack_printer__("::main object pool with vector"); + object_pool<element> elem_pool; + vector<element*> vec; + vec.reserve(n); + for (size_t i = 0; i < n; ++i) + vec.push_back(elem_pool.construct()); + + cout << "size of vector: " << vec.size() << endl; + } + + { + StackPrinter __stack_printer__("::main array new"); + element* parray = new element[n]; + for (size_t i = 0; i < n; ++i) + parray[i].number = 1.0; + cout << "size of array: " << sizeof(parray) / sizeof(element) << endl; + delete[] parray; + } + return 0; +} diff --git a/src/mixed_type_matrix_test.cpp b/src/mixed_type_matrix_test.cpp index 9e4a1ea..6fb046c 100644 --- a/src/mixed_type_matrix_test.cpp +++ b/src/mixed_type_matrix_test.cpp @@ -25,8 +25,8 @@ * ************************************************************************/ -#include "mdds/mixed_type_matrix.hpp" #include "test_global.hpp" +#include "mdds/mixed_type_matrix.hpp" #include <sstream> #include <cassert> @@ -263,11 +263,16 @@ void mtm_test_resize(matrix_density_t density) assert(mxsize.first == 6); assert(mxsize.second == 4); mx.resize(6, 6); + mx.set_boolean(5, 5, true); mx.dump(); mxsize = mx.size(); assert(mxsize.first == 6); assert(mxsize.second == 6); mx.resize(3, 6); + mx.set_numeric(2, 2, 4.2); + mx.set_numeric(2, 3, 3.2); + mx.set_numeric(2, 4, 2.2); + mx.set_numeric(2, 5, 1.2); mx.dump(); mxsize = mx.size(); assert(mxsize.first == 3); @@ -690,15 +695,16 @@ void traverse_itr_access(typename _StoreType::const_itr_access& itr_access) assert(i == 0); } +template<typename _FilledStoreType> void mtm_test_iterator_access_filled(size_t rows, size_t cols) { StackPrinter __stack_printer__("::mtm_test_iterator_access_filled"); - typedef storage_filled<mx_type> store_type; + typedef _FilledStoreType store_type; store_type store(rows, cols, matrix_init_element_zero); { cout << "rows: " << rows << " cols: " << cols << endl; - store_type::const_itr_access* itr_access = store.get_const_itr_access(); + typename store_type::const_itr_access* itr_access = store.get_const_itr_access(); traverse_itr_access<store_type>(*itr_access); delete itr_access; } @@ -839,6 +845,48 @@ void mtm_test_const_iterator() assert(itr == itr_end); // not found. } +/** + * Measure the performance of object instantiation for filled storage. + */ +void mtm_perf_test_filled_storage_creation() +{ + StackPrinter __stack_printer__("::mtm_perf_test_filled_storage_creation"); + cout << "measuring performance on matrix object creation." << endl; + size_t rowsize = 1000; + size_t obj_count = 30000; + cout << "row size: " << rowsize << " object count: " << obj_count << endl; + for (size_t colsize = 1; colsize <= 3; ++colsize) + { + StackPrinter __stack_printer2__("::mtm_perf_test_filled_storage_creation::group"); + cout << "column size: " << colsize << endl; + for (size_t i = 0; i < obj_count; ++i) + mx_type mx(rowsize, colsize, matrix_density_filled_zero); + } +} + +void mtm_perf_test_filled_storage_set_numeric() +{ + StackPrinter __stack_printer__("::mtm_perf_test_filled_storage_set_numeric"); + cout << "measuring performance on matrix object creation and populating it with numeric data." << endl; + size_t rowsize = 1000; + size_t obj_count = 30000; + cout << "row size: " << rowsize << " object count: " << obj_count << endl; + for (size_t colsize = 1; colsize <= 3; ++colsize) + { + StackPrinter __stack_printer2__("::mtm_perf_test_filled_storage_set_numeric::group"); + cout << "column size: " << colsize << endl; + for (size_t i = 0; i < obj_count; ++i) + { + mx_type mx(rowsize, colsize, matrix_density_filled_zero); + for (size_t row = 0; row < rowsize; ++row) + { + for (size_t col = 0; col < colsize; ++col) + mx.set_numeric(row, col, 1.0); + } + } + } +} + int main(int argc, char** argv) { cmd_options opt; @@ -861,16 +909,35 @@ int main(int argc, char** argv) run_tests_on_all_density_types(mtm_test_flag_storage); - mtm_test_iterator_access_filled(1, 1); - mtm_test_iterator_access_filled(3, 1); - mtm_test_iterator_access_filled(1, 3); - mtm_test_iterator_access_filled(3, 3); - mtm_test_iterator_access_filled(0, 0); + mtm_test_iterator_access_filled<storage_filled_nested_array<mx_type> >(1, 1); + mtm_test_iterator_access_filled<storage_filled_nested_array<mx_type> >(3, 1); + mtm_test_iterator_access_filled<storage_filled_nested_array<mx_type> >(1, 3); + mtm_test_iterator_access_filled<storage_filled_nested_array<mx_type> >(3, 3); + mtm_test_iterator_access_filled<storage_filled_nested_array<mx_type> >(0, 0); + + mtm_test_iterator_access_filled<storage_filled_linear<mx_type> >(1, 1); + mtm_test_iterator_access_filled<storage_filled_linear<mx_type> >(3, 1); + mtm_test_iterator_access_filled<storage_filled_linear<mx_type> >(1, 3); + mtm_test_iterator_access_filled<storage_filled_linear<mx_type> >(3, 3); + mtm_test_iterator_access_filled<storage_filled_linear<mx_type> >(0, 0); + + mtm_test_iterator_access_filled<storage_filled_linear_zero<mx_type> >(1, 1); + mtm_test_iterator_access_filled<storage_filled_linear_zero<mx_type> >(3, 1); + mtm_test_iterator_access_filled<storage_filled_linear_zero<mx_type> >(1, 3); + mtm_test_iterator_access_filled<storage_filled_linear_zero<mx_type> >(3, 3); + mtm_test_iterator_access_filled<storage_filled_linear_zero<mx_type> >(0, 0); mtm_test_iterator_access_sparse(); mtm_test_const_iterator(); } + + if (opt.test_perf) + { + mtm_perf_test_filled_storage_creation(); + mtm_perf_test_filled_storage_set_numeric(); + } + cout << "Test finished successfully!" << endl; return EXIT_SUCCESS; } diff --git a/src/test_global.hpp b/src/test_global.hpp index acf03c8..f734465 100644 --- a/src/test_global.hpp +++ b/src/test_global.hpp @@ -33,6 +33,7 @@ #ifdef _WIN32 #include <windows.h> #undef max +#undef min #else #include <sys/time.h> #endif -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-openoffice/mdds.git
