Subject: [Boost-commit] svn:boost r56025 - sandbox/statistics/tree_view/boost/tree_view
From: erwann.rogard_at_[hidden]
Date: 2009-09-04 20:39:27
Author: e_r
Date: 2009-09-04 20:39:26 EDT (Fri, 04 Sep 2009)
New Revision: 56025
URL: http://svn.boost.org/trac/boost/changeset/56025
Log:
m
Text files modified:
sandbox/statistics/tree_view/boost/tree_view/depth_first.hpp | 10 +++++++---
sandbox/statistics/tree_view/boost/tree_view/node.hpp | 23 ++++++++++++++++++-----
sandbox/statistics/tree_view/boost/tree_view/stage.hpp | 2 +-
3 files changed, 26 insertions(+), 9 deletions(-)
Modified: sandbox/statistics/tree_view/boost/tree_view/depth_first.hpp
==============================================================================
--- sandbox/statistics/tree_view/boost/tree_view/depth_first.hpp (original)
+++ sandbox/statistics/tree_view/boost/tree_view/depth_first.hpp 2009-09-04 20:39:26 EDT (Fri, 04 Sep 2009)
@@ -17,6 +17,7 @@
namespace boost{
namespace tree_view{
+ // Manages a node that moves in the tree according to breadth-first
template<unsigned n,unsigned m = BOOST_SWITCH_LIMIT>
class depth_first
: incrementable<
@@ -27,21 +28,24 @@
typedef node<n,m> node_type;
public:
+ // [ Construction ]
depth_first();
+ // Initialized with the root node:
depth_first(unsigned n_stages); //terminal stage = n_stages - 1
// [ Update ]
- void operator++();
+ void operator++();
// [ Access ]
- bool is_subtree()const;
+ // Whether the subtree rooted at the current node was visited
+ 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_;
+ bools_ tree_; // keeps is_subtree for each node in the tree
node_type node_;
};
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:39:26 EDT (Fri, 04 Sep 2009)
@@ -16,7 +16,12 @@
namespace boost{
namespace tree_view{
-// n = 3 :
+// Data structure reprensentation:
+// i : position in physical storage
+// k : position in stage
+// j : stage
+//
+// Example for n = 3 :
//
// j: 0 1 2
//
@@ -38,7 +43,8 @@
// ) )
// )
-
+ // Data structure representing a node in a tree
+ //
// n : number of branches
// m : number of stages
template<unsigned n,unsigned m = BOOST_SWITCH_LIMIT>
@@ -64,6 +70,8 @@
node();
node(unsigned j,unsigned k);
+
+ // ++ and -- are along breadth-first
this_& operator++();
this_& operator--();
bool operator==(const this_&)const;
@@ -90,7 +98,7 @@
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
+ // first_child(a) is first node in the next stage, with parent a.
// To visit all the nodes sharing the same parent:
// node<n,m> node = first_child(a);
// while(parent(node++)!=a){...}
@@ -98,7 +106,8 @@
tree_view::node<n,m>
first_child(const tree_view::node<n,m>& parent);
- // -> firs, back and last of each stage
+ // -> first, back and last of each stage
+ // [first,...,back,last)
template<unsigned n,unsigned m>
tree_view::node<n,m>
first(const tree_view::node<n,m>& root,unsigned stage);
@@ -112,6 +121,7 @@
last(const tree_view::node<n,m>& root,unsigned stage);
// <-
+ // prior and next by breadth first.
template<unsigned n,unsigned m>
tree_view::node<n,m>
prior(const tree_view::node<n,m>& node);
@@ -193,7 +203,10 @@
}
template<unsigned n,unsigned m>
- std::ostream& operator<<(std::ostream& out, const tree_view::node<n,m>& that){
+ std::ostream& operator<<(
+ std::ostream& out,
+ const tree_view::node<n,m>& that
+ ){
out
<< '(' << that.stage
<< ',' << that.position_in_stage
Modified: sandbox/statistics/tree_view/boost/tree_view/stage.hpp
==============================================================================
--- sandbox/statistics/tree_view/boost/tree_view/stage.hpp (original)
+++ sandbox/statistics/tree_view/boost/tree_view/stage.hpp 2009-09-04 20:39:26 EDT (Fri, 04 Sep 2009)
@@ -18,7 +18,7 @@
// The tree structure has a root node (stage 0) with n adjacent
// nodes (stage 1), each of which have n adjacent nodes (stage 2) etc.
// The nodes are stored in a vector, starting with the root node,
- // followed by those in stage1, then those in stage 2 etc.
+ // followed by those in stage1, then those in stage 2 etc. (breadth first)
// j : stage
// n : number of branches per node