[Boost-commit] svn:boost r49079 - in sandbox/SOC/2008/graphs/trunk: boost boost/descriptors libs/graphs/doc libs/graphs/test

Subject: [Boost-commit] svn:boost r49079 - in sandbox/SOC/2008/graphs/trunk: boost boost/descriptors libs/graphs/doc libs/graphs/test
From: asutton_at_[hidden]
Date: 2008-10-01 09:44:14

Author: asutton
Date: 2008-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
New Revision: 49079
URL: http://svn.boost.org/trac/boost/changeset/49079

Log:
Added a "kind" parameter to descriptors that can be used to differentiate
similar descriptors being used for different purposes. This also required
updates to their implicit cast to bool, being replaced by the unspecified
bool type idiom.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp                  |    56 ++++++++++++++++++++++++--------------- 
   sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp |    18 +++++++-----                            
   sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp  |    18 +++++++-----                            
   sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/descriptors.qbk        |    29 ++++++++++----------                    
   sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graphs.qbk             |     6 +++                                     
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/Jamfile               |     3 +                                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/desc.cpp              |    49 ++++++++++++++++++++++++++++------      
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_incs.cpp         |     4 +-                                      
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_ins.cpp          |     4 +-                                      
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_outs.cpp         |     4 +-                                      
   10 files changed, 124 insertions(+), 67 deletions(-)

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-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
@@ -8,6 +8,11 @@
 // Some descriptors are built on blobs.
 #include "blob.hpp"
 
+// A default "responsibility" tag. Because descriptors are mostly container-
+// neutral, debugging intermixed descriptors can be a painful and error-prone.
+// We use responsibility tags to imbue descriptors with semantics.
+struct basic_descriptor_kind { };
+
 // Descriptor implementations.
 #include "descriptors/node_descriptor.hpp"
 #include "descriptors/index_descriptor.hpp"
@@ -61,6 +66,8 @@
 // Note that it is certainly possible for a container to be unstable for both
 // insertions and removals. These data structures are generally constructed over
 // a known set of objects and are generally immutable afterwards.
+
+// Kind of concepts
 struct stable_mutators_tag { };
 struct unstable_insert_tag { };
 struct unstable_remove_tag { };
@@ -74,9 +81,10 @@
  *
  * This inherits a specialized version of container traits from boost/pending.
  */
-template <typename Container>
+template <typename Container, typename Kind = basic_descriptor_kind>
 struct descriptor_traits
 {
+    typedef Kind descriptor_kind;
     typedef typename Container::descriptor_type descriptor_type;
     typedef typename Container::mutator_stability mutator_stability;
 };
@@ -105,9 +113,7 @@
 template <typename Container>
 inline typename Container::iterator
 make_iterator(Container& c, typename descriptor_traits<Container>::descriptor_type d)
-{
-    return d ? d.get(c) : c.end();
-}
+{ return d ? d.get(c) : c.end(); }
 
 
 /** Return the descriptor stability tag for the given container. */
@@ -151,52 +157,58 @@
 // Specializations
 
 // Vector
-template <typename T, typename Alloc>
-struct descriptor_traits<std::vector<T, Alloc>>
+template <typename T, typename Alloc, typename Kind>
+struct descriptor_traits<std::vector<T, Alloc>, Kind>
 {
-    typedef index_descriptor<typename std::vector<T, Alloc>::size_type> descriptor_type;
+    typedef Kind descriptor_kind;
+    typedef index_descriptor<typename std::vector<T, Alloc>::size_type, Kind> descriptor_type;
     typedef unstable_remove_tag descriptor_stability;
 };
 
 // List
-template <typename T, typename Alloc>
-struct descriptor_traits<std::list<T, Alloc>>
+template <typename T, typename Alloc, typename Kind>
+struct descriptor_traits<std::list<T, Alloc>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::list<T, Alloc>::iterator)>> descriptor_type;
+    typedef Kind descriptor_kind;
+    typedef node_descriptor<blob<sizeof(typename std::list<T, Alloc>::iterator)>, Kind> descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
 // TODO: Dequeue
 
 // Set
-template <typename T, typename Comp, typename Alloc>
-struct descriptor_traits<std::set<T, Comp, Alloc>>
+template <typename T, typename Comp, typename Alloc, typename Kind>
+struct descriptor_traits<std::set<T, Comp, Alloc>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::set<T, Comp, Alloc>::iterator)>> descriptor_type;
+    typedef Kind descriptor_kind;
+    typedef node_descriptor<blob<sizeof(typename std::set<T, Comp, Alloc>::iterator)>, Kind> descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
 // Multiset
-template <typename T, typename Comp, typename Alloc>
-struct descriptor_traits<std::multiset<T, Comp, Alloc>>
+template <typename T, typename Comp, typename Alloc, typename Kind>
+struct descriptor_traits<std::multiset<T, Comp, Alloc>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::multiset<T, Comp, Alloc>::iterator)>> descriptor_type;
+    typedef Kind descriptor_kind;
+    typedef node_descriptor<blob<sizeof(typename std::multiset<T, Comp, Alloc>::iterator)>, Kind> descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
 // Map
-template <typename Key, typename T, typename Comp, typename Alloc>
-struct descriptor_traits<std::map<Key, T, Comp, Alloc>>
+template <typename Key, typename T, typename Comp, typename Alloc, typename Kind>
+struct descriptor_traits<std::map<Key, T, Comp, Alloc>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::map<Key, T, Comp, Alloc>::iterator)>> descriptor_type;
+    typedef Kind descriptor_kind;
+    typedef node_descriptor<blob<sizeof(typename std::map<Key, T, Comp, Alloc>::iterator)>, Kind> descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
 // Multimap
-template <typename Key, typename T, typename Comp, typename Alloc>
-struct descriptor_traits<std::multimap<Key, T, Comp, Alloc>>
+template <typename Key, typename T, typename Comp, typename Alloc, typename Kind>
+struct descriptor_traits<std::multimap<Key, T, Comp, Alloc>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::multimap<Key, T, Comp, Alloc>::iterator)>> descriptor_type;
+    typedef Kind descriptor_kind;
+    typedef node_descriptor<blob<sizeof(typename std::multimap<Key, T, Comp, Alloc>::iterator)>, Kind> descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp	2008-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
@@ -9,9 +9,13 @@
  * The index_descriptor simply maintains the descriptor as an index into the
  * given offset.
  */
-template <typename Index>
+template <typename Index, typename Kind = basic_descriptor_kind>
 struct index_descriptor
 {
+    typedef index_descriptor<Index, Kind> this_type;
+    typedef Index this_type::*unspecified_bool_type;
+
+    typedef Kind descriptor_kind;
     typedef Index descriptor_type;
 
     inline index_descriptor()
@@ -32,8 +36,8 @@
     { return value == descriptor_type(-1); }
 
     /** Cast to bool tests to see if the descritpor is null. */
-    inline operator bool() const
-    { return !is_null(); }
+    inline operator unspecified_bool_type() const
+    { return is_null() ? 0 : &this_type::value; }
 
     /** @name Equality Comparable */
     //@{
@@ -70,15 +74,15 @@
 };
 
 // A hash function for indexed descriptors.
-template <typename Index>
-std::size_t hash_value(index_descriptor<Index> const& x)
+template <typename Index, typename Kind>
+std::size_t hash_value(index_descriptor<Index, Kind> const& x)
 {
     using boost::hash_value;
     return hash_value(x.value);
 }
 
-template <typename Index>
-std::ostream& operator<<(std::ostream& os, index_descriptor<Index> const& x)
+template <typename Index, typename Kind>
+std::ostream& operator<<(std::ostream& os, index_descriptor<Index, Kind> const& x)
 { return os << x.value; }
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp	2008-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
@@ -9,9 +9,13 @@
  * container iterator is just a pattern for the actual iterator and has no
  * real type (it's opaque).
  */
-template <typename Blob>
+template <typename Blob, typename Kind = basic_descriptor_kind>
 struct node_descriptor
 {
+    typedef node_descriptor<Blob, Kind> this_type;
+    typedef Blob this_type::*unspecified_bool_type;
+
+    typedef Kind descriptor_kind;
     typedef Blob descriptor_type;
 
     inline node_descriptor()
@@ -32,8 +36,8 @@
     { return value == descriptor_type(); }
 
     /** Cast to bool tests to see if the descritpor is null. */
-    inline operator bool() const
-    { return !is_null(); }
+    inline operator unspecified_bool_type() const
+    { return is_null() ? 0 : &this_type::value; }
 
     /** @name Equality Comparable */
     //@{
@@ -70,15 +74,15 @@
 };
 
 // A hash function for indexed descriptors.
-template <typename Blob>
-std::size_t hash_value(node_descriptor<Blob> const& x)
+template <typename Blob, typename Kind>
+std::size_t hash_value(node_descriptor<Blob, Kind> const& x)
 {
     using boost::hash_value;
     return hash_value(x.value);
 }
 
-template <typename Blob>
-std::ostream& operator<<(std::ostream& os, node_descriptor<Blob> const& d)
+template <typename Blob, typename Kind>
+std::ostream& operator<<(std::ostream& os, node_descriptor<Blob, Kind> const& d)
 { return os << hash_value(d); }
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/descriptors.qbk
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/descriptors.qbk	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/descriptors.qbk	2008-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
@@ -1,5 +1,4 @@
 
-
 [section Descriptors]
 The vertices and edges of the graph are accessible via descriptor objects. A
 descriptor is a lightweight, opaque reference to an object. All operations on
@@ -12,43 +11,45 @@
 `null` state when default cosntructed, and are implicitly castable to `bool`,
 allowing convenient pointer-like tests for existence.
 
-Descriptors are also [LessThanComparable] and [Hashable], allowing them to be
-used in sets and maps and their unordered variants.
+Descriptors are also __LessThanComparable__ and can be used in a __HashFunction__,
+making them usable as keys in either a __SortedAsssociativeContainer__ or a
+__HashedAssociativeContainer__.
 
 [note Pointers (to vertices or edges) are not generally used because a) it is not
-always possible to convert them to and from iterators in constant time, b) pointers
-generally assume a uniform, non-distributed address space, and c) some of the graph
-types do not actually have edge objects.]
+always possible to convert them to and from iterators in constant time and b) pointers
+generally assume a uniform, non-distributed address space.]
 
-[heading Perspective]
 Descriptors can cause problems for programmers who expect a significant class
 interface for returned vertices and descriptors. In fact, most graph libraries
 prefer to return heavyweight vertex objects (or pointers to them) that define
 their own interfaces. This approach is not feasible when combined with the
 amount of genericism offered by this library.
 
-[heading Internals]
 Descriptors are an abstraction over iterators that do two things. First, they
 provide greater degrees of stability over insertions (especially with vectors).
 Second, they are entirely decoupled from the types of the containers that they
 reference into. Without this decoupling, it would be nearly impossible to define
 graph types because of mutual and cyclic type dependencies.
 
+[heading Defining Descriptors]
+
+[heading Descriptor Kinds]
+
+[heading Descriptor Operations]
 As mentioned, descriptors can't be used without their originating containers.
 There are two functions that can be used to translate between a container's
 iterators and its descriptors: `make_descriptor` and `make_iterator`.
 
-``
-Descriptor make_descriptor(Container& cont, Iterator iter);
-``
+
+ Descriptor make_descriptor(Container& cont, Iterator iter);
+
 
 Given a container and a valid iterator into the container, return a descriptor
 over the referenced element. If `iter` is past the end, the returned descriptor
 is null.
 
-``
-Iterator make_iterator(Container& cont, Descriptor desc);
-``
+
+ Iterator make_iterator(Container& cont, Descriptor desc);
 
 Given a container and a valid descriptor into the container, return an iterator
 to the described element. If `desc` is null, then the returned iterator is past

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graphs.qbk
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graphs.qbk	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graphs.qbk	2008-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
@@ -130,6 +130,10 @@
 
 [include concepts.qbk]
 
+[section Property Maps]
+Document information on interior and exterior labels.
+[endsect]
+
 [section Graph Types]
 Unlike the previous version of the BGL, this library's take on graph types is that
 more is better. Rather than parameterize all structural aspects of a graph data
@@ -201,9 +205,9 @@
 [endsect]
 
 [section Minimum Spanning Tree Algorithms]
-[endsect]
 Not implemented.
 [endsect]
+[endsect] [/ Aglorithms /]
 
 [section Details]
 [include descriptors.qbk]

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-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
@@ -16,7 +16,8 @@
 # exe map : map.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 ;
+
+exe desc : desc.cpp : <include>../../ <include>/usr/local/include ;
 
 exe test_verts : test_verts.cpp ;
 exe test_props : test_props.cpp ;

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/desc.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/desc.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/desc.cpp	2008-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
@@ -1,20 +1,48 @@
 
 #include <iostream>
+#include <vector>
+#include <list>
+#include <set>
+#include <map>
 
-#include <boost/graphs/descriptor.hpp>
+#include <boost/descriptors.hpp>
 
-#include "demangle.hpp"
+#include "typestr.hpp"
 
 using namespace std;
 
+struct my_kind { };
+
+struct foo
+{
+    typedef int* foo::*p;
+
+    void test()
+    {
+        cout << typestr(&foo::x) << endl;
+    }
+
+    int x;
+};
+
 template <typename C>
 void test(C& c)
 {
-    typedef descriptor<C> D;
+    typedef descriptor_traits<C, my_kind> Traits;
+    typedef typename Traits::descriptor_type D;
+
+    typedef typename descriptor_traits<vector<int>>::descriptor_type X;
+
+    cout << typestr(c) << endl;
+    // cout << typestr<typename D::descriptor_kind>() << " " << typestr<typename X::descriptor_kind>() << endl;
+
     D a(c, c.begin());
     D b(c, ++c.begin());
-    
-    cout << "--- " << demangle<C>() << " ---" << endl;
+    X x;
+    // cout << typestr(a) << " " << typestr(x) << endl;
+    // cout << "comp: " << (a == a) << endl;
+    // cout << "should not compile: " << (x == a) << endl;
+
     cout << "id a: " << hash_value(a) << endl;
     cout << "id b: " << hash_value(b) << endl;
     cout << (a != a) << std::endl;
@@ -27,21 +55,24 @@
     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);
-    
+
+    foo f;
+    f.test();
+
     return 0;
 }

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_incs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_incs.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_incs.cpp	2008-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
@@ -11,8 +11,8 @@
 using namespace std;
 using namespace boost;
 
-typedef index_descriptor<size_t> VertexDesc;
-typedef index_descriptor<size_t> PropDesc;
+typedef index_descriptor<size_t, basic_descriptor_kind> VertexDesc;
+typedef index_descriptor<size_t, basic_descriptor_kind> PropDesc;
 typedef std::pair<VertexDesc, PropDesc> Edge;
 typedef allocator<Edge> Alloc;
 typedef std::less<VertexDesc> Compare;

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_ins.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_ins.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_ins.cpp	2008-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
@@ -11,8 +11,8 @@
 using namespace std;
 using namespace boost;
 
-typedef index_descriptor<size_t> VertexDesc;
-typedef index_descriptor<size_t> OutDesc;
+typedef index_descriptor<size_t, basic_descriptor_kind> VertexDesc;
+typedef index_descriptor<size_t, basic_descriptor_kind> OutDesc;
 typedef pair<VertexDesc, OutDesc> InEdge;
 typedef allocator<InEdge> Alloc;
 typedef less<VertexDesc> Compare;

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_outs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_outs.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/test_outs.cpp	2008-10-01 09:44:13 EDT (Wed, 01 Oct 2008)
@@ -12,8 +12,8 @@
 using namespace boost;
 
 
-typedef index_descriptor<size_t> VertexDesc;
-typedef index_descriptor<size_t> InDesc;
+typedef index_descriptor<size_t, basic_descriptor_kind> VertexDesc;
+typedef index_descriptor<size_t, basic_descriptor_kind> InDesc;
 typedef int EdgeProps;
 typedef pair<VertexDesc, pair<EdgeProps, InDesc>> OutEdge;
 typedef allocator<OutEdge> Alloc;