From: asutton_at_[hidden]
Date: 2008-06-26 20:58:54
Author: asutton
Date: 2008-06-26 20:58:53 EDT (Thu, 26 Jun 2008)
New Revision: 46759
URL: http://svn.boost.org/trac/boost/changeset/46759
Log:
integrating new descriptor code into proplists.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor/
sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor/common.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor/vector.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/desc.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp | 77 +++++++++++++++++++++------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp | 67 +++++-----------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp | 2
sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile | 1
4 files changed, 54 insertions(+), 93 deletions(-)
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp 2008-06-26 20:58:53 EDT (Thu, 26 Jun 2008)
@@ -0,0 +1,70 @@
+
+#ifndef DESCRIPTOR_HPP
+#define DESCRIPTOR_HPP
+
+#include <vector>
+#include <list>
+#include <set>
+#include <map>
+#include <iterator>
+#include <algorithm>
+
+#include <boost/static_assert.hpp>
+#include <boost/type_traits.hpp>
+#include <boost/functional/hash.hpp>
+
+// The descriptor library provides an iterator-like reference into containers.
+// Unlike iterators, however, descriptors do not iterate and, more importantly,
+// are not easily invalidated. Descriptors are only invalidated when the object
+// being described are removed from the container. Like iterators, descriptors
+// can also be dereferenced, but are also testable for invalidity (unless they
+// are invalidated). The cost of additional stability comes in the size of
+// the descriptor. They tend to be a couple bytes larger than iterators or
+// pointers.
+
+// Descriptors should be const-neutral. Unfortunately, this is easier said than
+// done. Because const and non-const iterators cannot be converted to each
+// other, descriptors can only wrap iterators (or something similar). Therefore,
+// any class exposing a descriptor to a nested container will probably need to
+// declare the container as a mutable member. The other method is to const-cast
+// the this object getting iterators to the object.
+
+// Descriptors are also equality comparable, less than comparable, and hashable.
+
+// Hash values are provided over a unique identifier "given" to each element in
+// the container. The type of this value depends on the implementation of the
+// descriptor, but these values are guaranteed to be hashable.
+
+// Comparisons are also based on this unique identifier. Comparing two
+// descriptors is not the same as comparing the objects that they describe.
+
+// TODO: What's the validity of a descriptor? One that isn't iniitialized?
+
+// Include implementations and their specializations.
+#include "descriptor/common.hpp"
+#include "descriptor/vector.hpp"
+
+template <typename Container>
+struct descriptor
+ : descriptor_impl<Container>
+{
+ /** Create a null descriptor. */
+ descriptor()
+ : descriptor_impl<Container>()
+ { }
+
+ /** Create a descriptor over the given iterator. */
+ descriptor(Container& c, typename Container::iterator i)
+ : descriptor_impl<Container>(c, i)
+ { }
+};
+
+template <typename C>
+inline std::size_t
+hash_value(descriptor<C> const& d)
+{
+ using boost::hash_value;
+ return hash_value(d.index());
+}
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor/common.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor/common.hpp 2008-06-26 20:58:53 EDT (Thu, 26 Jun 2008)
@@ -0,0 +1,68 @@
+
+#ifndef NODE_DESCRIPTOR_HPP
+#define NODE_DESCRIPTOR_HPP
+
+/**
+ * The default implementation of descriptor implementations satisfies the
+ * requirements for most node-based containers such as lists, sets, and maps.
+ * These requirements are satisfied for node-based containers because they
+ * are relatively stable.
+ *
+ * Note that maps store key/value pairs, so the returned value is actually
+ * to the start of the pair rather than the intended mapped value.
+ */
+template <typename Container>
+struct descriptor_impl
+{
+ typedef Container container_type;
+ typedef typename container_type::iterator iterator;
+ typedef typename container_type::value_type value_type;
+ typedef typename iterator::pointer index_type;
+
+ inline descriptor_impl()
+ : cont(0), iter()
+ { }
+
+ inline descriptor_impl(container_type& c, iterator i)
+ : cont(&c), iter(i)
+ { }
+
+ inline bool valid() const
+ { return cont != 0; }
+
+ inline index_type index() const
+ { return &*iter; }
+
+ inline value_type& value()
+ { return *iter; }
+
+ void reset()
+ {
+ cont = 0;
+ iter = iterator();
+ }
+
+ inline bool operator==(descriptor_impl const& x) const
+ { return (cont == x.cont) && (index() == x.index()); }
+
+ inline bool operator!=(descriptor_impl const& x) const
+ { return !operator==(x); }
+
+ inline bool operator<(descriptor_impl const& x) const
+ { return std::make_pair(cont, index()) < std::make_pair(x.cont, x.index()); }
+
+ inline bool operator>(descriptor_impl const& x) const
+ { return x.operator<(*this); }
+
+ inline bool operator<=(descriptor_impl const& x) const
+ { return !x.operator<(*this); }
+
+ inline bool operator>=(descriptor_impl const& x) const
+ { return !operator<(x); }
+
+ container_type* cont;
+ iterator iter;
+};
+
+#endif
+
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor/vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor/vector.hpp 2008-06-26 20:58:53 EDT (Thu, 26 Jun 2008)
@@ -0,0 +1,69 @@
+
+#ifndef VECTOR_DESCRIPTOR_HPP
+#define VECTOR_DESCRIPTOR_HPP
+
+/**
+ * Vectors are some of the most troublesome data structures to work with because
+ * their iterators can be invalidated so easily - especially on insertion. This
+ * descriptor prevents invalidation on insertion, but any deletions will still
+ * invalidate all descriptors whose indices are greater than than the one
+ * deleted.
+ *
+ * Vector descriptors retain a pointer to the container itself, and the offset
+ * of the object being described.
+ */
+template <typename T, typename Alloc>
+struct descriptor_impl< std::vector<T, Alloc> >
+{
+ typedef std::vector<T, Alloc> container_type;
+ typedef typename container_type::iterator iterator;
+ typedef typename container_type::size_type index_type;
+ typedef typename container_type::value_type value_type;
+
+ inline descriptor_impl()
+ : cont(0), off(index_type(-1))
+ { }
+
+ inline descriptor_impl(container_type& c, iterator i)
+ : cont(&c), off(std::distance(c.begin(), i))
+ { }
+
+ inline bool valid() const
+ { return cont != 0; }
+
+ inline index_type index() const
+ { return off; }
+
+ inline value_type& value()
+ { return (*cont)[off]; }
+
+ void reset()
+ {
+ cont = 0;
+ off = index_type(-1);
+ }
+
+ inline bool operator==(descriptor_impl const& x) const
+ { return (cont == x.cont) && (off == x.off); }
+
+ inline bool operator!=(descriptor_impl const& x) const
+ { return !operator==(x); }
+
+ inline bool operator<(descriptor_impl const& x) const
+ { return std::make_pair(cont, off) < std::make_pair(x.cont, x.off); }
+
+ inline bool operator>(descriptor_impl const& x) const
+ { return x.operator<(*this); }
+
+ inline bool operator<=(descriptor_impl const& x) const
+ { return !x.operator<(*this); }
+
+ inline bool operator>=(descriptor_impl const& x) const
+ { return !operator<(x); }
+
+ container_type* cont;
+ index_type off;
+};
+
+#endif
+
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp 2008-06-26 20:58:53 EDT (Thu, 26 Jun 2008)
@@ -4,8 +4,8 @@
#include <list>
-// Forward descriptor
-template <typename Iter> class proplist_descriptor;
+#include "triple.hpp"
+#include "descriptor.hpp"
/**
* The property list implements global list of properties for node-based edge
@@ -28,13 +28,12 @@
typedef typename Props::second_type first_iterator;
typedef typename Props::third_type second_iterator;
public:
- typedef typename store_type::iterator iterator;
+ typedef typename store_type::const_iterator iterator;
typedef typename store_type::size_type size_type;
- typedef proplist_descriptor<typename store_type::iterator> property_descriptor;
+ typedef descriptor<store_type> property_descriptor;
inline property_list()
- : _props()
- , _size(0)
+ : _props(), _size(0)
{ }
// Add properties
@@ -52,14 +51,10 @@
template <typename Iter>
void bind(property_descriptor d, Iter src, Iter tgt)
{
- d.iter->second.put(src);
- d.iter->third.put(tgt);
+ d.value().second.put(src);
+ d.value().third.put(tgt);
}
- /** Convert an iterator to a descriptor. */
- inline property_descriptor describe(iterator i) const
- { return i; }
-
/** Return the number of properties. */
inline size_type size() const
{ return _size; }
@@ -71,8 +66,8 @@
{ return _props.end(); }
private:
- mutable store_type _props;
- size_type _size;
+ store_type _props;
+ size_type _size;
};
/**
@@ -93,7 +88,8 @@
property_list<P,A>::add(edge_properties const& p)
{
++_size;
- return _props.insert(_props.end(), make_triple(p, first_iterator(), second_iterator()));
+ _props.push_back(make_triple(p, first_iterator(), second_iterator()));
+ return property_descriptor(_props, boost::prior(_props.end()));
}
/**
@@ -120,8 +116,6 @@
template <typename Iter>
struct proplist_descriptor
{
- typedef typename Iter::pointer value_type;
-
inline proplist_descriptor()
: iter()
{ }
@@ -130,30 +124,41 @@
: iter(iter)
{ }
- inline value_type get() const
- { return &*iter; }
+ inline bool operator==(proplist_descriptor const& x) const
+ { return iter == x.iter; }
+
+ inline bool operator<(proplist_descriptor const& x) const
+ { return &*iter < &*x.iter; }
Iter iter;
};
-template <typename I>
-inline bool
-operator==(proplist_descriptor<I> const& a, proplist_descriptor<I> const& b)
-{ return a.iter == b.iter; }
-
-template <typename I>
-inline bool
-operator<(proplist_descriptor<I> const& a, proplist_descriptor<I> const& b)
-{ return a.get() < b.get(); }
-/**
- * Hashing a property descriptor returns the hash value over the address of
- * the property object pointed at by the descriptor inside the iterator.
- */
-template <typename Iter>
-inline std::size_t
-hash_value(proplist_descriptor<Iter> const& x)
-{ return boost::hash_value(x.get()); }
+// This helper type is used to erase global edge properties during edge removal
+// of undirected graphs.
+template <typename PropList>
+struct property_eraser
+{
+ property_eraser(PropList& props)
+ : props(props)
+ { }
+
+ template <typename PropDesc>
+ void operator()(PropDesc p)
+ { props.remove(p); }
+
+ PropList& props;
+};
+
+// The noop eraser does nothing.
+struct noop_eraser
+{
+ noop_eraser() { }
+
+ template <typename PropDesc>
+ void operator()(PropDesc)
+ { }
+};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp 2008-06-26 20:58:53 EDT (Thu, 26 Jun 2008)
@@ -1,12 +1,11 @@
-#ifndef PROPERTY_VERTEX_HPP
-#define PROPERTY_VERTEX_HPP
+#ifndef PROPERTY_VECTOR_HPP
+#define PROPERTY_VECTOR_HPP
#include <vector>
#include "triple.hpp"
-
-template <typename Store> class propvec_descriptor;
+#include "descriptor.hpp"
// NOTE: Property stores hold two additional values. Right now, they contain
// vertex descriptors, but would ideally by "iterators" into the incidence store
@@ -35,7 +34,7 @@
public:
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
- typedef propvec_descriptor<store_type> property_descriptor;
+ typedef descriptor<store_type> property_descriptor;
inline property_vector()
: _props()
@@ -51,24 +50,26 @@
template <typename VertexDesc>
void bind(property_descriptor d, VertexDesc src, VertexDesc tgt)
{
- BOOST_ASSERT(&_props == d.store);
- _props[d.off].second.put(src);
- _props[d.off].third.put(tgt);
+ d.value().second.put(src);
+ d.value().third.put(tgt);
}
/** Convert an iterator to a descriptor. */
inline property_descriptor describe(iterator i) const
- { return property_descriptor(&_props, std::distance(_props.begin(), i)); }
+ { return property_descriptor(_props, i); }
/** Return the number of properties in the store. */
inline size_type size() const
{ return _props.size(); }
+ /** @name Iterators */
+ //@{
inline iterator begin() const
{ return _props.begin(); }
inline iterator end() const
{ return _props.end(); }
+ //@}
private:
mutable store_type _props;
@@ -87,54 +88,8 @@
property_vector<P,A>::add(edge_properties const& p)
{
_props.push_back(make_triple(p, first_iterator(), second_iterator()));
- return property_descriptor(&_props, _props.size() - 1);
+ return property_descriptor(_props, boost::prior(_props.end()));
}
-/**
- * The propvec descriptor provides an opaque reference into the property list
- * for undirected graphs.
- */
-template <typename Store>
-struct propvec_descriptor
-{
- typedef Store store_type;
- typedef typename Store::size_type value_type;
-
- propvec_descriptor()
- : store(0), off(value_type(-1))
- { }
-
- propvec_descriptor(store_type* store, value_type n)
- : store(store), off(n)
- { }
-
- value_type get() const
- { return off; }
-
- store_type* store;
- value_type off;
-};
-
-template <typename S>
-inline bool
-operator==(propvec_descriptor<S> const& a, propvec_descriptor<S> const& b)
-{ return a.store == b.store && a.off == b.off; }
-
-template <typename S>
-inline bool
-operator<(propvec_descriptor<S> const& a, propvec_descriptor<S> const& b)
-{ return a.get() < b.get(); }
-
-/**
- * Hashing a property descriptor returns the hash value over the address of
- * the property object pointed at by the descriptor inside the iterator.
- */
-template <typename S>
-inline std::size_t
-hash_value(propvec_descriptor<S> const& x)
-{ return boost::hash_value(x.get()); }
-
-
-
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp 2008-06-26 20:58:53 EDT (Thu, 26 Jun 2008)
@@ -33,7 +33,7 @@
* edge. This is primarily used to support mapping applications for exterior
* edge properties.
*/
- inline typename property_descriptor::value_type get() const
+ inline typename property_descriptor::index_type get() const
{ return prop.get(); }
inline property_descriptor properties() const
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile 2008-06-26 20:58:53 EDT (Thu, 26 Jun 2008)
@@ -6,3 +6,4 @@
exe test : test.cpp : <include>../../ <include>/usr/local/include ;
exe props : props.cpp : <include>../../ <include>/usr/local/include ;
exe edge : edge.cpp : <include>../../ <include>/usr/local/include ;
+exe desc : desc.cpp : <include>../../ <include>/usr/local/include ;
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/desc.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/desc.cpp 2008-06-26 20:58:53 EDT (Thu, 26 Jun 2008)
@@ -0,0 +1,47 @@
+
+#include <iostream>
+
+#include <boost/graphs/descriptor.hpp>
+
+#include "demangle.hpp"
+
+using namespace std;
+
+template <typename C>
+void test(C& c)
+{
+ typedef descriptor<C> D;
+ D a(c, c.begin());
+ D b(c, ++c.begin());
+
+ cout << "--- " << demangle<C>() << " ---" << endl;
+ cout << "id a: " << hash_value(a) << endl;
+ cout << "id b: " << hash_value(b) << endl;
+ cout << (a != a) << std::endl;
+ cout << (a < b) << std::endl;
+}
+
+int main()
+{
+ std::vector<int> v;
+ v.push_back(10);
+ v.push_back(11);
+ test(v);
+
+ std::list<int> l;
+ l.push_back(10);
+ l.push_back(11);
+ test(l);
+
+ std::set<int> s;
+ s.insert(10);
+ s.insert(11);
+ test(s);
+
+ std::map<int, int> m;
+ m[10] = 20;
+ m[11] = 21;
+ test(m);
+
+ return 0;
+}