[Boost-commit] svn:boost r54595 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail libs/tree/doc libs/tree/doc/html

Subject: [Boost-commit] svn:boost r54595 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail libs/tree/doc libs/tree/doc/html
From: ockham_at_[hidden]
Date: 2009-07-02 15:55:07

Author: bernhard.reiter
Date: 2009-07-02 15:55:06 EDT (Thu, 02 Jul 2009)
New Revision: 54595
URL: http://svn.boost.org/trac/boost/changeset/54595

Log:
Create proposal from quickbook source plus doxygen docs: first efforts.
Added:
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/proposal.qbk
      - copied, changed from r54593, /sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/references.qbk   (contents, props changed)
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp       |    20 +--                                     
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp  |    10 -                                       
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2         |    14 +                                       
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html |     1                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk       |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/proposal.qbk       |   253 +++++++++++++++++++++++++++++++-------- 
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk           |    16 --                                      
   7 files changed, 222 insertions(+), 94 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp	2009-07-02 15:55:06 EDT (Thu, 02 Jul 2009)
@@ -63,14 +63,12 @@
     };
     
     explicit binary_tree (allocator_type const& alloc = allocator_type())
-    : m_header(), m_node_alloc(alloc)
-    {
-    }
+    : m_header(), m_node_alloc(alloc) {}
 
     template <class InputCursor>
-        binary_tree (InputCursor subtree,
-            allocator_type const& alloc = allocator_type())
-            : m_header(), m_node_alloc(alloc)
+    binary_tree(InputCursor subtree, 
+                allocator_type const& alloc = allocator_type())
+    : m_header(), m_node_alloc(alloc)
     {
         insert(root(), subtree);
     }
@@ -264,14 +262,10 @@
 
             m_node_alloc.destroy(pos_node);
             m_node_alloc.deallocate(pos_node, 1);
+            
+            if (position == root())
+                m_header.m_children[0] = 0;
         }
-
-         if (position == root()) {
-            m_header.m_parent = &m_header;
-            m_header.m_children[0] = 0;
-            m_header.m_children[1] = &m_header;
-         }
-
          return position;
     }     
 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp	2009-07-02 15:55:06 EDT (Thu, 02 Jul 2009)
@@ -89,14 +89,10 @@
     typedef self_type* base_pointer;
     typedef self_type const* const_base_pointer;
         
-    node_base() : node_with_parent_base(), node_with_children_base()
-    {
-    }
+    node_base() : node_with_parent_base(), node_with_children_base() {}
 
     node_base(node_with_parent_base* p)
-    : node_with_parent_base(p), node_with_children_base()
-    {
-    }
+    : node_with_parent_base(p), node_with_children_base() {}
     
     // Binary specific
     
@@ -160,7 +156,7 @@
 
 template <typename T>
 class ascending_node : public node_base {
- public:
+public:
     typedef T value_type;
 
     typedef ascending_node<value_type> node_type;

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	2009-07-02 15:55:06 EDT (Thu, 02 Jul 2009)
@@ -15,13 +15,20 @@
 doxygen autodoc
         :
                 [ glob ../../../boost/tree/*.hpp ]
-		[ glob ../../../boost/tree/detail/augmentors/*.hpp ]
-		[ glob ../../../boost/tree/detail/balancers/*.hpp ]
+		#[ glob ../../../boost/tree/detail/augmentors/*.hpp ]
+		#[ glob ../../../boost/tree/detail/balancers/*.hpp ]
         :
                 <doxygen:param>"PREDEFINED=\"BOOST_PROCESS_DOXYGEN\""
-		<xsl:param>boost.doxygen.detailns=documenteverything
+		
+		# Include documentation for the code in the detail namespace?
+		#<xsl:param>boost.doxygen.detailns=documenteverything
         ;
 
+#doxygen proposal
+#	:
+#		<dependency>autodoc
+#	;
+
 xml tree
         :
                 tree.qbk
@@ -30,6 +37,7 @@
 boostbook standalone
         :
                 tree
+		#proposal
         :
                 <dependency>autodoc
                 <xsl:param>boost.libraries=$(BOOST_ROOT)/libs/libraries.htm

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html	2009-07-02 15:55:06 EDT (Thu, 02 Jul 2009)
@@ -7,6 +7,7 @@
 <head>
   <title>Hierarchical Data Structures and Related Concepts for the C++
   Standard Library (TR2)</title>
+  
 <style type="text/css">
   /*<![CDATA[*/
   li.c1 {list-style: none}

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	2009-07-02 15:55:06 EDT (Thu, 02 Jul 2009)
@@ -31,7 +31,7 @@
 STL-compatible iterator-like types and tree classes for mapping the latter kind of external or "explicit" 
 structures (ref); or, on the other hand, untangle balancing mechanisms from key search and other 
 additional features (which are referred to as "augmenting" here, using the terminology from 
-[link clrs CLRS]). 
+[link cormen Cormen ['et al.]]). 
 At the time of this writing, no efforts are known to the author that would cater for both cases; and, as 
 an aspect of this fact, there are presently no efforts that try in turn to separate the underlying tree 
 structure or "topology" from searching, balancing and augmenting and open up its hierarchical interface.

Copied: sandbox/SOC/2006/tree/trunk/libs/tree/doc/proposal.qbk (from r54593, /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/proposal.qbk	2009-07-02 15:55:06 EDT (Thu, 02 Jul 2009)
@@ -8,65 +8,206 @@
  //////////////////////////////////////////////////////////////////////////////////////////////
  /
  / Boost.Tree
- / Overview documentation file.
+ / Proposal documentation file.
  /]
 
 
-[section Overview]
+[section Hierarchical Data Structures and Related Concepts for the
+C++ Standard Library]
 
-[section Motivation]
-Trees can be found in most fields of computer science. In C++, 
-[http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree self-balancing binary search trees
-(SBBSTs)] are used in prominent implementations of the Standard Template Library's (STL) associative containers, ie
-`std::map`, `std::set` and their "multi" variants (Ref gcc?). But as we're only talking about implementations here,
-the actual trees aren't ever visible to a user of the STL. This of course already hints at the importance of
-trees plus at least one other level of indirection: trees for quick (O(log n)) associative storage and 
-retrieval of data.
-
-Furthermore, there are a couple of libraries that provide tree classes for the somewhat more obvious cases 
-in which the tree is not just an implementation detail, but where the actual hierarchical structure interface 
-is needed, eg for representing a directory hierarchy or an XML file.
-
-Existing efforts concerning C++ tree designs and implementations mostly try either to present somewhat 
-STL-compatible iterator-like types and tree classes for mapping the latter kind of external or "explicit" 
-structures (ref); or, on the other hand, untangle balancing mechanisms from key search and other 
-additional features (which are referred to as "augmenting" here, using the terminology from 
-[link clrs CLRS]). 
-At the time of this writing, no efforts are known to the author that would cater for both cases; and, as 
-an aspect of this fact, there are presently no efforts that try in turn to separate the underlying tree 
-structure or "topology" from searching, balancing and augmenting and open up its hierarchical interface.
-
-The present approach in providing a consistent framework for trees is arranged roughly around the following 
-principles:
-
-* ['Cursors] as a consequent continuation of the iterator concept for tree structures, abstracting the
-  usually underlying nodes.
-* ['Multiway tree search] as a generalization of binary tree search that in turn is viewed as a generalization
-of existing "linear" binary search algorithms (like `lower_bound`, `upper_bound` etc.) for STL containers.
-
-Note that this approach seeks to hide ['nodes] as much as possible from the library client, although they 
-play of course an important role in the assembly of a tree; nevertheless it was felt that they were not
-suitable for interface purposes. (Note e.g. that nodes are not as atomic an element for a tree as they
-might seem at first glance; in case of multiway trees, for example, each node contains a number of 
-values.)
-[endsect] [/ Motivation]
-
-[section Scope]
-Due to the nature of the fields of interest concerning trees (as opposed to their graph superset) in 
-computer science as well as the underlying technique, we implicitly mean a ['rooted ordered connected 
-acyclic graph] when we're
-talking about trees in the following.
-
-This includes, but is not limited to
-
-* Binary search trees; most notably, self-balancing ones, such as
-	* Red-black trees
-* B-trees
-* Ternary search trees
-* Forests, i.e. trees that aren't primarily used for searching but for mapping a hierarchical strucutre.
-...
+[heading Bernhard Reiter and René Rivera]
 
-[endsect] [/ Scope]
-
-[endsect] [/ Overview]
+[variablelist
+[[Document No.] [WG21/N2101=J16/06-0171]]
+[[Date]         [2006-11-05]]
+[[Project]      [Programming Language C++]]
+[[Reply to]     [Bernhard Reiter <[@mailto:ockham_at_[hidden] ockham_at_[hidden]>],
+                 René Rivera <[@mailto:rrivera_at_[hidden] rrivera_at_[hidden]]>]]
+]
+
+
+[section Introduction]
+This paper proposes addition of library components covering tree structures and related
+concepts to the C++ Standard Library Technical Report 2. The proposal is based on work
+towards a Boost tree component library.
+The library strives to cover many of the relevant aspects within the vast field linked to
+the notion of trees in computer science.
+[endsect]
+
+[section Motivation and Scope]
+
+[section Why is this important?]
+This proposal is motivated by the wish to establish methods of dealing with hierarchical
+data structures in a manner that is similar to that of the Standard Template Library (STL)
+for linear ones. That is,
+it seeks to provide clear, straight-forward, versatile and comprehensive concepts, data
+structures and algorithms for trees and related structures that allow efficient
+implementation while not exposing implementation details.
+In particular, this proposal strives to unite types of hierarchical data structures that
+have historically been treated separately, although there is arguably good reason to view
+their role for algorithms as different aspects of common underlying concepts. Formally,
+this proposal's desired scope is covering all rooted ordered connected acyclic graphs.
+[endsect]
+
+[section What kinds of problems does it address, and what kinds of
+programmers is it intended to support?]
+Existing tree implementations as listed in the References section as well as the number
+of posts on C++ related newsgroups give an evidence of very general, high interest in
+tree and related data structures. Formalization of how to deal with hierarchical data
+structures seems to be relevant as programmers of any level of skill working in any given
+field is likely to need such a structure at one point.
+[endsect]
+
+[section Is it based on existing practice?]
+No; this proposal originates in an effort to create a generic tree container component
+for [@http://www.boost.org Boost] in the course of 
+[@http://code.google.com/soc/2006/boost/appinfo.html?csaid=E17EA7C7C537C131
+Google Summer of CodeTM 2006], so at the time of this
+writing, implementation work is still unfinished and, however inspired by and striving to
+avoid past issues and such ones arising from current implementation efforts (see below)
+it is, it has not been used in practice yet.
+[endsect]
+
+[section Is there a reference implementation?]
+Yes; the current state is available from svn from 
+[@http://svn.boost.org/svn/boost/sandbox/SOC/2006/tree/trunk].
+Alternatively, the source code can be viewed in a web browser at
+[@https://svn.boost.org/trac/boost/browser/sandbox/SOC/2006/tree/trunk].
+[endsect]
+
+[endsect]
+
+[section Impact on the Standard]
+
+[section What does it depend on, and what depends on it?]
+It depends on some standard library components, such as [^std::allocator] which is used
+as the default allocator template argument at some points. Concepts like allocators or
+iterators are reused and in some cases adapted.
+[endsect]
+
+[section Is it a pure extension, or does it require changes to
+standard components?]
+Most of the proposed library is a pure extension.
+Some extensions [^<algorithm>] and some extensions to [^<iterator>] are proposed.
+Additionally, while not proposed herein, it has sometimes been suggested to add a
+template parameter to the STL associative containers [^set], [^multiset], [^map], and
+[^multimap] (and possibly an argument to their constructors) specifying a policy for
+storing elements, or, more concretely, what tree. The balancers presented in this
+proposal would lend themselves to such use. Indicating what type of balanced hierarchy to
+use for associative containers would create some amount of symmetry to TR1's [^unordered]
+containers that allow specification of a hash functor; it is however a momentous decision
+in which position to put such a parameter. The same position as for [^unordered]
+containers (before the comparison functor) would require changes in existing code; making
+it the last parameter (after the allocator) would allow existing code to remain
+unchanged, but seems somewhat irritating when compared to [^unordered] containers.
+[endsect]
+
+[section Can it be implemented using today's compilers, or does it
+require language features that will only be available as part of C++0x?]
+It can be, and partly has been, implemented with today's compilers.
+Note that it might be worthwhile to investigate if the present Container concept should
+be modified so that it only covers the requirements as of paragraph 2 of section
+[@#tr.hierarchy.req [tr.hierarchy.req]] of this proposal, which correspond to the current
+Container concept with the exception of any expressions that implicitly assume linear
+internal structure and outsource those to a "Linear Container" concept as similarly
+formalized in the [@http://boost.org/libs/range/doc/range.html Boost Range concept]
+([@http://boost.org/libs/range/doc/range.html]) externally to the Standard.
+[endsect]
+
+[endsect]
+[section Important Design Decisions]
+
+[section Why did you choose the specific design that you did?]
+One of the most important assets of the present design is the cursor concept as a
+hierarchical continuation to the STL's iterator concept, and the externally defined range
+concept. Among their benefits, cursors allow to handle both client data access, by
+dereference, and subtree access while hiding the normally underlying node structure and
+providing a uniform interface to algorithms that are thus enabled to deal with a number
+of different kinds of trees. On the other hand, this abstraction achieves independence of
+implementation details, such as nodes for storage in many cases, allowing the underlying
+concepts to be applicable to other possible implementations as well.
+[endsect]
+
+[section What alternatives did you consider, and what are the
+tradeoffs?]
+
+[section Trees of trees]
+Trees, being recursively defined data structures, seem to somewhat lend themselves to
+recursive implementation, i.e. declaring them in a way so they consist of a client value
+part and a certain number of trees in turn (as e.g. in case of [link haas \[haas\]]). Such
+an approach would allow for uniform treatment of the subtrees, but would duplicate
+allocators and imply structure that need not be present. The tree, like existing STL
+containers, should be responsible for data representation and storage.
+[endsect]
+
+[section Augmentors/balancers as policies]
+Inspired by [link austern \[austern\]] and [link dreizin \[dreizin\]], the original
+approach undertaken when working on the reference implementation was to pass policy
+template arguments to template class [^binary_tree]. While reproducing the (otherwise
+unbalanced) tree/cursor interface seemed logical at first, it turned out that this was
+conceptually not entirely clean, as e.g. it preferred one type of linear order, namely
+inorder, over the others by putting such strong focus on inorder-invariant balancing and
+its possible applications; also, balancing and augmenting metadata would inevitably have
+been much more visible. It seemed more appropriate to have different balancing adaptors
+and augmenting adaptors that would replicate the interface to do that work.
+[endsect]
+
+[endsect]
+
+[section What are the consequences of your choices, for users and
+implementors?]
+As focus was put on versatility and comprehensiveness, we hope users will find this a
+powerful framework that covers most important aspects of dealing with hierarchical data
+structures in a rather intuitive way, once they have adapted to the notion of cursors
+which, although being the interface relevant portion of the well-known node
+implementation of trees, partly diverge in their usage from plain node objects.
+Wherever reasonably possible, strong time complexity guarantees are given, which mostly,
+while trying not to require much space overhead, demand implementations that make use of
+any time and space saving techniques available (e.g. using arrays for both children of a
+binary tree node, see e.g. [link austern \[austern\]]), which may partly restrict
+implementors to one "proper" way of doing things.
+[endsect]
+
+[section What decisions are left up to implementors?]
+Most of the requirements for the library components presented in this proposal are rather
+tightly formulated in order to allow for them being both efficient and general enough. It
+is however hoped that the conceptual abstraction of hierarchies and cursors may be of
+general use, also allowing for more specific implementations where required (although
+probably not as part of the library; ideally comparable to the role of containers and
+iterators in modern C++ code).
+[endsect]
+
+[section If there are any similar libraries in use, how do their
+design decisions compare to yours?]
+Trees, having attracted much attention in the C++ community, are found in various
+implementations and as subjects of a number of papers. Contrary to the present proposal,
+practically all of them deal either with trees as used for sorted associative containers
+(with logarithmic time complexity for more relevant operations, achieved by some sort of
+balancing; examples are [link dreizin \[dreizin\]], [link ekman \[ekman\]] and 
+[link karas \[karas\]]; plus, most current STL implementations use a red-black tree as their
+associative containers' base) or with what we call "external" hierarchies in the
+following (whose structure is dictated e.g. by a file system directory tree, an XML file
+or an AST; see e.g. [link gottschlich \[gottschlich\]], [link haas \[haas\]], 
+[link parent \[parent\]] and [link peeters \[peeters\]]), but rarely both fields of application.
+Approaches as found in [link austern \[austern\]] or [link mirwaisi \[mirwaisi\]] go some
+steps further and have provided valuable inspiration for this project, but still do not
+formalize anything similar as the cursor-based interface in this proposal for dealing
+with a tree's contents.
+The [@http://www.boost.org/libs/graph/ BGL], finally, deals with graphs that are even
+more general than hierarchical ones, which does not allow them to profit from specific
+hierarchy properties as much as the ones presented in this proposal. Making cursors
+logical extensions of iterators would probably also have been more difficult with a
+BGL-based approach.
+[endsect]
+
+[endsect]
+
+[section Future Directions]
+While it is hoped that the current proposal somewhat reunites balanced binary trees,
+B-trees and "external" hierarchies, which should also facilitate work with some
+higher-level structures (e.g. n-ary trees to implement tries), some of those higher-level
+components might be an interesting feature to add to the library, such as patricia tries
+or ternary search tries.
+[endsect]
 
+[endsect] [/Title]

Added: sandbox/SOC/2006/tree/trunk/libs/tree/doc/references.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/references.qbk	2009-07-02 15:55:06 EDT (Thu, 02 Jul 2009)
@@ -0,0 +1,56 @@
+[/
+ /  Copyright (c) 2006-2009, 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
+ / References documentation file.
+ /]
+
+[section References]
+[variablelist
+[[[#austern] \[austern\]]
+[Austern, Matthew H.; Stroustrup, Bjarne; Thorup, Mikkel; Wilikinson, John. Untangling
+the Balancing and Searching of Balanced Binary Search Trees, Software: Practice and
+Experience 33(13): 1273-1298 (2003)
+Electronic Appendix: [@http://www.research.att.com/~bs/tree-appendix.pdf]]]
+[[[#cormen] \[cormen\]]
+[Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford.
+Introduction to Algorithms. Second Edition (MIT Press, 2001)]]
+[[[#dreizin] \[dreizin\]]
+[Dreizin, Vladimir; Kosnik, Benjamin; Tavory, Ami. Policy-Based Data Structures,
+[@http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/]]]
+[[[#ekman] \[ekman\]]
+[Ekman, Rasmus. Structured Associative Containers, [@http://www.abc.se/~re/code/tst]]]
+[[[#gottschlich] \[gottschlich\]]
+[Gottschlich, Justin. C++ Trees, 
+[@http://www.gamedev.net/reference/articles/article2192.asp] and 
+[@http://www.gamedev.net/reference/articles/article2233.asp]]]
+[[[#haas] \[haas\]]
+[Haas, Mitchell. Tree Container Library, 
+[@http://www.datasoftsolutions.net/tree_container_library/overview.php]]]
+[[[#karas] \[karas\]]
+[Karas, Walt. C++ AVL Tree Template, 
+[@http://us.geocities.com/wkaras/gen_cpp/avl_tree.html]]]
+[[[#knuth97] \[knuth97\]]
+[Knuth, Donald E. The Art of Computer Programming. Volume 1: Fundamental Algorithms.
+Third Edition (Reading, Massachusetts: Addison-Wesley, 1997)]]
+[[[#knuth98] \[knuth98\]]
+[Knuth, Donald E. The Art of Computer Programming. Volume 3: Sorting and Searching.
+Second Edition (Reading, Massachusetts: Addison-Wesley, 1998)]]
+[[[#mirwaisi] \[mirwaisi\]]
+[Mirwaisi, Jeff. treelib, 
+[@https://boost-consulting.com:8443/trac/soc/attachment/wiki/tree/resources/trees/treelib.tar.bz2]]]
+[[[#parent] \[parent\]]
+[Parent, Sean ['et al]. forest, [@http://opensource.adobe.com/group__forest__related.html]]]
+[[[#peeters] \[peeters\]]
+[Peeters, Kasper. tree.hh: an STL-like C++ tree class, 
+[@http://www.aei.mpg.de/~peekas/tree/]]]
+[[[#rivera] \[rivera\]]
+[Rivera, René. RankTree.h, [@http://redshift-software.com/~grafik/RankTree.h]]]
+] [/ variablelist]
+[endsect] [/ References]
\ No newline at end of file

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	2009-07-02 15:55:06 EDT (Thu, 02 Jul 2009)
@@ -79,20 +79,6 @@
 
 [endsect] [/Acknowledgements]
 
-[section References]
-
-* [#austern] Austern, Matthew H.; Stroustrup, Bjarne; Thorup, Mikkel; Wilikinson, John. Untangling the Balancing and 
-Searching of Balanced Binary Search Trees, Software: Practice and Experience 33(13): 1273-1298 (2003)
-	* [#austern_app] [@http://www.research.att.com/~bs/tree-appendix.pdf Electronic appendix]
-* Knuth, Donald E. The Art of Computer Programming
-	* [#taocp1] Volume 1: Fundamental Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997)
-	* [#taocp3] Volume 3: Sorting and Searching. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998)
-* [#clrs] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Algorithmen - Eine
-Einführung (Oldenbourg, 2004) (German translation of Introduction to Algorithms. Second Edition 
-(MIT Press, 2001)
-
-[endsect] [/References]
-
 [endsect] [/Introduction]
 
 [include overview.qbk]
@@ -101,7 +87,9 @@
 [include concepts.qbk]
 [include algorithms.qbk]
 
+[include proposal.qbk]
 [include implementation.qbk]
 [include glossary.qbk]
+[include references.qbk]
 [include ../../../TODO]
 [xinclude autodoc.xml]
\ No newline at end of file