[mdds] 15/62: Imported Upstream version 0.5.3
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 <rene@debian.org>
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 <kohei.yoshida@gmail.com>.
#
@@ -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='kohei.yoshida@gmail.com'
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
Reply to: