Subject: [Boost-commit] svn:boost r49838 - in sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list: . vs
From: asutton_at_[hidden]
Date: 2008-11-19 10:07:54
Author: asutton
Date: 2008-11-19 10:07:53 EST (Wed, 19 Nov 2008)
New Revision: 49838
URL: http://svn.boost.org/trac/boost/changeset/49838
Log:
More work on rewriting the adjlist
Added:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/
Text files modified:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp | 16 ---------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_map.hpp | 3 -
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp | 17 ----------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp | 65 ++++++++++++++++++++++-----------------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp | 17 ----------
5 files changed, 37 insertions(+), 81 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp 2008-11-19 10:07:53 EST (Wed, 19 Nov 2008)
@@ -10,9 +10,6 @@
namespace boost { namespace graphs { namespace adjacency_list {
-// Forward declarations
-template <typename, typename> class vertices_list;
-
/**
* @param Alloc A unary template class that will allocate stored vertices.
*/
@@ -33,19 +30,6 @@
};
};
-template <typename T, typename A>
-struct vertex_store_traits<counted_list<T,A>>
-{
-private:
- typedef counted_list<T,A> base_type;
-public:
- typedef typename base_type::iterator store_iterator;
-
- typedef typename base_type::size_type vertices_size_type;
- typedef typename descriptor_traits<base_type>::descriptor_type vertex_descriptor;
- typedef basic_vertex_iterator<base_type> vertex_iterator;
- typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
-};
} } } /* namespace boost::graphs::adjacency_list */
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_map.hpp 2008-11-19 10:07:53 EST (Wed, 19 Nov 2008)
@@ -9,9 +9,6 @@
namespace boost { namespace graphs { namespace adjacency_list {
-// Forward declarations
-template <typename, typename, typename, typename> class vertices_map;
-
/**
* @param Key The key type of the vertex map can be any LessThanComparable type.
* @param Compare A unary template class that implements a comparison of keys.
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp 2008-11-19 10:07:53 EST (Wed, 19 Nov 2008)
@@ -10,8 +10,6 @@
namespace boost { namespace graphs { namespace adjacency_list {
-// Forward declarations
-template <typename, typename, typename> class vertices_set;
/**
* @param Compare A unary template class that compares vertex label.
@@ -40,21 +38,6 @@
};
};
-
-template <typename T, typename A, typename C>
-struct vertex_store_traits<std::set<T,A,C>>
-{
-private:
- typedef std::vector<T,A> base_type;
-public:
- typedef typename base_type::iterator store_iterator;
-
- typedef typename base_type::size_type vertices_size_type;
- typedef typename descriptor_traits<base_type>::descriptor_type vertex_descriptor;
- typedef basic_vertex_iterator<base_type> vertex_iterator;
- typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
-};
-
} } } /* namespace boost::graphs::adjacency_list */
#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp 2008-11-19 10:07:53 EST (Wed, 19 Nov 2008)
@@ -8,16 +8,31 @@
#include <boost/descriptors.hpp>
#include <boost/graphs/label.hpp>
-#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
+#include <boost/graphs/adjacency_list/vs/vector.hpp>
-namespace boost { namespace graphs { namespace adjacency_list {
+// The Vertex Store defines the generic interface for working with a vertex
+// set for both directed and undirected adjacency lists. Its primary goal is
+// to provide generic interfaces that abstract common operations on these
+// sets. Important kinds of types are:
+// - Store - the selected container. Must model Container.
+// - Iterator - a non-const iterator into the store.
+// - Size - the size type of the container
+// - Vertex - a type of vertex. Can be labelled.
+// - Label - a vertex label
+// - Key - a key maapping to a vertex.
+// - Result - pair<Iterator, bool>
+//
+// Supported operations are:
+// - Iterator vs_add_vertex (Store, Vertex)
+// - Iterator vs_add_vertex (Store, Key, Vertex)
+// - Result vs_try_add_vertex (Store, Vertex)
+// - Result vs_try_add_vertex (Store, Key, Vertex)
+// - Iterator vs_find_vertex (Store, Label)
+// - void vs_remove_vertex (Store, Iterator)
+// - bool vs_empty (Store)
+// - Size vs_size (Store)
-/**
- * The vertex store traits defines the basic types associate with a vertex set.
- */
-template <typename VertexStore>
-struct vertex_store_traits
-{ };
+namespace boost { namespace graphs { namespace adjacency_list {
namespace detail
{
@@ -50,17 +65,6 @@
bind2nd(labelled_equal_to<typename Store::value_type>(), l));
}
- // Iterate and compare for sequences.
- template <typename Store, typename Label>
- inline typename Store::const_iterator
- dispatch_vs_find(Store const& store, Label const& l, sequence_tag)
- {
- return std::find_if(
- store.begin(),
- store.end(),
- bind2nd(labelled_equal_to<typename Store::value_type>(), l));
- }
-
// Associative containers already forward the label as the key, so we just
// have to use the basic find command.
template <typename Store, typename Label>
@@ -68,11 +72,6 @@
dispatch_vs_find(Store& store, Label const& l, associative_container_tag)
{ return store.find(l); }
- template <typename Store, typename Label>
- inline typename Store::const_iterator
- dispatch_vs_find(Store const& store, Label const& l, associative_container_tag)
- { return store.find(l); }
-
// Explicitly remove the ability use this function, by failing a concept
// check when it is instantiated.
template <typename Store>
@@ -137,10 +136,11 @@
vs_find_vertex(Store& store, Label const& l)
{ return detail::dispatch_vs_find(store, l, container_category(store)); }
+// Does not return a const iterator!
template <typename Store, typename Label>
-inline typename Store::const_iterator
+inline typename Store::iterator
vs_find_vertex(Store const& store, Label const& l)
-{ return detail::dispatch_vs_find(store, l, container_category(store)); }
+{ return detail::dispatch_vs_find(const_cast<Store&>(store), l, container_category(store)); }
//@}
/**
@@ -149,12 +149,21 @@
* store, it cannot operate on edges.
*/
//@{
-// Since all container support a positional erase.
-// TODO: Can I make this fail to compile if Store is
template <typename Store>
void vs_remove_vertex(Store& store, typename Store::iterator i)
{ detail::dispatch_vs_remove(store, i, container_category(store)); }
//@}
+
+/** Return the number of elements in the vertex store. */
+template <typename Store>
+typename Store::size_type vs_size(Store const& store)
+{ return store.size(); }
+
+/** Return true if the store is empty. */
+template <typename Store>
+bool vs_empty(Store const& store)
+{ return store.empty(); }
+
} } } /* namespace boost::graphs::adjacency_list */
#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp 2008-11-19 10:07:53 EST (Wed, 19 Nov 2008)
@@ -10,9 +10,6 @@
namespace boost { namespace graphs { namespace adjacency_list {
-// Forward declarations
-template <typename, typename> struct vertices_vector;
-
/**
* @param Alloc A unary template class that will allocate stored vertices.
*/
@@ -36,20 +33,6 @@
};
};
-template <typename T, typename A>
-struct vertex_store_traits<std::vector<T,A>>
-{
-private:
- typedef std::vector<T,A> base_type;
-public:
- typedef typename base_type::iterator store_iterator;
-
- typedef typename base_type::size_type vertices_size_type;
- typedef typename descriptor_traits<base_type>::descriptor_type vertex_descriptor;
- typedef basic_vertex_iterator<base_type> vertex_iterator;
- typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
-};
-
} } } /* namespace boost::graphs::adjacency_list */
#endif