|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r55896 - in sandbox/statistics/tree_view: . boost boost/tree_view libs libs/tree_view libs/tree_view/doc libs/tree_view/example libs/tree_view/src
From: erwann.rogard_at_[hidden]
Date: 2009-08-30 18:32:40
Author: e_r
Date: 2009-08-30 18:32:39 EDT (Sun, 30 Aug 2009)
New Revision: 55896
URL: http://svn.boost.org/trac/boost/changeset/55896
Log:
tree_view replaces tree
Added:
sandbox/statistics/tree_view/
sandbox/statistics/tree_view/boost/
sandbox/statistics/tree_view/boost/tree_view/
sandbox/statistics/tree_view/boost/tree_view/dynamic_stage.hpp (contents, props changed)
sandbox/statistics/tree_view/boost/tree_view/node.hpp (contents, props changed)
sandbox/statistics/tree_view/boost/tree_view/stage.hpp (contents, props changed)
sandbox/statistics/tree_view/libs/
sandbox/statistics/tree_view/libs/tree_view/
sandbox/statistics/tree_view/libs/tree_view/doc/
sandbox/statistics/tree_view/libs/tree_view/doc/readme.txt (contents, props changed)
sandbox/statistics/tree_view/libs/tree_view/example/
sandbox/statistics/tree_view/libs/tree_view/example/tree.cpp (contents, props changed)
sandbox/statistics/tree_view/libs/tree_view/example/tree.h (contents, props changed)
sandbox/statistics/tree_view/libs/tree_view/src/
sandbox/statistics/tree_view/libs/tree_view/src/main.cpp (contents, props changed)
Added: sandbox/statistics/tree_view/boost/tree_view/dynamic_stage.hpp
==============================================================================
--- (empty file)
+++ sandbox/statistics/tree_view/boost/tree_view/dynamic_stage.hpp 2009-08-30 18:32:39 EDT (Sun, 30 Aug 2009)
@@ -0,0 +1,81 @@
+///////////////////////////////////////////////////////////////////////////////
+// tree_view::dynamic_stage.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_DYNAMIC_STAGE_HPP_ER_2009
+#define BOOST_TREE_VIEW_DYNAMIC_STAGE_HPP_ER_2009
+#include <stdexcept>
+#include <ostream>
+#include <boost/mpl/range_c.hpp>
+#include <boost/tree_view/stage.hpp>
+#include <boost/switch.hpp>
+
+namespace boost{
+namespace tree_view{
+
+ // n : number of branches
+ // m : number of stages
+ template<unsigned n,unsigned m = BOOST_SWITCH_LIMIT>
+ class dynamic_stage{
+ typedef unsigned size_;
+ typedef mpl::range_c<size_,0,m> mpl_range_;
+
+ public:
+ static unsigned position_first(unsigned i);
+ static unsigned position_last(unsigned i);
+ static unsigned number_nodes(unsigned i);
+
+ private:
+ template<template<typename> class F>
+ struct switch_case{
+ typedef size_ result_type;
+ switch_case(){}
+ template<class Case>
+ result_type operator()(Case)const{
+ typedef stage<Case::value,n> stage_;
+ return F<stage_>::get();
+ }
+ };
+ struct throw_out_of_range {
+ template<class Case>
+ void operator()(Case) const {
+ throw(std::out_of_range());
+ }
+ };
+ template<template<typename> class F>
+ static unsigned switch_(unsigned j);
+ };
+
+ // Implementation //
+
+ template<unsigned n,unsigned m>
+ template<template<typename> class F>
+ unsigned dynamic_stage<n,m>::switch_(unsigned j){
+ return boost::switch_<mpl_range_>(
+ j,
+ switch_case<F>()//,
+ //throw_out_of_range()
+ );
+ }
+
+ template<unsigned n,unsigned m>
+ unsigned dynamic_stage<n,m>::position_first(unsigned j){
+ return switch_<position_first_>(j);
+ }
+ template<unsigned n,unsigned m>
+ unsigned dynamic_stage<n,m>::position_last(unsigned j){
+ return switch_<position_last_>(j);
+ }
+
+ template<unsigned n,unsigned m>
+ unsigned dynamic_stage<n,m>::number_nodes(unsigned j){
+ return switch_<number_nodes_>(j);
+ }
+
+}// tree_view
+}// boost
+
+#endif
Added: sandbox/statistics/tree_view/boost/tree_view/node.hpp
==============================================================================
--- (empty file)
+++ sandbox/statistics/tree_view/boost/tree_view/node.hpp 2009-08-30 18:32:39 EDT (Sun, 30 Aug 2009)
@@ -0,0 +1,227 @@
+///////////////////////////////////////////////////////////////////////////////
+// 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_VIEW_NODE_HPP_ER_2009
+#define BOOST_TREE_VIEW_NODE_HPP_ER_2009
+#include <stdexcept>
+#include <ostream>
+#include <boost/operators.hpp>
+#include <boost/tree_view/stage.hpp>
+#include <boost/tree_view/dynamic_stage.hpp>
+
+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 : number of branches
+ // m : number of stages
+ template<unsigned n,unsigned m = BOOST_SWITCH_LIMIT>
+ struct node :
+ incrementable<
+ node<n,m>,
+ decrementable<
+ node<n,m>,
+ less_than_comparable<
+ node<n,m>,
+ equality_comparable<
+ node<n,m>
+ >
+ >
+ >
+ >
+ {
+ typedef std::size_t size_type;
+ typedef node<n,m> this_;
+ typedef dynamic_stage<n> dyna_stage_;
+ unsigned stage;
+ unsigned position_in_stage;
+
+ node();
+ node(unsigned j,unsigned k);
+ this_& operator++();
+ this_& operator--();
+ bool operator==(const this_&);
+ bool operator<(const this_&);
+
+ static std::string header;
+
+ };
+
+}//tree_view
+
+ 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
+ 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>
+ 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_view{
+
+ // Implementation
+
+ // j: stage
+ // 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 = "(j,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_::number_nodes(this->stage);
+ if(! (k < l) ){
+ format f(msg);
+ f % j % k % l;
+ throw std::out_of_range(
+ f.str()
+ );
+ }
+ }
+
+ 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;
+ (this->position_in_stage) = 0;
+ }
+ return (*this);
+ }
+
+ 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 mm = dyna_stage_::position_first( this->stage );
+ if( position(*this)-1 >= mm){
+ --(this->position_in_stage);
+ }else{
+ --stage;
+ (this->position_in_stage)
+ = dyna_stage_::number_nodes( this->stage) - 1;
+ }
+ return (*this);
+ }
+
+ template<unsigned n,unsigned m>
+ bool node<n,m>::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,unsigned m>
+ std::ostream& operator<<(std::ostream& out, const tree_view::node<n,m>& that){
+ out
+ << '(' << that.stage
+ << ',' << that.position_in_stage
+ << ',' << position(that)
+ << ')';
+ return out;
+ }
+
+ 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,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
+ );
+ }
+ node_ node = that;
+ --node.stage;
+ node.position_in_stage /= n;
+ return 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,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_;
+ return node_(stage,0);
+ }
+
+ 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 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
Added: sandbox/statistics/tree_view/boost/tree_view/stage.hpp
==============================================================================
--- (empty file)
+++ sandbox/statistics/tree_view/boost/tree_view/stage.hpp 2009-08-30 18:32:39 EDT (Sun, 30 Aug 2009)
@@ -0,0 +1,82 @@
+///////////////////////////////////////////////////////////////////////////////
+// tree_view::stage.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_STAGE_HPP_ER_2009
+#define BOOST_TREE_VIEW_STAGE_HPP_ER_2009
+#include <stdexcept>
+#include <boost/format.hpp>
+
+namespace boost{
+namespace tree_view{
+
+ // This class maps a position in a tree structure to a position in a vector
+ //
+ // 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.
+
+ // j : stage
+ // n : number of branches per node
+ template<unsigned j,unsigned n>
+ struct stage{
+ static unsigned position_first;
+ static unsigned position_last;
+ static unsigned number_nodes;
+ };
+
+ template<unsigned n>
+ struct stage<0,n>{
+ static unsigned position_first;
+ static unsigned position_last;
+ static unsigned number_nodes;
+ };
+
+
+ // Client may ignore this:
+ template<typename T> struct position_first_{ static unsigned get(); };
+ template<typename T> struct position_last_{ static unsigned get(); };
+ template<typename T> struct number_nodes_{ static unsigned get(); };
+
+ // Implementation //
+
+ // Initialization
+ template<unsigned n>
+ unsigned stage<0,n>::position_first = 0;
+
+ template<unsigned n>
+ unsigned stage<0,n>::position_last = 1;
+
+ template<unsigned n>
+ unsigned stage<0,n>::number_nodes = 1;
+
+ // Recursion
+ template<unsigned j,unsigned n>
+ unsigned stage<j,n>::position_first
+ = stage<j-1,n>::template position_last;
+
+ template<unsigned j,unsigned n>
+ unsigned stage<j,n>::position_last
+ = stage<j,n>::position_first
+ + stage<j,n>::number_nodes;
+
+ template<unsigned j,unsigned n>
+ unsigned stage<j,n>::number_nodes
+ = stage<j-1,n>::number_nodes * n;
+
+ // T = stage
+ template<typename T>
+ unsigned position_first_<T>::get(){ return T::position_first; }
+ template<typename T>
+ unsigned position_last_<T>::get(){ return T::position_last; }
+ template<typename T>
+ unsigned number_nodes_<T>::get(){ return T::number_nodes; }
+
+}// tree_view
+}// boost
+
+#endif
\ No newline at end of file
Added: sandbox/statistics/tree_view/libs/tree_view/doc/readme.txt
==============================================================================
--- (empty file)
+++ sandbox/statistics/tree_view/libs/tree_view/doc/readme.txt 2009-08-30 18:32:39 EDT (Sun, 30 Aug 2009)
@@ -0,0 +1,58 @@
+///////////////////////////////////////////////////////////////////////////////
+// tree_view::doc::readme.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) //
+///////////////////////////////////////////////////////////////////////////////
+
+[ Contact ]
+
+erwann.rogard_at_[hidden]
+
+[ Overview ]
+
+ Maps a vector to a tree view, where each node has a fixed number of
+ branches.
+
+[ Useful links ]
+
+ A comprehensive tree framework that is unrelated to this package:
+ http://raz.or.at/soc2006/doc/html/
+
+[ Compiler ]
+
+gcc version i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1
+
+[ Dependencies ]
+
+/usr/local/boost_1_39_0/
+/switch
+
+[ Links ]
+Here's the current link to switch:
+http://www.boostpro.com/vault/index.php?action=downloadfile&filename=switch.zip&directory=&
+
+
+[ History ]
+
+Sep 01, 2009 : Rename tree to tree_view, fixed some bugs and added dynamic_stage.hpp
+July 2009 : First version
+
+[ Output ]
+
+main.cpp
+
+-> example_tree
+{[i(j),i(j+1)) : j=0,...,3}:(0,1)(1,4)(4,13)(13,40)
+(j,k,i)
+(0,0,0)
+(1,0,1)(1,1,2)(1,2,3)
+(2,0,4)(2,1,5)(2,2,6)(2,3,7)(2,4,8)(2,5,9)(2,6,10)(2,7,11)(2,8,12)
+(3,0,13)(3,1,14)(3,2,15)(3,3,16)(3,4,17)(3,5,18)(3,6,19)(3,7,20)(3,8,21)(3,9,22)(3,10,23)(3,11,24)(3,12,25)(3,13,26)(3,14,27)(3,15,28)(3,16,29)(3,17,30)(3,18,31)(3,19,32)(3,20,33)(3,21,34)(3,22,35)(3,23,36)(3,24,37)(3,25,38)(3,26,39)
+(j,k,i)
+(3,26,39)(3,25,38)(3,24,37)(3,23,36)(3,22,35)(3,21,34)(3,20,33)(3,19,32)(3,18,31)(3,17,30)(3,16,29)(3,15,28)(3,14,27)(3,13,26)(3,12,25)(3,11,24)(3,10,23)(3,9,22)(3,8,21)(3,7,20)(3,6,19)(3,5,18)(3,4,17)(3,3,16)(3,2,15)(3,1,14)(3,0,13)
+(2,8,12)(2,7,11)(2,6,10)(2,5,9)(2,4,8)(2,3,7)(2,2,6)(2,1,5)(2,0,4)
+(1,2,3)(1,1,2)(1,0,1)
+(0,0,0) <-
+
Added: sandbox/statistics/tree_view/libs/tree_view/example/tree.cpp
==============================================================================
--- (empty file)
+++ sandbox/statistics/tree_view/libs/tree_view/example/tree.cpp 2009-08-30 18:32:39 EDT (Sun, 30 Aug 2009)
@@ -0,0 +1,71 @@
+///////////////////////////////////////////////////////////////////////////////
+// tree_view::example::tree.cpp //
+// //
+// 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) //
+///////////////////////////////////////////////////////////////////////////////
+#include <boost/format.hpp>
+#include <boost/tree_view/stage.hpp>
+#include <boost/tree_view/node.hpp>
+#include <boost/tree_view/dynamic_stage.hpp>
+#include <libs/tree_view/example/tree.h>
+
+void example_tree(std::ostream& out){
+ out << "-> example_tree " << 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_;
+
+ using namespace boost;
+ const unsigned n_stages = 4;
+ const node_ root_node;
+
+ out << (format("{[i(j),i(j+1)) : j=0,...,%1%}:")%(n_stages-1)).str();
+ for(unsigned j = 0; j<n_stages; j++){
+ out
+ << '('
+ << stage_::position_first(j)
+ << ','
+ << stage_::position_last(j)
+ << ')';
+ }
+ 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
+ out << node_::header << std::endl;
+ node_ node = root_node;
+ unsigned old_stage = node.stage;
+ do{
+ if(node.stage != old_stage){
+ out << std::endl;
+ old_stage = node.stage;
+ }
+ out << node;
+ }while(
+ ++node< the_last
+ );
+ }
+
+ out << std::endl;
+ { // Visits all nodes from that prior to the_last to the root_node
+ out << node_::header;
+ node_ node = the_last;
+
+ unsigned old_stage = node.stage;
+ while(node.stage > 0){
+ --node;
+ if(node.stage != old_stage){
+ old_stage = node.stage;
+ out << std::endl;
+ }
+ out << node;
+ }
+ }
+
+ out << " <- ";
+}
\ No newline at end of file
Added: sandbox/statistics/tree_view/libs/tree_view/example/tree.h
==============================================================================
--- (empty file)
+++ sandbox/statistics/tree_view/libs/tree_view/example/tree.h 2009-08-30 18:32:39 EDT (Sun, 30 Aug 2009)
@@ -0,0 +1,14 @@
+///////////////////////////////////////////////////////////////////////////////
+// tree_view::example::tree.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_TREE_HPP_ER_2009
+#define LIBS_TREE_VIEW_EXAMPLE_TREE_HPP_ER_2009
+#include <ostream>
+
+void example_tree(std::ostream&);
+
+#endif
\ No newline at end of file
Added: sandbox/statistics/tree_view/libs/tree_view/src/main.cpp
==============================================================================
--- (empty file)
+++ sandbox/statistics/tree_view/libs/tree_view/src/main.cpp 2009-08-30 18:32:39 EDT (Sun, 30 Aug 2009)
@@ -0,0 +1,15 @@
+///////////////////////////////////////////////////////////////////////////////
+// example::tree.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) //
+///////////////////////////////////////////////////////////////////////////////
+#include <iostream>
+#include <libs/tree_view/example/tree.h>
+
+int main(){
+ example_tree(std::cout);
+
+ return 0;
+}
\ 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