[Boost-commit] svn:boost r56024 - in sandbox/statistics/tree_view: boost/tree_view libs/tree_view/doc libs/tree_view/example libs/tree_view/src

Subject: [Boost-commit] svn:boost r56024 - in sandbox/statistics/tree_view: boost/tree_view libs/tree_view/doc libs/tree_view/example libs/tree_view/src
From: erwann.rogard_at_[hidden]
Date: 2009-09-04 20:25:46

Author: e_r
Date: 2009-09-04 20:25:45 EDT (Fri, 04 Sep 2009)
New Revision: 56024
URL: http://svn.boost.org/trac/boost/changeset/56024

Log:
m/a
Added:
   sandbox/statistics/tree_view/boost/tree_view/depth_first.hpp   (contents, props changed)
   sandbox/statistics/tree_view/libs/tree_view/example/depth_first.cpp   (contents, props changed)
   sandbox/statistics/tree_view/libs/tree_view/example/depth_first.h   (contents, props changed)
Text files modified: 
   sandbox/statistics/tree_view/boost/tree_view/dynamic_stage.hpp |     2                                         
   sandbox/statistics/tree_view/boost/tree_view/node.hpp          |   106 +++++++++++++++++++++++++++++++-------- 
   sandbox/statistics/tree_view/libs/tree_view/doc/readme.txt     |    15 +++-                                    
   sandbox/statistics/tree_view/libs/tree_view/example/tree.cpp   |     6 +-                                      
   sandbox/statistics/tree_view/libs/tree_view/src/main.cpp       |     5 +                                       
   5 files changed, 102 insertions(+), 32 deletions(-)

Added: sandbox/statistics/tree_view/boost/tree_view/depth_first.hpp
==============================================================================
--- (empty file)
+++ sandbox/statistics/tree_view/boost/tree_view/depth_first.hpp	2009-09-04 20:25:45 EDT (Fri, 04 Sep 2009)
@@ -0,0 +1,117 @@
+///////////////////////////////////////////////////////////////////////////////
+// tree_view::depth_first.hpp                                                //
+//                                                                           //
+//  Copyright 2009 Erwann Rogard. Distributed under the Boost                //
+//  Software License, Version 1.0. (See accompanying file                    //
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)         //
+///////////////////////////////////////////////////////////////////////////////
+#ifndef BOOST_TREE_VIEW_DEPTH_FIRST_HPP_ER_2009
+#define BOOST_TREE_VIEW_DEPTH_FIRST_HPP_ER_2009
+//#include <iostream> // TODO remove
+#include <deque>
+#include <stdexcept>
+#include <boost/switch.hpp>
+#include <boost/operators.hpp>
+#include <boost/tree_view/node.hpp>
+
+namespace boost{
+namespace tree_view{
+
+    template<unsigned n,unsigned m = BOOST_SWITCH_LIMIT>
+    class depth_first
+        : incrementable<
+            depth_first<n,m>   
+        >
+    {
+        typedef std::deque<bool> bools_;
+        typedef node<n,m> node_type;
+        public:
+        
+        depth_first();
+        depth_first(unsigned n_stages); //terminal stage = n_stages - 1
+        
+        // [ Update ]
+        void operator++();
+        
+        // [ Access ]
+        bool is_subtree()const;
+        const node_type& node()const;
+        unsigned n_stages()const;
+
+        private:
+        const bools_& tree()const{ return this->tree_; }
+        unsigned    n_stages_;
+        bools_      tree_;
+        node_type   node_;
+    };
+    
+    // Update
+    template<unsigned n,unsigned m>
+    void 
+    depth_first<n,m>::operator++(){
+        
+        bool b = false;
+        if(this->is_subtree()){
+            static const node_type root_node;
+            if(this->node() == root_node){
+                static const char* msg 
+        = "tree_view::depth_first : next of completed root_node not allowed";
+                throw std::runtime_error(
+                    msg
+                );
+            }
+            if( parent( next( this->node() ) ) != parent( this->node()) ){ 
+                this->node_ = parent(this->node_);
+                b = true;
+            }else{
+                ++this->node_;
+                unsigned j = (this->node()).stage;
+                if( (j+1) == this->n_stages()){
+                    b = true;
+                }
+            }
+        }else{
+            this->node_ = first_child(this->node_);
+            unsigned j = ((this->node()).stage);
+            if((j+1) == this->n_stages()){
+                b = true;
+            }
+        }
+        this->tree_[position(this->node())] = b;
+    }
+
+    template<unsigned n,unsigned m>
+    depth_first<n,m>::depth_first():n_stages_(0){}
+    
+    template<unsigned n,unsigned m>
+    depth_first<n,m>::depth_first(unsigned n_stages)
+    :n_stages_(n_stages),
+    node_(0,0),
+    tree_(position(last(this->node(),this->n_stages()-1)),false)
+    {}
+        
+    // [ Access ]
+    template<unsigned n,unsigned m>
+    bool depth_first<n,m>::is_subtree()const{
+        return this->tree()[
+            position(
+                this->node()
+            )
+        ];
+    }
+
+    template<unsigned n,unsigned m>
+    const typename depth_first<n,m>::node_type& 
+    depth_first<n,m>::node()const{
+        return this->node_;
+    }
+
+    template<unsigned n,unsigned m>
+    unsigned depth_first<n,m>::n_stages()const{
+        return this->n_stages_;
+    }
+
+}// tree_view
+}// boost
+    
+#endif
\ No newline at end of file

Modified: sandbox/statistics/tree_view/boost/tree_view/dynamic_stage.hpp
==============================================================================
--- sandbox/statistics/tree_view/boost/tree_view/dynamic_stage.hpp	(original)
+++ sandbox/statistics/tree_view/boost/tree_view/dynamic_stage.hpp	2009-09-04 20:25:45 EDT (Fri, 04 Sep 2009)
@@ -16,6 +16,8 @@
 namespace boost{
 namespace tree_view{
 
+    // A runtime (a.k.a dynamic) version of stage
+    //
     // n : number of branches
     // m : number of stages
     template<unsigned n,unsigned m = BOOST_SWITCH_LIMIT>

Modified: sandbox/statistics/tree_view/boost/tree_view/node.hpp
==============================================================================
--- sandbox/statistics/tree_view/boost/tree_view/node.hpp	(original)
+++ sandbox/statistics/tree_view/boost/tree_view/node.hpp	2009-09-04 20:25:45 EDT (Fri, 04 Sep 2009)
@@ -16,11 +16,28 @@
 namespace boost{
 namespace tree_view{
 
-// n = 3
-//                                             ( 1 )                                          n^0
-//                                         ( 1 , 2 ,3)                                        n^1
-//                    ( 1 , 2 , 3 )        ( 1 ,[2], 3 )            ( 1, 2 , 3 )              n^2
-//            (1,2,3) (1,2,3)(1,2,3)  (1,2,3) (1,2,3) (1,2,3)  (1,2,3) (1,2,3) (1,2,3)        n^3
+// n = 3 :
+//
+// j:   0   1   2        
+//
+// i:   0->(            k:  0->(
+//          1->(                0->(
+//              4                   0
+//              5                   1
+//              6                   2
+//          )                   )
+//          2->(                1->(
+//              7                   3
+//              8                   4
+//              9                   5
+//          )                   )
+//          3->(                2->(
+//              10                  6
+//              11                  7
+//              12                  8
+//          )                   )
+//      )
+
 
     // n : number of branches
     // m : number of stages
@@ -49,8 +66,8 @@
         node(unsigned j,unsigned k);
         this_& operator++();
         this_& operator--();
-        bool operator==(const this_&);
-        bool operator<(const this_&);
+        bool operator==(const this_&)const;
+        bool operator<(const this_&)const;
         
         static std::string header;
 
@@ -61,17 +78,27 @@
     template<unsigned n,unsigned m> std::ostream& 
     operator<<(std::ostream& out, const tree_view::node<n,m>& that);
 
-    template<unsigned n,unsigned m> typename tree_view::node<n,m>::size_type 
+    template<unsigned n,unsigned m> 
+    bool 
+    is_root(const tree_view::node<n,m>& that);
+
+    template<unsigned n,unsigned m> 
+    typename tree_view::node<n,m>::size_type 
     position(const tree_view::node<n,m>& that);
-    template<unsigned n,unsigned m> tree_view::node<n,m> root(const tree_view::node<n,m>& leaf);
-    // The leaf(root) is node in the next stage, rooted at root, and 
-    // which occupies the same position as root among its neighbors.
-    template<unsigned n,unsigned m> tree_view::node<n,m> leaf(const tree_view::node<n,m>& root);
-
-    // To visit all the nodes sharing the same root:
-    // node<n,m> node = leaf(the_root);
-    // while(root(node++)!=the_root){...}
+    
+    template<unsigned n,unsigned m> 
+    tree_view::node<n,m> 
+    parent(const tree_view::node<n,m>& child);
 
+    // first_child(a) is first node in the next stage, parented at a
+    // To visit all the nodes sharing the same parent:
+    // node<n,m> node = first_child(a);
+    // while(parent(node++)!=a){...}
+    template<unsigned n,unsigned m> 
+    tree_view::node<n,m> 
+    first_child(const tree_view::node<n,m>& parent);
+
+    // -> firs, back and last of each stage 
     template<unsigned n,unsigned m> 
     tree_view::node<n,m> 
     first(const tree_view::node<n,m>& root,unsigned stage);
@@ -83,6 +110,15 @@
     template<unsigned n,unsigned m> 
     tree_view::node<n,m> 
     last(const tree_view::node<n,m>& root,unsigned stage);
+    // <-
+
+    template<unsigned n,unsigned m>
+    tree_view::node<n,m>
+    prior(const tree_view::node<n,m>& node);
+
+    template<unsigned n,unsigned m>
+    tree_view::node<n,m>
+    next(const tree_view::node<n,m>& node);
 
 namespace tree_view{
 
@@ -145,12 +181,12 @@
     }
 
     template<unsigned n,unsigned m>
-    bool node<n,m>::operator==(const this_& that){
-        return (this->position()) == (that.position());
+    bool node<n,m>::operator==(const this_& that)const{
+        return position(*this) == position(that);
     }
 
     template<unsigned n,unsigned m>
-    bool node<n,m>::operator<(const this_& that){
+    bool node<n,m>::operator<(const this_& that)const{
         return position(*this) < position(that);
     }
 
@@ -166,8 +202,17 @@
         return out;
     }
 
+    template<unsigned n,unsigned m> 
+    bool 
+    is_root(const tree_view::node<n,m>& that){
+        typedef tree_view::node<n,m> node_;
+        static const node_ root_node;
+        return that == root_node;
+    }
+
     template<unsigned n,unsigned m>
-    tree_view::node<n,m> leaf(const tree_view::node<n,m>& that){
+    tree_view::node<n,m> 
+    first_child(const tree_view::node<n,m>& that){
         typedef tree_view::node<n,m> node_;
         node_ node = that;
         ++node.stage;
@@ -177,10 +222,10 @@
 
     template<unsigned n,unsigned m>
     tree_view::node<n,m> 
-    root(const tree_view::node<n,m>& that){
+    parent(const tree_view::node<n,m>& that){
         typedef tree_view::node<n,m> node_;
-        const char* msg = "node<n,m>::jump_to_root() already at root";
-        if(that.stage == 0 ){
+        const char* msg = "node<n,m>::parent() root has no parent";
+        if( that.stage == 0 ){
             throw std::out_of_range(
                 msg
             );
@@ -221,6 +266,21 @@
         return first(root,stage+1);
     }
 
+    template<unsigned n,unsigned m>
+    tree_view::node<n,m>
+    prior(const tree_view::node<n,m>& node){
+        typedef tree_view::node<n,m> node_;
+        node_ new_node = node;
+        return --new_node;
+    }
+
+    template<unsigned n,unsigned m>
+    tree_view::node<n,m>
+    next(const tree_view::node<n,m>& node){
+        typedef tree_view::node<n,m> node_;
+        node_ new_node = node;
+        return ++new_node;
+    }
 
 }// boost
 

Modified: sandbox/statistics/tree_view/libs/tree_view/doc/readme.txt
==============================================================================
--- sandbox/statistics/tree_view/libs/tree_view/doc/readme.txt	(original)
+++ sandbox/statistics/tree_view/libs/tree_view/doc/readme.txt	2009-09-04 20:25:45 EDT (Fri, 04 Sep 2009)
@@ -13,12 +13,13 @@
 [ Overview ]
 
     Maps a vector to a tree view, where each node has a fixed number of
-    branches. 
+    branches. Both breadth-first and depth-first visitation procedure are 
+    offered.
+        
+[ More advanced graph packages: ]
     
-[ Useful links ]
-
-    A comprehensive tree framework that is unrelated to this package:
-        http://raz.or.at/soc2006/doc/html/
+   http://raz.or.at/soc2006/doc/html/
+   http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/index.html
 
 [ Compiler ]
 
@@ -33,6 +34,10 @@
 Here's the current link to switch:
 http://www.boostpro.com/vault/index.php?action=downloadfile&filename=switch.zip&directory=&
 
+[ Sources ] 
+http://en.wikipedia.org/wiki/Tree_%28data_structure%29
+http://en.wikipedia.org/wiki/Depth-first_search
+http://en.wikipedia.org/wiki/Breadth-first_search
 
 [ History ]
 

Added: sandbox/statistics/tree_view/libs/tree_view/example/depth_first.cpp
==============================================================================
--- (empty file)
+++ sandbox/statistics/tree_view/libs/tree_view/example/depth_first.cpp	2009-09-04 20:25:45 EDT (Fri, 04 Sep 2009)
@@ -0,0 +1,34 @@
+#include <boost/tree_view/depth_first.hpp>
+#include <libs/tree_view/example/depth_first.h>
+
+void example_depth_first(std::ostream& os){
+    os << "-> example_depth_first " << std::endl;
+
+    using namespace boost;
+    
+    const unsigned n_branches = 3;
+    typedef tree_view::dynamic_stage<n_branches>     stage_;
+    typedef tree_view::node<n_branches>              node_;
+    typedef tree_view::depth_first<n_branches>       depth_first_;
+
+    using namespace boost;
+    const unsigned n_stages = 4;
+    const node_ root_node;
+
+    depth_first_ visit(n_stages);
+
+    do{
+        bool b = visit.is_subtree();
+        if(b){
+            os << '[' << visit.node() << ']';
+        }else{
+            os << visit.node();
+        }
+        ++visit;
+    }while(
+        !(visit.is_subtree() && (visit.node()==root_node))
+    );
+    os << "<-"; 
+}
+
+

Added: sandbox/statistics/tree_view/libs/tree_view/example/depth_first.h
==============================================================================
--- (empty file)
+++ sandbox/statistics/tree_view/libs/tree_view/example/depth_first.h	2009-09-04 20:25:45 EDT (Fri, 04 Sep 2009)
@@ -0,0 +1,14 @@
+///////////////////////////////////////////////////////////////////////////////
+// tree_view::example::depth_first.h                                         //
+//                                                                           //
+//  Copyright 2009 Erwann Rogard. Distributed under the Boost                //
+//  Software License, Version 1.0. (See accompanying file                    //
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)         //
+///////////////////////////////////////////////////////////////////////////////
+#ifndef LIBS_TREE_VIEW_EXAMPLE_DEPTH_FIRST_HPP_ER_2009
+#define LIBS_TREE_VIEW_EXAMPLE_DEPTH_FIRST_HPP_ER_2009
+#include <ostream>
+
+void example_depth_first(std::ostream& os);
+
+#endif
\ No newline at end of file

Modified: sandbox/statistics/tree_view/libs/tree_view/example/tree.cpp
==============================================================================
--- sandbox/statistics/tree_view/libs/tree_view/example/tree.cpp	(original)
+++ sandbox/statistics/tree_view/libs/tree_view/example/tree.cpp	2009-09-04 20:25:45 EDT (Fri, 04 Sep 2009)
@@ -18,7 +18,7 @@
     
     const unsigned n_branches = 3;
     typedef tree_view::dynamic_stage<n_branches>     stage_;
-    typedef tree_view::node<n_branches> node_;
+    typedef tree_view::node<n_branches>              node_;
 
     using namespace boost;
     const unsigned n_stages = 4;
@@ -36,7 +36,7 @@
     out << std::endl;
     node_ the_last = last( root_node, n_stages-1);
 
-    {   // Visits all nodes from the root node to that prior to the_last
+    {   // Breadth-first visitation
         out << node_::header << std::endl;
         node_ node = root_node;
         unsigned old_stage = node.stage;
@@ -52,7 +52,7 @@
     }
 
     out << std::endl;
-    {   // Visits all nodes from that prior to the_last to the root_node
+    {   // Breadth-first visitation, in reverse
         out << node_::header;
         node_ node = the_last;
         

Modified: sandbox/statistics/tree_view/libs/tree_view/src/main.cpp
==============================================================================
--- sandbox/statistics/tree_view/libs/tree_view/src/main.cpp	(original)
+++ sandbox/statistics/tree_view/libs/tree_view/src/main.cpp	2009-09-04 20:25:45 EDT (Fri, 04 Sep 2009)
@@ -7,9 +7,12 @@
 ///////////////////////////////////////////////////////////////////////////////
 #include <iostream>
 #include <libs/tree_view/example/tree.h>
+#include <libs/tree_view/example/depth_first.h>
 
 int main(){
-    example_tree(std::cout);
+    
+    // example_tree(std::cout);
+    example_depth_first(std::cout);
     
     return 0;
 }
\ No newline at end of file