|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2007-08-29 16:41:02
Author: bernhard.reiter
Date: 2007-08-29 16:41:00 EDT (Wed, 29 Aug 2007)
New Revision: 39063
URL: http://svn.boost.org/trac/boost/changeset/39063
Log:
* More documentation
* Some URL changes (from old to new SVN repo)
* Add boost/tree/algorithm subdir to documentation Jamfile.v2
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp | 2 +
sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2 | 1
sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk | 52 ++++++++++++++++++++++++++++++++++++++++
sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk | 15 ++++++-----
4 files changed, 63 insertions(+), 7 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp 2007-08-29 16:41:00 EDT (Wed, 29 Aug 2007)
@@ -48,6 +48,7 @@
* postorder. @p f must not modify the order of the sequence.
* If @p f has a return value it is ignored.
*/
+//[postorder_for_each
template <class Cursor, class Op>
Op for_each(Cursor s, Op f)
{
@@ -59,6 +60,7 @@
f(*subtree);
return f;
}
+//]
/**
* @brief First element of a MultiwayTree in postorder traversal
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2 (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2 2007-08-29 16:41:00 EDT (Wed, 29 Aug 2007)
@@ -15,6 +15,7 @@
doxygen autodoc
:
[ glob ../../../boost/tree/*.hpp ]
+ [ glob ../../../boost/tree/algorithm/*.hpp ]
[ glob ../../../boost/tree/augmentors/*.hpp ]
[ glob ../../../boost/tree/balancers/*.hpp ]
[ glob ../../../boost/tree/comparators/*.hpp ]
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk 2007-08-29 16:41:00 EDT (Wed, 29 Aug 2007)
@@ -56,6 +56,7 @@
[endsect] [/ Scope]
+[section Some Introductory Examples]
[section (Multiway) Tree Search]
Due to their implicit-only nature within the Standard Library (as used by `map`or `set` internally),
@@ -185,6 +186,55 @@
[endsect] [/ (Multiway) Tree Search]
+[section Tree Traversal]
+An interesting aspect of trees is that there are many ways to traverse a tree in a meaningful order.
+Among others, ['preorder], ['postorder] and ['inorder] are frequently encountered. For an overview,
+consult your favorite Computer Science textbook or [@http://en.wikipedia.org/wiki/Tree_traversal
+Wikipedia on Tree Traversal].
+Given only the essential minimum of information (i.e. child "pointers" from a parent "node", but
+no parent "pointers" from a child "node"), you will be told there, you have basically the choice between
+
+# a recursion (which implicitly uses the stack for storing the current "position" within the tree), or
+# an explicit stack representation, which has the advantage of also working iteratively.
+# With any amount of extra information, such as parent "pointers", using a stack can become obsolete
+altogether.
+
+[/import ../../../boost/tree/algorithm/postorder.hpp]
+
+Boost.Tree offers you each of the options listed above, each found in a namepace indicating the respective
+traversal order. For option number 1, pass the (root cursor of the) subtree to be traversed to either of
+
+[/postorder_for_each]
+[/warning TODO: Use up-to-date Boostbook to embed current code snip form header files directly!]
+
+[funcref boost::tree::preorder::for_each preorder::for_each]
+
+[funcref boost::tree::postorder::for_each postorder::for_each]
+
+[funcref boost::tree::inorder::for_each inorder::for_each]
+
+The other two options are both invoked by constructing an `iterator` with a cursor as argument:
+
+[/warning FIXME: Invalid class reference]
+
+[classref boost::tree::preorder::iterator preorder::iterator]
+
+[classref boost::tree::postorder::iterator postorder::iterator]
+
+[classref boost::tree::inorder::iterator inorder::iterator]
+
+If the argument cursor is descending, the iterator that will be constructed will internally use a `std::stack`
+of cursors. If on the other hand the cursor is ascending (has a `parent` member function), the iterator
+does not need such an explicit stack representation. Looking at textbook examples,
+you will however notice that it does need one piece of extra information: normally in these examples,
+there is a check if a given node's parent pointer is zero. There is no equivalent check possible with
+Boost.Tree, and in fact, it wouldn't even be desirable, as we also might want to traverse a subtree that
+is not equivalent to a "complete" tree object. Therefore, we need a second parameter beside the ascending
+cursor: an `int` indicating the "vertical" distance (or "generations") between the given cursor and the
+root of the subtree it belongs to.
+
+[endsect] [/ Tree Traversal]
+
[section Insertion and erasure semantics]
Given the cursor semantics developed in the above section, the logically next step is to ask how
modifications of trees, i.e. in particular insertion and erasure operations are to be performed.
@@ -259,6 +309,8 @@
[endsect] [/ Insertion and erasure semantics]
+[endsect] [/Some Introductory Examples]
+
[section Components]
[section Searcher]
[endsect] [/ Searcher]
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk 2007-08-29 16:41:00 EDT (Wed, 29 Aug 2007)
@@ -51,9 +51,10 @@
[section Download]
This library's current state is only available via [@http://subversion.tigris.org/ svn] from the
-Boost repository for Google Summer of Code 2006(tm) at
-[@https://www.boost-consulting.com/svn/main/boost/soc/2006]. The source code can be
-browsed online at [@https://boost-consulting.com/trac/soc/browser/boost/soc/2006/tree]. \n
+Boost Sandbox repository at [@https://svn.boost.org/svn/boost/sandbox/SOC/2006/tree]
+(This obsoletes the old Boost Consulting repository for Google Summer of Code 2006(tm) at
+https://www.boost-consulting.com/svn/main/boost/soc/2006.) The source code can be
+browsed online at [@http://svn.boost.org/trac/boost/browser/sandbox/SOC/2006/tree]. \n
A [@http://boost-consulting.com/vault/index.php?action=downloadfile&filename=tree-soc2006.zip&directory=Containers& snapshot]
of the final GSoC 2006 state (kindly provided by René Rivera) can be found at the
[@http://boost-consulting.com/vault/ Boost Vault].
@@ -67,9 +68,9 @@
[section Acknowledgements]
-This library originated in [@http://code.google.com/soc/boost/appinfo.html?csaid=E17EA7C7C537C131 one]
-out of [@http://code.google.com/soc/boost/about.html ten] [@http://www.boost.org/ Boost] projects
-sponsored by [@http://www.google.com Google] during their [@http://code.google.com/soc Summer of Code 2006].
+This library originated in [@http://code.google.com/soc/2006/boost/appinfo.html?csaid=E17EA7C7C537C131 one]
+out of [@http://code.google.com/soc/2006/boost/about.html ten] [@http://www.boost.org/ Boost] projects
+sponsored by [@http://www.google.com Google] during their [@http://code.google.com/soc/2006 Summer of Code 2006].
It was mentored by [@http://www.boost.org/people/rene_rivera.htm René Rivera]. \n
Kudos to DHL for forwarding my second check from rainy Vienna airport, Austria (30 minutes ride from
my place) on to Dubai, UAE, so it could catch some sun first.
@@ -92,8 +93,8 @@
[endsect] [/Introduction]
-[include tutorial.qbk]
[include overview.qbk]
+[include tutorial.qbk]
[include concepts.qbk]
[include glossary.qbk]
[include ../../../TODO]
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