From: asutton_at_[hidden]
Date: 2008-07-07 07:23:02
Author: asutton
Date: 2008-07-07 07:23:01 EDT (Mon, 07 Jul 2008)
New Revision: 47177
URL: http://svn.boost.org/trac/boost/changeset/47177
Log:
Rewriting all of the vertex stores.
Fixed demangle so it doesn't leak memory.
Making a vertex set test.
Added:
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp
- copied, changed from r47111, /sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp
Removed:
sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/containers.hpp | 19 ---
sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp | 24 ++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp | 5
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp | 196 +++++++++--------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp | 217 +++++++++------------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp | 5
sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp | 5
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp | 40 ++++++
8 files changed, 161 insertions(+), 350 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-07-07 07:23:01 EDT (Mon, 07 Jul 2008)
@@ -238,21 +238,6 @@
inline typename Container::iterator
find(Container& c, T const& x, associative_container_tag)
{ return c.find(x); }
-
- // Erase implementations
- template <typename Container>
- inline typename Container::iterator
- erase(Container& c, typename Container::iterator i, sequence_tag)
- { return c.erase(i); }
-
- template <typename Container>
- inline typename Container::iterator
- erase(Container& c, typename Container::iterator i, associative_container_tag)
- {
- typename Container::iterator j = ++i;
- c.erase(i);
- return j;
- }
}
template <typename Container, typename T>
@@ -266,9 +251,9 @@
{ return dispatch::find(c, x, container_category(c)); }
template <typename Container>
-inline typename Container::iterator
+void
erase(Container& c, typename Container::iterator i)
-{ return dispatch::erase(c, i, container_category(c)); }
+{ c.erase(i); }
#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-07-07 07:23:01 EDT (Mon, 07 Jul 2008)
@@ -161,34 +161,34 @@
// TODO: Dequeue
// Set
-template <typename T, typename Compare, typename Alloc>
-struct descriptor_traits<std::set<T, Compare, Alloc>>
+template <typename T, typename Comp, typename Alloc>
+struct descriptor_traits<std::set<T, Comp, Alloc>>
{
- typedef node_descriptor<blob<sizeof(typename std::set<T, Compare, Alloc>::iterator)>> descriptor_type;
+ typedef node_descriptor<blob<sizeof(typename std::set<T, Comp, Alloc>::iterator)>> descriptor_type;
typedef stable_descriptor_tag descriptor_stability;
};
// Multiset
-template <typename T, typename Compare, typename Alloc>
-struct descriptor_traits<std::multiset<T, Compare, Alloc>>
+template <typename T, typename Comp, typename Alloc>
+struct descriptor_traits<std::multiset<T, Comp, Alloc>>
{
- typedef node_descriptor<blob<sizeof(typename std::multiset<T, Compare, Alloc>::iterator)>> descriptor_type;
+ typedef node_descriptor<blob<sizeof(typename std::multiset<T, Comp, Alloc>::iterator)>> descriptor_type;
typedef stable_descriptor_tag descriptor_stability;
};
// Map
-template <typename K, typename T, typename Compare, typename Alloc>
-struct descriptor_traits<std::map<K, T, Compare, Alloc>>
+template <typename Key, typename T, typename Comp, typename Alloc>
+struct descriptor_traits<std::map<Key, T, Comp, Alloc>>
{
- typedef node_descriptor<blob<sizeof(typename std::map<T, K, Compare, Alloc>::iterator)>> descriptor_type;
+ typedef node_descriptor<blob<sizeof(typename std::map<Key, T, Comp, Alloc>::iterator)>> descriptor_type;
typedef stable_descriptor_tag descriptor_stability;
};
// Multimap
-template <typename K, typename T, typename Compare, typename Alloc>
-struct descriptor_traits<std::multimap<K, T, Compare, Alloc>>
+template <typename Key, typename T, typename Comp, typename Alloc>
+struct descriptor_traits<std::multimap<Key, T, Comp, Alloc>>
{
- typedef node_descriptor<blob<sizeof(typename std::multimap<T, K, Compare, Alloc>::iterator)>> descriptor_type;
+ typedef node_descriptor<blob<sizeof(typename std::multimap<Key, T, Comp, Alloc>::iterator)>> descriptor_type;
typedef stable_descriptor_tag descriptor_stability;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp 2008-07-07 07:23:01 EDT (Mon, 07 Jul 2008)
@@ -9,8 +9,7 @@
#include "vertex_iterator.hpp"
// Forward declarations
-template <typename V, template <typename> class A> class vertex_list_elem;
-template <typename V, typename A> class vertex_list_impl;
+template <typename, typename> class vertex_list_impl;
/**
* This metafunction defines the basic elements of a vertex list.
@@ -88,7 +87,7 @@
//@{
inline void remove(vertex_descriptor v)
{
- _verts.erase(make_iterator(_verts, v));
+ erase(_verts, make_iterator(_verts, v));
--_size;
}
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp 2008-07-07 07:23:01 EDT (Mon, 07 Jul 2008)
@@ -4,11 +4,11 @@
#include <map>
-#include "vertex_descriptor.hpp"
+#include <boost/descriptors.hpp>
+
#include "vertex_iterator.hpp"
// Forward declarations
-template <typename, typename, typename, template <typename> class> class vertex_map_elem;
template <typename, typename, typename, typename> class vertex_map_impl;
/**
@@ -30,63 +30,25 @@
*/
template <
typename Key,
- template <typename> class Compare,
- template <typename> class Alloc>
-struct basic_vertex_map
+ template <typename> class Compare = std::less,
+ template <typename> class Alloc = std::allocator>
+struct vertex_map
{
typedef Key key_type;
- typedef basic_vertex_descriptor<void*> descriptor_type;
+
+ typedef std::map<Key, int, Compare<Key>, Alloc<std::pair<Key, int>>> dummy;
+ typedef typename descriptor_traits<dummy>::descriptor_type descriptor_type;
template <typename Vertex>
struct store
{
- // Build the key comparator (note: independent of vertex!)
- typedef Compare<key_type> compare_type;
-
- // Build the stored vertex type.
- typedef vertex_map_elem<Vertex, Key, compare_type, Alloc> stored_vertex;
-
- // Build the allocator
- typedef Alloc<stored_vertex> allocator_type;
-
- // Build the underlying store
- typedef vertex_map_impl<stored_vertex, key_type, compare_type, allocator_type> type;
+ typedef vertex_map_impl<
+ Vertex, Key, Compare<Key>, Alloc<std::pair<Key, Vertex>>
+ > type;
};
};
/**
- * The most common vertex set allows parameterization over the comparator used
- * to sort vertices and uses the standard omnibus allocator.
- */
-template <typename Key, template <typename> class Compare = std::less>
-struct vertex_map : basic_vertex_map<Key, Compare, std::allocator> { };
-
-/**
- * Extend the notion of a vertex for map storage so that we can store each
- * vertex's iterator with current vertex. This is used to provide constant
- * time access to the correct position in the underliying store.
- */
-template <
- typename Vertex,
- typename Key,
- typename Compare,
- template <typename> class Alloc>
-class vertex_map_elem
- : public Vertex
-{
- typedef vertex_map_elem<Vertex, Key, Compare, Alloc> this_type;
-public:
- typedef typename std::map<Key, this_type, Compare, Alloc<this_type> >::iterator iterator;
-
- inline vertex_map_elem(typename Vertex::vertex_properties const& vp)
- : Vertex(vp)
- , iter()
- { }
-
- iterator iter;
-};
-
-/**
* Implementation of the vertex set. This requires that vertices (actually
* their properties) are less-than comparable.
*
@@ -98,31 +60,49 @@
template <typename Vertex, typename Key, typename Compare, typename Allocator>
class vertex_map_impl
{
- typedef std::map<Key, Vertex, Compare, Allocator> vertex_store;
public:
- typedef basic_vertex_descriptor<void*> vertex_descriptor;
+ typedef std::map<Key, Vertex, Compare, Allocator> store_type;
+ typedef typename store_type::size_type size_type;
+ typedef typename store_type::iterator iterator;
+ typedef typename store_type::const_iterator const_iterator;
+
+ typedef Key key_type;
typedef Vertex vertex_type;
typedef typename Vertex::vertex_properties vertex_properties;
- typedef typename vertex_store::size_type size_type;
- typedef typename vertex_store::iterator iterator;
- typedef typename vertex_store::const_iterator const_iterator;
-
- typedef Key key_type;
+ typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
- typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+ typedef simple_vertex_iterator<store_type> vertex_iterator;
typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
- // Constructors
- vertex_map_impl();
+ inline vertex_map_impl()
+ : _verts()
+ { }
- vertex_descriptor add(key_type const& k, vertex_properties const& vp);
- vertex_descriptor find(key_type const& vp) const;
- void remove(vertex_descriptor);
- void remove(key_type const&);
+ /**
+ * Add a vertex to the store mapped to the given key, and having the given
+ * properties.
+ */
+ inline vertex_descriptor add(key_type const& k, vertex_properties const& vp)
+ { return make_descriptor(_verts, _verts.insert(std::make_pair(k, vp)).first); }
+
+ /**
+ * Find the vertex mapped to the given key and return a descriptor to it.
+ */
+ inline vertex_descriptor find(key_type const& k) const
+ { return make_descriptor(_verts, _verts.find(k)); }
+
+ /** @name Remove Vertex
+ * Remove the vertex identified by the descriptor or the its properties.
+ */
+ //@{
+ inline void remove(vertex_descriptor d)
+ { _verts.erase(make_iterator(_verts, d)); }
- key_type const& key(vertex_descriptor) const;
+ inline void remove(key_type const& k)
+ { _verts.erase(_verts.find(k)); }
+ //@}
/** Return the number of vertices in the map. */
inline size_type size() const
@@ -140,13 +120,16 @@
{ return std::make_pair(begin_vertices(), end_vertices()); }
//@}
- /** @name Vertex Accessors */
+ /** @name Vertex and Key Accessors */
//@{
vertex_type& vertex(vertex_descriptor v)
- { return *static_cast<vertex_type*>(v.get()); }
+ { return make_iterator(_verts, v)->second; }
vertex_type const& vertex(vertex_descriptor v) const
- { return *static_cast<vertex_type*>(v.get()); }
+ { return make_iterator(_verts, v)->second; }
+
+ key_type const& key(vertex_descriptor d) const
+ { return make_iterator(_verts, d)->first; }
//@}
/** @name Property Accessors */
@@ -159,85 +142,8 @@
//@}
private:
- vertex_store _verts;
+ mutable store_type _verts;
};
-template <typename V, typename K, typename C, typename A>
-vertex_map_impl<V,K,C,A>::vertex_map_impl()
- : _verts()
-{ }
-
-/**
- * Add the vertex with the given properties. If there is already a vertex with
- * these properties, then this returns the descriptor of the existing vertex
- * and does not insert a new vertex.
- *
- * @complexity O(lg(V))
- */
-template <typename V, typename K, typename C, typename A>
-typename vertex_map_impl<V,K,C,A>::vertex_descriptor
-vertex_map_impl<V,K,C,A>::add(key_type const& k, vertex_properties const& vp)
-{
- // Try to insert the vertex into the map.
- vertex_descriptor ret;
- std::pair<iterator, bool> ins = _verts.insert(std::make_pair(k, vertex_type(vp)));
- if(ins.second) {
- vertex_type& v = ins.first->second;
- v.iter = ins.first;
- ret = &v;
- }
- else {
- ret = &ins.first->second;
- }
- return ret;
-}
-
-/**
- * Find the vertex in the map with the given key.
- *
- * @complexity O(log(V))
- */
-template <typename V, typename K, typename C, typename A>
-typename vertex_map_impl<V,K,C,A>::vertex_descriptor
-vertex_map_impl<V,K,C,A>::find(key_type const& k) const
-{
- return &const_cast<vertex_type&>(_verts.find(k)->second);
-}
-
-/**
- * Remove a vertex from the map. Removing a vertex will invalidate all
- * descriptors and iterators to the vertex being removed.
- *
- * @complexity O(log(V))
- */
-template <typename V, typename K, typename C, typename A>
-void
-vertex_map_impl<V,K,C,A>::remove(vertex_descriptor v)
-{
- _verts.erase(vertex(v).iter);
-}
-
-/**
- * Remove the vertex with the given key from the map. This operation finds
- * the vertex before removing it.
- *
- * @complexity O(log(V))
- */
-template <typename V, typename K, typename C, typename A>
-void
-vertex_map_impl<V,K,C,A>::remove(key_type const& k)
-{
- remove(find(k));
-}
-
-/**
- * Return the key for the given vertex.
- */
-template <typename V, typename K, typename C, typename A>
-typename vertex_map_impl<V,K,C,A>::key_type const&
-vertex_map_impl<V,K,C,A>::key(vertex_descriptor v) const
-{
- return vertex(v).iter->first;
-}
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp 2008-07-07 07:23:01 EDT (Mon, 07 Jul 2008)
@@ -4,12 +4,12 @@
#include <set>
-#include "vertex_descriptor.hpp"
+#include <boost/descriptors.hpp>
+#include <boost/graphs/utility.hpp>
+
#include "vertex_iterator.hpp"
// Forward declarations
-template <typename, template <typename> class, template <typename> class> class vertex_set_elem;
-template <typename, typename> class vertex_set_compare;
template <typename, typename, typename> class vertex_set_impl;
/**
@@ -27,87 +27,28 @@
* @param Compare A unary template class that compares vertex properties.
* @param Alloc A unary template class that allocates vertices.
*/
-template <template <typename> class Compare, template <typename> class Alloc>
-struct basic_vertex_set
+template <
+ template <typename> class Compare = std::less,
+ template <typename> class Alloc = std::allocator>
+struct vertex_set
{
typedef unused key_type;
- typedef basic_vertex_descriptor<void*> descriptor_type;
+ typedef std::set<int, Compare<int>, Alloc<int>> dummy;
+ typedef typename descriptor_traits<dummy>::descriptor_type descriptor_type;
+
+ // This metafunction generates the underlying vertex store implementation.
template <typename Vertex>
struct store
{
- // Build the stored vertex type.
- typedef vertex_set_elem<Vertex, Compare, Alloc> stored_vertex;
-
- // Build the vertex comparator.
- typedef Compare<typename stored_vertex::vertex_properties> vertex_compare;
- typedef vertex_set_compare<stored_vertex, vertex_compare> compare_type;
-
- // Build the allocator.
- typedef Alloc<stored_vertex> allocator_type;
-
- // Build the vertex set implementation.
- typedef vertex_set_impl<stored_vertex, compare_type, allocator_type> type;
+ typedef vertex_set_impl<
+ Vertex,
+ property_comparator<Compare<typename Vertex::vertex_properties>>,
+ Alloc<Vertex>
+ > type;
};
};
-/**
- * The most common vertex set allows parameterization over the comparator used
- * to sort vertices and uses the standard omnibus allocator.
- */
-template <template <typename> class Compare = std::less>
-struct vertex_set : basic_vertex_set<Compare, std::allocator> { };
-
-/**
- * Extend the notion of a vertex for set storage so that we can store each
- * vertex's iterator with current vertex. This is used to provide constant
- * time access to the correct position in the underliying store.
- */
-template <typename Vertex,
- template <typename> class Compare,
- template <typename> class Alloc>
-class vertex_set_elem
- : public Vertex
-{
- typedef vertex_set_elem<Vertex, Compare, Alloc> this_type;
-public:
- typedef typename std::set<
- this_type, Compare<this_type>, Alloc<this_type>
- >::iterator iterator;
-
- inline vertex_set_elem(typename Vertex::vertex_properties const& vp)
- : Vertex(vp)
- , iter()
- { }
-
- iterator iter;
-};
-
-/**
- * A forwarding comparator for the vertex forwards the comparison to the given
- * comparator. This type is used internally to forward comparisons of vertices
- * to the property comparison provided by the edge set parameter.
- *
- * @param StoredVertex The type of vertex being compared
- * @param Compare An ordering over vertex properties.
- */
-template <typename StoredVertex, typename Compare>
-struct vertex_set_compare
-{
- inline vertex_set_compare()
- : comp(Compare())
- { }
-
- inline vertex_set_compare(vertex_set_compare const& x)
- : comp(x.comp)
- { }
-
- inline bool operator()(StoredVertex const& a, StoredVertex const& b) const
- { return comp(a.properties(), b.properties()); }
-
- Compare comp;
-};
-
/**
* Implementation of the vertex set. This requires that vertices (actually
@@ -120,28 +61,48 @@
template <typename Vertex, typename Compare, typename Allocator>
class vertex_set_impl
{
- typedef std::set<Vertex, Compare, Allocator> vertex_store;
public:
- typedef basic_vertex_descriptor<void*> vertex_descriptor;
+ typedef std::set<Vertex, Compare, Allocator> store_type;
+ typedef typename store_type::size_type size_type;
+ typedef typename store_type::iterator iterator;
+ typedef typename store_type::const_iterator const_iterator;
typedef Vertex vertex_type;
typedef typename Vertex::vertex_properties vertex_properties;
- typedef typename vertex_store::size_type size_type;
- typedef typename vertex_store::iterator iterator;
- typedef typename vertex_store::const_iterator const_iterator;
+ typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
- typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+ typedef simple_vertex_iterator<store_type> vertex_iterator;
typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
- // Constructors
- vertex_set_impl();
+ inline vertex_set_impl()
+ : _verts()
+ { }
- // Add vertices. Note that you can't add without properties.
- vertex_descriptor add(vertex_properties const& vp);
- vertex_descriptor find(vertex_properties const& vp) const;
- void remove(vertex_descriptor v);
- void remove(vertex_properties const& v);
+ /**
+ * Add a vertex to the store with the given properties (or none). Return
+ * a descriptor to the vertex that was added to the vector.
+ */
+ inline vertex_descriptor add(vertex_properties const& vp)
+ { return make_descriptor(_verts, insert(_verts, vertex_type(vp))); }
+
+ /** Find the vertex with the given properties. */
+ inline vertex_descriptor find(vertex_properties const& vp) const
+ { return make_descriptor(_verts, _verts.find(vp)); }
+
+ /** @name Remove Vertex
+ * Remove the given vertex or the one identified by the given properties.
+ */
+ //@{
+ inline void remove(vertex_descriptor v)
+ {
+ iterator i = make_iterator(_verts, v);
+ erase(_verts, make_iterator(_verts, v));
+ }
+
+ inline void remove(vertex_properties const& v)
+ { remove(find(v)); }
+ //@}
/** Return the number of vertices in the set. */
inline size_type size() const
@@ -162,10 +123,10 @@
/** @name Vertex Accessors */
//@{
vertex_type& vertex(vertex_descriptor v)
- { return *static_cast<vertex_type*>(v.get()); }
+ { return const_cast<vertex_type&>(*make_iterator(_verts, v)); }
vertex_type const& vertex(vertex_descriptor v) const
- { return *static_cast<vertex_type*>(v.get()); }
+ { return *make_iterator(_verts, v); }
//@}
/** @name Property Accessors */
@@ -178,81 +139,7 @@
//@{
private:
- vertex_store _verts;
+ mutable store_type _verts;
};
-
-#define BOOST_GRAPH_VS_PARAMS \
- typename V, typename C, typename A
-
-template <BOOST_GRAPH_VS_PARAMS>
-vertex_set_impl<V,C,A>::vertex_set_impl()
- : _verts()
-{ }
-
-/**
- * Add the vertex with the given properties. If there is already a vertex with
- * these properties, then this returns the descriptor of the existing vertex
- * and does not insert a new vertex.
- *
- * @complexity O(lg(V))
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_descriptor
-vertex_set_impl<V,C,A>::add(vertex_properties const& vp)
-{
- // Try to insert the vertex.
- vertex_descriptor ret;
- std::pair<iterator, bool> ins = _verts.insert(vertex_type(vp));
- if(ins.second) {
- vertex_type& v = const_cast<vertex_type&>(*(ins.first));
- v.iter = ins.first;
- ret = &v;
- }
- else {
- ret = &const_cast<vertex_type&>(*ins.first);
- }
- return ret;
-}
-
-/**
- * Find the descriptor with the given properties.
- *
- * @complexity O(log(V))
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_descriptor
-vertex_set_impl<V,C,A>::find(vertex_properties const& vp) const
-{
- return &const_cast<vertex_type&>(*_verts.find(vp));
-}
-
-/**
- * Remove a vertex from the set. Removing a vertex will invalidate all
- * descriptors and iterators to the vertex being removed.
- *
- * @complexity O(log(V))
- */
-template <BOOST_GRAPH_VS_PARAMS>
-void
-vertex_set_impl<V,C,A>::remove(vertex_descriptor v)
-{
- _verts.erase(vertex(v).iter);
-}
-
-/**
- * Remove the vertex identified by the given properties from the set. This
- * finds the vertex before removing it.
- *
- * @complexity O(log(V))
- */
-template <BOOST_GRAPH_VS_PARAMS>
-void
-vertex_set_impl<V,C,A>::remove(vertex_properties const& vp)
-{
- remove(find(vp));
-}
-
-#undef BOOST_GRAPH_VS_PARAMS
-
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp 2008-07-07 07:23:01 EDT (Mon, 07 Jul 2008)
@@ -11,7 +11,7 @@
#include "vertex_iterator.hpp"
// Forward declarations
-template <typename V, typename A> struct vertex_vector_impl;
+template <typename, typename> struct vertex_vector_impl;
/**
* The vertex vector stores vertices in a vector, allowing for fast inserts
@@ -84,7 +84,8 @@
inline vertex_descriptor add(vertex_properties const& vp)
{
- return make_descriptor(_verts, insert(_verts, vertex_type(vp)));
+ iterator i = insert(_verts, vertex_type(vp));
+ return make_descriptor(_verts, i);
}
//@}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp 2008-07-07 07:23:01 EDT (Mon, 07 Jul 2008)
@@ -9,7 +9,10 @@
inline std::string
demangle(std::string const& name)
{
- return std::string(abi::__cxa_demangle(name.c_str(), 0, 0, 0));
+ std::size_t n = 2048;
+ char buf[2048];
+ abi::__cxa_demangle(name.c_str(), buf, &n, 0);
+ return std::string(buf, ::strnlen(buf, n));
}
template <typename T>
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp 2008-07-07 07:23:01 EDT (Mon, 07 Jul 2008)
+++ (empty file)
@@ -1,71 +0,0 @@
-
-#include <iostream>
-#include <string>
-#include <list>
-
-#include <boost/none.hpp>
-#include <boost/graphs/vertex_vector.hpp>
-#include <boost/graphs/vertex_list.hpp>
-
-#include "demangle.hpp"
-
-using namespace std;
-using namespace boost;
-
-struct no_remove_tag { };
-struct has_remove_tag { };
-
-// A fake vertex type.
-struct Vertex
-{
- typedef int vertex_properties;
-
- Vertex(int x)
- : value(x)
- { }
-
- int& properties()
- { return value; }
-
- int const& properties() const
- { return value; }
-
- int value;
-};
-
-
-template <typename Store>
-void test_remove(Store& verts, stable_descriptor_tag)
-{
- verts.remove(3);
- cout << "size after remove: " << verts.size() << endl;
-}
-
-template <typename VertexSet>
-void test_remove(VertexSet& vs, unstable_remove_tag)
-{ /* Noop for unstable removes */ }
-
-template <typename VertexSet>
-void test()
-{
- typedef typename VertexSet::template store<Vertex>::type Store;
- typedef typename VertexSet::descriptor_type Descriptor;
-
- cout << "--- " << demangle<VertexSet>() << " ---" << endl;
-
- Store verts;
- Descriptor d1 = verts.add(3);
-
- cout << "value of added props: " << verts.vertex(d1).value << endl;
- cout << "value of found props: " << verts.vertex(verts.find(3)).value << endl;
-
- test_remove(verts, typename descriptor_traits<typename Store::store_type>::descriptor_stability());
-}
-
-int main()
-{
- test<vertex_vector<>>();
- test<vertex_list<>>();
-
- return 0;
-}
\ No newline at end of file
Copied: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp (from r47111, /sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp 2008-07-07 07:23:01 EDT (Mon, 07 Jul 2008)
@@ -6,6 +6,8 @@
#include <boost/none.hpp>
#include <boost/graphs/vertex_vector.hpp>
#include <boost/graphs/vertex_list.hpp>
+#include <boost/graphs/vertex_set.hpp>
+#include <boost/graphs/vertex_map.hpp>
#include "demangle.hpp"
@@ -33,12 +35,35 @@
int value;
};
+template <typename Store>
+void populate(Store& verts, sequence_tag)
+{
+ for(int i = 0; i < 5; ++i) {
+ verts.add(i);
+ }
+}
+
+template <typename Store>
+void populate(Store& verts, simple_associative_container_tag)
+{
+ for(int i = 0; i < 5; ++i) {
+ verts.add(i);
+ }
+}
+
+template <typename Store>
+void populate(Store& verts, pair_associative_container_tag)
+{
+ for(int i = 0; i < 5; ++i) {
+ verts.add(i, 2 * i);
+ }
+}
template <typename Store>
void test_remove(Store& verts, stable_descriptor_tag)
{
verts.remove(3);
- cout << "size after remove: " << verts.size() << endl;
+ cout << "num verts after remove: " << verts.size() << endl;
}
template <typename VertexSet>
@@ -50,22 +75,27 @@
{
typedef typename VertexSet::template store<Vertex>::type Store;
typedef typename VertexSet::descriptor_type Descriptor;
+ typedef typename Store::store_type StoreImpl;
cout << "--- " << demangle<VertexSet>() << " ---" << endl;
Store verts;
- Descriptor d1 = verts.add(3);
- cout << "value of added props: " << verts.vertex(d1).value << endl;
- cout << "value of found props: " << verts.vertex(verts.find(3)).value << endl;
+ populate(verts, typename container_traits<StoreImpl>::category());
+ cout << "num verts after building: " << verts.size() << endl;
+
+ Descriptor d = verts.find(3);
+ cout << "value of vertex properties: " << verts.properties(d) << endl;
- test_remove(verts, typename descriptor_traits<typename Store::store_type>::descriptor_stability());
+ test_remove(verts, typename descriptor_traits<StoreImpl>::descriptor_stability());
}
int main()
{
test<vertex_vector<>>();
test<vertex_list<>>();
+ test<vertex_set<>>();
+ test<vertex_map<int>>();
return 0;
}
\ No newline at end of file