|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r55887 - sandbox/statistics/tree/boost/tree
From: erwann.rogard_at_[hidden]
Date: 2009-08-30 17:56:46
Author: e_r
Date: 2009-08-30 17:56:45 EDT (Sun, 30 Aug 2009)
New Revision: 55887
URL: http://svn.boost.org/trac/boost/changeset/55887
Log:
m
Text files modified:
sandbox/statistics/tree/boost/tree/node.hpp | 174 ++++++++++++++++++++++-----------------
1 files changed, 98 insertions(+), 76 deletions(-)
Modified: sandbox/statistics/tree/boost/tree/node.hpp
==============================================================================
--- sandbox/statistics/tree/boost/tree/node.hpp (original)
+++ sandbox/statistics/tree/boost/tree/node.hpp 2009-08-30 17:56:45 EDT (Sun, 30 Aug 2009)
@@ -1,42 +1,46 @@
///////////////////////////////////////////////////////////////////////////////
-// tree::node.hpp //
+// tree_view::node.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_NODE_HPP_ER_2009
-#define BOOST_TREE_NODE_HPP_ER_2009
+#ifndef BOOST_TREE_VIEW_NODE_HPP_ER_2009
+#define BOOST_TREE_VIEW_NODE_HPP_ER_2009
#include <stdexcept>
#include <ostream>
#include <boost/operators.hpp>
#include <boost/tree/stage.hpp>
+#include <boost/tree/dynamic_stage.hpp>
namespace boost{
-namespace tree{
+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
- template<unsigned n>
+ // n : number of branches
+ // m : number of stages
+ template<unsigned n,unsigned m = BOOST_SWITCH_LIMIT>
struct node :
incrementable<
- node<n>,
+ node<n,m>,
decrementable<
- node<n>,
+ node<n,m>,
less_than_comparable<
- node<n>,
+ node<n,m>,
equality_comparable<
- node<n>
+ node<n,m>
>
>
>
>
{
typedef std::size_t size_type;
- typedef node<n> this_;
+ typedef node<n,m> this_;
typedef dynamic_stage<n> dyna_stage_;
unsigned stage;
unsigned position_in_stage;
@@ -47,46 +51,57 @@
this_& operator--();
bool operator==(const this_&);
bool operator<(const this_&);
+
+ static std::string header;
};
-}//tree
+}//tree_view
- template<unsigned n> std::ostream&
- operator<<(std::ostream& out, const tree::node<n>& that);
+ template<unsigned n,unsigned m> std::ostream&
+ operator<<(std::ostream& out, const tree_view::node<n,m>& that);
- template<unsigned n> typename tree::node<n>::size_type
- position(const tree::node<n>& that);
- template<unsigned n> tree::node<n> root(const tree::node<n>& leaf);
- template<unsigned n> tree::node<n> leaf(const tree::node<n>& root);
+ 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> node = leaf(root);
+ // node<n,m> node = leaf(the_root);
// while(root(node++)!=the_root){...}
- template<unsigned n>
- tree::node<n>
- first(const tree::node<n>& root,unsigned stage);
-
- template<unsigned n>
- tree::node<n>
- back(const tree::node<n>& root,unsigned stage);
-
- // ++back == last. The reason I don't define last is because the
- // for now only a fixed number of stages are available
+ template<unsigned n,unsigned m>
+ tree_view::node<n,m>
+ first(const tree_view::node<n,m>& root,unsigned stage);
+
+ template<unsigned n,unsigned m>
+ tree_view::node<n,m>
+ back(const tree_view::node<n,m>& root,unsigned stage);
+
+ template<unsigned n,unsigned m>
+ tree_view::node<n,m>
+ last(const tree_view::node<n,m>& root,unsigned stage);
-namespace tree{
+namespace tree_view{
// Implementation
- template<unsigned n>
- node<n>::node():stage(0),position_in_stage(0){}
- template<unsigned n>
- node<n>::node(unsigned j,unsigned k)
+ // k: position relative to other nodes at the same stage in the tree_view
+ // i: position in the vector
+ template<unsigned n,unsigned m>
+ std::string node<n,m>::header = "(stage,k,i)";
+
+ template<unsigned n,unsigned m>
+ node<n,m>::node():stage(0),position_in_stage(0){}
+
+ template<unsigned n,unsigned m>
+ node<n,m>::node(unsigned j,unsigned k)
:stage(j),position_in_stage(k){
const char* msg = "node(%1%,!(%2%<%3%)), ";
- unsigned l = dyna_stage_::position_last(this->stage);
- if(! (k < l) ){
+ unsigned l = dyna_stage_::number_nodes(this->stage);
+ if(! (k < l) ){
format f(msg);
f % j % k % l;
throw std::out_of_range(
@@ -95,11 +110,11 @@
}
}
- template<unsigned n>
- node<n>&
- node<n>::operator++(){
- unsigned m = dyna_stage_::position_last(this->stage);
- if( 1 + position(*this) < m){
+ template<unsigned n,unsigned m>
+ node<n,m>&
+ node<n,m>::operator++(){
+ unsigned mm = dyna_stage_::position_last(this->stage);
+ if( 1 + position(*this) < mm){
++(this->position_in_stage);
}else{
++stage;
@@ -108,39 +123,40 @@
return (*this);
}
- template<unsigned n>
- node<n>&
- node<n>::operator--(){
- const char* msg = "--node<n> at root";
+ template<unsigned n,unsigned m>
+ node<n,m>&
+ node<n,m>::operator--(){
+ const char* msg = "--node<n,m> at root";
if(this->stage == 0){
throw std::out_of_range(
msg
);
}
- unsigned m = dyna_stage_::position_last(this->stage-1);
- if( position(*this)-1 >= m){
+ unsigned mm = dyna_stage_::position_first( this->stage );
+ if( position(*this)-1 >= mm){
--(this->position_in_stage);
}else{
--stage;
- (this->position_in_stage) = m-1;
+ (this->position_in_stage)
+ = dyna_stage_::number_nodes( this->stage) - 1;
}
return (*this);
}
- template<unsigned n>
- bool node<n>::operator==(const this_& that){
+ template<unsigned n,unsigned m>
+ bool node<n,m>::operator==(const this_& that){
return (this->position()) == (that.position());
}
- template<unsigned n>
- bool node<n>::operator<(const this_& that){
- return (this->position()) < (that.position());
+ template<unsigned n,unsigned m>
+ bool node<n,m>::operator<(const this_& that){
+ return position(*this) < position(that);
}
}
- template<unsigned n>
- std::ostream& operator<<(std::ostream& out, const tree::node<n>& that){
+ template<unsigned n,unsigned m>
+ std::ostream& operator<<(std::ostream& out, const tree_view::node<n,m>& that){
out
<< '(' << that.stage
<< ',' << that.position_in_stage
@@ -149,20 +165,20 @@
return out;
}
- template<unsigned n>
- tree::node<n> leaf(const tree::node<n>& that){
- typedef tree::node<n> node_;
+ template<unsigned n,unsigned m>
+ tree_view::node<n,m> leaf(const tree_view::node<n,m>& that){
+ typedef tree_view::node<n,m> node_;
node_ node = that;
++node.stage;
(node.position_in_stage) *= n;
return node;
}
- template<unsigned n>
- tree::node<n>
- root(const tree::node<n>& that){
- typedef tree::node<n> node_;
- const char* msg = "node<n>::jump_to_root() already at root";
+ template<unsigned n,unsigned m>
+ tree_view::node<n,m>
+ root(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 ){
throw std::out_of_range(
msg
@@ -174,31 +190,37 @@
return node;
}
- template<unsigned n>
- typename tree::node<n>::size_type
- position(const tree::node<n>& that){
- typedef tree::node<n> node_;
+ template<unsigned n,unsigned m>
+ typename tree_view::node<n,m>::size_type
+ position(const tree_view::node<n,m>& that){
+ typedef tree_view::node<n,m> node_;
typedef typename node_::dyna_stage_ dyna_stage_;
return dyna_stage_::position_first(that.stage)
+(that.position_in_stage);
}
- template<unsigned n> tree::node<n>
- first(const tree::node<n>& root,unsigned stage){
- typedef tree::node<n> node_;
+ template<unsigned n,unsigned m>
+ tree_view::node<n,m>
+ first(const tree_view::node<n,m>& root,unsigned stage){
+ typedef tree_view::node<n,m> node_;
typedef typename node_::dyna_stage_ dyna_stage_;
- unsigned idx = dyna_stage_::position_first(stage);
- return node_(stage,idx);
+ return node_(stage,0);
}
- template<unsigned n> tree::node<n>
- back(const tree::node<n>& root,unsigned stage){
- typedef tree::node<n> node_;
+ template<unsigned n,unsigned m> tree_view::node<n,m>
+ back(const tree_view::node<n,m>& root,unsigned stage){
+ typedef tree_view::node<n,m> node_;
typedef typename node_::dyna_stage_ dyna_stage_;
- unsigned idx = dyna_stage_::position_last(stage)-1;
- return node_(stage,idx);
+ unsigned k = dyna_stage_::number_nodes( stage ) - 1;
+ return node_(stage,k);
}
+ template<unsigned n,unsigned m> tree_view::node<n,m>
+ last(const tree_view::node<n,m>& root,unsigned stage){
+ return first(root,stage+1);
+ }
+
+
}// boost
#endif
\ No newline at end of file
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk