Subject: [Boost-commit] svn:boost r48797 - in sandbox/SOC/2006/tree/trunk: . libs/tree/doc
Date: 2008-09-16 10:28:45
Date: 2008-09-16 10:28:44 EDT (Tue, 16 Sep 2008)
New Revision: 48797
Some documentation work (glossary, algorithms).
sandbox/SOC/2006/tree/trunk/libs/tree/doc/algorithms.qbk (contents, props changed)
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 19 +++++++++++-----
sandbox/SOC/2006/tree/trunk/libs/tree/doc/glossary.qbk | 46 +++++++++++++++++++++++++++++++++------
sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk | 14 +++++++----
3 files changed, 60 insertions(+), 19 deletions(-)
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-09-16 10:28:44 EDT (Tue, 16 Sep 2008)
@@ -15,6 +15,9 @@
+* Look into SOC 2008 projects dsearch (already using concepts from Boost.Tree) and
+ spacial_indexing (with tree classes of its own)
+* Can't we really do without inorder_erase()?
* Remove the word "recursive" from *order subtree algorithms context, as we might
implement these using iterative versions. Rename *_recursive algorithms to
*_with_references or so; and use something like #ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
@@ -40,7 +43,7 @@
(Compare this again to container vs sequence; also look into graph concepts.)
Finally, mind the implications for internal/external adaptation; they might be
generalised, if the above assumption is true.
-* Revisit binary_tree. Can it be usable for both balanced and forest trees and still be
+* Revisit binary_tree . Can it be usable for both balanced and forest trees and still be
"light-weight" at the same time?
* Re-organize traversal tests:
* Verify recursive algorithms to work
@@ -55,7 +58,7 @@
* Also test copy with two trees (not just one tree and a container/output iterator)
* Rename parity() (which looks somewhat binary-related) to index (more general for forest
-* _Possibly_ move detail/algorithm/cursor/ to detail/cursor/algorithm/ or even just
+* /Possibly/ move detail/algorithm/cursor/ to detail/cursor/algorithm/ or even just
detail/cursor/ (same for iterator).
* Make *order iterators work with empty subtrees; same for cursor algorithms.
(Not necessarily! If that means a check for empty(), it's better to leave it to
@@ -88,13 +91,13 @@
Ask on the mailing list:
-* [iterator] Can we get rid of the need to declare iterator_core_access a friend (as we're already
+* (iterator) Can we get rid of the need to declare iterator_core_access a friend (as we're already
doing so with cursor_core_access, this should be enough).
-* [property_map]: any need for an extract_property_map?
+* (property_map): any need for an extract_property_map?
-* Change complexity requirements for *order end() to constant? We're using root(), and
+* Change complexity requirements for * order end() to constant? We're using root(), and
for postorder begin() - which is also root() - it's already constant. Then again, how much
do we cater for "pathological" implementations (and not so pathological ones, like
@@ -135,8 +138,12 @@
+* Add a tree visualisation of the documentation structure (as some kind of frontispiece)
+ to the docs!
+* Add FAQ
+ * How can I visualise a tree, eg as SVG image?
* Take a look at BGL docs; they seem to be really well structured and written.
-* Add some illustrations
+* Add some illustrations (also for mapping how concepts relate to each other)
* Overview: develop hierarchy/cursor concept step by step, using illustrations that
depict what is introduced at what step (nodes with pointers to their siblings, children, parents,
a frame around a given cursor [and possibly additionally required information stated]
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/algorithms.qbk 2008-09-16 10:28:44 EDT (Tue, 16 Sep 2008)
@@ -0,0 +1,27 @@
+ / Copyright (c) 2006-2008, Bernhard Reiter
+ / 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)
+ / Boost.Tree
+ / Algorithms documentation file.
+While STL algorithms operate on (at least a pair of) iterators, for hierarchic structures
+as trees it is just natural to operate on a subtree which in turn are referenced by their
+"subtree root" cursor.
+Contrarily to iterator-based algorithms that normally just traverse a range given by two
+iterators starting at the first element linearly and terminating past the last element,
+there is no one such "natural" traversal for subtrees.
+[section Pre-, In-, and Postorder Algorithms]
+[endsect] [/ Pre-, In-, and Postorder Algorithms]
+[endsect] [/ Algorithms]
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/glossary.qbk (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/glossary.qbk 2008-09-16 10:28:44 EDT (Tue, 16 Sep 2008)
@@ -16,13 +16,43 @@
[caution TODO Write!]
-Cursor (link to concept)
-Header(really or only impl. detail?)
+A given cursor's child is any cursor that is found in the range described by its
+`begin()` and `end()` member functions.
+Informally, a cursor is to a tree what an iterator is to a standard library container:
+a kind of pointer abstraction that denotes a position within the tree and can be
+ereferenced or used to traverse the tree both horizontally and vertically.
+For a more formal definition, see (TODO: link to concept).
+A cursor's descendant is best defined recursively: It is
+* either a given cursor's child,
+* or a descendant of one of it's children.
+[[Multiway Tree] [
+Pretty obvious: the inverse of a child.
+All descendants of a given cursor.
[endsect] [/ Glossary]
\ No newline at end of file
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk 2008-09-16 10:28:44 EDT (Tue, 16 Sep 2008)
@@ -12,7 +12,7 @@
- [quickbook 1.3]
+ [quickbook 1.4]
[authors [Reiter, Bernhard]]
[copyright 2006 Bernhard Reiter]
[purpose Generic tree framework]
@@ -54,7 +54,8 @@
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
+browsed online at [@http://svn.boost.org/trac/boost/browser/sandbox/SOC/2006/tree].
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].
@@ -71,7 +72,8 @@
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
+It was mentored by [@http://www.boost.org/people/rene_rivera.htm RenÃ© Rivera].
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.
@@ -95,8 +97,10 @@
\ 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