[Boost-commit] svn:boost r46399 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/doc/html libs/tree/test

From: ockham_at_[hidden]
Date: 2008-06-14 18:41:52

Author: bernhard.reiter
Date: 2008-06-14 18:41:51 EDT (Sat, 14 Jun 2008)
New Revision: 46399
URL: http://svn.boost.org/trac/boost/changeset/46399

Log:
Some changes to graph adaptor stub.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                       |     5 +++                                     
   sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp                       |    66 +++++++++++++++++++++++++++------------ 
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html           |     8 ++--                                    
   sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp              |    24 ++------------                          
   sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp |     2                                         
   5 files changed, 59 insertions(+), 46 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-06-14 18:41:51 EDT (Sat, 14 Jun 2008)
@@ -71,11 +71,16 @@
 
 Proposal:
 
+* Change complexity requirements for *order end() to constant? We're using root(), and
+  for postorder begin() - which is also root() - it's already constant. Then again, how much
+  do we cater for "pathological" implementations (and not so pathological ones, like 
+  threaded trees)?
 * Write a cursor_facade, cursor_adaptor as well as ascending_adaptor 
   (and output_cursor_iterator_wrapper?) proposal.
 * Add a revision log:
  * Add to_parent() (replaces operator!()), to_begin() and to_end() descending cursor members.
  * Remove shoot()
+ * Change some occurences of "vector" (oops) to the respective tree type.
 * Add (subtree) cursor algorithms.
 * Probably split up cursor categories into: cursor (value access) category, vertical traversal 
   and horizontal traversal (along the lines of the new iterator concepts).

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp	2008-06-14 18:41:51 EDT (Sat, 14 Jun 2008)
@@ -15,6 +15,7 @@
 #include <boost/tree/cursor.hpp>
 
 #include <boost/graph/graph_traits.hpp>
+#include <boost/property_map.hpp>
 #include <boost/iterator/iterator_adaptor.hpp>
 
 #include <boost/type_traits/integral_constant.hpp>
@@ -77,50 +78,73 @@
 
 template <class Tree>
 struct graph_traits<typename Tree::cursor> {
-	typedef typename Tree::cursor Cursor;
-    typedef Cursor vertex_descriptor;
-    typedef std::pair<Cursor, Cursor> edge_descriptor; // Might be tunable...
+    typedef typename Tree::cursor vertex_descriptor;
+    typedef std::pair<vertex_descriptor
+    				, vertex_descriptor> edge_descriptor; // Might be tunable...
 
-	typedef boost::tree::out_edge_iterator<Cursor> out_edge_iterator;
+	typedef boost::tree::out_edge_iterator<vertex_descriptor> out_edge_iterator;
 
     typedef directed_tag directed_category;
     typedef disallow_parallel_edge_tag edge_parallel_category;
         typedef incidence_graph_tag traversal_category;
-    typedef typename cursor_size<Cursor>::type vertices_size_type;
-    typedef typename cursor_size<Cursor>::type edges_size_type;
-    typedef typename cursor_size<Cursor>::type degree_size_type;
+    typedef 
+    	typename cursor_size<vertex_descriptor>::type 
+    	vertices_size_type;
+    typedef
+    	typename cursor_size<vertex_descriptor>::type
+    	edges_size_type;
+    typedef
+    	typename cursor_size<vertex_descriptor>::type
+    	degree_size_type;
 };
 
-template <class Cursor>
-typename graph_traits<Cursor>::vertex_descriptor
+template <class Tree>
+typename graph_traits<typename Tree::cursor>::vertex_descriptor
 source(
-    typename graph_traits<Cursor>::edge_descriptor e,
-    const Cursor& g)
+    typename graph_traits<typename Tree::cursor>::edge_descriptor e,
+    const typename Tree::cursor& g)
 {
     return e.first;
 }
 
-template <class Cursor>
-typename graph_traits<Cursor>::vertex_descriptor
+template <class Tree>
+typename graph_traits<typename Tree::cursor>::vertex_descriptor
 target(
-    typename graph_traits<Cursor>::edge_descriptor e,
-    const Cursor& g)
+    typename graph_traits<typename Tree::cursor>::edge_descriptor e,
+    const typename Tree::cursor& g)
 {
     return e.second;
 }
 
-template <class Cursor>
+template <class Tree>
 inline std::pair<
-    typename graph_traits<Cursor>::out_edge_iterator,
-    typename graph_traits<Cursor>::out_edge_iterator >  
+    typename graph_traits<typename Tree::cursor>::out_edge_iterator,
+    typename graph_traits<typename Tree::cursor>::out_edge_iterator >  
 out_edges(
-    typename graph_traits<Cursor>::vertex_descriptor u, 
-    const Cursor& g)
+    typename graph_traits<typename Tree::cursor>::vertex_descriptor u, 
+    const typename Tree::cursor& g)
 {
-    typedef typename graph_traits<Cursor>::out_edge_iterator Iter;
+    typedef
+    	typename graph_traits<typename Tree::cursor>::out_edge_iterator
+    	Iter;
     return std::make_pair(Iter(u, u.begin()), Iter(u, u.end()));
 }
 
+template <class Cursor> struct deref_property_map;
+
+template <class Cursor>
+struct deref_property_map
+: public boost::put_get_helper<typename boost::tree::cursor_reference<Cursor>::type
+							 , deref_property_map<Cursor> >
+{
+    typedef Cursor key_type;
+    typedef typename boost::tree::cursor_value<Cursor>::type value_type;
+    typedef typename boost::tree::cursor_reference<Cursor>::type reference;
+    typedef boost::lvalue_property_map_tag category;
+
+    inline reference operator[](const key_type& v) const { return *v; }
+};
+
 // TODO
 // We still need suitable property_maps, don't we?
 // (which have to invoke *c.begin())

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html	2008-06-14 18:41:51 EDT (Sat, 14 Jun 2008)
@@ -1165,7 +1165,7 @@
     <ol>
       <li>
         <p><strong>Complexity:</strong> The constructor <tt>template
-        &lt;class InputCursor&gt; vector(InputCursor subtree)</tt> makes only
+        &lt;class InputCursor&gt; binary_tree(InputCursor subtree)</tt> makes only
         <tt>N</tt> calls to the copy constructor of <tt>T</tt> (where
         <tt>N</tt> is the number of elements in <tt>subtree</tt>) and no
         reallocations if the cursor <tt>subtree</tt> is of (either descending
@@ -1492,7 +1492,7 @@
     <ol>
       <li>
         <p><strong>Complexity:</strong> The constructor <tt>template
-        &lt;class InputCursor&gt; vector(InputCursor subtree)</tt> makes only
+        &lt;class InputCursor&gt; nary_tree(InputCursor subtree)</tt> makes only
         <tt>N</tt> calls to the copy constructor of <tt>T</tt> (where
         <tt>N</tt> is the number of elements in <tt>subtree</tt>) and no
         reallocations if the cursor <tt>subtree</tt> is of (either descending
@@ -1862,7 +1862,7 @@
     <ol>
       <li>
         <p><strong>Complexity:</strong> The constructor <tt>template
-        &lt;class InputCursor&gt; vector(InputCursor subtree)</tt> makes only
+        &lt;class InputCursor&gt; forest_tree(InputCursor subtree)</tt> makes only
         <tt>N</tt> calls to the copy constructor of <tt>T</tt> (where
         <tt>N</tt> is the number of elements in <tt>subtree</tt>) and no
         reallocations if the cursor <tt>subtree</tt> is of (either descending
@@ -2107,7 +2107,7 @@
     <ol>
       <li>
         <p><strong>Complexity:</strong> The constructor <tt>template
-        &lt;class InputCursor&gt; vector(InputCursor subtree)</tt> makes only
+        &lt;class InputCursor&gt; multiway_tree(InputCursor subtree)</tt> makes only
         <tt>N</tt> calls to the copy constructor of <tt>T</tt> (where
         <tt>N</tt> is the number of elements in <tt>subtree</tt>) and no
         reallocations if the cursor <tt>subtree</tt> is of (either descending

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp	2008-06-14 18:41:51 EDT (Sat, 14 Jun 2008)
@@ -5,11 +5,9 @@
 //  http://www.boost.org/LICENSE_1_0.txt)
 
 #include <boost/tree/graph.hpp>
-#include <boost/tree/cursor.hpp>
 
 #include <boost/graph/depth_first_search.hpp>
 #include <boost/graph/visitors.hpp>
-#include <boost/property_map.hpp>
 
 #include <boost/test/minimal.hpp>
 
@@ -19,21 +17,6 @@
 #include "helpers.hpp"
 #include "test_tree_traversal_data.hpp"
 
-template <class Cursor> struct deref_property_map;
-
-template <class Cursor>
-struct deref_property_map
-: public boost::put_get_helper<typename cursor_reference<Cursor>::type
-							 , deref_property_map<Cursor> >
-{
-    typedef Cursor key_type;
-    typedef typename cursor_value<Cursor>::type value_type;
-    typedef typename cursor_reference<Cursor>::type reference;
-    typedef boost::lvalue_property_map_tag category;
-
-    inline reference operator[](const key_type& v) const { return *v; }
-};
-
 int test_main(int, char* [])
 {
         using boost::tree::binary_tree;
@@ -55,18 +38,19 @@
         // a visitor that is invoked at entering (preorder)
         // the vertices.
 
-	deref_property_map<cursor> dpm;
+	boost::deref_property_map<cursor> dpm;
         BOOST_CHECK(get(dpm, test_tree.root().begin()) == 8); // Check the entire tree?
         
         boost::dfs_visitor< boost::property_writer<
-							deref_property_map<cursor>, 
+							boost::deref_property_map<cursor>, 
                                                         bi_list_int_type, 
                                                         boost::on_discover_vertex> 
 						> 
                 preorder_writer(write_property(dpm, bi_list_int, 
                                             boost::on_discover_vertex()));
         
- 	//boost::depth_first_visit(test_tree.root(), test_tree.root(), preorder_writer);
+	// We need a color map!
+ 	//boost::depth_first_visit(test_tree, test_tree.root(), preorder_writer);
         
         // Output test_tree using write_graphviz. This might require copying
         // the IncidenceGraph to a VertexListGraph (using copy_component) 

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp	2008-06-14 18:41:51 EDT (Sat, 14 Jun 2008)
@@ -66,7 +66,7 @@
                 if (!s.empty())
                         underefed_for_each_recursive(s, f);
         while (s++ != t);
-		
+
         return f;
 }