[Boost-commit] svn:boost r49786 - in sandbox/SOC/2008/graphs/trunk: boost boost/graphs/adjacency_list libs/graphs/test

Subject: [Boost-commit] svn:boost r49786 - in sandbox/SOC/2008/graphs/trunk: boost boost/graphs/adjacency_list libs/graphs/test
From: asutton_at_[hidden]
Date: 2008-11-16 08:14:30

Author: asutton
Date: 2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
New Revision: 49786
URL: http://svn.boost.org/trac/boost/changeset/49786

Log:
More work rewriting the internals of adjacency list.

Added:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store.hpp   (contents, props changed)
      - copied, changed from r49774, /sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store_traits.hpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/unordered_pair.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp   (contents, props changed)
Removed:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store_traits.hpp
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/containers.hpp                          |     9 ++++++++                                
   sandbox/SOC/2008/graphs/trunk/boost/counted_list.hpp                        |    27 ++++++++++++++++++++---                 
   sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp                         |    45 ++++++++++++++++----------------------- 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp   |    18 +++++++++------                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store.hpp  |    15 +++++++++++++                           
   sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp |    13 ++++++-----                             
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/Jamfile                      |     4 +-                                      
   7 files changed, 86 insertions(+), 45 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/containers.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/containers.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/containers.hpp	2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
@@ -7,6 +7,8 @@
 #ifndef BOOST_CONTAINERS_HPP
 #define BOOST_CONTAINERS_HPP
 
+#include <algorithm>
+
 #include <boost/type_traits.hpp>
 
 // Forward declarations of stdandard types. Jeremy's right! There does need
@@ -247,6 +249,13 @@
     { return c.find(x); }
 }
 
+/**
+ * Insert an object into a container. The actual method of insertion depends
+ * on the underlying container. For back insertion sequences, this appends
+ * the object to the sequence. For associative containers, it is simply
+ * inserted. For unique associative containers, the object is not inserted if
+ * an object with the same key already exists.
+ */
 template <typename Container, typename T>
 inline typename Container::iterator
 insert(Container& c, T const& x)

Modified: sandbox/SOC/2008/graphs/trunk/boost/counted_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/counted_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/counted_list.hpp	2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
@@ -5,6 +5,8 @@
 #include <list>
 #include <algorithm>
 
+#include <boost/containers.hpp>
+
 namespace boost {
 
 /**
@@ -20,9 +22,9 @@
     typedef List base_type;
 public:
     typedef typename base_type::value_type value_type;
-    typedef typename base-type::pointer pointer;
+    typedef typename base_type::pointer pointer;
     typedef typename base_type::reference reference;
-    typedef typename base-type::const_reference const_reference;
+    typedef typename base_type::const_reference const_reference;
     typedef typename base_type::iterator iterator;
     typedef typename base_type::const_iterator const_iterator;
     typedef typename base_type::reverse_iterator reverse_iterator;
@@ -65,7 +67,7 @@
     const_reverse_iterator rend() const     { return _list.rend(); }
 
     size_type size() const          { return _size; }
-    size_type max_size() const      { return _list.max_size() }
+    size_type max_size() const      { return _list.max_size(); }
 
     bool empty() const              { return _list.empty(); }
 
@@ -109,7 +111,7 @@
     }
 
     void resize(size_type n, T const& x = T())
-    { _list.resize(n, t); _size = n; }
+    { _list.resize(n, x); _size = n; }
 
     void clear()
     { _list.clear(); _size = 0; }
@@ -134,6 +136,23 @@
     size_type   _size;
 };
 
+// Specialize container traits
+template <typename T, typename Alloc, typename List>
+struct container_traits<counted_list<T, Alloc, List>>
+{
+    typedef list_tag category;
+    typedef stable_iterator_tag iterator_stability;
+};
+
+// Specialize descriptor traits
+template <typename T, typename Alloc, typename List>
+struct descriptor_traits<counted_list<T, Alloc, List>>
+{
+    typedef node_descriptor<blob<sizeof(typename std::list<T, Alloc>::iterator)>> descriptor_type;
+    typedef stable_mutators_tag descriptor_stability;
+
+};
+
 } /* namespace boost */
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp	2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
@@ -83,10 +83,9 @@
  *
  * This inherits a specialized version of container traits from boost/pending.
  */
-template <typename Container, typename Kind = basic_descriptor_kind>
+template <typename Container>
 struct descriptor_traits
 {
-    typedef Kind descriptor_kind;
     typedef typename Container::descriptor_type descriptor_type;
     typedef typename Container::mutator_stability mutator_stability;
 };
@@ -159,58 +158,52 @@
 // Specializations
 
 // Vector
-template <typename T, typename Alloc, typename Kind>
-struct descriptor_traits<std::vector<T, Alloc>, Kind>
+template <typename T, typename Alloc>
+struct descriptor_traits<std::vector<T, Alloc>>
 {
-    typedef Kind descriptor_kind;
-    typedef index_descriptor<typename std::vector<T, Alloc>::size_type, Kind> descriptor_type;
+    typedef index_descriptor<typename std::vector<T, Alloc>::size_type> descriptor_type;
     typedef unstable_remove_tag descriptor_stability;
 };
 
 // List
-template <typename T, typename Alloc, typename Kind>
-struct descriptor_traits<std::list<T, Alloc>, Kind>
+template <typename T, typename Alloc>
+struct descriptor_traits<std::list<T, Alloc>>
 {
-    typedef Kind descriptor_kind;
-    typedef node_descriptor<blob<sizeof(typename std::list<T, Alloc>::iterator)>, Kind> descriptor_type;
+    typedef node_descriptor<blob<sizeof(typename std::list<T, Alloc>::iterator)>> descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
 // TODO: Dequeue
 
 // Set
-template <typename T, typename Comp, typename Alloc, typename Kind>
-struct descriptor_traits<std::set<T, Comp, Alloc>, Kind>
+template <typename T, typename Comp, typename Alloc>
+struct descriptor_traits<std::set<T, Comp, Alloc>>
 {
-    typedef Kind descriptor_kind;
-    typedef node_descriptor<blob<sizeof(typename std::set<T, Comp, Alloc>::iterator)>, Kind> descriptor_type;
+    typedef node_descriptor<blob<sizeof(typename std::set<T, Comp, Alloc>::iterator)>> descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
 // Multiset
-template <typename T, typename Comp, typename Alloc, typename Kind>
-struct descriptor_traits<std::multiset<T, Comp, Alloc>, Kind>
+template <typename T, typename Comp, typename Alloc>
+struct descriptor_traits<std::multiset<T, Comp, Alloc>>
 {
-    typedef Kind descriptor_kind;
-    typedef node_descriptor<blob<sizeof(typename std::multiset<T, Comp, Alloc>::iterator)>, Kind> descriptor_type;
+    typedef node_descriptor<blob<sizeof(typename std::multiset<T, Comp, Alloc>::iterator)>> descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
 // Map
-template <typename Key, typename T, typename Comp, typename Alloc, typename Kind>
-struct descriptor_traits<std::map<Key, T, Comp, Alloc>, Kind>
+template <typename Key, typename T, typename Comp, typename Alloc>
+struct descriptor_traits<std::map<Key, T, Comp, Alloc>>
 {
-    typedef Kind descriptor_kind;
-    typedef node_descriptor<blob<sizeof(typename std::map<Key, T, Comp, Alloc>::iterator)>, Kind> descriptor_type;
+    typedef node_descriptor<blob<sizeof(typename std::map<Key, T, Comp, Alloc>::iterator)>> descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
 // Multimap
-template <typename Key, typename T, typename Comp, typename Alloc, typename Kind>
-struct descriptor_traits<std::multimap<Key, T, Comp, Alloc>, Kind>
+template <typename Key, typename T, typename Comp, typename Alloc>
+struct descriptor_traits<std::multimap<Key, T, Comp, Alloc>>
 {
-    typedef Kind descriptor_kind;
-    typedef node_descriptor<blob<sizeof(typename std::multimap<Key, T, Comp, Alloc>::iterator)>, Kind> descriptor_type;
+    typedef node_descriptor<blob<sizeof(typename std::multimap<Key, T, Comp, Alloc>::iterator)>> descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp	2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
@@ -6,6 +6,8 @@
 
 #include <boost/none.hpp>
 #include <boost/descriptors.hpp>
+#include <boost/counted_list.hpp>
+#include <boost/graphs/adjacency_list/vertex_store.hpp>
 #include <boost/graphs/adjacency_list/vertex_iterator.hpp>
 
 namespace boost { namespace graphs { namespace adjacency_list {
@@ -14,29 +16,31 @@
 template <typename, typename> class vertices_list;
 
 /**
- * This metafunction defines the basic elements of a vertex list.
+ * This metafunction defines the basic elements of a vertex list. This builds
+ * the list on a counted_list over the std::list class.
  */
 template <template <typename> class Alloc = std::allocator>
 struct vertex_list
 {
     typedef unused key_type;
 
-    typedef std::list<int, Alloc<int>> dummy;
-    typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
+    typedef typename descriptor_traits<
+        std::list<int, Alloc<int>>
+    >::descriptor_type vertex_descriptor;
 
     template <typename Vertex>
-    struct store
+    struct vertex_store
     {
-        typedef vertices_list<Vertex, Alloc<Vertex>> type;
+        typedef Alloc<Vertex> allocator_type;
+        typedef counted_list<Vertex, allocator_type> type;
     };
 };
 
-
 template <typename T, typename A>
 struct vertex_store_traits<counted_list<T,A>>
 {
 private:
-    typedef std::counted_list<T,A> base_type;
+    typedef counted_list<T,A> base_type;
 public:
     typedef typename base_type::iterator store_iterator;
 

Copied: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store.hpp (from r49774, /sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store_traits.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store_traits.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store.hpp	2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
@@ -2,8 +2,13 @@
 #ifndef BOOST_GRAPH_ADJLIST_VERTEX_STORE_TRAITS_HPP
 #define BOOST_GRAPH_ADJLIST_VERTEX_STORE_TRAITS_HPP
 
+#include <boost/containers.hpp>
+#include <boost/descriptors.hpp>
+
 namespace boost { namespace graphs { namespace adjacency_list {
 
+struct vertex_descriptor_kind { };
+
 /**
  * The vertex store traits defines the basic types associate with a vertex set.
  */
@@ -11,6 +16,16 @@
 struct vertex_store_traits
 { };
 
+/**
+ * Add a vertex to the given store, returning a descriptor to the added
+ * vertex. The semantics and performance of this function depend on the
+ * kind of vertex store.
+ */
+template <typename Store, typename Vertex>
+typename descriptor_traits<Store>::descriptor_type
+add_vertex_to_store(Store& store, Vertex v)
+{ return make_descriptor(store, insert(store, v)); }
+
 } } } /* namespace boost::graphs::adjacency_list */
 
 #endif

Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store_traits.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store_traits.hpp	2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
+++ (empty file)
@@ -1,16 +0,0 @@
-
-#ifndef BOOST_GRAPH_ADJLIST_VERTEX_STORE_TRAITS_HPP
-#define BOOST_GRAPH_ADJLIST_VERTEX_STORE_TRAITS_HPP
-
-namespace boost { namespace graphs { namespace adjacency_list {
-
-/**
- * The vertex store traits defines the basic types associate with a vertex set.
- */
-template <typename VertexStore>
-struct vertex_store_traits
-{ };
-
-} } } /* namespace boost::graphs::adjacency_list */
-
-#endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp	2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
@@ -8,7 +8,7 @@
 #include <boost/none.hpp>
 #include <boost/descriptors.hpp>
 #include <boost/graphs/utility.hpp>
-#include <boost/graphs/adjacency_list/vertex_store_traits.hpp>
+#include <boost/graphs/adjacency_list/vertex_store.hpp>
 #include <boost/graphs/adjacency_list/vertex_iterator.hpp>
 
 namespace boost { namespace graphs { namespace adjacency_list {
@@ -31,17 +31,18 @@
 {
     typedef unused key_type;
 
-    typedef std::vector<int, Alloc<int>> dummy;
-    typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
+    typedef typename descriptor_traits<
+        std::vector<int, Alloc<int>>
+    >::descriptor_type vertex_descriptor;
 
     // The store metafunction generates the type used to store vertices in
     // either a directed or undirected graph. This metafunction takes the
     // fully configured vertex type as a type parameter.
     template <typename Vertex>
-    struct store
+    struct vertex_store
     {
-        typedef Alloc<Vertex> allocator;
-        typedef vertices_vector<Vertex, allocator> type;
+        typedef Alloc<Vertex> allocator_type;
+        typedef std::vector<Vertex, allocator_type> type;
     };
 };
 

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/Jamfile	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/Jamfile	2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
@@ -17,6 +17,8 @@
 # exe props : props.cpp : <include>../../ <include>/usr/local/include ;
 # exe edge : edge.cpp : <include>../../ <include>/usr/local/include ;
 
+exe vertex_store : vertex_store.cpp ;
+
 exe opt : opt.cpp ;
 exe unordered_pair : unordered_pair.cpp ;
 exe desc : desc.cpp ;
@@ -42,5 +44,3 @@
 exe basic_matrix : basic_matrix.cpp ;
 exe un_matrix : un_matrix.cpp ;
 
-# Various application tests
-exe dawg : dawg.cpp ;

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/unordered_pair.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/unordered_pair.cpp	2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
@@ -0,0 +1,13 @@
+
+#include <boost/assert.hpp>
+#include <boost/unordered_pair.hpp>
+
+using namespace boost;
+
+int main()
+{
+    unordered_pair<int> a(5, 10), b(10, 5);
+    BOOST_ASSERT(a.first() == 5 && a.second() == 10);
+    BOOST_ASSERT(b.first() == 5 && b.second() == 10);
+    return 0;
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp	2008-11-16 08:14:29 EST (Sun, 16 Nov 2008)
@@ -0,0 +1,36 @@
+
+#include <iostream>
+
+#include <boost/graphs/adjacency_list/vertex_store.hpp>
+#include <boost/graphs/adjacency_list/vertex_vector.hpp>
+#include <boost/graphs/adjacency_list/vertex_list.hpp>
+
+using namespace std;
+using namespace boost;
+using namespace boost::graphs::adjacency_list;
+
+struct my_vertex
+{ };
+
+template <typename Store>
+void test()
+{
+    typedef typename Store::value_type Vertex;
+    typedef typename descriptor_traits<Store>::descriptor_type VertexDesc;
+
+    Store store;
+
+    VertexDesc u = add_vertex_to_store(store, Vertex());
+    VertexDesc v = add_vertex_to_store(store, Vertex());
+    cout << u << " " << v << endl;
+}
+
+int main()
+{
+    typedef vertex_vector<>::vertex_store<my_vertex>::type VV;
+    typedef vertex_list<>::vertex_store<my_vertex>::type VL;
+
+    test<VV>();
+    test<VL>();
+}
+