[Boost-commit] svn:boost r46759 - in sandbox/SOC/2008/graphs/trunk: boost/graphs boost/graphs/descriptor libs/graphs

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;
+}