[Boost-commit] svn:boost r49166 - sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix

Subject: [Boost-commit] svn:boost r49166 - sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix
From: asutton_at_[hidden]
Date: 2008-10-07 11:33:32

Author: asutton
Date: 2008-10-07 11:33:31 EDT (Tue, 07 Oct 2008)
New Revision: 49166
URL: http://svn.boost.org/trac/boost/changeset/49166

Log:
- Broke out some of the details into their own headers.
- Implemented a specialization on optional_value that will use absentee
  values to indicate missing edges.

Added:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix/column_traits.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix/matrix_element.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix/basic_matrix.hpp |    96 ++++++++++------------------------------
   1 files changed, 24 insertions(+), 72 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix/basic_matrix.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix/basic_matrix.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix/basic_matrix.hpp	2008-10-07 11:33:31 EDT (Tue, 07 Oct 2008)
@@ -5,73 +5,17 @@
 #include <vector>
 
 #include <boost/optional.hpp>
+#include <boost/optional_value.hpp>
 #include <boost/none.hpp>
 #include <boost/triple.hpp>
 
+#include <boost/graphs/adjacency_matrix/matrix_element.hpp>
+#include <boost/graphs/adjacency_matrix/column_traits.hpp>
+
 namespace boost { namespace graphs { namespace adjacency_matrix {
 
 namespace detail
 {
-    // Metafunctions to generate the value type of a basic matrix.
-    // TODO: This facility probably needs to be exposed to other matrix
-    // implementations (e.g., triangular matrix, compressed matrix, etc.).
-    template <typename T>
-    struct matrix_element { typedef optional<T> type; };
-    template <> struct matrix_element<none> { typedef bool type; };
-
-    // Specialize the case of matrix references and various operations on them.
-    // Note that the generic case is empty.
-    template <typename T> struct column_traits { };
-    template <typename T>
-    struct column_traits<std::vector<optional<T>>>
-    {
-        typedef std::vector<optional<T>> container;
-        typedef typename container::size_type size_type;
-        typedef typename container::reference reference;
-        typedef typename container::const_reference const_reference;
-
-        typedef T const& get_result;
-
-        static optional<T> make_value(T const& x)
-        { return optional<T>(x); }
-
-        // This can easily segfault c[i] is not valid.
-        get_result get(container const& c, size_type i)
-        { return c[i].get(); }
-
-        static void set(container& c, size_type i)
-        { c[i] = optional<T>(); }
-
-        static void set(container&c, size_type i, T const& x)
-        { c[i] = x; }
-
-        static void clear(container& c, size_type i)
-        { c[i].reset(); }
-    };
-    template <>
-    struct column_traits<std::vector<bool>>
-    {
-        typedef std::vector<bool> container;
-        typedef container::size_type size_type;
-        typedef container::reference reference;
-        typedef container::const_reference const_reference;
-
-        typedef const_reference get_result;
-
-        static bool make_value(none)
-        { return false; }
-
-        static get_result get(container const& c, size_type i)
-        { return c[i]; }
-
-        static void set(container& c, size_type i)
-        { c[i] = true; }
-
-        static void clear(container& c, size_type i)
-        { c[i] = false; }
-    };
-
-
     // A little helper function for the template constructor.
     // TODO Write this for tuples also.
     template <typename Matrix, typename T1, typename T2>
@@ -85,10 +29,7 @@
 
 /**
  * An unoptimized implementation of the basic square matrix that contains
- * optional elements T. Note that the underlying storage type is specialized
- * for the type 'none', because this is essentially already a boolean data
- * structure, and we don't need to store any additional information. Otherwise,
- * T is made to be optional<T>.
+ * optional elements T.
  *
  * This is not a basic matrix in the linear algebra sense of things. This is a
  * legitimate container, albeit arranged in a fairly rigid fashion. This class
@@ -96,19 +37,26 @@
  * The reason for this is that we can return optional values for all non-boolean
  * value types.
  *
+ * There are three important variations of this structure that depend on the
+ * type T. If T is given as none, then the value type stored by this class is
+ * boolean. If T is an optional_value<U,A> then this stores exactly objects of
+ * exactly that type, buit the value_type is reinterpreted to be U. Otherwise,
+ * this will store optional<T> and the value_type is T.
+ *
  * This is currently implemented using std::vectors, but could potentially be
  * rewritten to use a simple dynamic array.
+ *
+ * @todo Invert the meanings of element_type and value_type.
  */
 template <typename T, template <typename> class Allocator = std::allocator>
 struct basic_matrix
 {
-    typedef typename detail::matrix_element<T>::type value_type;
-    typedef std::vector<value_type> columns_type;    // contains edges
-    typedef std::vector<columns_type> rows_type;     // contains rows
+    typedef typename detail::matrix_element<T>::value_type value_type;
+    typedef typename detail::matrix_element<T>::element_type element_type;
+    typedef std::vector<element_type> columns_type;     // contains edges
+    typedef std::vector<columns_type> rows_type;        // contains rows
 
     typedef detail::column_traits<columns_type> ct;
-
-    // The reference type of these vectors may not be the same as value_type&.
     typedef typename ct::reference reference;
     typedef typename ct::const_reference const_reference;
 
@@ -116,7 +64,11 @@
 
     /** @name Constructors/Destructor */
     //@{
-    basic_matrix(size_type n, T const& x = T())
+    basic_matrix(size_type n)
+        : _rows(n, columns_type(n))
+    { }
+
+    basic_matrix(size_type n, value_type const& x)
         : _rows(n, columns_type(n, ct::make_value(x)))
     { }
 
@@ -170,7 +122,7 @@
     /**
      * Set the value of this element to the given value.
      */
-    void set(size_type i, size_type j, T const& x)
+    void set(size_type i, size_type j, element_type const& x)
     { ct::set(_rows[i], j, x); }
 
     /**
@@ -202,6 +154,6 @@
     rows_type _rows;
 };
 
-} } }
+} } } /* namespace boost::graphs::adjacency_matrix */
 
 #endif

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix/column_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix/column_traits.hpp	2008-10-07 11:33:31 EDT (Tue, 07 Oct 2008)
@@ -0,0 +1,98 @@
+
+#ifndef BOOST_GRAPHS_ADJMATRIX_COLUMN_TRAITS_HPP
+#define BOOST_GRAPHS_ADJMATRIX_COLUMN_TRAITS_HPP
+
+namespace boost { namespace graphs { namespace adjacency_matrix {
+
+namespace detail
+{
+    // Specialize the case of matrix references and various operations on them.
+    // Note that the generic case is empty to force compiler errors.
+    template <typename T>
+    struct column_traits { };
+
+    // Delegate operations onto a vector of optionals.
+    template <typename T>
+    struct column_traits<std::vector<optional<T>>>
+    {
+        typedef std::vector<optional<T>> container;
+        typedef typename container::size_type size_type;
+        typedef typename container::reference reference;
+        typedef typename container::const_reference const_reference;
+
+        typedef T const& get_result;
+
+        static optional<T> make_value(T const& x)
+        { return optional<T>(x); }
+
+        // This can easily segfault c[i] is not valid.
+        get_result get(container const& c, size_type i)
+        { return c[i].get(); }
+
+        /* Set the optional to a default-constructed value. */
+        static void set(container& c, size_type i)
+        { c[i] = optional<T>(T()); }
+
+        /* Set the element to a valid value x. */
+        static void set(container&c, size_type i, T const& x)
+        { c[i] = x; }
+
+        static void clear(container& c, size_type i)
+        { c[i].reset(); }
+    };
+
+    template <typename T, typename A>
+    struct column_traits<std::vector<optional_value<T,A>>>
+    {
+        typedef std::vector<optional_value<T,A>> container;
+        typedef typename container::size_type size_type;
+        typedef typename container::reference reference;
+        typedef typename container::const_reference const_reference;
+
+        typedef T const& get_result;
+
+        static optional_value<T,A> make_value(T const& x)
+        { return optional_value<T,A>(x); }
+
+        // This can easily segfault c[i] is not valid.
+        get_result get(container const& c, size_type i)
+        { return c[i].get(); }
+
+        static void set(container& c, size_type i)
+        { c[i] = optional_value<T>(T()); }
+
+        static void set(container&c, size_type i, T const& x)
+        { c[i] = x; }
+
+        static void clear(container& c, size_type i)
+        { c[i].reset(); }
+    };
+
+    // Delegate operations onto the yea-olde bit vector.
+    template <>
+    struct column_traits<std::vector<bool>>
+    {
+        typedef std::vector<bool> container;
+        typedef container::size_type size_type;
+        typedef container::reference reference;
+        typedef container::const_reference const_reference;
+
+        typedef const_reference get_result;
+
+        static bool make_value(none)
+        { return false; }
+
+        static get_result get(container const& c, size_type i)
+        { return c[i]; }
+
+        static void set(container& c, size_type i)
+        { c[i] = true; }
+
+        static void clear(container& c, size_type i)
+        { c[i] = false; }
+    };
+}
+
+} } } /* namespace boost::graphs::adjacency_matrix */
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix/matrix_element.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_matrix/matrix_element.hpp	2008-10-07 11:33:31 EDT (Tue, 07 Oct 2008)
@@ -0,0 +1,41 @@
+
+#ifndef BOOST_GRAPHS_ADJMATRIX_MATRIX_ELEMENT_HPP
+#define BOOST_GRAPHS_ADJMATRIX_MATRIX_ELEMENT_HPP
+
+namespace boost { namespace graphs { namespace adjacency_matrix {
+
+namespace detail
+{
+    // Metafunctions to generate the value type of a basic matrix.
+    // TODO: This facility probably needs to be exposed to other matrix
+    // implementations (e.g., triangular matrix, compressed matrix, etc.).
+    template <typename T>
+    struct matrix_element
+    {
+        typedef T value_type;
+        typedef optional<T> element_type;
+    };
+
+    // When parameterized over optional values, we simply store those objects.
+    // Note that this reduces the storage cost by using the absentee value of
+    // the optional_value to represent missing values.
+    template <typename T, typename A>
+    struct matrix_element<optional_value<T,A>>
+    {
+        typedef T value_type;
+        typedef optional_value<T,A> element_type;
+    };
+
+    // For unparameterized matrix elements, we can simply revert to using a
+    // boolean value to indicate the presence or absence of edge types.
+    template <>
+    struct matrix_element<none>
+    {
+        typedef none value_type;
+        typedef bool element_type;
+    };
+}
+
+} } } /* namespace boost::graphs::adjacency_matrix */
+
+#endif