[Boost-commit] svn:boost r76504 - in sandbox/tree/libs/tree/proposal: . single

Subject: [Boost-commit] svn:boost r76504 - in sandbox/tree/libs/tree/proposal: . single
From: grafikrobot_at_[hidden]
Date: 2012-01-15 01:16:47

Author: grafik
Date: 2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
New Revision: 76504
URL: http://svn.boost.org/trac/boost/changeset/76504

Log:
Changes to proposal document generation so that it works cross-platform (i.e. on Windows also). And more style tweaks to get even closer to the look&feel of a standard doc.
Added:
   sandbox/tree/libs/tree/proposal/preamble.qbk   (contents, props changed)
   sandbox/tree/libs/tree/proposal/single/proposal.docbook   (contents, props changed)
   sandbox/tree/libs/tree/proposal/tr-algorithms.qbk   (contents, props changed)
   sandbox/tree/libs/tree/proposal/tr-containers.qbk   (contents, props changed)
   sandbox/tree/libs/tree/proposal/tr-hierarchy-augment.qbk   (contents, props changed)
   sandbox/tree/libs/tree/proposal/tr-hierarchy-balance.qbk   (contents, props changed)
   sandbox/tree/libs/tree/proposal/tr-hierarchy-bintree.qbk   (contents, props changed)
   sandbox/tree/libs/tree/proposal/tr-hierarchy-foresttree.qbk   (contents, props changed)
   sandbox/tree/libs/tree/proposal/tr-hierarchy-multiwaytree.qbk   (contents, props changed)
   sandbox/tree/libs/tree/proposal/tr-hierarchy-narytree.qbk   (contents, props changed)
   sandbox/tree/libs/tree/proposal/tr-iterators.qbk   (contents, props changed)
Text files modified: 
   sandbox/tree/libs/tree/proposal/Jamfile.v2           |    55                                         
   sandbox/tree/libs/tree/proposal/proposal.css.xml     |   564 ++++++++--------                        
   sandbox/tree/libs/tree/proposal/proposal.qbk         |   325 ---------                               
   sandbox/tree/libs/tree/proposal/single/proposal.html |  1378 ++++++++++++++++++++++++++------------- 
   4 files changed, 1234 insertions(+), 1088 deletions(-)

Modified: sandbox/tree/libs/tree/proposal/Jamfile.v2
==============================================================================
--- sandbox/tree/libs/tree/proposal/Jamfile.v2	(original)
+++ sandbox/tree/libs/tree/proposal/Jamfile.v2	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -1,4 +1,5 @@
 #  Copyright (c) 2006-2009, Bernhard Reiter
+#  Copyright (c) 2006-2012, Rene Rivera
 #
 #  Distributed under the Boost Software License, Version 1.0.
 #  (See accompanying file LICENSE_1_0.txt or copy at
@@ -8,27 +9,24 @@
 
 if ! $(BOOST_ROOT)
 {
-	BOOST_ROOT = [ modules.peek : BOOST_ROOT ] ;
+    BOOST_ROOT = [ modules.peek : BOOST_ROOT ] ;
 }
 
-xml proposal
-	:
-		proposal.qbk
-	;
-explicit proposal ;
-
 boostbook proposal-standalone
     :
-    	proposal
+        proposal.qbk
     :
-    	<xsl:param>html.stylesheet=proposal.css
-    	<xsl:param>doc.standalone=1
-    	<xsl:param>nav.layout=none
-    	<xsl:param>toc.section.depth=2
-    	<xsl:param>section.autolabel=1
-    	<xsl:param>section.autolabel.max.depth=3
-    	<xsl:param>chapter.autolabel=0
-    	<xsl:param>navig.graphics=0
+        <location>xhtml
+        <format>xhtml
+        
+        <xsl:param>html.stylesheet=proposal.css
+        <xsl:param>doc.standalone=1
+        <xsl:param>nav.layout=none
+        <xsl:param>toc.section.depth=2
+        <xsl:param>section.autolabel=1
+        <xsl:param>section.autolabel.max.depth=3
+        <xsl:param>chapter.autolabel=0
+        <xsl:param>navig.graphics=0
         <xsl:param>boost.root=../../..
         #<xsl:param>generate.section.toc.level=3
         <xsl:param>chunk.section.depth=1
@@ -44,31 +42,34 @@
 
 install proposal-standalone-images
     : [ glob $(BOOST_ROOT)/doc/src/images/*.png ]
-    : <location>html/images ;
+    : <location>standalone/images ;
 explicit proposal-standalone-images ;
 
 install proposal-standalone-callouts
     : [ glob $(BOOST_ROOT)/doc/src/images/callouts/*.png ]
-    : <location>html/images/callouts ;
+    : <location>standalone/images/callouts ;
 explicit proposal-standalone-callouts ;
 
 install proposal-standalone-css
     : [ glob $(BOOST_ROOT)/doc/src/*.css ]
-    : <location>html ;
+    : <location>standalone ;
 explicit proposal-standalone-css ;
 
 boostbook proposal-single
     :
-        proposal
+        proposal.qbk
     :
-        #<xsl:param>html.stylesheet=proposal.css
-        #<xsl:param>html.stylesheet=
+        <location>single
+        <format>onehtml
+        
+        <dependency>proposal.css.xml
+        
         <xsl:param>doc.standalone=1
         <xsl:param>nav.layout=none
         <xsl:param>navig.graphics=0
         <xsl:param>boost.root=../../..
         <xsl:param>admon.graphics=0
-        <xsl:param>toc.section.depth=100
+        <xsl:param>toc.section.depth=5
         <xsl:param>section.autolabel=1
         <xsl:param>section.autolabel.max.depth=100
         <xsl:param>chapter.autolabel=0
@@ -77,11 +78,7 @@
         <xsl:param>chunk.first.sections=100
         <xsl:param>generate.id.attributes=1
         <xsl:param>generate.css.header=1
-        <xsl:param>custom.css.source=$(BOOST_TREE_ROOT)/libs/tree/proposal/proposal.css.xml
+        <xsl:param>custom.css.source=../proposal.css.xml
         <xsl:param>make.clean.html=1
-        
-        <location>single
-        <format>onehtml
-        <dependency>proposal.css.xml
     ;
-	
\ No newline at end of file
+    
\ No newline at end of file

Added: sandbox/tree/libs/tree/proposal/preamble.qbk
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/preamble.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,240 @@
+[/
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2011, René Rivera
+ /
+ /  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)
+ /]
+
+[section:preamble Hierarchical Data Structures and Related Concepts for the
+C++ Standard Library]
+
+[*Bernhard Reiter and René Rivera]
+
+[variablelist
+[[Document No.] [WG21/N????=J16/??-????]]
+[[Supercedes]   [WG21/N2101=J16/06-0171]]
+[[Date]         [__DATE__]]
+[[Project]      [Programming Language C++]]
+[[Reply to]     [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 Code(tm) 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 __code_rep__.
+
+[endsect]
+
+[endsect] [/Motivation and Scope]
+
+[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++11]
+
+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] [/Impact on the Standard]
+
+[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?]
+
+[heading 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.
+
+[heading 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]
+
+[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] [/Important Design Decisions]
+
+[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] [/Future Directions]
+
+[endsect] [/preamble]

Modified: sandbox/tree/libs/tree/proposal/proposal.css.xml
==============================================================================
--- sandbox/tree/libs/tree/proposal/proposal.css.xml	(original)
+++ sandbox/tree/libs/tree/proposal/proposal.css.xml	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -13,17 +13,17 @@
     Body defaults
 =============================================================================*/
 body {
-	margin: 1em;
-	font-family: sans-serif;
+  margin: 1em;
+  font-family: sans-serif;
 }
 
 /*=============================================================================
     Paragraphs
 =============================================================================*/
 p {
-	text-align: left;
-	font-size: 10pt;
-	line-height: 1.15;
+  text-align: left;
+  font-size: 10pt;
+  line-height: 1.15;
 }
 
 /*=============================================================================
@@ -32,254 +32,254 @@
 
 /* Code on paragraphs */
 p tt.computeroutput {
-	font-size: 9pt;
+  font-size: 9pt;
 }
 
 pre.synopsis {
-	font-size: 90%;
-	margin: 1pc 4% 0pc 4%;
-	padding: 0.5pc 0.5pc 0.5pc 0.5pc;
+  font-size: 90%;
+  margin: 1pc 4% 0pc 4%;
+  padding: 0.5pc 0.5pc 0.5pc 0.5pc;
 }
 
 .programlisting,.screen {
-	font-size: 9pt;
-	display: block;
-	margin: 1pc 4% 0pc 4%;
-	padding: 0.5pc 0.5pc 0.5pc 0.5pc;
+  font-size: 9pt;
+  display: block;
+  margin: 1pc 4% 0pc 4%;
+  padding: 0.5pc 0.5pc 0.5pc 0.5pc;
 }
 
 /* Program listings in tables don't get borders */
 td .programlisting,td .screen {
-	margin: 0pc 0pc 0pc 0pc;
-	padding: 0pc 0pc 0pc 0pc;
+  margin: 0pc 0pc 0pc 0pc;
+  padding: 0pc 0pc 0pc 0pc;
 }
 
 /*=============================================================================
     Headings
 =============================================================================*/
 h1,h2,h3,h4,h5,h6 {
-	text-align: left;
-	margin: 1em 0em 0.5em 0em;
-	font-weight: bold;
+  text-align: left;
+  margin: 1em 0em 0.5em 0em;
+  font-weight: bold;
 }
 
 h1 {
-	font: 140%
+  font: 140%
 }
 
 h2 {
-	font: bold 140%
+  font: bold 140%
 }
 
 h3 {
-	font: bold 130%
+  font: bold 130%
 }
 
 h4 {
-	font: bold 120%
+  font: bold 120%
 }
 
 h5 {
-	font: italic 110%
+  font: italic 110%
 }
 
 h6 {
-	font: italic 100%
+  font: italic 100%
 }
 
 /* Top page titles */
 title,h1.title,h2.title
     h3.title,h4.title,h5.title,h6.title,.refentrytitle {
-	font-weight: bold;
-	margin-bottom: 1pc;
+  font-weight: bold;
+  margin-bottom: 1pc;
 }
 
 h1.title {
-	font-size: 140%
+  font-size: 140%
 }
 
 h2.title {
-	font-size: 140%
+  font-size: 140%
 }
 
 h3.title {
-	font-size: 130%
+  font-size: 130%
 }
 
 h4.title {
-	font-size: 120%
+  font-size: 120%
 }
 
 h5.title {
-	font-size: 110%
+  font-size: 110%
 }
 
 h6.title {
-	font-size: 100%
+  font-size: 100%
 }
 
 .section h1 {
-	margin: 0em 0em 0.5em 0em;
-	font-size: 140%;
+  margin: 0em 0em 0.5em 0em;
+  font-size: 140%;
 }
 
 .section h2 {
-	font-size: 140%
+  font-size: 140%
 }
 
 .section h3 {
-	font-size: 130%
+  font-size: 130%
 }
 
 .section h4 {
-	font-size: 120%
+  font-size: 120%
 }
 
 .section h5 {
-	font-size: 110%
+  font-size: 110%
 }
 
 .section h6 {
-	font-size: 100%
+  font-size: 100%
 }
 
 /* Code on titles */
 h1 tt.computeroutput {
-	font-size: 140%
+  font-size: 140%
 }
 
 h2 tt.computeroutput {
-	font-size: 140%
+  font-size: 140%
 }
 
 h3 tt.computeroutput {
-	font-size: 130%
+  font-size: 130%
 }
 
 h4 tt.computeroutput {
-	font-size: 120%
+  font-size: 120%
 }
 
 h5 tt.computeroutput {
-	font-size: 110%
+  font-size: 110%
 }
 
 h6 tt.computeroutput {
-	font-size: 100%
+  font-size: 100%
 }
 
 /*=============================================================================
     Author
 =============================================================================*/
 h3.author {
-	font-size: 100%
+  font-size: 100%
 }
 
 /*=============================================================================
     Lists
 =============================================================================*/
 li {
-	font-size: 10pt;
-	line-height: 1.3;
+  font-size: 10pt;
+  line-height: 1.3;
 }
 
 /* Unordered lists */
 ul {
-	text-align: left;
+  text-align: left;
 }
 
 /* Ordered lists */
 ol {
-	text-align: left;
+  text-align: left;
 }
 
 /*=============================================================================
     Links
 =============================================================================*/
 a {
-	text-decoration: none; /* no underline */
+  text-decoration: none; /* no underline */
 }
 
 a:hover {
-	text-decoration: underline;
+  text-decoration: underline;
 }
 
 /*=============================================================================
     Spirit style navigation
 =============================================================================*/
 .spirit-nav {
-	text-align: right;
+  text-align: right;
 }
 
 .spirit-nav a {
-	color: white;
-	padding-left: 0.5em;
+  color: white;
+  padding-left: 0.5em;
 }
 
 .spirit-nav img {
-	border-width: 0px;
+  border-width: 0px;
 }
 
 /*=============================================================================
     Table of contents
 =============================================================================*/
 .toc {
-	margin: 1pc 4% 0pc 4%;
-	padding: 0.1pc 1pc 0.1pc 1pc;
-	font-size: 80%;
-	line-height: 1.15;
+  margin: 1pc 4% 0pc 4%;
+  padding: 0.1pc 1pc 0.1pc 1pc;
+  font-size: 80%;
+  line-height: 1.15;
 }
 
 .boost-toc {
-	float: right;
-	padding: 0.5pc;
+  float: right;
+  padding: 0.5pc;
 }
 
 /*=============================================================================
     Tables
 =============================================================================*/
 .table-title,div.table p.title {
-	margin-left: 4%;
-	padding-right: 0.5em;
-	padding-left: 0.5em;
+  margin-left: 4%;
+  padding-right: 0.5em;
+  padding-left: 0.5em;
 }
 
 .informaltable table,.table table {
-	width: 92%;
-	margin-left: 4%;
-	margin-right: 4%;
+  width: 92%;
+  margin-left: 4%;
+  margin-right: 4%;
 }
 
 div.informaltable table,div.table table {
-	padding: 4px;
+  padding: 4px;
 }
 
 /* Table Cells */
 div.informaltable table tr td,div.table table tr td {
-	padding: 0.5em;
-	text-align: left;
-	font-size: 9pt;
+  padding: 0.5em;
+  text-align: left;
+  font-size: 9pt;
 }
 
 div.informaltable table tr th,div.table table tr th {
-	padding: 0.5em 0.5em 0.5em 0.5em;
-	border: 1pt solid white;
-	font-size: 80%;
+  padding: 0.5em 0.5em 0.5em 0.5em;
+  border: 1pt solid white;
+  font-size: 80%;
 }
 
 /*=============================================================================
     Blurbs
 =============================================================================*/
 div.note,div.tip,div.important,div.caution,div.warning,p.blurb {
-	font-size: 9pt; /* A little bit smaller than the main text */
-	line-height: 1.2;
-	display: block;
-	margin: 1pc 4% 0pc 4%;
-	padding: 0.5pc 0.5pc 0.5pc 0.5pc;
+  font-size: 9pt; /* A little bit smaller than the main text */
+  line-height: 1.2;
+  display: block;
+  margin: 1pc 4% 0pc 4%;
+  padding: 0.5pc 0.5pc 0.5pc 0.5pc;
 }
 
 p.blurb img {
-	padding: 1pt;
+  padding: 1pt;
 }
 
 /*=============================================================================
@@ -288,31 +288,31 @@
 
 /* Make the terms in definition lists bold */
 div.variablelist dl dt,span.term {
-	font-weight: bold;
-	font-size: 10pt;
+  font-weight: bold;
+  font-size: 10pt;
 }
 
 div.variablelist table tbody tr td {
-	text-align: left;
-	vertical-align: top;
-	padding: 0em 2em 0em 0em;
-	font-size: 10pt;
-	margin: 0em 0em 0.5em 0em;
-	line-height: 1;
+  text-align: left;
+  vertical-align: top;
+  padding: 0em 2em 0em 0em;
+  font-size: 10pt;
+  margin: 0em 0em 0.5em 0em;
+  line-height: 1;
 }
 
 div.variablelist dl dt {
-	margin-bottom: 0.2em;
+  margin-bottom: 0.2em;
 }
 
 div.variablelist dl dd {
-	margin: 0em 0em 0.5em 2em;
-	font-size: 10pt;
+  margin: 0em 0em 0.5em 2em;
+  font-size: 10pt;
 }
 
 div.variablelist table tbody tr td p,div.variablelist dl dd p {
-	margin: 0em 0em 0.5em 0em;
-	line-height: 1;
+  margin: 0em 0em 0.5em 0em;
+  line-height: 1;
 }
 
 /*=============================================================================
@@ -321,226 +321,231 @@
 
 /* Title of books and articles in bibliographies */
 span.title {
-	font-style: italic;
+  font-style: italic;
 }
 
 span.underline {
-	text-decoration: underline;
+  text-decoration: underline;
 }
 
 span.strikethrough {
-	text-decoration: line-through;
+  text-decoration: line-through;
 }
 
 /* Copyright, Legal Notice */
 div div.legalnotice p {
-	text-align: left
+  text-align: left
 }
 
 /*=============================================================================
     Colors
 =============================================================================*/
 @media screen { /* Links */
-	a {
-		color: #005a9c;
-	}
-	a:visited {
-		color: #9c5a9c;
-	}
-	h1 a,h2 a,h3 a,h4 a,h5 a,h6 a,h1 a:hover,h2 a:hover,h3 a:hover,h4 a:hover,h5 a:hover,h6 a:hover,h1 a:visited,h2 a:visited,h3 a:visited,h4 a:visited,h5 a:visited,h6 a:visited
-		{
-		text-decoration: none; /* no underline */
-		color: #000000;
-	}
-
-	/* Syntax Highlighting */
-	.keyword {
-		color: #0000AA;
-	}
-	.identifier {
-		color: #000000;
-	}
-	.special {
-		color: #707070;
-	}
-	.preprocessor {
-		color: #402080;
-	}
-	.char {
-		color: teal;
-	}
-	.comment {
-		color: #800000;
-	}
-	.string {
-		color: teal;
-	}
-	.number {
-		color: teal;
-	}
-	.white_bkd {
-		background-color: #FFFFFF;
-	}
-	.dk_grey_bkd {
-		background-color: #999999;
-	}
-
-	/* Copyright, Legal Notice */
-	.copyright {
-		color: #666666;
-		font-size: small;
-	}
-	div div.legalnotice p {
-		color: #666666;
-	}
-
-	/* Program listing */
-	pre.synopsis {
-		border: 1px solid #DCDCDC;
-	}
-	.programlisting,.screen {
-		border: 1px solid #DCDCDC;
-	}
-	td .programlisting,td .screen {
-		border: 0px solid #DCDCDC;
-	}
-
-	/* Blurbs */
-	div.note,div.tip,div.important,div.caution,div.warning,p.blurb {
-		border: 1px solid #DCDCDC;
-	}
-
-	/* Table of contents */
-	.toc {
-		border: 1px solid #DCDCDC;
-	}
-
-	/* Tables */
-	div.informaltable table tr td,div.table table tr td {
-		border: 1px solid #DCDCDC;
-	}
-	div.informaltable table tr th,div.table table tr th {
-		background-color: #F0F0F0;
-		border: 1px solid #DCDCDC;
-	}
-
-	/* Misc */
-	span.highlight {
-		color: #00A000;
-	}
+  a {
+    color: #005a9c;
+  }
+  a:visited {
+    color: #9c5a9c;
+  }
+  h1 a,h2 a,h3 a,h4 a,h5 a,h6 a,h1 a:hover,h2 a:hover,h3 a:hover,h4 a:hover,h5 a:hover,h6 a:hover,h1 a:visited,h2 a:visited,h3 a:visited,h4 a:visited,h5 a:visited,h6 a:visited
+    {
+    text-decoration: none; /* no underline */
+    color: #000000;
+  }
+
+  /* Syntax Highlighting */
+  .keyword {
+    color: #0000AA;
+  }
+  .identifier {
+    color: #000000;
+  }
+  .special {
+    color: #707070;
+  }
+  .preprocessor {
+    color: #402080;
+  }
+  .char {
+    color: teal;
+  }
+  .comment {
+    color: #800000;
+  }
+  .string {
+    color: teal;
+  }
+  .number {
+    color: teal;
+  }
+  .white_bkd {
+    background-color: #FFFFFF;
+  }
+  .dk_grey_bkd {
+    background-color: #999999;
+  }
+
+  /* Copyright, Legal Notice */
+  .copyright {
+    color: #666666;
+    font-size: small;
+  }
+  div div.legalnotice p {
+    color: #666666;
+  }
+
+  /* Program listing */
+  pre.synopsis {
+    border: 1px solid #DCDCDC;
+  }
+  .programlisting,.screen {
+    border: 1px solid #DCDCDC;
+  }
+  td .programlisting,td .screen {
+    border: 0px solid #DCDCDC;
+  }
+
+  /* Blurbs */
+  div.note,div.tip,div.important,div.caution,div.warning,p.blurb {
+    border: 1px solid #DCDCDC;
+  }
+
+  /* Table of contents */
+  .toc {
+    border: 1px solid #DCDCDC;
+  }
+
+  /* Tables */
+  div.informaltable table tr td,div.table table tr td {
+    border: 1px solid #DCDCDC;
+  }
+  div.informaltable table tr th,div.table table tr th {
+    background-color: #F0F0F0;
+    border: 1px solid #DCDCDC;
+  }
+
+  /* Misc */
+  span.highlight {
+    color: #00A000;
+  }
 }
 
 @media print { /* Links */
-	a {
-		color: black;
-	}
-	a:visited {
-		color: black;
-	}
-	.spirit-nav {
-		display: none;
-	}
-
-	/* Program listing */
-	pre.synopsis {
-		border: 1px solid gray;
-	}
-	.programlisting,.screen {
-		border: 1px solid gray;
-	}
-	td .programlisting,td .screen {
-		border: 0px solid #DCDCDC;
-	}
-
-	/* Table of contents */
-	.toc {
-		border: 1px solid gray;
-	}
-	.informaltable table,.table table {
-		border: 1px solid gray;
-		border-collapse: collapse;
-	}
-
-	/* Tables */
-	div.informaltable table tr td,div.table table tr td {
-		border: 1px solid gray;
-	}
-	div.informaltable table tr th,div.table table tr th {
-		border: 1px solid gray;
-	}
-
-	/* Misc */
-	span.highlight {
-		font-weight: bold;
-	}
+  a {
+    color: black;
+  }
+  a:visited {
+    color: black;
+  }
+  .spirit-nav {
+    display: none;
+  }
+
+  /* Program listing */
+  pre.synopsis {
+    border: 1px solid gray;
+  }
+  .programlisting,.screen {
+    border: 1px solid gray;
+  }
+  td .programlisting,td .screen {
+    border: 0px solid #DCDCDC;
+  }
+
+  /* Table of contents */
+  .toc {
+    border: 1px solid gray;
+  }
+  .informaltable table,.table table {
+    border: 1px solid gray;
+    border-collapse: collapse;
+  }
+
+  /* Tables */
+  div.informaltable table tr td,div.table table tr td {
+    border: 1px solid gray;
+  }
+  div.informaltable table tr th,div.table table tr th {
+    border: 1px solid gray;
+  }
+
+  /* Misc */
+  span.highlight {
+    font-weight: bold;
+  }
 }
 
 .tree_proposal>.section {
-	font-family: serif;
+  font-family: serif;
 }
 
 .tree_proposal>.section {
-	margin: 1em;
-	padding: 1em 0em 1em 1.5em;
-	border-top: 1px solid #888888;
-	border-bottom: 1px solid #888888;
+  margin: 1em;
+  padding: 1em 0em 1em 1.5em;
+  border-top: 1px solid #888888;
+  border-bottom: 1px solid #888888;
+}
+
+.tree_proposal .tr_section_label {
+  float: right;
 }
 
 .tree_proposal ol {
-	margin: 0em;
-	padding: 0em;
+  margin: 0em;
+  padding: 0em;
 }
 
 .tree_proposal ol li {
-	margin: 0em 0em 1em 0em;
-	padding: 0em 0em 0em 0em;
+  margin: 0em 0em 1em 0em;
+  padding: 0em 0em 0em 0em;
 }
 
 .tree_proposal table {
-	border: 1px solid;
-	margin: 0em auto 0em auto;
-	border-spacing: 0em;
-	width: inherit;
-	padding: 0em !important;
+  border: 1px solid;
+  margin: 0em auto 0em auto;
+  border-spacing: 0em;
+  width: inherit;
+  padding: 0em !important;
+  border-collapse: separate;
 }
 
 .tree_proposal .table .title,
 .tree_proposal .table-title {
-	font-weight: bold;
-	margin: 1em auto 1em auto;
-	text-align: center;
-	caption-side: top;
+  font-weight: bold;
+  margin: 1em auto 1em auto;
+  text-align: center;
+  caption-side: top;
 }
 
 .tree_proposal table th {
-    border: none !important;
-    border-bottom: 1px solid !important;
-    padding: 0.25em 0.5em 0em 0.5em;
-    background: transparent !important;
+  border: none !important;
+  border-bottom: 1px solid !important;
+  padding: 0.25em 0.5em 0em 0.5em !important;
+  background: transparent !important;
 }
 .tree_proposal table th p {
-    text-align: center !important;
+  text-align: center !important;
 }
 
 .tree_proposal table td {
-	border: none !important;
-	border-top: 1px solid !important;
-	vertical-align: top;
-	padding: 0.25em 0.5em 0em 0.5em;
-    background: transparent !important;
+  border: none !important;
+  border-top: 1px solid !important;
+  vertical-align: top !important;
+  padding: 0.25em 0.5em 0em 0.5em !important;
+  background: transparent !important;
 }
 
 .tree_proposal .docref {
-	float: right;
+  float: right;
 }
 
 .tree_proposal .docref dt {
-	float: left;
-	font-style: italic;
+  float: left;
+  font-style: italic;
 }
 
 .tree_proposal .docref dd {
-	margin-left: 8em;
+  margin-left: 8em;
 }
 
 .tree_proposal h1,
@@ -549,52 +554,59 @@
 .tree_proposal h4,
 .tree_proposal h5,
 .tree_proposal h6 {
-	clear: both;
+  clear: both;
+  font-style: normal;
 }
 
 .tree_proposal .byline {
-	text-align: center;
+  text-align: center;
 }
 
 .tree_proposal .note {
-    background: #EEEEEE;
-    border: 1px solid #AAAAAA;
-    padding: 0.25em;
+  background: #EEEEEE;
+  border: 1px solid #AAAAAA;
+  padding: 0.25em;
 }
 .tree_proposal .note .title {
-	display: none;
+  display: none;
 }
 .tree_proposal .note p {
-	margin: 0.25em 0em 0.25em 0em;
+  margin: 0.25em 0em 0.25em 0em;
 }
 .tree_proposal .note table {
-    border: none;
-    margin: 0em;
-    padding: 0em;
+  border: none;
+  margin: 0em;
+  padding: 0em;
 }
 .tree_proposal .note table td,
 .tree_proposal .note table th {
-    border: none !important;
+  border: none !important;
 }
 
 .tree_proposal .add {
-	text-decoration: overline;
+  text-decoration: overline;
 }
 
 .tree_proposal h2 {
-	font-size: 150%
+  font-size: 150%
 }
 
 .tree_proposal h3,
 .tree_proposal h4,
 .tree_proposal h5,
 .tree_proposal h6 {
-	font-size: 100%;
+  font-size: 100%;
 }
 
 .tree_proposal .section-id {
-	float: right;
-	position: relative;
-	top: -1.25em;
+  float: right;
+  position: relative;
+  top: -1.25em;
+}
+.tree_proposal .programlisting {
+  border: none !important;
+  margin-left: 0em !important;
+  margin-right: 0em !important;
+  padding: 0em !important;
 }
 </style>
\ No newline at end of file

Modified: sandbox/tree/libs/tree/proposal/proposal.qbk
==============================================================================
--- sandbox/tree/libs/tree/proposal/proposal.qbk	(original)
+++ sandbox/tree/libs/tree/proposal/proposal.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -1,5 +1,6 @@
 [/
- /  Copyright (c) 2006-2009, Bernhard Reiter and René Rivera
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2012, René Rivera
  /
  /  Distributed under the Boost Software License, Version 1.0.
  /  (See accompanying file LICENSE_1_0.txt or copy at
@@ -13,336 +14,36 @@
 
 [/ TODO: The generated docs should contain boostinspect:nolicense ]
 
-[library Hierarchical Data Structures and Related Concepts for the C++ Standard Library
-    [quickbook 1.6]
+[article Hierarchical Data Structures and Related Concepts for the C++ Standard Library
+    [quickbook 1.7]
     [authors [Reiter, Bernhard], [Rivera, René]]
-    [copyright 2006-2009 Bernhard Reiter and René Rivera]
+    [copyright 2006-2009 Bernhard Reiter]
+    [copyright 2006-2012 René Rivera]
     [purpose Hierarchical Data Structures and Related Concepts for the C++ Standard Library]
     [license
-        
         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])
-        
     ]
     [id tree]
 ]
 
 [def (tm) '''&#8482;''']
 [def __code_rep__ [@http://svn.boost.org/svn/boost/sandbox/tree]]
-[template tr[id] \[tr.[id]\]]
+[def __tech_report_x__ Technical Report 2]
+[def __trx__ tr2]
+[template label[id] [role tr_section_label \[[id]\]]]
+[def __nbsp__ '''&nbsp;''']
 
-[section:preamble Hierarchical Data Structures and Related Concepts for the
-C++ Standard Library]
-
-[*Bernhard Reiter and René Rivera]
-
-[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 Code(tm) 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 __code_rep__.
-
-[endsect]
-
-[endsect] [/Motivation and Scope]
-
-[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++11]
-
-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] [/Impact on the Standard]
-
-[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?]
-
-[heading 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.
-
-[heading 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]
-
-[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] [/Important Design Decisions]
-
-[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] [/Future Directions]
-
-[endsect] [/Title]
+[include preamble.qbk]
 
 [section:proposal Proposed Text for Technical Report 2]
 
 [note Notes that are not part of the proposed text appear in gray boxes.]
 
-[section:tr_containers Containers library [tr containers]]
-
-[section:tr_hierarchy Hierarchy containers [tr hierarchy]]
-
-[section:tr_hierarchy_req Hierarchy container requirements [tr hierarchy.req]]
-
-# A hierarchy is an object that stores a finite set of objects, all of the same type,
-  in a hierarchical manner. Hierarchies introduce a cursor concept for navigation
-  instead of iterators. The library provides two kinds of native hierarchies:
-  =binary_tree=, and =nary_tree=, along with hierarchy-yielding hierarchy adaptors
-  =forest_tree=, and =multiway_tree=.
-
-# Hierarchy containers conform to the requirements of Containers (\[lib.container.requirements\]),
-  except that the expressions in Table 1 are not required to be valid, where =a= and =b=
-  denote values of a type =X=, and =X= is a hierarchy container class:
-  
-  [table Container requirements that are not required for hierarchy containers
-    [[ unsupported expression ]]
-    [[ [^X::iterator] ]]
-    [[ [^X::const_iterator] ]]
-    [[ [^X::reverse_iterator] ]]
-    [[ [^X::const_reverse_iterator] ]]
-    [[ [^a.begin()] ]]
-    [[ [^a.end()] ]]
-    [[ [^a.rbegin()] ]]
-    [[ [^a.rend()] ]]
-    [[ [^a < b] ]]
-    [[ [^a > b] ]]
-    [[ [^a <= b] ]]
-    [[ [^a >= b] ]]
-  ]
-
-# Non-constant complexity requirements in this clause are stated in one of a
-  number of possible different ways: unless specified otherwise, they are
-  expressed in terms of the number of operations =n=, which stands for the
-  total number of elements in the hierarchy; in some cases, however, they
-  are stated in terms of another value.
-
-# In Table 2 =X= denotes a hierarchy class containing objects of type =T= and =a= denotes a value of type =X=.
-
-  [table Hierarchy requirements (in addition to container)
-    [[ expression ][ return type ][ assertion/note[br]pre/post-condition ][ complexity ]]
-    [   [ [^X::cursor] ]
-        [ cursor type pointing to =T= ]
-        [ any cursor category ]
-        [ compile time ]]
-    [   [ X::const_cursor ]
-        [ cursor type pointing to =const T= ]
-        [ any cursor category ]
-        [ compile time ]]
-    [   [ [^a.root()] ]
-        [ =iterator= for mutable =a=;[br]
-          =const_iterator= for constant =a= ]
-        []
-        [ constant ]]
-    [   [ [^a.croot()] ]
-        [ =const_iterator= ]
-        []
-        [ constant ]]
-    [   [ [^typename X::template rebind<U>::other] ]
-        [ =Y= ]
-        [ For all =U= (including =T=), [^Y::template rebind<T>::other] is =X=. ]
-        [ compile time ]]
-  ]
-  
-  Notes: Those entries marked "(Note A)" should have at worst linear complexity.
-  See the individual hierarchy containers for specific complexity.
-
-[endsect] [/tr_hierarchy_req]
-
-[endsect] [/tr_hierarchy]
-
-[endsect] [/Containers library]
+[include tr-containers.qbk]
 
-[endsect] [/TR2]
+[endsect] [/proposal]
 
 [section:references References]
 

Added: sandbox/tree/libs/tree/proposal/single/proposal.docbook
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/single/proposal.docbook	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,1441 @@
+<?xml version="1.0"?>
+<!DOCTYPE article PUBLIC "-//OASIS//DTD DocBook XML V4.2//EN" "http://www.oasis-open.org/docbook/xml/4.2/docbookx.dtd">
+<article xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" id="tree" rev:last-revision="$Date: 2012/01/15 06:05:46 $">
+  <title>Hierarchical Data Structures and Related Concepts for the C++ Standard Library</title>
+  <articleinfo>
+    <authorgroup>
+    <author>
+      <firstname>Bernhard</firstname> <surname>Reiter</surname>
+    </author>
+    <author>
+      <firstname>René</firstname> <surname>Rivera</surname>
+    </author>
+    </authorgroup>
+    <copyright>
+      <year>2006</year> <year>2007</year> <year>2008</year> <year>2009</year> <holder>Bernhard
+      Reiter</holder>
+    </copyright>
+    <copyright>
+      <year>2006</year> <year>2007</year> <year>2008</year> <year>2009</year> <year>2010</year>
+      <year>2011</year> <year>2012</year> <holder>René Rivera</holder>
+    </copyright>
+    <legalnotice id="tree.legal">
+      <para>
+        Distributed under the Boost Software License, Version 1.0. (See accompanying
+        file LICENSE_1_0.txt or copy at <ulink url="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt>)
+      </para>
+    </legalnotice>
+    <articlepurpose>
+      Hierarchical Data Structures and Related Concepts for the C++ Standard Library
+    </articlepurpose>
+  </articleinfo>
+  <section id="tree.preamble">
+    <title><link linkend="tree.preamble">Hierarchical Data Structures and Related
+    Concepts for the C++ Standard Library</link></title>
+    <para>
+      <emphasis role="bold">Bernhard Reiter and René Rivera</emphasis>
+    </para>
+    <variablelist>
+      <title/>
+      <varlistentry>
+        <term>Document No.</term>
+        <listitem>
+          <para>
+            WG21/N????=J16/??-????
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>Supercedes</term>
+        <listitem>
+          <para>
+            WG21/N2101=J16/06-0171
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>Date</term>
+        <listitem>
+          <para>
+            2012-Jan-15
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>Project</term>
+        <listitem>
+          <para>
+            Programming Language C++
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>Reply to</term>
+        <listitem>
+          <para>
+            René Rivera &lt;<ulink url="mailto:rrivera_at_[hidden]">rrivera_at_[hidden]</ulink>&gt;
+          </para>
+        </listitem>
+      </varlistentry>
+    </variablelist>
+    <section id="tree.preamble.introduction">
+      <title><link linkend="tree.preamble.introduction">Introduction</link></title>
+      <para>
+        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.
+      </para>
+      <para>
+        The library strives to cover many of the relevant aspects within the vast
+        field linked to the notion of trees in computer science.
+      </para>
+    </section>
+    <section id="tree.preamble.motivation_and_scope">
+      <title><link linkend="tree.preamble.motivation_and_scope">Motivation and Scope</link></title>
+      <section id="tree.preamble.motivation_and_scope.why_is_this_important">
+        <title><link linkend="tree.preamble.motivation_and_scope.why_is_this_important">Why
+        is this important?</link></title>
+        <para>
+          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.
+        </para>
+        <para>
+          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 <emphasis>rooted ordered connected acyclic graphs</emphasis>.
+        </para>
+      </section>
+      <section id="tree.preamble.motivation_and_scope.what_kinds_of_problems_does_it_a">
+        <title><link linkend="tree.preamble.motivation_and_scope.what_kinds_of_problems_does_it_a">What
+        kinds of problems does it address, and what kinds of programmers is it intended
+        to support?</link></title>
+        <para>
+          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.
+        </para>
+      </section>
+      <section id="tree.preamble.motivation_and_scope.is_it_based_on_existing_practice">
+        <title><link linkend="tree.preamble.motivation_and_scope.is_it_based_on_existing_practice">Is
+        it based on existing practice?</link></title>
+        <para>
+          No; this proposal originates in an effort to create a generic tree container
+          component for <ulink url="http://www.boost.org">Boost</ulink> in the course
+          of <ulink url="http://code.google.com/soc/2006/boost/appinfo.html?csaid=E17EA7C7C537C131">Google
+          Summer of Codeâ„¢ 2006</ulink>, 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.
+        </para>
+      </section>
+      <section id="tree.preamble.motivation_and_scope.is_there_a_reference_implementat">
+        <title><link linkend="tree.preamble.motivation_and_scope.is_there_a_reference_implementat">Is
+        there a reference implementation?</link></title>
+        <para>
+          Yes; the current state is available from svn from <ulink url="http://svn.boost.org/svn/boost/sandbox/tree">http://svn.boost.org/svn/boost/sandbox/tree>.
+        </para>
+      </section>
+    </section>
+    <section id="tree.preamble.impact_on_the_standard">
+      <title><link linkend="tree.preamble.impact_on_the_standard">Impact on the Standard</link></title>
+      <section id="tree.preamble.impact_on_the_standard.what_does_it_depend_on_and_what_">
+        <title><link linkend="tree.preamble.impact_on_the_standard.what_does_it_depend_on_and_what_">What
+        does it depend on, and what depends on it?</link></title>
+        <para>
+          It depends on some standard library components, such as <literal moreinfo="none">std::allocator</literal>
+          which is used as the default allocator template argument at some points.
+          Concepts like allocators or iterators are reused and in some cases adapted.
+        </para>
+      </section>
+      <section id="tree.preamble.impact_on_the_standard.is_it_a_pure_extension_or_does_i">
+        <title><link linkend="tree.preamble.impact_on_the_standard.is_it_a_pure_extension_or_does_i">Is
+        it a pure extension, or does it require changes to standard components?</link></title>
+        <para>
+          Most of the proposed library is a pure extension.
+        </para>
+        <para>
+          Some extensions <literal moreinfo="none">&lt;algorithm&gt;</literal> and some extensions
+          to <literal moreinfo="none">&lt;iterator&gt;</literal> are proposed.
+        </para>
+        <para>
+          Additionally, while not proposed herein, it has sometimes been suggested
+          to add a template parameter to the STL associative containers <literal moreinfo="none">set</literal>,
+          <literal moreinfo="none">multiset</literal>, <literal moreinfo="none">map</literal>, and <literal moreinfo="none">multimap</literal>
+          (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 <literal moreinfo="none">unordered</literal> 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 <literal moreinfo="none">unordered</literal>
+          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
+          <literal moreinfo="none">unordered</literal> containers.
+        </para>
+      </section>
+      <section id="tree.preamble.impact_on_the_standard.can_it_be_implemented_using_toda">
+        <title><link linkend="tree.preamble.impact_on_the_standard.can_it_be_implemented_using_toda">Can
+        it be implemented using today's compilers, or does it require language features
+        that will only be available as part of C++11</link></title>
+        <para>
+          It can be, and partly has been, implemented with today's compilers.
+        </para>
+        <para>
+          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 <ulink url="#tr.hierarchy.req">[tr.hierarchy.req]</ulink>
+          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 <ulink url="http://boost.org/libs/range/doc/range.html">Boost
+          Range concept</ulink> (<ulink url="http://boost.org/libs/range/doc/range.html">http://boost.org/libs/range/doc/range.html>)
+          externally to the Standard.
+        </para>
+      </section>
+    </section>
+    <section id="tree.preamble.important_design_decisions">
+      <title><link linkend="tree.preamble.important_design_decisions">Important Design
+      Decisions</link></title>
+      <section id="tree.preamble.important_design_decisions.why_did_you_choose_the_specific_">
+        <title><link linkend="tree.preamble.important_design_decisions.why_did_you_choose_the_specific_">Why
+        did you choose the specific design that you did?</link></title>
+        <para>
+          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.
+        </para>
+      </section>
+      <section id="tree.preamble.important_design_decisions.what_alternatives_did_you_consid">
+        <title><link linkend="tree.preamble.important_design_decisions.what_alternatives_did_you_consid">What
+        alternatives did you consider, and what are the tradeoffs?</link></title>
+        <bridgehead renderas="sect5" id="tree.preamble.important_design_decisions.what_alternatives_did_you_consid.h0">
+          <phrase id="tree.preamble.important_design_decisions.what_alternatives_did_you_consid.trees_of_trees"/><link linkend="tree.preamble.important_design_decisions.what_alternatives_did_you_consid.trees_of_trees">Trees
+          of trees</link>
+        </bridgehead>
+        <para>
+          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 linkend="haas">[haas]</link>). 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.
+        </para>
+        <bridgehead renderas="sect5" id="tree.preamble.important_design_decisions.what_alternatives_did_you_consid.h1">
+          <phrase id="tree.preamble.important_design_decisions.what_alternatives_did_you_consid.augmentors_balancers_as_policies"/><link linkend="tree.preamble.important_design_decisions.what_alternatives_did_you_consid.augmentors_balancers_as_policies">Augmentors/balancers
+          as policies</link>
+        </bridgehead>
+        <para>
+          Inspired by <link linkend="austern">[austern]</link> and <link linkend="dreizin">[dreizin]</link>,
+          the original approach undertaken when working on the reference implementation
+          was to pass policy template arguments to template class <literal moreinfo="none">binary_tree</literal>.
+          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.
+        </para>
+      </section>
+      <section id="tree.preamble.important_design_decisions.what_are_the_consequences_of_you">
+        <title><link linkend="tree.preamble.important_design_decisions.what_are_the_consequences_of_you">What
+        are the consequences of your choices, for users and implementors?</link></title>
+        <para>
+          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.
+        </para>
+        <para>
+          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 linkend="austern">[austern]</link>),
+          which may partly restrict implementors to one "proper" way of
+          doing things.
+        </para>
+      </section>
+      <section id="tree.preamble.important_design_decisions.what_decisions_are_left_up_to_im">
+        <title><link linkend="tree.preamble.important_design_decisions.what_decisions_are_left_up_to_im">What
+        decisions are left up to implementors?</link></title>
+        <para>
+          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).
+        </para>
+      </section>
+      <section id="tree.preamble.important_design_decisions.if_there_are_any_similar_librari">
+        <title><link linkend="tree.preamble.important_design_decisions.if_there_are_any_similar_librari">If
+        there are any similar libraries in use, how do their design decisions compare
+        to yours?</link></title>
+        <para>
+          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 linkend="dreizin">[dreizin]</link>, <link linkend="ekman">[ekman]</link>
+          and <link linkend="karas">[karas]</link>; 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 linkend="gottschlich">[gottschlich]</link>, <link linkend="haas">[haas]</link>,
+          <link linkend="parent">[parent]</link> and <link linkend="peeters">[peeters]</link>),
+          but rarely both fields of application.
+        </para>
+        <para>
+          Approaches as found in <link linkend="austern">[austern]</link> or <link linkend="mirwaisi">[mirwaisi]</link> 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.
+        </para>
+        <para>
+          The <ulink url="http://www.boost.org/libs/graph/">BGL</ulink>, 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.
+        </para>
+      </section>
+    </section>
+    <section id="tree.preamble.future_directions">
+      <title><link linkend="tree.preamble.future_directions">Future Directions</link></title>
+      <para>
+        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.
+      </para>
+    </section>
+  </section>
+  <section id="tree.proposal">
+    <title><link linkend="tree.proposal">Proposed Text for Technical Report 2</link></title>
+    <note>
+      <para>
+        Notes that are not part of the proposed text appear in gray boxes.
+      </para>
+    </note>
+    <section id="tree.proposal.containers">
+      <title><link linkend="tree.proposal.containers">Containers library <phrase role="tr_section_label">[tr.containers]</phrase></link></title>
+      <section id="tree.proposal.containers.hierarchy">
+        <title><link linkend="tree.proposal.containers.hierarchy">Hierarchy containers
+        <phrase role="tr_section_label">[tr.hierarchy]</phrase></link></title>
+        <section id="tree.proposal.containers.hierarchy.req">
+          <title><link linkend="tree.proposal.containers.hierarchy.req">Hierarchy
+          containers requirements <phrase role="tr_section_label">[tr.hierarchy.req]</phrase></link></title>
+          <orderedlist inheritnum="ignore" continuation="restarts">
+            <listitem>
+              <para>
+                A hierarchy is an object that stores a finite set of objects, all
+                of the same type, in a hierarchical manner. Hierarchies introduce
+                a cursor concept for navigation instead of iterators. The library
+                provides two kinds of native hierarchies: <literal moreinfo="none">binary_tree</literal>,
+                and <literal moreinfo="none">nary_tree</literal>, along with hierarchy-yielding hierarchy
+                adaptors <literal moreinfo="none">forest_tree</literal>, and <literal moreinfo="none">multiway_tree</literal>.
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                Hierarchy containers conform to the requirements of Containers ([lib.container.requirements]),
+                except that the expressions in Table 1 are not required to be valid,
+                where a and b denote values of a type X, and X is a hierarchy container
+                class:
+              </para>
+              <table frame="all" id="tree.proposal.containers.hierarchy.req.table1">
+                <title>Container requirements that are not required for hierarchy
+                containers</title>
+                <tgroup cols="1">
+                  <thead>
+                    <row>
+                      <entry>
+                        <para>
+                          unsupported expression
+                        </para>
+                      </entry>
+                    </row>
+                  </thead>
+                  <tbody>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">X::iterator</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">X::const_iterator</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">X::reverse_iterator</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">X::const_reverse_iterator</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.begin()</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.end()</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.rbegin()</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.rend()</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a &lt; b</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a &gt; b</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a &lt;= b</literal>
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a &gt;= b</literal>
+                        </para>
+                      </entry>
+                    </row>
+                  </tbody>
+                </tgroup>
+              </table>
+            </listitem>
+            <listitem>
+              <para>
+                Non-constant complexity requirements in this clause are stated in
+                one of a number of possible different ways: unless specified otherwise,
+                they are expressed in terms of the number of operations <literal moreinfo="none">n</literal>,
+                which stands for the total number of elements in the hierarchy; in
+                some cases, however, they are stated in terms of another value.
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                In Table 2: <literal moreinfo="none">X</literal> denotes a hierarchy class containing
+                objects of type <literal moreinfo="none">T</literal> and <literal moreinfo="none">a</literal> denotes
+                a value of type <literal moreinfo="none">X</literal>.
+              </para>
+              <table frame="all" id="tree.proposal.containers.hierarchy.req.table2">
+                <title>Hierarchy requirements (in addition to container)</title>
+                <tgroup cols="4">
+                  <thead>
+                    <row>
+                      <entry>
+                        <para>
+                          expression
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          return type
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          assertion/note<sbr/> pre/post-condition
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          complexity
+                        </para>
+                      </entry>
+                    </row>
+                  </thead>
+                  <tbody>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">X::cursor</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          cursor type pointing to <literal moreinfo="none">T</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          any cursor category
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          compile time
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">X::const_cursor</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          cursor type pointing to <literal moreinfo="none">const T</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          any cursor category
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          compile time
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.root()</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">iterator</literal> for mutable <literal moreinfo="none">a</literal>;<sbr/>
+                          <literal moreinfo="none">const_iterator</literal> for constant <literal moreinfo="none">a</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          Â 
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          constant
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.croot()</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">const_iterator</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          Â 
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          constant
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.shoot()</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">iterator</literal> for mutable <literal moreinfo="none">a</literal>;<sbr/>
+                          <literal moreinfo="none">const_iterator</literal> for constant <literal moreinfo="none">a</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          Â 
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          (Note A)
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.cshoot()</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">const_iterator</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          Â 
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          (Note A)
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">typename X::template rebind&lt;U&gt;::other</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">Y</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          For all <literal moreinfo="none">U</literal> (including <literal moreinfo="none">T</literal>),
+                          <literal moreinfo="none">Y::template rebind&lt;T&gt;::other</literal> is
+                          <literal moreinfo="none">X</literal>.
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          compile time
+                        </para>
+                      </entry>
+                    </row>
+                  </tbody>
+                </tgroup>
+              </table>
+              <para>
+                Notes: Those entries marked "(Note A)" should have at worst
+                linear complexity. See the individual hierarchy containers for specific
+                complexity.
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                <literal moreinfo="none">root()</literal> and <literal moreinfo="none">croot()</literal> return a
+                cursor which is the on-top value for the hierarchy. <literal moreinfo="none">shoot()</literal>
+                and <literal moreinfo="none">cshoot()</literal> return a cursor which is the past-the-end
+                value that is found one past the hierarchy's rightmost element. If
+                the hierarchy is empty, then <literal moreinfo="none">root() == shoot();</literal>
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                Copy constructors for all hierarchy types defined in this clause
+                copy the allocator argument from their respective first parameters.
+                All other constructors for these hierarchy types take an <literal moreinfo="none">Allocator&amp;</literal>
+                argument (20.1.5). A copy of this argument is used for any memory
+                allocation performed, by these constructors and by all member functions,
+                during the lifetime of each hierarchy object. In all hierarchy types
+                defined in this clause, the member <literal moreinfo="none">get_allocator()</literal>
+                returns a copy of the Allocator object used to construct the hierarchy.
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                The member class template <literal moreinfo="none">rebind</literal> in the table
+                above is effectively a typedef template: if the name <literal moreinfo="none">Hierarchy</literal>
+                is bound to <literal moreinfo="none">SomeHierarchy&lt;T&gt;</literal>, then <literal moreinfo="none">Hierarchy::rebind&lt;U&gt;::other</literal>
+                is the same type as <literal moreinfo="none">SomeHierarchy&lt;U&gt;</literal>. Additionally,
+                because of the related assertion, given <literal moreinfo="none">SomeHierarchy&lt;T,R0,...,Rn&gt;</literal>
+                for all template arguments present is bound to the name <literal moreinfo="none">Hierarchy</literal>,
+                then <literal moreinfo="none">Hierarchy::rebind&lt;U&gt;::other</literal> is the
+                same type as <literal moreinfo="none">SomeHierarchy&lt;U,S0,...,Sn&gt;</literal>
+                such that the types <literal moreinfo="none">S0</literal> through <literal moreinfo="none">Sn</literal>
+                are the same as <literal moreinfo="none">R0</literal> through <literal moreinfo="none">Rn</literal>,
+                respectively, when <literal moreinfo="none">U</literal> is the same type as <literal moreinfo="none">T</literal>.
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                A hierarchy satisfying the requirements shown in Table 3 is called
+                a <emphasis>mutable hierarchy</emphasis>. In Table 3, <literal moreinfo="none">X</literal>
+                denotes a hierarchy class, <literal moreinfo="none">a</literal> denotes a value of
+                <literal moreinfo="none">X</literal>, <literal moreinfo="none">c</literal> denotes a valid, non-on-top
+                cursor satisfying input cursor requirements, <literal moreinfo="none">p</literal>
+                denotes a valid, non-on-top cursor to <literal moreinfo="none">a</literal>, <literal moreinfo="none">q</literal>
+                denotes a valid, dereferenceable cursor to <literal moreinfo="none">a</literal>,
+                and <literal moreinfo="none">t</literal> denotes a value of <literal moreinfo="none">X::value_type</literal>.
+              </para>
+              <table frame="all" id="tree.proposal.containers.hierarchy.req.table3">
+                <title>Mutable hierarchy requirements</title>
+                <tgroup cols="4">
+                  <thead>
+                    <row>
+                      <entry>
+                        <para>
+                          expression
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          return type
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          assertion/note<sbr/> pre/post-condition
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          complexity
+                        </para>
+                      </entry>
+                    </row>
+                  </thead>
+                  <tbody>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.insert(p,t)</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">cursor</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          inserts a copy of <literal moreinfo="none">t</literal> before <literal moreinfo="none">p</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          (Note A)
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.clear(q)</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">void</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          deletes the subtree of <literal moreinfo="none">q</literal> and the element
+                          <literal moreinfo="none">q</literal> points to.<sbr/> pre: <literal moreinfo="none">q</literal>
+                          is dereferenceable.
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          Should be at worst linear in the the number of elements
+                          in the subtree of <literal moreinfo="none">q</literal> plus the distance
+                          to <literal moreinfo="none">q</literal>'s parent's <literal moreinfo="none">end()</literal>.
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.clear()</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">void</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">while (a.size()) clear(a.begin());</literal><sbr/>
+                          post: <literal moreinfo="none">a.size() == 0</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          (Note A)
+                        </para>
+                      </entry>
+                    </row>
+                  </tbody>
+                </tgroup>
+              </table>
+              <para>
+                Notes: Those entries marked "(Note A)" should have at worst
+                linear complexity. See the individual hierarchy containers for specific
+                complexity.
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                The cursor returned from <literal moreinfo="none">a.insert(p,t)</literal> points
+                to the copy of <literal moreinfo="none">t</literal> inserted into <literal moreinfo="none">a</literal>.
+                Its parent cursor is the same as that of <literal moreinfo="none">p</literal>.
+              </para>
+            </listitem>
+          </orderedlist>
+        </section>
+        <section id="tree.proposal.containers.hierarchy.plain">
+          <title><link linkend="tree.proposal.containers.hierarchy.plain">Plain hierarchies
+          <phrase role="tr_section_label">[tr.hierarchy.plain]</phrase></link></title>
+          <orderedlist inheritnum="ignore" continuation="restarts">
+            <listitem>
+              <para>
+                A hierarchy is called plain hierarchy if its cursor and const_cursor
+                types satisfy the requirements of a plain cursor.
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                The library provides one native kind of plain hierarchy, nary_tree,
+                and a hierarchy adaptor that in turn yields a plain hierarchy, forest_tree.
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                For a mutable plain hierarchy, the following expressions as shown
+                in Table 4, is additionally required to be valid:
+              </para>
+              <table frame="all" id="tree.proposal.containers.hierarchy.plain.table4">
+                <title>Plain hierarchy requirements</title>
+                <tgroup cols="4">
+                  <thead>
+                    <row>
+                      <entry>
+                        <para>
+                          expression
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          return type
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          assertion/note<sbr/> pre/post-condition
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          complexity
+                        </para>
+                      </entry>
+                    </row>
+                  </thead>
+                  <tbody>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.insert(p,c)</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">cursor</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          inserts a copy of the subtree of <literal moreinfo="none">c</literal> before
+                          <literal moreinfo="none">p</literal>.<sbr/> pre: <literal moreinfo="none">c</literal> is
+                          dereferenceable.
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          Should be at worst linear in the the number of elements
+                          in the subtree of <literal moreinfo="none">c</literal> plus the distance
+                          to <literal moreinfo="none">p</literal>'s parent's <literal moreinfo="none">end()</literal>.
+                        </para>
+                      </entry>
+                    </row>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.insert_above(p,t)</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">cursor</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          inserts a copy of <literal moreinfo="none">t</literal> as child of <literal moreinfo="none">p</literal>'s
+                          parent and new parent of <literal moreinfo="none">p</literal> and its siblings.<sbr/>
+                          pre: <literal moreinfo="none">c</literal> is dereferenceable.
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          Linear in the the number <literal moreinfo="none">p</literal>'s siblings.
+                        </para>
+                      </entry>
+                    </row>
+                  </tbody>
+                </tgroup>
+              </table>
+            </listitem>
+            <listitem>
+              <para>
+                The cursor returned from <literal moreinfo="none">a.insert(p,c)</literal> points
+                to the copy of the element that <literal moreinfo="none">c</literal> points to, inserted
+                into <literal moreinfo="none">a</literal>. Its parent cursor is the same as that
+                of <literal moreinfo="none">p</literal>.
+              </para>
+            </listitem>
+          </orderedlist>
+        </section>
+        <section id="tree.proposal.containers.hierarchy.multiway">
+          <title><link linkend="tree.proposal.containers.hierarchy.multiway">Multiway
+          hierarchies <phrase role="tr_section_label">[tr.hierarchy.multiway]</phrase></link></title>
+          <orderedlist inheritnum="ignore" continuation="restarts">
+            <listitem>
+              <para>
+                A hierarchy is called multiway hierarchy if its <literal moreinfo="none">cursor</literal>
+                and <literal moreinfo="none">const_cursor</literal> types satisfy the requirements
+                of a multiway cursor.
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                The library provides one native kind of multiway hierarchy, <literal moreinfo="none">binary_tree</literal>,
+                and a hierarchy adaptor that in turn yields a multiway hierarchy,
+                <literal moreinfo="none">multiway_tree</literal>.
+              </para>
+            </listitem>
+            <listitem>
+              <para>
+                For a mutable multiway hierarchy, the semantics of some expressions
+                from Table 3 are modified as shown in Table 5.
+              </para>
+              <table frame="all" id="tree.proposal.containers.hierarchy.multiway.table5">
+                <title>Multiway hierarchy requirements</title>
+                <tgroup cols="4">
+                  <thead>
+                    <row>
+                      <entry>
+                        <para>
+                          expression
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          return type
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          assertion/note<sbr/> pre/post-condition
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          complexity
+                        </para>
+                      </entry>
+                    </row>
+                  </thead>
+                  <tbody>
+                    <row>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">a.clear(q)</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          <literal moreinfo="none">void</literal>
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          deletes the subtree of <literal moreinfo="none">q</literal>.<sbr/> If
+                          <literal moreinfo="none">q</literal> is dereferenceable, the expression
+                          also deletes the element <literal moreinfo="none">q</literal> points to.<sbr/>
+                          If <literal moreinfo="none">q</literal> is past-the-end, the expression
+                          deletes the element <literal moreinfo="none">q</literal>'s predecessor
+                          points to.<sbr/> If after either of these steps <literal moreinfo="none">q</literal>
+                          has only a non-empty past-the-end child, that child's children
+                          become <literal moreinfo="none">q</literal>'s children instead. Finally,
+                          that child is deleted.<sbr/> pre: <literal moreinfo="none">q</literal>
+                          is internal.
+                        </para>
+                      </entry>
+                      <entry>
+                        <para>
+                          Should be at worst linear in the the number of elements
+                          in the subtree of <literal moreinfo="none">c</literal> plus the distance
+                          to <literal moreinfo="none">p</literal>'s parent's <literal moreinfo="none">end()</literal>.
+                        </para>
+                      </entry>
+                    </row>
+                  </tbody>
+                </tgroup>
+              </table>
+            </listitem>
+          </orderedlist>
+        </section>
+        <section id="tree.proposal.containers.hierarchy.tree">
+          <title><link linkend="tree.proposal.containers.hierarchy.tree">Trees <phrase role="tr_section_label">[tr.hierarchy.tree]</phrase></link></title>
+          <orderedlist inheritnum="ignore" continuation="restarts">
+            <listitem>
+              <para>
+                Headers <literal moreinfo="none">&lt;binary_tree&gt;</literal>, <literal moreinfo="none">&lt;nary_tree&gt;</literal>,
+                <literal moreinfo="none">&lt;forest_tree&gt;</literal>, and <literal moreinfo="none">&lt;multiway_tree&gt;</literal>.
+              </para>
+              <para>
+                <emphasis role="bold">Header <literal moreinfo="none">&lt;binary_tree&gt;</literal>
+                synopsis</emphasis>
+              </para>
+<programlisting xmlns:xi="http://www.w3.org/2001/XInclude"><phrase role="keyword">namespace</phrase> <phrase role="identifier">std</phrase> <phrase role="special">{</phrase>
+<phrase role="keyword">namespace</phrase> <phrase role="identifier">tr2</phrase> <phrase role="special">{</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase> <phrase role="special">=</phrase> <phrase role="identifier">std</phrase><phrase role="special">::</phrase><phrase role="identifier">allocator</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">&gt;</phrase> <phrase role="special">&gt;</phrase>
+    <phrase role="keyword">class</phrase> <phrase role="identifier">binary_tree</phrase><phrase role="special">;</phrase>
+
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="keyword">bool</phrase> <phrase role="keyword">operator</phrase><phrase role="special">==(</phrase>  <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+                      <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="keyword">bool</phrase> <phrase role="keyword">operator</phrase><phrase role="special">!=(</phrase>  <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+                      <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="keyword">void</phrase> <phrase role="identifier">swap</phrase><phrase role="special">(</phrase>  <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+                <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">namespace</phrase> <phrase role="identifier">inorder</phrase> <phrase role="special">{</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">Tp</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="identifier">inorder</phrase><phrase role="special">::</phrase><phrase role="identifier">iterator</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">Tp</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;::</phrase><phrase role="identifier">cursor</phrase><phrase role="special">&gt;</phrase>
+      <phrase role="identifier">begin</phrase><phrase role="special">(</phrase><phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">Tp</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">h</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">Tp</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="identifier">inorder</phrase><phrase role="special">::</phrase><phrase role="identifier">iterator</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">Tp</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;::</phrase><phrase role="identifier">const_cursor</phrase><phrase role="special">&gt;</phrase>
+      <phrase role="identifier">cbegin</phrase><phrase role="special">(</phrase><phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">Tp</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">h</phrase><phrase role="special">);</phrase>
+  <phrase role="special">}</phrase> <phrase role="comment">// namespace inorder</phrase>
+
+<phrase role="special">}</phrase> <phrase role="comment">// namespace tr2</phrase>
+<phrase role="special">}</phrase> <phrase role="comment">// namespace std</phrase>
+</programlisting>
+              <para>
+                <emphasis role="bold">Header <literal moreinfo="none">&lt;nary_tree&gt;</literal>
+                synopsis</emphasis>
+              </para>
+<programlisting xmlns:xi="http://www.w3.org/2001/XInclude"><phrase role="keyword">namespace</phrase> <phrase role="identifier">std</phrase> <phrase role="special">{</phrase>
+<phrase role="keyword">namespace</phrase> <phrase role="identifier">tr2</phrase> <phrase role="special">{</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase> <phrase role="special">=</phrase> <phrase role="identifier">std</phrase><phrase role="special">::</phrase><phrase role="identifier">allocator</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">&gt;</phrase> <phrase role="special">&gt;</phrase>
+    <phrase role="keyword">class</phrase> <phrase role="identifier">nary_tree</phrase><phrase role="special">;</phrase>
+
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="keyword">bool</phrase> <phrase role="keyword">operator</phrase><phrase role="special">==(</phrase>  <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+                      <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="keyword">bool</phrase> <phrase role="keyword">operator</phrase><phrase role="special">!=(</phrase>  <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+                      <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+  <phrase role="keyword">void</phrase> <phrase role="identifier">swap</phrase><phrase role="special">(</phrase>  <phrase role="identifier">nary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+              <phrase role="identifier">nary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">namespace</phrase> <phrase role="identifier">inorder</phrase> <phrase role="special">{</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="identifier">inorder</phrase><phrase role="special">::</phrase><phrase role="identifier">iterator</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;::</phrase><phrase role="identifier">cursor</phrase><phrase role="special">&gt;</phrase>
+      <phrase role="identifier">begin</phrase><phrase role="special">(</phrase><phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">h</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="identifier">inorder</phrase><phrase role="special">::</phrase><phrase role="identifier">iterator</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;::</phrase><phrase role="identifier">const_cursor</phrase><phrase role="special">&gt;</phrase>
+      <phrase role="identifier">cbegin</phrase><phrase role="special">(</phrase><phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">h</phrase><phrase role="special">);</phrase>
+  <phrase role="special">}</phrase> <phrase role="comment">// namespace inorder</phrase>
+<phrase role="special">}</phrase> <phrase role="comment">// namespace tr2</phrase>
+<phrase role="special">}</phrase> <phrase role="comment">// namespace std</phrase>
+</programlisting>
+              <para>
+                <emphasis role="bold">Header <literal moreinfo="none">&lt;forest_tree&gt;</literal>
+                synopsis</emphasis>
+              </para>
+<programlisting xmlns:xi="http://www.w3.org/2001/XInclude"><phrase role="keyword">namespace</phrase> <phrase role="identifier">std</phrase> <phrase role="special">{</phrase>
+<phrase role="keyword">namespace</phrase> <phrase role="identifier">tr2</phrase> <phrase role="special">{</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Hierarchy</phrase> <phrase role="special">=</phrase> <phrase role="identifier">binary_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">&gt;</phrase> <phrase role="special">&gt;</phrase>
+    <phrase role="keyword">class</phrase> <phrase role="identifier">forest_tree</phrase><phrase role="special">;</phrase>
+
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="keyword">bool</phrase> <phrase role="keyword">operator</phrase><phrase role="special">==(</phrase>  <phrase role="identifier">forest_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+                      <phrase role="identifier">forest_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="keyword">bool</phrase> <phrase role="keyword">operator</phrase><phrase role="special">!=(</phrase>  <phrase role="identifier">forest_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+                      <phrase role="identifier">forest_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase>
+  <phrase role="keyword">void</phrase> <phrase role="identifier">swap</phrase><phrase role="special">(</phrase>  <phrase role="identifier">forest_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+              <phrase role="identifier">forest_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">namespace</phrase> <phrase role="identifier">inorder</phrase> <phrase role="special">{</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="identifier">inorder</phrase><phrase role="special">::</phrase><phrase role="identifier">iterator</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">forest_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;::</phrase><phrase role="identifier">cursor</phrase><phrase role="special">&gt;</phrase>
+      <phrase role="identifier">begin</phrase><phrase role="special">(</phrase><phrase role="identifier">forest_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">h</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="identifier">inorder</phrase><phrase role="special">::</phrase><phrase role="identifier">iterator</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">forest_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;::</phrase><phrase role="identifier">const_cursor</phrase><phrase role="special">&gt;</phrase>
+      <phrase role="identifier">cbegin</phrase><phrase role="special">(</phrase><phrase role="identifier">forest_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">h</phrase><phrase role="special">);</phrase>
+  <phrase role="special">}</phrase> <phrase role="comment">// namespace inorder</phrase>
+<phrase role="special">}</phrase> <phrase role="comment">// namespace tr2</phrase>
+<phrase role="special">}</phrase> <phrase role="comment">// namespace std</phrase>
+</programlisting>
+              <para>
+                <emphasis role="bold">Header <literal moreinfo="none">&lt;multiway_tree&gt;</literal>
+                synopsis</emphasis>
+              </para>
+<programlisting xmlns:xi="http://www.w3.org/2001/XInclude"><phrase role="keyword">namespace</phrase> <phrase role="identifier">std</phrase> <phrase role="special">{</phrase>
+<phrase role="keyword">namespace</phrase> <phrase role="identifier">tr2</phrase> <phrase role="special">{</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Hierarchy</phrase> <phrase role="special">=</phrase> <phrase role="identifier">nary_tree</phrase><phrase role="special">&lt;</phrase> <phrase role="identifier">std</phrase><phrase role="special">::</phrase><phrase role="identifier">vector</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">&gt;</phrase> <phrase role="special">&gt;</phrase> <phrase role="special">&gt;</phrase>
+    <phrase role="keyword">class</phrase> <phrase role="identifier">multiway_tree</phrase><phrase role="special">;</phrase>
+
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="keyword">bool</phrase> <phrase role="keyword">operator</phrase><phrase role="special">==(</phrase>  <phrase role="identifier">multiway_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+                      <phrase role="identifier">multiway_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="keyword">bool</phrase> <phrase role="keyword">operator</phrase><phrase role="special">!=(</phrase>  <phrase role="identifier">multiway_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+                      <phrase role="identifier">multiway_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="keyword">void</phrase> <phrase role="identifier">swap</phrase><phrase role="special">(</phrase>  <phrase role="identifier">multiway_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">x</phrase><phrase role="special">,</phrase>
+                <phrase role="identifier">multiway_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">y</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">namespace</phrase> <phrase role="identifier">inorder</phrase> <phrase role="special">{</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="identifier">inorder</phrase><phrase role="special">::</phrase><phrase role="identifier">iterator</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">multiway_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;::</phrase><phrase role="identifier">cursor</phrase><phrase role="special">&gt;</phrase>
+      <phrase role="identifier">begin</phrase><phrase role="special">(</phrase><phrase role="identifier">multiway_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;&amp;</phrase> <phrase role="identifier">h</phrase><phrase role="special">);</phrase>
+  <phrase role="keyword">template</phrase> <phrase role="special">&lt;</phrase><phrase role="keyword">class</phrase> <phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="keyword">class</phrase> <phrase role="identifier">Alloc</phrase><phrase role="special">&gt;</phrase>
+    <phrase role="identifier">inorder</phrase><phrase role="special">::</phrase><phrase role="identifier">iterator</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">multiway_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;::</phrase><phrase role="identifier">const_cursor</phrase><phrase role="special">&gt;</phrase>
+      <phrase role="identifier">cbegin</phrase><phrase role="special">(</phrase><phrase role="identifier">multiway_tree</phrase><phrase role="special">&lt;</phrase><phrase role="identifier">T</phrase><phrase role="special">,</phrase> <phrase role="identifier">Hierarchy</phrase><phrase role="special">&gt;</phrase> <phrase role="keyword">const</phrase><phrase role="special">&amp;</phrase> <phrase role="identifier">h</phrase><phrase role="special">);</phrase>
+  <phrase role="special">}</phrase> <phrase role="comment">// namespace inorder</phrase>
+<phrase role="special">}</phrase> <phrase role="comment">// namespace tr2</phrase>
+<phrase role="special">}</phrase> <phrase role="comment">// namespace std</phrase>
+</programlisting>
+            </listitem>
+          </orderedlist>
+          <section id="tree.proposal.containers.hierarchy.tree.bintree">
+            <title><link linkend="tree.proposal.containers.hierarchy.tree.bintree">Template
+            class <literal moreinfo="none">binary_tree</literal> <phrase role="tr_section_label">[tr.hierarchy.bintree]</phrase></link></title>
+            <section id="tree.proposal.containers.hierarchy.tree.bintree.types">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.bintree.types"><literal moreinfo="none">binary_tree</literal>
+              types <phrase role="tr_section_label">[tr.hierarchy.bintree.types]</phrase></link></title>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.bintree.cons">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.bintree.cons"><literal moreinfo="none">binary_tree</literal>
+              constructors, copy, and assignment <phrase role="tr_section_label">[tr.hierarchy.bintree.cons]</phrase></link></title>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.bintree.cursors">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.bintree.cursors"><literal moreinfo="none">binary_tree</literal>
+              cursors <phrase role="tr_section_label">[tr.hierarchy.bintree.cursors]</phrase></link></title>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.bintree.modifiers">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.bintree.modifiers"><literal moreinfo="none">binary_tree</literal>
+              modifiers <phrase role="tr_section_label">[tr.hierarchy.bintree.modifiers]</phrase></link></title>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.bintree.special">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.bintree.special"><literal moreinfo="none">binary_tree</literal>
+              specialized algorithms <phrase role="tr_section_label">[tr.hierarchy.bintree.special]</phrase></link></title>
+            </section>
+          </section>
+          <section id="tree.proposal.containers.hierarchy.tree.narytree">
+            <title><link linkend="tree.proposal.containers.hierarchy.tree.narytree">Template
+            class <literal moreinfo="none">nary_tree</literal> <phrase role="tr_section_label">[tr.hierarchy.narytree]</phrase></link></title>
+            <section id="tree.proposal.containers.hierarchy.tree.narytree.types">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.narytree.types"><literal moreinfo="none">nary_tree</literal>
+              types <phrase role="tr_section_label">[tr.hierarchy.narytree.types]</phrase></link></title>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.narytree.cons">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.narytree.cons"><literal moreinfo="none">nary_tree</literal>
+              constructors, copy, and assignment <phrase role="tr_section_label">[tr.hierarchy.narytree.cons]</phrase></link></title>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.narytree.cursors">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.narytree.cursors"><literal moreinfo="none">nary_tree</literal>
+              cursors <phrase role="tr_section_label">[tr.hierarchy.narytree.cursors]</phrase></link></title>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.narytree.capacity">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.narytree.capacity"><literal moreinfo="none">nary_tree</literal>
+              capacity <phrase role="tr_section_label">[tr.hierarchy.narytree.capacity]</phrase></link></title>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.narytree.modifiers">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.narytree.modifiers"><literal moreinfo="none">nary_tree</literal>
+              modifiers <phrase role="tr_section_label">[tr.hierarchy.narytree.modifiers]</phrase></link></title>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.narytree.special">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.narytree.special"><literal moreinfo="none">nary_tree</literal>
+              specialized algorithms <phrase role="tr_section_label">[tr.hierarchy.narytree.special]</phrase></link></title>
+            </section>
+          </section>
+          <section id="tree.proposal.containers.hierarchy.tree.adaptors">
+            <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors">Hierarchy
+            adaptors <phrase role="tr_section_label">[tr.hierarchy.adaptors]</phrase></link></title>
+            <section id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.foresttree">Template
+              class <literal moreinfo="none">forest_tree</literal> <phrase role="tr_section_label">[tr.hierarchy.foresttree]</phrase></link></title>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.types">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.types"><literal moreinfo="none">forest_tree</literal>
+                types <phrase role="tr_section_label">[tr.hierarchy.foresttree.types]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.cons">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.cons"><literal moreinfo="none">forest_tree</literal>
+                constructors, copy, and assignment <phrase role="tr_section_label">[tr.hierarchy.foresttree.cons]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.cursors">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.cursors"><literal moreinfo="none">forest_tree</literal>
+                cursors <phrase role="tr_section_label">[tr.hierarchy.foresttree.cursors]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.modifiers">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.modifiers"><literal moreinfo="none">forest_tree</literal>
+                modifiers <phrase role="tr_section_label">[tr.hierarchy.foresttree.modifiers]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.special">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.special"><literal moreinfo="none">forest_tree</literal>
+                specialized algorithms <phrase role="tr_section_label">[tr.hierarchy.foresttree.special]</phrase></link></title>
+              </section>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree">Template
+              class <literal moreinfo="none">multiway_tree</literal> <phrase role="tr_section_label">[tr.hierarchy.multiwaytree]</phrase></link></title>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.types">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.types"><literal moreinfo="none">multiway_tree</literal>
+                types <phrase role="tr_section_label">[tr.hierarchy.multiwaytree.types]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.cons">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.cons"><literal moreinfo="none">multiway_tree</literal>
+                constructors, copy, and assignment <phrase role="tr_section_label">[tr.hierarchy.multiwaytree.cons]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.cursors">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.cursors"><literal moreinfo="none">multiway_tree</literal>
+                cursors <phrase role="tr_section_label">[tr.hierarchy.multiwaytree.cursors]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.capacity">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.capacity"><literal moreinfo="none">multiway_tree</literal>
+                capacity <phrase role="tr_section_label">[tr.hierarchy.multiwaytree.capacity]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.modifiers">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.modifiers"><literal moreinfo="none">multiway_tree</literal>
+                modifiers <phrase role="tr_section_label">[tr.hierarchy.multiwaytree.modifiers]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.special">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.special"><literal moreinfo="none">multiway_tree</literal>
+                specialized algorithms <phrase role="tr_section_label">[tr.hierarchy.multiwaytree.special]</phrase></link></title>
+              </section>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.adaptors.augment">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.augment">Augmenting
+              hierarchy adaptors <phrase role="tr_section_label">[tr.hierarchy.augment]</phrase></link></title>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.augment.ranktree">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.augment.ranktree">Template
+                class <literal moreinfo="none">rank_tree</literal> <phrase role="tr_section_label">[tr.hierarchy.ranktree]</phrase></link></title>
+              </section>
+            </section>
+            <section id="tree.proposal.containers.hierarchy.tree.adaptors.balance">
+              <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.balance">Balancing
+              hierarchy adaptors <phrase role="tr_section_label">[tr.hierarchy.balance]</phrase></link></title>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.balance.cons">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.balance.cons">Balancing
+                adaptor constructors, copy, and assigment <phrase role="tr_section_label">[tr.hierarchy.balance.cons]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.balance.map">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.balance.map">Balancing
+                adaptor map operations <phrase role="tr_section_label">[tr.hierarchy.balance.map]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.balance.modifiers">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.balance.modifiers">Balancing
+                adaptor modifiers <phrase role="tr_section_label">[tr.hierarchy.balance.modifiers]</phrase></link></title>
+              </section>
+              <section id="tree.proposal.containers.hierarchy.tree.adaptors.balance.special">
+                <title><link linkend="tree.proposal.containers.hierarchy.tree.adaptors.balance.special">Balancing
+                adaptor specialized algorithms <phrase role="tr_section_label">[tr.hierarchy.balance.special]</phrase></link></title>
+              </section>
+            </section>
+          </section>
+        </section>
+      </section>
+    </section>
+  </section>
+  <section id="tree.references">
+    <title><link linkend="tree.references">References</link></title>
+    <variablelist>
+      <title>References</title>
+      <varlistentry>
+        <term>austern</term>
+        <listitem>
+          <para>
+            Austern, Matthew H.; Stroustrup, Bjarne; Thorup, Mikkel; Wilikinson,
+            John. <emphasis>Untangling the Balancing and Searching of Balanced Binary
+            Search Trees</emphasis>, Software: Practice and Experience 33(13): 1273-1298
+            (2003) Electronic Appendix: http://www.research.att.com/~bs/tree-appendix.pdf
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>cormen</term>
+        <listitem>
+          <para>
+            Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford.
+            <emphasis>Introduction to Algorithms</emphasis>. Second Edition (MIT
+            Press, 2001)
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>dreizin</term>
+        <listitem>
+          <para>
+            Dreizin, Vladimir; Kosnik, Benjamin; Tavory, Ami. <emphasis>Policy-Based
+            Data Structures</emphasis>, http://gcc.gnu.org/onlinedocs/libstdc++
>ext/pb_ds</emphasis>
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>ekman</term>
+        <listitem>
+          <para>
+            Ekman, Rasmus. <emphasis>Structured Associative Containers</emphasis>,
+
http://www.abc.se/~re/code/tst
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>gottschlich</term>
+        <listitem>
+          <para>
+            Gottschlich, Justin. <emphasis>C++ Trees</emphasis>, http://www.gamedev.net/reference/articles/article2192.asp
+            and http://www.gamedev.net/reference/articles/article2233.asp
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>haas</term>
+        <listitem>
+          <para>
+            Haas, Mitchell. <emphasis>Tree Container Library</emphasis>, http://www.datasoftsolutions.net/tree_container_library/overview.php
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>karas</term>
+        <listitem>
+          <para>
+            Karas, Walt. <emphasis>C++ AVL Tree Template</emphasis>, http://us.geocities.com/wkaras/gen_cpp/avl_tree.html
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>knuth97</term>
+        <listitem>
+          <para>
+            Knuth, Donald E. <emphasis>The Art of Computer Programming</emphasis>.
+            Volume 1: Fundamental Algorithms. Third Edition (Reading, Massachusetts:
+            Addison-Wesley, 1997)
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>knuth98</term>
+        <listitem>
+          <para>
+            Knuth, Donald E. <emphasis>The Art of Computer Programming</emphasis>.
+            Volume 3: Sorting and Searching. Second Edition (Reading, Massachusetts:
+            Addison-Wesley, 1998)
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>mirwaisi</term>
+        <listitem>
+          <para>
+            Mirwaisi, Jeff. <emphasis>treelib</emphasis>, https://boost-consulting.com:8443/trac/soc/attachment/wiki/tree/resources/trees/treelib.tar.bz2
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>parent</term>
+        <listitem>
+          <para>
+            Parent, Sean et al. <emphasis>forest</emphasis>, http://opensource.adobe.com/group__forest__related.html
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>peeters</term>
+        <listitem>
+          <para>
+            Peeters, Kasper. <emphasis>tree.hh: an STL-like C++ tree class</emphasis>,
+            http://www.aei.mpg.de/~peekas/tree/
+          </para>
+        </listitem>
+      </varlistentry>
+      <varlistentry>
+        <term>rivera</term>
+        <listitem>
+          <para>
+            Rivera, René. <emphasis>RankTree.h</emphasis>, http://redshift-software.com/~grafik/RankTree.h
+          </para>
+        </listitem>
+      </varlistentry>
+    </variablelist>
+  </section>
+</article>

Modified: sandbox/tree/libs/tree/proposal/single/proposal.html
==============================================================================
--- sandbox/tree/libs/tree/proposal/single/proposal.html	(original)
+++ sandbox/tree/libs/tree/proposal/single/proposal.html	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -1,4 +1,4 @@
-<html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Hierarchical Data Structures and Related Concepts for the C++ Standard Library</title><style type="text/css">
+<html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Hierarchical Data Structures and Related Concepts for the C++ Standard Library</title><style type="text/css">
 
 /********************************/
 /* start of styles in block.xsl */
@@ -119,17 +119,17 @@
     Body defaults
 =============================================================================*/
 body {
-	margin: 1em;
-	font-family: sans-serif;
+  margin: 1em;
+  font-family: sans-serif;
 }
 
 /*=============================================================================
     Paragraphs
 =============================================================================*/
 p {
-	text-align: left;
-	font-size: 10pt;
-	line-height: 1.15;
+  text-align: left;
+  font-size: 10pt;
+  line-height: 1.15;
 }
 
 /*=============================================================================
@@ -138,254 +138,254 @@
 
 /* Code on paragraphs */
 p tt.computeroutput {
-	font-size: 9pt;
+  font-size: 9pt;
 }
 
 pre.synopsis {
-	font-size: 90%;
-	margin: 1pc 4% 0pc 4%;
-	padding: 0.5pc 0.5pc 0.5pc 0.5pc;
+  font-size: 90%;
+  margin: 1pc 4% 0pc 4%;
+  padding: 0.5pc 0.5pc 0.5pc 0.5pc;
 }
 
 .programlisting,.screen {
-	font-size: 9pt;
-	display: block;
-	margin: 1pc 4% 0pc 4%;
-	padding: 0.5pc 0.5pc 0.5pc 0.5pc;
+  font-size: 9pt;
+  display: block;
+  margin: 1pc 4% 0pc 4%;
+  padding: 0.5pc 0.5pc 0.5pc 0.5pc;
 }
 
 /* Program listings in tables don't get borders */
 td .programlisting,td .screen {
-	margin: 0pc 0pc 0pc 0pc;
-	padding: 0pc 0pc 0pc 0pc;
+  margin: 0pc 0pc 0pc 0pc;
+  padding: 0pc 0pc 0pc 0pc;
 }
 
 /*=============================================================================
     Headings
 =============================================================================*/
 h1,h2,h3,h4,h5,h6 {
-	text-align: left;
-	margin: 1em 0em 0.5em 0em;
-	font-weight: bold;
+  text-align: left;
+  margin: 1em 0em 0.5em 0em;
+  font-weight: bold;
 }
 
 h1 {
-	font: 140%
+  font: 140%
 }
 
 h2 {
-	font: bold 140%
+  font: bold 140%
 }
 
 h3 {
-	font: bold 130%
+  font: bold 130%
 }
 
 h4 {
-	font: bold 120%
+  font: bold 120%
 }
 
 h5 {
-	font: italic 110%
+  font: italic 110%
 }
 
 h6 {
-	font: italic 100%
+  font: italic 100%
 }
 
 /* Top page titles */
 title,h1.title,h2.title
     h3.title,h4.title,h5.title,h6.title,.refentrytitle {
-	font-weight: bold;
-	margin-bottom: 1pc;
+  font-weight: bold;
+  margin-bottom: 1pc;
 }
 
 h1.title {
-	font-size: 140%
+  font-size: 140%
 }
 
 h2.title {
-	font-size: 140%
+  font-size: 140%
 }
 
 h3.title {
-	font-size: 130%
+  font-size: 130%
 }
 
 h4.title {
-	font-size: 120%
+  font-size: 120%
 }
 
 h5.title {
-	font-size: 110%
+  font-size: 110%
 }
 
 h6.title {
-	font-size: 100%
+  font-size: 100%
 }
 
 .section h1 {
-	margin: 0em 0em 0.5em 0em;
-	font-size: 140%;
+  margin: 0em 0em 0.5em 0em;
+  font-size: 140%;
 }
 
 .section h2 {
-	font-size: 140%
+  font-size: 140%
 }
 
 .section h3 {
-	font-size: 130%
+  font-size: 130%
 }
 
 .section h4 {
-	font-size: 120%
+  font-size: 120%
 }
 
 .section h5 {
-	font-size: 110%
+  font-size: 110%
 }
 
 .section h6 {
-	font-size: 100%
+  font-size: 100%
 }
 
 /* Code on titles */
 h1 tt.computeroutput {
-	font-size: 140%
+  font-size: 140%
 }
 
 h2 tt.computeroutput {
-	font-size: 140%
+  font-size: 140%
 }
 
 h3 tt.computeroutput {
-	font-size: 130%
+  font-size: 130%
 }
 
 h4 tt.computeroutput {
-	font-size: 120%
+  font-size: 120%
 }
 
 h5 tt.computeroutput {
-	font-size: 110%
+  font-size: 110%
 }
 
 h6 tt.computeroutput {
-	font-size: 100%
+  font-size: 100%
 }
 
 /*=============================================================================
     Author
 =============================================================================*/
 h3.author {
-	font-size: 100%
+  font-size: 100%
 }
 
 /*=============================================================================
     Lists
 =============================================================================*/
 li {
-	font-size: 10pt;
-	line-height: 1.3;
+  font-size: 10pt;
+  line-height: 1.3;
 }
 
 /* Unordered lists */
 ul {
-	text-align: left;
+  text-align: left;
 }
 
 /* Ordered lists */
 ol {
-	text-align: left;
+  text-align: left;
 }
 
 /*=============================================================================
     Links
 =============================================================================*/
 a {
-	text-decoration: none; /* no underline */
+  text-decoration: none; /* no underline */
 }
 
 a:hover {
-	text-decoration: underline;
+  text-decoration: underline;
 }
 
 /*=============================================================================
     Spirit style navigation
 =============================================================================*/
 .spirit-nav {
-	text-align: right;
+  text-align: right;
 }
 
 .spirit-nav a {
-	color: white;
-	padding-left: 0.5em;
+  color: white;
+  padding-left: 0.5em;
 }
 
 .spirit-nav img {
-	border-width: 0px;
+  border-width: 0px;
 }
 
 /*=============================================================================
     Table of contents
 =============================================================================*/
 .toc {
-	margin: 1pc 4% 0pc 4%;
-	padding: 0.1pc 1pc 0.1pc 1pc;
-	font-size: 80%;
-	line-height: 1.15;
+  margin: 1pc 4% 0pc 4%;
+  padding: 0.1pc 1pc 0.1pc 1pc;
+  font-size: 80%;
+  line-height: 1.15;
 }
 
 .boost-toc {
-	float: right;
-	padding: 0.5pc;
+  float: right;
+  padding: 0.5pc;
 }
 
 /*=============================================================================
     Tables
 =============================================================================*/
 .table-title,div.table p.title {
-	margin-left: 4%;
-	padding-right: 0.5em;
-	padding-left: 0.5em;
+  margin-left: 4%;
+  padding-right: 0.5em;
+  padding-left: 0.5em;
 }
 
 .informaltable table,.table table {
-	width: 92%;
-	margin-left: 4%;
-	margin-right: 4%;
+  width: 92%;
+  margin-left: 4%;
+  margin-right: 4%;
 }
 
 div.informaltable table,div.table table {
-	padding: 4px;
+  padding: 4px;
 }
 
 /* Table Cells */
 div.informaltable table tr td,div.table table tr td {
-	padding: 0.5em;
-	text-align: left;
-	font-size: 9pt;
+  padding: 0.5em;
+  text-align: left;
+  font-size: 9pt;
 }
 
 div.informaltable table tr th,div.table table tr th {
-	padding: 0.5em 0.5em 0.5em 0.5em;
-	border: 1pt solid white;
-	font-size: 80%;
+  padding: 0.5em 0.5em 0.5em 0.5em;
+  border: 1pt solid white;
+  font-size: 80%;
 }
 
 /*=============================================================================
     Blurbs
 =============================================================================*/
 div.note,div.tip,div.important,div.caution,div.warning,p.blurb {
-	font-size: 9pt; /* A little bit smaller than the main text */
-	line-height: 1.2;
-	display: block;
-	margin: 1pc 4% 0pc 4%;
-	padding: 0.5pc 0.5pc 0.5pc 0.5pc;
+  font-size: 9pt; /* A little bit smaller than the main text */
+  line-height: 1.2;
+  display: block;
+  margin: 1pc 4% 0pc 4%;
+  padding: 0.5pc 0.5pc 0.5pc 0.5pc;
 }
 
 p.blurb img {
-	padding: 1pt;
+  padding: 1pt;
 }
 
 /*=============================================================================
@@ -394,31 +394,31 @@
 
 /* Make the terms in definition lists bold */
 div.variablelist dl dt,span.term {
-	font-weight: bold;
-	font-size: 10pt;
+  font-weight: bold;
+  font-size: 10pt;
 }
 
 div.variablelist table tbody tr td {
-	text-align: left;
-	vertical-align: top;
-	padding: 0em 2em 0em 0em;
-	font-size: 10pt;
-	margin: 0em 0em 0.5em 0em;
-	line-height: 1;
+  text-align: left;
+  vertical-align: top;
+  padding: 0em 2em 0em 0em;
+  font-size: 10pt;
+  margin: 0em 0em 0.5em 0em;
+  line-height: 1;
 }
 
 div.variablelist dl dt {
-	margin-bottom: 0.2em;
+  margin-bottom: 0.2em;
 }
 
 div.variablelist dl dd {
-	margin: 0em 0em 0.5em 2em;
-	font-size: 10pt;
+  margin: 0em 0em 0.5em 2em;
+  font-size: 10pt;
 }
 
 div.variablelist table tbody tr td p,div.variablelist dl dd p {
-	margin: 0em 0em 0.5em 0em;
-	line-height: 1;
+  margin: 0em 0em 0.5em 0em;
+  line-height: 1;
 }
 
 /*=============================================================================
@@ -427,226 +427,231 @@
 
 /* Title of books and articles in bibliographies */
 span.title {
-	font-style: italic;
+  font-style: italic;
 }
 
 span.underline {
-	text-decoration: underline;
+  text-decoration: underline;
 }
 
 span.strikethrough {
-	text-decoration: line-through;
+  text-decoration: line-through;
 }
 
 /* Copyright, Legal Notice */
 div div.legalnotice p {
-	text-align: left
+  text-align: left
 }
 
 /*=============================================================================
     Colors
 =============================================================================*/
 @media screen { /* Links */
-	a {
-		color: #005a9c;
-	}
-	a:visited {
-		color: #9c5a9c;
-	}
-	h1 a,h2 a,h3 a,h4 a,h5 a,h6 a,h1 a:hover,h2 a:hover,h3 a:hover,h4 a:hover,h5 a:hover,h6 a:hover,h1 a:visited,h2 a:visited,h3 a:visited,h4 a:visited,h5 a:visited,h6 a:visited
-		{
-		text-decoration: none; /* no underline */
-		color: #000000;
-	}
-
-	/* Syntax Highlighting */
-	.keyword {
-		color: #0000AA;
-	}
-	.identifier {
-		color: #000000;
-	}
-	.special {
-		color: #707070;
-	}
-	.preprocessor {
-		color: #402080;
-	}
-	.char {
-		color: teal;
-	}
-	.comment {
-		color: #800000;
-	}
-	.string {
-		color: teal;
-	}
-	.number {
-		color: teal;
-	}
-	.white_bkd {
-		background-color: #FFFFFF;
-	}
-	.dk_grey_bkd {
-		background-color: #999999;
-	}
-
-	/* Copyright, Legal Notice */
-	.copyright {
-		color: #666666;
-		font-size: small;
-	}
-	div div.legalnotice p {
-		color: #666666;
-	}
-
-	/* Program listing */
-	pre.synopsis {
-		border: 1px solid #DCDCDC;
-	}
-	.programlisting,.screen {
-		border: 1px solid #DCDCDC;
-	}
-	td .programlisting,td .screen {
-		border: 0px solid #DCDCDC;
-	}
-
-	/* Blurbs */
-	div.note,div.tip,div.important,div.caution,div.warning,p.blurb {
-		border: 1px solid #DCDCDC;
-	}
-
-	/* Table of contents */
-	.toc {
-		border: 1px solid #DCDCDC;
-	}
-
-	/* Tables */
-	div.informaltable table tr td,div.table table tr td {
-		border: 1px solid #DCDCDC;
-	}
-	div.informaltable table tr th,div.table table tr th {
-		background-color: #F0F0F0;
-		border: 1px solid #DCDCDC;
-	}
-
-	/* Misc */
-	span.highlight {
-		color: #00A000;
-	}
+  a {
+    color: #005a9c;
+  }
+  a:visited {
+    color: #9c5a9c;
+  }
+  h1 a,h2 a,h3 a,h4 a,h5 a,h6 a,h1 a:hover,h2 a:hover,h3 a:hover,h4 a:hover,h5 a:hover,h6 a:hover,h1 a:visited,h2 a:visited,h3 a:visited,h4 a:visited,h5 a:visited,h6 a:visited
+    {
+    text-decoration: none; /* no underline */
+    color: #000000;
+  }
+
+  /* Syntax Highlighting */
+  .keyword {
+    color: #0000AA;
+  }
+  .identifier {
+    color: #000000;
+  }
+  .special {
+    color: #707070;
+  }
+  .preprocessor {
+    color: #402080;
+  }
+  .char {
+    color: teal;
+  }
+  .comment {
+    color: #800000;
+  }
+  .string {
+    color: teal;
+  }
+  .number {
+    color: teal;
+  }
+  .white_bkd {
+    background-color: #FFFFFF;
+  }
+  .dk_grey_bkd {
+    background-color: #999999;
+  }
+
+  /* Copyright, Legal Notice */
+  .copyright {
+    color: #666666;
+    font-size: small;
+  }
+  div div.legalnotice p {
+    color: #666666;
+  }
+
+  /* Program listing */
+  pre.synopsis {
+    border: 1px solid #DCDCDC;
+  }
+  .programlisting,.screen {
+    border: 1px solid #DCDCDC;
+  }
+  td .programlisting,td .screen {
+    border: 0px solid #DCDCDC;
+  }
+
+  /* Blurbs */
+  div.note,div.tip,div.important,div.caution,div.warning,p.blurb {
+    border: 1px solid #DCDCDC;
+  }
+
+  /* Table of contents */
+  .toc {
+    border: 1px solid #DCDCDC;
+  }
+
+  /* Tables */
+  div.informaltable table tr td,div.table table tr td {
+    border: 1px solid #DCDCDC;
+  }
+  div.informaltable table tr th,div.table table tr th {
+    background-color: #F0F0F0;
+    border: 1px solid #DCDCDC;
+  }
+
+  /* Misc */
+  span.highlight {
+    color: #00A000;
+  }
 }
 
 @media print { /* Links */
-	a {
-		color: black;
-	}
-	a:visited {
-		color: black;
-	}
-	.spirit-nav {
-		display: none;
-	}
-
-	/* Program listing */
-	pre.synopsis {
-		border: 1px solid gray;
-	}
-	.programlisting,.screen {
-		border: 1px solid gray;
-	}
-	td .programlisting,td .screen {
-		border: 0px solid #DCDCDC;
-	}
-
-	/* Table of contents */
-	.toc {
-		border: 1px solid gray;
-	}
-	.informaltable table,.table table {
-		border: 1px solid gray;
-		border-collapse: collapse;
-	}
-
-	/* Tables */
-	div.informaltable table tr td,div.table table tr td {
-		border: 1px solid gray;
-	}
-	div.informaltable table tr th,div.table table tr th {
-		border: 1px solid gray;
-	}
-
-	/* Misc */
-	span.highlight {
-		font-weight: bold;
-	}
+  a {
+    color: black;
+  }
+  a:visited {
+    color: black;
+  }
+  .spirit-nav {
+    display: none;
+  }
+
+  /* Program listing */
+  pre.synopsis {
+    border: 1px solid gray;
+  }
+  .programlisting,.screen {
+    border: 1px solid gray;
+  }
+  td .programlisting,td .screen {
+    border: 0px solid #DCDCDC;
+  }
+
+  /* Table of contents */
+  .toc {
+    border: 1px solid gray;
+  }
+  .informaltable table,.table table {
+    border: 1px solid gray;
+    border-collapse: collapse;
+  }
+
+  /* Tables */
+  div.informaltable table tr td,div.table table tr td {
+    border: 1px solid gray;
+  }
+  div.informaltable table tr th,div.table table tr th {
+    border: 1px solid gray;
+  }
+
+  /* Misc */
+  span.highlight {
+    font-weight: bold;
+  }
 }
 
 .tree_proposal>.section {
-	font-family: serif;
+  font-family: serif;
 }
 
 .tree_proposal>.section {
-	margin: 1em;
-	padding: 1em 0em 1em 1.5em;
-	border-top: 1px solid #888888;
-	border-bottom: 1px solid #888888;
+  margin: 1em;
+  padding: 1em 0em 1em 1.5em;
+  border-top: 1px solid #888888;
+  border-bottom: 1px solid #888888;
+}
+
+.tree_proposal .tr_section_label {
+  float: right;
 }
 
 .tree_proposal ol {
-	margin: 0em;
-	padding: 0em;
+  margin: 0em;
+  padding: 0em;
 }
 
 .tree_proposal ol li {
-	margin: 0em 0em 1em 0em;
-	padding: 0em 0em 0em 0em;
+  margin: 0em 0em 1em 0em;
+  padding: 0em 0em 0em 0em;
 }
 
 .tree_proposal table {
-	border: 1px solid;
-	margin: 0em auto 0em auto;
-	border-spacing: 0em;
-	width: inherit;
-	padding: 0em !important;
+  border: 1px solid;
+  margin: 0em auto 0em auto;
+  border-spacing: 0em;
+  width: inherit;
+  padding: 0em !important;
+  border-collapse: separate;
 }
 
 .tree_proposal .table .title,
 .tree_proposal .table-title {
-	font-weight: bold;
-	margin: 1em auto 1em auto;
-	text-align: center;
-	caption-side: top;
+  font-weight: bold;
+  margin: 1em auto 1em auto;
+  text-align: center;
+  caption-side: top;
 }
 
 .tree_proposal table th {
-    border: none !important;
-    border-bottom: 1px solid !important;
-    padding: 0.25em 0.5em 0em 0.5em;
-    background: transparent !important;
+  border: none !important;
+  border-bottom: 1px solid !important;
+  padding: 0.25em 0.5em 0em 0.5em !important;
+  background: transparent !important;
 }
 .tree_proposal table th p {
-    text-align: center !important;
+  text-align: center !important;
 }
 
 .tree_proposal table td {
-	border: none !important;
-	border-top: 1px solid !important;
-	vertical-align: top;
-	padding: 0.25em 0.5em 0em 0.5em;
-    background: transparent !important;
+  border: none !important;
+  border-top: 1px solid !important;
+  vertical-align: top !important;
+  padding: 0.25em 0.5em 0em 0.5em !important;
+  background: transparent !important;
 }
 
 .tree_proposal .docref {
-	float: right;
+  float: right;
 }
 
 .tree_proposal .docref dt {
-	float: left;
-	font-style: italic;
+  float: left;
+  font-style: italic;
 }
 
 .tree_proposal .docref dd {
-	margin-left: 8em;
+  margin-left: 8em;
 }
 
 .tree_proposal h1,
@@ -655,59 +660,66 @@
 .tree_proposal h4,
 .tree_proposal h5,
 .tree_proposal h6 {
-	clear: both;
+  clear: both;
+  font-style: normal;
 }
 
 .tree_proposal .byline {
-	text-align: center;
+  text-align: center;
 }
 
 .tree_proposal .note {
-    background: #EEEEEE;
-    border: 1px solid #AAAAAA;
-    padding: 0.25em;
+  background: #EEEEEE;
+  border: 1px solid #AAAAAA;
+  padding: 0.25em;
 }
 .tree_proposal .note .title {
-	display: none;
+  display: none;
 }
 .tree_proposal .note p {
-	margin: 0.25em 0em 0.25em 0em;
+  margin: 0.25em 0em 0.25em 0em;
 }
 .tree_proposal .note table {
-    border: none;
-    margin: 0em;
-    padding: 0em;
+  border: none;
+  margin: 0em;
+  padding: 0em;
 }
 .tree_proposal .note table td,
 .tree_proposal .note table th {
-    border: none !important;
+  border: none !important;
 }
 
 .tree_proposal .add {
-	text-decoration: overline;
+  text-decoration: overline;
 }
 
 .tree_proposal h2 {
-	font-size: 150%
+  font-size: 150%
 }
 
 .tree_proposal h3,
 .tree_proposal h4,
 .tree_proposal h5,
 .tree_proposal h6 {
-	font-size: 100%;
+  font-size: 100%;
 }
 
 .tree_proposal .section-id {
-	float: right;
-	position: relative;
-	top: -1.25em;
+  float: right;
+  position: relative;
+  top: -1.25em;
+}
+.tree_proposal .programlisting {
+  border: none !important;
+  margin-left: 0em !important;
+  margin-right: 0em !important;
+  padding: 0em !important;
 }
-</style><meta name="generator" content="DocBook XSL Stylesheets V1.76.1"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="chapter" title="Hierarchical Data Structures and Related Concepts for the C++ Standard Library" id="tree"><div class="titlepage"><div><div><h2 class="title">Hierarchical Data Structures and Related Concepts for the C++ Standard Library</h2></div><div><div class="author"><h3 class="author"><span class="firstname">Bernhard</span> <span class="surname">Reiter</span></h3></div></div><div><div class="author"><h3 class="author"><span class="firstname">René</span> <span class="surname">Rivera</span></h3></div></div><div><p class="copyright">Copyright © 2006-2009 Bernhard
-      Reiter and René Rivera</p></div><div><div class="legalnotice" title="Legal Notice"><a name="tree.legal"></a><p>
+</style><meta name="generator" content="DocBook XSL Stylesheets V1.76.1"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="article" title="Hierarchical Data Structures and Related Concepts for the C++ Standard Library" id="tree"><div class="titlepage"><div><div><h2 class="title">Hierarchical Data Structures and Related Concepts for the C++ Standard Library</h2></div><div><div class="authorgroup"><div class="author"><h3 class="author"><span class="firstname">Bernhard</span> <span class="surname">Reiter</span></h3></div><div class="author"><h3 class="author"><span class="firstname">René</span> <span class="surname">Rivera</span></h3></div></div></div><div><p class="copyright">Copyright © 2006-2009 Bernhard
+      Reiter</p></div><div><p class="copyright">Copyright © 2006-2012 René Rivera</p></div><div><div class="legalnotice" title="Legal Notice"><a name="tree.legal"></a><p>
         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)
-      </p></div></div></div></div><div class="toc"><div class="toc-title">Table of Contents</div><dl><dt><span class="section"><a href="#tree.preamble">1. Hierarchical Data Structures and Related
+      </p></div></div></div><hr></div><div class="toc"><div class="toc-title">Table of Contents</div><dl><dt><span class="section"><a href="#tree.preamble">1. Hierarchical Data Structures and Related
     Concepts for the C++ Standard Library</a></span></dt><dd><dl><dt><span class="section">1.1. Introduction</span></dt><dt><span class="section">1.2. Motivation and Scope</span></dt><dd><dl><dt><span class="section"><a href="#tree.preamble.motivation_and_scope.why_is_this_important">1.2.1. Why
         is this important?</a></span></dt><dt><span class="section"><a href="#tree.preamble.motivation_and_scope.what_kinds_of_problems_does_it_a">1.2.2. What
         kinds of problems does it address, and what kinds of programmers is it intended
@@ -724,28 +736,34 @@
         are the consequences of your choices, for users and implementors?</a></span></dt><dt><span class="section"><a href="#tree.preamble.important_design_decisions.what_decisions_are_left_up_to_im">1.4.4. What
         decisions are left up to implementors?</a></span></dt><dt><span class="section"><a href="#tree.preamble.important_design_decisions.if_there_are_any_similar_librari">1.4.5. If
         there are any similar libraries in use, how do their design decisions compare
-        to yours?</a></span></dt></dl></dd><dt><span class="section">1.5. Future Directions</span></dt></dl></dd><dt><span class="section">2. Proposed Text for Technical Report 2</span></dt><dd><dl><dt><span class="section">2.1. Containers library [tr.containers]</span></dt><dd><dl><dt><span class="section"><a href="#tree.proposal.tr_containers.tr_hierarchy">2.1.1. Hierarchy
-        containers [tr.hierarchy]</a></span></dt><dd><dl><dt><span class="section"><a href="#tree.proposal.tr_containers.tr_hierarchy.tr_hierarchy_req">2.1.1.1. Hierarchy
-          container requirements [tr.hierarchy.req]</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section">3. References</span></dt></dl></div><div class="section tree_preamble" title="1. Hierarchical Data Structures and Related Concepts for the C++ Standard Library"><div class="titlepage"><div><div><h2 class="title" style="clear: both" id="tree.preamble">1. <a class="link" href="#tree.preamble" title="1. Hierarchical Data Structures and Related Concepts for the C++ Standard Library">Hierarchical Data Structures and Related
+        to yours?</a></span></dt></dl></dd><dt><span class="section">1.5. Future Directions</span></dt></dl></dd><dt><span class="section">2. Proposed Text for Technical Report 2</span></dt><dd><dl><dt><span class="section">2.1. Containers library [tr.containers]</span></dt><dd><dl><dt><span class="section"><a href="#tree.proposal.containers.hierarchy">2.1.1. Hierarchy containers
+        <span class="tr_section_label">[tr.hierarchy]</span></a></span></dt><dd><dl><dt><span class="section"><a href="#tree.proposal.containers.hierarchy.req">2.1.1.1. Hierarchy
+          containers requirements <span class="tr_section_label">[tr.hierarchy.req]</span></a></span></dt><dt><span class="section"><a href="#tree.proposal.containers.hierarchy.plain">2.1.1.2. Plain hierarchies
+          <span class="tr_section_label">[tr.hierarchy.plain]</span></a></span></dt><dt><span class="section"><a href="#tree.proposal.containers.hierarchy.multiway">2.1.1.3. Multiway
+          hierarchies <span class="tr_section_label">[tr.hierarchy.multiway]</span></a></span></dt><dt><span class="section">2.1.1.4. Trees [tr.hierarchy.tree]</span></dt><dd><dl><dt><span class="section"><a href="#tree.proposal.containers.hierarchy.tree.bintree">2.1.1.4.1. Template
+            class <code class="literal">binary_tree</code> <span class="tr_section_label">[tr.hierarchy.bintree]</span></a></span></dt><dt><span class="section"><a href="#tree.proposal.containers.hierarchy.tree.narytree">2.1.1.4.2. Template
+            class <code class="literal">nary_tree</code> <span class="tr_section_label">[tr.hierarchy.narytree]</span></a></span></dt><dt><span class="section"><a href="#tree.proposal.containers.hierarchy.tree.adaptors">2.1.1.4.3. Hierarchy
+            adaptors <span class="tr_section_label">[tr.hierarchy.adaptors]</span></a></span></dt></dl></dd></dl></dd></dl></dd></dl></dd><dt><span class="section">3. References</span></dt></dl></div><div class="section tree_preamble" title="1. Hierarchical Data Structures and Related Concepts for the C++ Standard Library"><div class="titlepage"><div><div><h2 class="title" style="clear: both" id="tree.preamble">1. <a class="link" href="#tree.preamble" title="1. Hierarchical Data Structures and Related Concepts for the C++ Standard Library">Hierarchical Data Structures and Related
     Concepts for the C++ Standard Library</a></h2></div></div></div><p>
-      <span class="bold"><strong>Bernhard Reiter and René Rivera</strong></span>
+      <span class="bold"><strong>Bernhard Reiter and René Rivera</strong></span>
     </p><div class="variablelist"><div class="variablelist-title"></div><dl><dt><span class="term">Document No.</span></dt><dd><p>
+            WG21/N????=J16/??-????
+          </p></dd><dt><span class="term">Supercedes</span></dt><dd><p>
             WG21/N2101=J16/06-0171
           </p></dd><dt><span class="term">Date</span></dt><dd><p>
-            2006-11-05
+            2012-Jan-15
           </p></dd><dt><span class="term">Project</span></dt><dd><p>
             Programming Language C++
           </p></dd><dt><span class="term">Reply to</span></dt><dd><p>
-            Bernhard Reiter &lt;<a href="mailto:ockham_at_[hidden]" target="_top">ockham_at_[hidden]&gt;</a>,
-            René Rivera &lt;<a href="mailto:rrivera_at_[hidden]" target="_top">rrivera_at_[hidden]</a>&gt;
-          </p></dd></dl></div><div class="section tree_preamble_introduction" title="1.1. Introduction"><div class="titlepage"><div><div><h3 class="title" id="tree.preamble.introduction">1.1. <a class="link" href="#tree.preamble.introduction" title="1.1. Introduction">Introduction</a></h3></div></div></div><p>
+            René Rivera &lt;<a href="mailto:rrivera_at_[hidden]" target="_top">rrivera_at_[hidden]</a>&gt;
+          </p></dd></dl></div><div class="section tree_preamble_introduction" title="1.1. Introduction"><div class="titlepage"><div><div><h3 class="title" id="tree.preamble.introduction">1.1. <a class="link" href="#tree.preamble.introduction" title="1.1. Introduction">Introduction</a></h3></div></div></div><p>
         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.
       </p><p>
         The library strives to cover many of the relevant aspects within the vast
         field linked to the notion of trees in computer science.
-      </p></div><div class="section tree_preamble_motivation_and_scope" title="1.2. Motivation and Scope"><div class="titlepage"><div><div><h3 class="title" id="tree.preamble.motivation_and_scope">1.2. <a class="link" href="#tree.preamble.motivation_and_scope" title="1.2. Motivation and Scope">Motivation and Scope</a></h3></div></div></div><div class="section tree_preamble_motivation_and_scope_why_is_this_important" title="1.2.1. Why is this important?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.motivation_and_scope.why_is_this_important">1.2.1. <a class="link" href="#tree.preamble.motivation_and_scope.why_is_this_important" title="1.2.1. Why is this important?">Why
+      </p></div><div class="section tree_preamble_motivation_and_scope" title="1.2. Motivation and Scope"><div class="titlepage"><div><div><h3 class="title" id="tree.preamble.motivation_and_scope">1.2. <a class="link" href="#tree.preamble.motivation_and_scope" title="1.2. Motivation and Scope">Motivation and Scope</a></h3></div></div></div><div class="section tree_preamble_motivation_and_scope_why_is_this_important" title="1.2.1. Why is this important?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.motivation_and_scope.why_is_this_important">1.2.1. <a class="link" href="#tree.preamble.motivation_and_scope.why_is_this_important" title="1.2.1. Why is this important?">Why
         is this important?</a></h4></div></div></div><p>
           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
@@ -759,7 +777,7 @@
           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 <span class="emphasis"><em>rooted ordered connected acyclic graphs</em></span>.
-        </p></div><div class="section tree_preamble_motivation_and_scope_what_kinds_of_problems_does_it_a" title="1.2.2. What kinds of problems does it address, and what kinds of programmers is it intended to support?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.motivation_and_scope.what_kinds_of_problems_does_it_a">1.2.2. <a class="link" href="#tree.preamble.motivation_and_scope.what_kinds_of_problems_does_it_a" title="1.2.2. What kinds of problems does it address, and what kinds of programmers is it intended to support?">What
+        </p></div><div class="section tree_preamble_motivation_and_scope_what_kinds_of_problems_does_it_a" title="1.2.2. What kinds of problems does it address, and what kinds of programmers is it intended to support?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.motivation_and_scope.what_kinds_of_problems_does_it_a">1.2.2. <a class="link" href="#tree.preamble.motivation_and_scope.what_kinds_of_problems_does_it_a" title="1.2.2. What kinds of problems does it address, and what kinds of programmers is it intended to support?">What
         kinds of problems does it address, and what kinds of programmers is it intended
         to support?</a></h4></div></div></div><p>
           Existing tree implementations as listed in the References section as well
@@ -768,24 +786,24 @@
           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.
-        </p></div><div class="section tree_preamble_motivation_and_scope_is_it_based_on_existing_practice" title="1.2.3. Is it based on existing practice?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.motivation_and_scope.is_it_based_on_existing_practice">1.2.3. <a class="link" href="#tree.preamble.motivation_and_scope.is_it_based_on_existing_practice" title="1.2.3. Is it based on existing practice?">Is
+        </p></div><div class="section tree_preamble_motivation_and_scope_is_it_based_on_existing_practice" title="1.2.3. Is it based on existing practice?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.motivation_and_scope.is_it_based_on_existing_practice">1.2.3. <a class="link" href="#tree.preamble.motivation_and_scope.is_it_based_on_existing_practice" title="1.2.3. Is it based on existing practice?">Is
         it based on existing practice?</a></h4></div></div></div><p>
           No; this proposal originates in an effort to create a generic tree container
           component for Boost in the course
           of <a href="http://code.google.com/soc/2006/boost/appinfo.html?csaid=E17EA7C7C537C131" target="_top">Google
-          Summer of Code&#8482; 2006</a>, so at the time of this writing, implementation
+          Summer of Codeâ„¢ 2006</a>, 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.
-        </p></div><div class="section tree_preamble_motivation_and_scope_is_there_a_reference_implementat" title="1.2.4. Is there a reference implementation?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.motivation_and_scope.is_there_a_reference_implementat">1.2.4. <a class="link" href="#tree.preamble.motivation_and_scope.is_there_a_reference_implementat" title="1.2.4. Is there a reference implementation?">Is
+        </p></div><div class="section tree_preamble_motivation_and_scope_is_there_a_reference_implementat" title="1.2.4. Is there a reference implementation?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.motivation_and_scope.is_there_a_reference_implementat">1.2.4. <a class="link" href="#tree.preamble.motivation_and_scope.is_there_a_reference_implementat" title="1.2.4. Is there a reference implementation?">Is
         there a reference implementation?</a></h4></div></div></div><p>
           Yes; the current state is available from svn from http://svn.boost.org/svn/boost/sandbox/tree.
-        </p></div></div><div class="section tree_preamble_impact_on_the_standard" title="1.3. Impact on the Standard"><div class="titlepage"><div><div><h3 class="title" id="tree.preamble.impact_on_the_standard">1.3. <a class="link" href="#tree.preamble.impact_on_the_standard" title="1.3. Impact on the Standard">Impact on the Standard</a></h3></div></div></div><div class="section tree_preamble_impact_on_the_standard_what_does_it_depend_on_and_what_" title="1.3.1. What does it depend on, and what depends on it?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.impact_on_the_standard.what_does_it_depend_on_and_what_">1.3.1. <a class="link" href="#tree.preamble.impact_on_the_standard.what_does_it_depend_on_and_what_" title="1.3.1. What does it depend on, and what depends on it?">What
+        </p></div></div><div class="section tree_preamble_impact_on_the_standard" title="1.3. Impact on the Standard"><div class="titlepage"><div><div><h3 class="title" id="tree.preamble.impact_on_the_standard">1.3. <a class="link" href="#tree.preamble.impact_on_the_standard" title="1.3. Impact on the Standard">Impact on the Standard</a></h3></div></div></div><div class="section tree_preamble_impact_on_the_standard_what_does_it_depend_on_and_what_" title="1.3.1. What does it depend on, and what depends on it?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.impact_on_the_standard.what_does_it_depend_on_and_what_">1.3.1. <a class="link" href="#tree.preamble.impact_on_the_standard.what_does_it_depend_on_and_what_" title="1.3.1. What does it depend on, and what depends on it?">What
         does it depend on, and what depends on it?</a></h4></div></div></div><p>
           It depends on some standard library components, such as <code class="literal">std::allocator</code>
           which is used as the default allocator template argument at some points.
           Concepts like allocators or iterators are reused and in some cases adapted.
-        </p></div><div class="section tree_preamble_impact_on_the_standard_is_it_a_pure_extension_or_does_i" title="1.3.2. Is it a pure extension, or does it require changes to standard components?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.impact_on_the_standard.is_it_a_pure_extension_or_does_i">1.3.2. <a class="link" href="#tree.preamble.impact_on_the_standard.is_it_a_pure_extension_or_does_i" title="1.3.2. Is it a pure extension, or does it require changes to standard components?">Is
+        </p></div><div class="section tree_preamble_impact_on_the_standard_is_it_a_pure_extension_or_does_i" title="1.3.2. Is it a pure extension, or does it require changes to standard components?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.impact_on_the_standard.is_it_a_pure_extension_or_does_i">1.3.2. <a class="link" href="#tree.preamble.impact_on_the_standard.is_it_a_pure_extension_or_does_i" title="1.3.2. Is it a pure extension, or does it require changes to standard components?">Is
         it a pure extension, or does it require changes to standard components?</a></h4></div></div></div><p>
           Most of the proposed library is a pure extension.
         </p><p>
@@ -806,22 +824,22 @@
           code; making it the last parameter (after the allocator) would allow existing
           code to remain unchanged, but seems somewhat irritating when compared to
           <code class="literal">unordered</code> containers.
-        </p></div><div class="section tree_preamble_impact_on_the_standard_can_it_be_implemented_using_toda" title="1.3.3. Can it be implemented using today's compilers, or does it require language features that will only be available as part of C++11"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.impact_on_the_standard.can_it_be_implemented_using_toda">1.3.3. <a class="link" href="#tree.preamble.impact_on_the_standard.can_it_be_implemented_using_toda" title="1.3.3. Can it be implemented using today's compilers, or does it require language features that will only be available as part of C++11">Can
+        </p></div><div class="section tree_preamble_impact_on_the_standard_can_it_be_implemented_using_toda" title="1.3.3. Can it be implemented using today's compilers, or does it require language features that will only be available as part of C++11"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.impact_on_the_standard.can_it_be_implemented_using_toda">1.3.3. <a class="link" href="#tree.preamble.impact_on_the_standard.can_it_be_implemented_using_toda" title="1.3.3. Can it be implemented using today's compilers, or does it require language features that will only be available as part of C++11">Can
         it be implemented using today's compilers, or does it require language features
         that will only be available as part of C++11</a></h4></div></div></div><p>
           It can be, and partly has been, implemented with today's compilers.
         </p><p>
           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]
+          paragraph 2 of section [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 <a href="http://boost.org/libs/range/doc/range.html" target="_top">Boost
           Range concept</a> (http://boost.org/libs/range/doc/range.html)
           externally to the Standard.
-        </p></div></div><div class="section tree_preamble_important_design_decisions" title="1.4. Important Design Decisions"><div class="titlepage"><div><div><h3 class="title" id="tree.preamble.important_design_decisions">1.4. <a class="link" href="#tree.preamble.important_design_decisions" title="1.4. Important Design Decisions">Important Design
-      Decisions</a></h3></div></div></div><div class="section tree_preamble_important_design_decisions_why_did_you_choose_the_specific_" title="1.4.1. Why did you choose the specific design that you did?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.important_design_decisions.why_did_you_choose_the_specific_">1.4.1. <a class="link" href="#tree.preamble.important_design_decisions.why_did_you_choose_the_specific_" title="1.4.1. Why did you choose the specific design that you did?">Why
+        </p></div></div><div class="section tree_preamble_important_design_decisions" title="1.4. Important Design Decisions"><div class="titlepage"><div><div><h3 class="title" id="tree.preamble.important_design_decisions">1.4. <a class="link" href="#tree.preamble.important_design_decisions" title="1.4. Important Design Decisions">Important Design
+      Decisions</a></h3></div></div></div><div class="section tree_preamble_important_design_decisions_why_did_you_choose_the_specific_" title="1.4.1. Why did you choose the specific design that you did?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.important_design_decisions.why_did_you_choose_the_specific_">1.4.1. <a class="link" href="#tree.preamble.important_design_decisions.why_did_you_choose_the_specific_" title="1.4.1. Why did you choose the specific design that you did?">Why
         did you choose the specific design that you did?</a></h4></div></div></div><p>
           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
@@ -833,7 +851,7 @@
           implementation details, such as nodes for storage in many cases, allowing
           the underlying concepts to be applicable to other possible implementations
           as well.
-        </p></div><div class="section tree_preamble_important_design_decisions_what_alternatives_did_you_consid" title="1.4.2. What alternatives did you consider, and what are the tradeoffs?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.important_design_decisions.what_alternatives_did_you_consid">1.4.2. <a class="link" href="#tree.preamble.important_design_decisions.what_alternatives_did_you_consid" title="1.4.2. What alternatives did you consider, and what are the tradeoffs?">What
+        </p></div><div class="section tree_preamble_important_design_decisions_what_alternatives_did_you_consid" title="1.4.2. What alternatives did you consider, and what are the tradeoffs?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.important_design_decisions.what_alternatives_did_you_consid">1.4.2. <a class="link" href="#tree.preamble.important_design_decisions.what_alternatives_did_you_consid" title="1.4.2. What alternatives did you consider, and what are the tradeoffs?">What
         alternatives did you consider, and what are the tradeoffs?</a></h4></div></div></div><h6><a name="tree.preamble.important_design_decisions.what_alternatives_did_you_consid.h0"></a>
           <span><a name="tree.preamble.important_design_decisions.what_alternatives_did_you_consid.trees_of_trees"></a></span><a class="link" href="#tree.preamble.important_design_decisions.what_alternatives_did_you_consid.trees_of_trees">Trees
           of trees</a>
@@ -861,7 +879,7 @@
           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.
-        </p></div><div class="section tree_preamble_important_design_decisions_what_are_the_consequences_of_you" title="1.4.3. What are the consequences of your choices, for users and implementors?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.important_design_decisions.what_are_the_consequences_of_you">1.4.3. <a class="link" href="#tree.preamble.important_design_decisions.what_are_the_consequences_of_you" title="1.4.3. What are the consequences of your choices, for users and implementors?">What
+        </p></div><div class="section tree_preamble_important_design_decisions_what_are_the_consequences_of_you" title="1.4.3. What are the consequences of your choices, for users and implementors?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.important_design_decisions.what_are_the_consequences_of_you">1.4.3. <a class="link" href="#tree.preamble.important_design_decisions.what_are_the_consequences_of_you" title="1.4.3. What are the consequences of your choices, for users and implementors?">What
         are the consequences of your choices, for users and implementors?</a></h4></div></div></div><p>
           As focus was put on versatility and comprehensiveness, we hope users will
           find this a powerful framework that covers most important aspects of dealing
@@ -876,7 +894,7 @@
           arrays for both children of a binary tree node, see e.g. <a class="link" href="#">[austern]</a>),
           which may partly restrict implementors to one "proper" way of
           doing things.
-        </p></div><div class="section tree_preamble_important_design_decisions_what_decisions_are_left_up_to_im" title="1.4.4. What decisions are left up to implementors?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.important_design_decisions.what_decisions_are_left_up_to_im">1.4.4. <a class="link" href="#tree.preamble.important_design_decisions.what_decisions_are_left_up_to_im" title="1.4.4. What decisions are left up to implementors?">What
+        </p></div><div class="section tree_preamble_important_design_decisions_what_decisions_are_left_up_to_im" title="1.4.4. What decisions are left up to implementors?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.important_design_decisions.what_decisions_are_left_up_to_im">1.4.4. <a class="link" href="#tree.preamble.important_design_decisions.what_decisions_are_left_up_to_im" title="1.4.4. What decisions are left up to implementors?">What
         decisions are left up to implementors?</a></h4></div></div></div><p>
           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
@@ -885,7 +903,7 @@
           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).
-        </p></div><div class="section tree_preamble_important_design_decisions_if_there_are_any_similar_librari" title="1.4.5. If there are any similar libraries in use, how do their design decisions compare to yours?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.important_design_decisions.if_there_are_any_similar_librari">1.4.5. <a class="link" href="#tree.preamble.important_design_decisions.if_there_are_any_similar_librari" title="1.4.5. If there are any similar libraries in use, how do their design decisions compare to yours?">If
+        </p></div><div class="section tree_preamble_important_design_decisions_if_there_are_any_similar_librari" title="1.4.5. If there are any similar libraries in use, how do their design decisions compare to yours?"><div class="titlepage"><div><div><h4 class="title" id="tree.preamble.important_design_decisions.if_there_are_any_similar_librari">1.4.5. <a class="link" href="#tree.preamble.important_design_decisions.if_there_are_any_similar_librari" title="1.4.5. If there are any similar libraries in use, how do their design decisions compare to yours?">If
         there are any similar libraries in use, how do their design decisions compare
         to yours?</a></h4></div></div></div><p>
           Trees, having attracted much attention in the C++ community, are found
@@ -913,194 +931,612 @@
           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.
-        </p></div></div><div class="section tree_preamble_future_directions" title="1.5. Future Directions"><div class="titlepage"><div><div><h3 class="title" id="tree.preamble.future_directions">1.5. <a class="link" href="#tree.preamble.future_directions" title="1.5. Future Directions">Future Directions</a></h3></div></div></div><p>
+        </p></div></div><div class="section tree_preamble_future_directions" title="1.5. Future Directions"><div class="titlepage"><div><div><h3 class="title" id="tree.preamble.future_directions">1.5. <a class="link" href="#tree.preamble.future_directions" title="1.5. Future Directions">Future Directions</a></h3></div></div></div><p>
         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.
-      </p></div></div><div class="section tree_proposal" title="2. Proposed Text for Technical Report 2"><div class="titlepage"><div><div><h2 class="title" style="clear: both" id="tree.proposal">2. <a class="link" href="#tree.proposal" title="2. Proposed Text for Technical Report 2">Proposed Text for Technical Report 2</a></h2></div></div></div><div class="note" title="Note"><h3 class="title">Note</h3><p>
+      </p></div></div><div class="section tree_proposal" title="2. Proposed Text for Technical Report 2"><div class="titlepage"><div><div><h2 class="title" style="clear: both" id="tree.proposal">2. <a class="link" href="#tree.proposal" title="2. Proposed Text for Technical Report 2">Proposed Text for Technical Report 2</a></h2></div></div></div><div class="note" title="Note"><h3 class="title">Note</h3><p>
         Notes that are not part of the proposed text appear in gray boxes.
-      </p></div><div class="section tree_proposal_tr_containers" title="2.1. Containers library [tr.containers]"><div class="titlepage"><div><div><h3 class="title" id="tree.proposal.tr_containers">2.1. <a class="link" href="#tree.proposal.tr_containers" title="2.1. Containers library [tr.containers]">Containers library [tr.containers]</a></h3></div></div></div><div class="section tree_proposal_tr_containers_tr_hierarchy" title="2.1.1. Hierarchy containers [tr.hierarchy]"><div class="titlepage"><div><div><h4 class="title" id="tree.proposal.tr_containers.tr_hierarchy">2.1.1. <a class="link" href="#tree.proposal.tr_containers.tr_hierarchy" title="2.1.1. Hierarchy containers [tr.hierarchy]">Hierarchy
-        containers [tr.hierarchy]</a></h4></div></div></div><div class="section tree_proposal_tr_containers_tr_hierarchy_tr_hierarchy_req" title="2.1.1.1. Hierarchy container requirements [tr.hierarchy.req]"><div class="titlepage"><div><div><h5 class="title" id="tree.proposal.tr_containers.tr_hierarchy.tr_hierarchy_req">2.1.1.1. <a class="link" href="#tree.proposal.tr_containers.tr_hierarchy.tr_hierarchy_req" title="2.1.1.1. Hierarchy container requirements [tr.hierarchy.req]">Hierarchy
-          container requirements [tr.hierarchy.req]</a></h5></div></div></div><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem">
+      </p></div><div class="section tree_proposal_containers" title="2.1. Containers library [tr.containers]"><div class="titlepage"><div><div><h3 class="title" id="tree.proposal.containers">2.1. <a class="link" href="#tree.proposal.containers" title="2.1. Containers library [tr.containers]">Containers library <span class="tr_section_label">[tr.containers]</span></a></h3></div></div></div><div class="section tree_proposal_containers_hierarchy" title="2.1.1. Hierarchy containers [tr.hierarchy]"><div class="titlepage"><div><div><h4 class="title" id="tree.proposal.containers.hierarchy">2.1.1. <a class="link" href="#tree.proposal.containers.hierarchy" title="2.1.1. Hierarchy containers [tr.hierarchy]">Hierarchy containers
+        <span class="tr_section_label">[tr.hierarchy]</span></a></h4></div></div></div><div class="section tree_proposal_containers_hierarchy_req" title="2.1.1.1. Hierarchy containers requirements [tr.hierarchy.req]"><div class="titlepage"><div><div><h5 class="title" id="tree.proposal.containers.hierarchy.req">2.1.1.1. <a class="link" href="#tree.proposal.containers.hierarchy.req" title="2.1.1.1. Hierarchy containers requirements [tr.hierarchy.req]">Hierarchy
+          containers requirements <span class="tr_section_label">[tr.hierarchy.req]</span></a></h5></div></div></div><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
                 A hierarchy is an object that stores a finite set of objects, all
                 of the same type, in a hierarchical manner. Hierarchies introduce
                 a cursor concept for navigation instead of iterators. The library
                 provides two kinds of native hierarchies: <code class="literal">binary_tree</code>,
                 and <code class="literal">nary_tree</code>, along with hierarchy-yielding hierarchy
                 adaptors <code class="literal">forest_tree</code>, and <code class="literal">multiway_tree</code>.
-              </li><li class="listitem">
+              </p></li><li class="listitem"><p>
                 Hierarchy containers conform to the requirements of Containers ([lib.container.requirements]),
                 except that the expressions in Table 1 are not required to be valid,
-                where <code class="literal">a</code> and <code class="literal">b</code> denote values
-                of a type <code class="literal">X</code>, and <code class="literal">X</code> is a hierarchy
-                container class:
-                <div class="table"><a name="tree.proposal.tr_containers.tr_hierarchy.tr_hierarchy_req.container_requirements_that_are_"></a><div class="table-title">Table 1. Container requirements that are not required for hierarchy
-                  containers</div><div class="table-contents"><table class="table" summary="Container requirements that are not required for hierarchy
-                  containers"><colgroup><col></colgroup><thead><tr><th>
-                          <p>
-                            unsupported expression
-                          </p>
-                        </th></tr></thead><tbody><tr><td>
-                          <p>
-                            <code class="literal">X::iterator</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">X::const_iterator</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">X::reverse_iterator</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">X::const_reverse_iterator</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">a.begin()</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">a.end()</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">a.rbegin()</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">a.rend()</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">a &lt; b</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">a &gt; b</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">a &lt;= b</code>
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">a &gt;= b</code>
-                          </p>
-                        </td></tr></tbody></table></div></div><br class="table-break">
-              </li><li class="listitem">
+                where a and b denote values of a type X, and X is a hierarchy container
+                class:
+              </p><div class="table"><a name="tree.proposal.containers.hierarchy.req.table1"></a><div class="table-title">Table 1. Container requirements that are not required for hierarchy
+                containers</div><div class="table-contents"><table class="table" summary="Container requirements that are not required for hierarchy
+                containers"><colgroup><col></colgroup><thead><tr><th>
+                        <p>
+                          unsupported expression
+                        </p>
+                      </th></tr></thead><tbody><tr><td>
+                        <p>
+                          <code class="literal">X::iterator</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">X::const_iterator</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">X::reverse_iterator</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">X::const_reverse_iterator</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.begin()</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.end()</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.rbegin()</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.rend()</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a &lt; b</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a &gt; b</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a &lt;= b</code>
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a &gt;= b</code>
+                        </p>
+                      </td></tr></tbody></table></div></div><br class="table-break"></li><li class="listitem"><p>
                 Non-constant complexity requirements in this clause are stated in
                 one of a number of possible different ways: unless specified otherwise,
                 they are expressed in terms of the number of operations <code class="literal">n</code>,
                 which stands for the total number of elements in the hierarchy; in
                 some cases, however, they are stated in terms of another value.
-              </li><li class="listitem">
-                In Table 2 <code class="literal">X</code> denotes a hierarchy class containing
+              </p></li><li class="listitem"><p>
+                In Table 2: <code class="literal">X</code> denotes a hierarchy class containing
                 objects of type <code class="literal">T</code> and <code class="literal">a</code> denotes
                 a value of type <code class="literal">X</code>.
-                <div class="table"><a name="tree.proposal.tr_containers.tr_hierarchy.tr_hierarchy_req.hierarchy_requirements_in_additi"></a><div class="table-title">Table 2. Hierarchy requirements (in addition to container)</div><div class="table-contents"><table class="table" summary="Hierarchy requirements (in addition to container)"><colgroup><col><col><col><col></colgroup><thead><tr><th>
-                          <p>
-                            expression
-                          </p>
-                        </th><th>
-                          <p>
-                            return type
-                          </p>
-                        </th><th>
-                          <p>
-                            assertion/note<br> pre/post-condition
-                          </p>
-                        </th><th>
-                          <p>
-                            complexity
-                          </p>
-                        </th></tr></thead><tbody><tr><td>
-                          <p>
-                            <code class="literal">X::cursor</code>
-                          </p>
-                        </td><td>
-                          <p>
-                            cursor type pointing to <code class="literal">T</code>
-                          </p>
-                        </td><td>
-                          <p>
-                            any cursor category
-                          </p>
-                        </td><td>
-                          <p>
-                            compile time
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            X::const_cursor
-                          </p>
-                        </td><td>
-                          <p>
-                            cursor type pointing to <code class="literal">const T</code>
-                          </p>
-                        </td><td>
-                          <p>
-                            any cursor category
-                          </p>
-                        </td><td>
-                          <p>
-                            compile time
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">a.root()</code>
-                          </p>
-                        </td><td>
-                          <p>
-                            <code class="literal">iterator</code> for mutable <code class="literal">a</code>;<br>
-                            <code class="literal">const_iterator</code> for constant <code class="literal">a</code>
-                          </p>
-                        </td><td>
-                        </td><td>
-                          <p>
-                            constant
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">a.croot()</code>
-                          </p>
-                        </td><td>
-                          <p>
-                            <code class="literal">const_iterator</code>
-                          </p>
-                        </td><td>
-                        </td><td>
-                          <p>
-                            constant
-                          </p>
-                        </td></tr><tr><td>
-                          <p>
-                            <code class="literal">typename X::template rebind&lt;U&gt;::other</code>
-                          </p>
-                        </td><td>
-                          <p>
-                            <code class="literal">Y</code>
-                          </p>
-                        </td><td>
-                          <p>
-                            For all <code class="literal">U</code> (including <code class="literal">T</code>),
-                            <code class="literal">Y::template rebind&lt;T&gt;::other</code>
-                            is <code class="literal">X</code>.
-                          </p>
-                        </td><td>
-                          <p>
-                            compile time
-                          </p>
-                        </td></tr></tbody></table></div></div><br class="table-break">
-                <p>
-                  Notes: Those entries marked "(Note A)" should have at
-                  worst linear complexity. See the individual hierarchy containers
-                  for specific complexity.
-                </p>
-              </li></ol></div></div></div></div></div><div class="section tree_references" title="3. References"><div class="titlepage"><div><div><h2 class="title" style="clear: both" id="tree.references">3. <a class="link" href="#tree.references" title="3. References">References</a></h2></div></div></div><div class="variablelist" title="References"><div class="variablelist-title">References</div><dl><dt><span class="term">austern</span></dt><dd><p>
+              </p><div class="table"><a name="tree.proposal.containers.hierarchy.req.table2"></a><div class="table-title">Table 2. Hierarchy requirements (in addition to container)</div><div class="table-contents"><table class="table" summary="Hierarchy requirements (in addition to container)"><colgroup><col><col><col><col></colgroup><thead><tr><th>
+                        <p>
+                          expression
+                        </p>
+                      </th><th>
+                        <p>
+                          return type
+                        </p>
+                      </th><th>
+                        <p>
+                          assertion/note<br> pre/post-condition
+                        </p>
+                      </th><th>
+                        <p>
+                          complexity
+                        </p>
+                      </th></tr></thead><tbody><tr><td>
+                        <p>
+                          <code class="literal">X::cursor</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          cursor type pointing to <code class="literal">T</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          any cursor category
+                        </p>
+                      </td><td>
+                        <p>
+                          compile time
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">X::const_cursor</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          cursor type pointing to <code class="literal">const T</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          any cursor category
+                        </p>
+                      </td><td>
+                        <p>
+                          compile time
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.root()</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">iterator</code> for mutable <code class="literal">a</code>;<br>
+                          <code class="literal">const_iterator</code> for constant <code class="literal">a</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          Â 
+                        </p>
+                      </td><td>
+                        <p>
+                          constant
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.croot()</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">const_iterator</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          Â 
+                        </p>
+                      </td><td>
+                        <p>
+                          constant
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.shoot()</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">iterator</code> for mutable <code class="literal">a</code>;<br>
+                          <code class="literal">const_iterator</code> for constant <code class="literal">a</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          Â 
+                        </p>
+                      </td><td>
+                        <p>
+                          (Note A)
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.cshoot()</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">const_iterator</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          Â 
+                        </p>
+                      </td><td>
+                        <p>
+                          (Note A)
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">typename X::template rebind&lt;U&gt;::other</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">Y</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          For all <code class="literal">U</code> (including <code class="literal">T</code>),
+                          <code class="literal">Y::template rebind&lt;T&gt;::other</code> is
+                          <code class="literal">X</code>.
+                        </p>
+                      </td><td>
+                        <p>
+                          compile time
+                        </p>
+                      </td></tr></tbody></table></div></div><br class="table-break"><p>
+                Notes: Those entries marked "(Note A)" should have at worst
+                linear complexity. See the individual hierarchy containers for specific
+                complexity.
+              </p></li><li class="listitem"><p>
+                <code class="literal">root()</code> and <code class="literal">croot()</code> return a
+                cursor which is the on-top value for the hierarchy. <code class="literal">shoot()</code>
+                and <code class="literal">cshoot()</code> return a cursor which is the past-the-end
+                value that is found one past the hierarchy's rightmost element. If
+                the hierarchy is empty, then <code class="literal">root() == shoot();</code>
+              </p></li><li class="listitem"><p>
+                Copy constructors for all hierarchy types defined in this clause
+                copy the allocator argument from their respective first parameters.
+                All other constructors for these hierarchy types take an <code class="literal">Allocator&amp;</code>
+                argument (20.1.5). A copy of this argument is used for any memory
+                allocation performed, by these constructors and by all member functions,
+                during the lifetime of each hierarchy object. In all hierarchy types
+                defined in this clause, the member <code class="literal">get_allocator()</code>
+                returns a copy of the Allocator object used to construct the hierarchy.
+              </p></li><li class="listitem"><p>
+                The member class template <code class="literal">rebind</code> in the table
+                above is effectively a typedef template: if the name <code class="literal">Hierarchy</code>
+                is bound to <code class="literal">SomeHierarchy&lt;T&gt;</code>, then <code class="literal">Hierarchy::rebind&lt;U&gt;::other</code>
+                is the same type as <code class="literal">SomeHierarchy&lt;U&gt;</code>. Additionally,
+                because of the related assertion, given <code class="literal">SomeHierarchy&lt;T,R0,...,Rn&gt;</code>
+                for all template arguments present is bound to the name <code class="literal">Hierarchy</code>,
+                then <code class="literal">Hierarchy::rebind&lt;U&gt;::other</code> is the
+                same type as <code class="literal">SomeHierarchy&lt;U,S0,...,Sn&gt;</code>
+                such that the types <code class="literal">S0</code> through <code class="literal">Sn</code>
+                are the same as <code class="literal">R0</code> through <code class="literal">Rn</code>,
+                respectively, when <code class="literal">U</code> is the same type as <code class="literal">T</code>.
+              </p></li><li class="listitem"><p>
+                A hierarchy satisfying the requirements shown in Table 3 is called
+                a <span class="emphasis"><em>mutable hierarchy</em></span>. In Table 3, <code class="literal">X</code>
+                denotes a hierarchy class, <code class="literal">a</code> denotes a value of
+                <code class="literal">X</code>, <code class="literal">c</code> denotes a valid, non-on-top
+                cursor satisfying input cursor requirements, <code class="literal">p</code>
+                denotes a valid, non-on-top cursor to <code class="literal">a</code>, <code class="literal">q</code>
+                denotes a valid, dereferenceable cursor to <code class="literal">a</code>,
+                and <code class="literal">t</code> denotes a value of <code class="literal">X::value_type</code>.
+              </p><div class="table"><a name="tree.proposal.containers.hierarchy.req.table3"></a><div class="table-title">Table 3. Mutable hierarchy requirements</div><div class="table-contents"><table class="table" summary="Mutable hierarchy requirements"><colgroup><col><col><col><col></colgroup><thead><tr><th>
+                        <p>
+                          expression
+                        </p>
+                      </th><th>
+                        <p>
+                          return type
+                        </p>
+                      </th><th>
+                        <p>
+                          assertion/note<br> pre/post-condition
+                        </p>
+                      </th><th>
+                        <p>
+                          complexity
+                        </p>
+                      </th></tr></thead><tbody><tr><td>
+                        <p>
+                          <code class="literal">a.insert(p,t)</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">cursor</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          inserts a copy of <code class="literal">t</code> before <code class="literal">p</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          (Note A)
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.clear(q)</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">void</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          deletes the subtree of <code class="literal">q</code> and the element
+                          <code class="literal">q</code> points to.<br> pre: <code class="literal">q</code>
+                          is dereferenceable.
+                        </p>
+                      </td><td>
+                        <p>
+                          Should be at worst linear in the the number of elements
+                          in the subtree of <code class="literal">q</code> plus the distance
+                          to <code class="literal">q</code>'s parent's <code class="literal">end()</code>.
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.clear()</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">void</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">while (a.size()) clear(a.begin());</code><br>
+                          post: <code class="literal">a.size() == 0</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          (Note A)
+                        </p>
+                      </td></tr></tbody></table></div></div><br class="table-break"><p>
+                Notes: Those entries marked "(Note A)" should have at worst
+                linear complexity. See the individual hierarchy containers for specific
+                complexity.
+              </p></li><li class="listitem"><p>
+                The cursor returned from <code class="literal">a.insert(p,t)</code> points
+                to the copy of <code class="literal">t</code> inserted into <code class="literal">a</code>.
+                Its parent cursor is the same as that of <code class="literal">p</code>.
+              </p></li></ol></div></div><div class="section tree_proposal_containers_hierarchy_plain" title="2.1.1.2. Plain hierarchies [tr.hierarchy.plain]"><div class="titlepage"><div><div><h5 class="title" id="tree.proposal.containers.hierarchy.plain">2.1.1.2. <a class="link" href="#tree.proposal.containers.hierarchy.plain" title="2.1.1.2. Plain hierarchies [tr.hierarchy.plain]">Plain hierarchies
+          <span class="tr_section_label">[tr.hierarchy.plain]</span></a></h5></div></div></div><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
+                A hierarchy is called plain hierarchy if its cursor and const_cursor
+                types satisfy the requirements of a plain cursor.
+              </p></li><li class="listitem"><p>
+                The library provides one native kind of plain hierarchy, nary_tree,
+                and a hierarchy adaptor that in turn yields a plain hierarchy, forest_tree.
+              </p></li><li class="listitem"><p>
+                For a mutable plain hierarchy, the following expressions as shown
+                in Table 4, is additionally required to be valid:
+              </p><div class="table"><a name="tree.proposal.containers.hierarchy.plain.table4"></a><div class="table-title">Table 4. Plain hierarchy requirements</div><div class="table-contents"><table class="table" summary="Plain hierarchy requirements"><colgroup><col><col><col><col></colgroup><thead><tr><th>
+                        <p>
+                          expression
+                        </p>
+                      </th><th>
+                        <p>
+                          return type
+                        </p>
+                      </th><th>
+                        <p>
+                          assertion/note<br> pre/post-condition
+                        </p>
+                      </th><th>
+                        <p>
+                          complexity
+                        </p>
+                      </th></tr></thead><tbody><tr><td>
+                        <p>
+                          <code class="literal">a.insert(p,c)</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">cursor</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          inserts a copy of the subtree of <code class="literal">c</code> before
+                          <code class="literal">p</code>.<br> pre: <code class="literal">c</code> is
+                          dereferenceable.
+                        </p>
+                      </td><td>
+                        <p>
+                          Should be at worst linear in the the number of elements
+                          in the subtree of <code class="literal">c</code> plus the distance
+                          to <code class="literal">p</code>'s parent's <code class="literal">end()</code>.
+                        </p>
+                      </td></tr><tr><td>
+                        <p>
+                          <code class="literal">a.insert_above(p,t)</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">cursor</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          inserts a copy of <code class="literal">t</code> as child of <code class="literal">p</code>'s
+                          parent and new parent of <code class="literal">p</code> and its siblings.<br>
+                          pre: <code class="literal">c</code> is dereferenceable.
+                        </p>
+                      </td><td>
+                        <p>
+                          Linear in the the number <code class="literal">p</code>'s siblings.
+                        </p>
+                      </td></tr></tbody></table></div></div><br class="table-break"></li><li class="listitem"><p>
+                The cursor returned from <code class="literal">a.insert(p,c)</code> points
+                to the copy of the element that <code class="literal">c</code> points to, inserted
+                into <code class="literal">a</code>. Its parent cursor is the same as that
+                of <code class="literal">p</code>.
+              </p></li></ol></div></div><div class="section tree_proposal_containers_hierarchy_multiway" title="2.1.1.3. Multiway hierarchies [tr.hierarchy.multiway]"><div class="titlepage"><div><div><h5 class="title" id="tree.proposal.containers.hierarchy.multiway">2.1.1.3. <a class="link" href="#tree.proposal.containers.hierarchy.multiway" title="2.1.1.3. Multiway hierarchies [tr.hierarchy.multiway]">Multiway
+          hierarchies <span class="tr_section_label">[tr.hierarchy.multiway]</span></a></h5></div></div></div><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
+                A hierarchy is called multiway hierarchy if its <code class="literal">cursor</code>
+                and <code class="literal">const_cursor</code> types satisfy the requirements
+                of a multiway cursor.
+              </p></li><li class="listitem"><p>
+                The library provides one native kind of multiway hierarchy, <code class="literal">binary_tree</code>,
+                and a hierarchy adaptor that in turn yields a multiway hierarchy,
+                <code class="literal">multiway_tree</code>.
+              </p></li><li class="listitem"><p>
+                For a mutable multiway hierarchy, the semantics of some expressions
+                from Table 3 are modified as shown in Table 5.
+              </p><div class="table"><a name="tree.proposal.containers.hierarchy.multiway.table5"></a><div class="table-title">Table 5. Multiway hierarchy requirements</div><div class="table-contents"><table class="table" summary="Multiway hierarchy requirements"><colgroup><col><col><col><col></colgroup><thead><tr><th>
+                        <p>
+                          expression
+                        </p>
+                      </th><th>
+                        <p>
+                          return type
+                        </p>
+                      </th><th>
+                        <p>
+                          assertion/note<br> pre/post-condition
+                        </p>
+                      </th><th>
+                        <p>
+                          complexity
+                        </p>
+                      </th></tr></thead><tbody><tr><td>
+                        <p>
+                          <code class="literal">a.clear(q)</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          <code class="literal">void</code>
+                        </p>
+                      </td><td>
+                        <p>
+                          deletes the subtree of <code class="literal">q</code>.<br> If
+                          <code class="literal">q</code> is dereferenceable, the expression
+                          also deletes the element <code class="literal">q</code> points to.<br>
+                          If <code class="literal">q</code> is past-the-end, the expression
+                          deletes the element <code class="literal">q</code>'s predecessor
+                          points to.<br> If after either of these steps <code class="literal">q</code>
+                          has only a non-empty past-the-end child, that child's children
+                          become <code class="literal">q</code>'s children instead. Finally,
+                          that child is deleted.<br> pre: <code class="literal">q</code>
+                          is internal.
+                        </p>
+                      </td><td>
+                        <p>
+                          Should be at worst linear in the the number of elements
+                          in the subtree of <code class="literal">c</code> plus the distance
+                          to <code class="literal">p</code>'s parent's <code class="literal">end()</code>.
+                        </p>
+                      </td></tr></tbody></table></div></div><br class="table-break"></li></ol></div></div><div class="section tree_proposal_containers_hierarchy_tree" title="2.1.1.4. Trees [tr.hierarchy.tree]"><div class="titlepage"><div><div><h5 class="title" id="tree.proposal.containers.hierarchy.tree">2.1.1.4. <a class="link" href="#tree.proposal.containers.hierarchy.tree" title="2.1.1.4. Trees [tr.hierarchy.tree]">Trees <span class="tr_section_label">[tr.hierarchy.tree]</span></a></h5></div></div></div><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
+                Headers <code class="literal">&lt;binary_tree&gt;</code>, <code class="literal">&lt;nary_tree&gt;</code>,
+                <code class="literal">&lt;forest_tree&gt;</code>, and <code class="literal">&lt;multiway_tree&gt;</code>.
+              </p><p>
+                <span class="bold"><strong>Header <code class="literal">&lt;binary_tree&gt;</code>
+                synopsis</strong></span>
+              </p><div class="programlisting"><span class="keyword">namespace</span> <span class="identifier">std</span> <span class="special">{</span>
+<span class="keyword">namespace</span> <span class="identifier">tr2</span> <span class="special">{</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">allocator</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span> <span class="special">&gt;</span>
+    <span class="keyword">class</span> <span class="identifier">binary_tree</span><span class="special">;</span>
+
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">==(</span>  <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+                      <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">!=(</span>  <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+                      <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="keyword">void</span> <span class="identifier">swap</span><span class="special">(</span>  <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+                <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">namespace</span> <span class="identifier">inorder</span> <span class="special">{</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Tp</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="identifier">inorder</span><span class="special">::</span><span class="identifier">iterator</span><span class="special">&lt;</span><span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">Tp</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;::</span><span class="identifier">cursor</span><span class="special">&gt;</span>
+      <span class="identifier">begin</span><span class="special">(</span><span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">Tp</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;&amp;</span> <span class="identifier">h</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Tp</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="identifier">inorder</span><span class="special">::</span><span class="identifier">iterator</span><span class="special">&lt;</span><span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">Tp</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;::</span><span class="identifier">const_cursor</span><span class="special">&gt;</span>
+      <span class="identifier">cbegin</span><span class="special">(</span><span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">Tp</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">h</span><span class="special">);</span>
+  <span class="special">}</span> <span class="comment">// namespace inorder</span>
+
+<span class="special">}</span> <span class="comment">// namespace tr2</span>
+<span class="special">}</span> <span class="comment">// namespace std</span>
+</div><p>
+                <span class="bold"><strong>Header <code class="literal">&lt;nary_tree&gt;</code>
+                synopsis</strong></span>
+              </p><div class="programlisting"><span class="keyword">namespace</span> <span class="identifier">std</span> <span class="special">{</span>
+<span class="keyword">namespace</span> <span class="identifier">tr2</span> <span class="special">{</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">allocator</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span> <span class="special">&gt;</span>
+    <span class="keyword">class</span> <span class="identifier">nary_tree</span><span class="special">;</span>
+
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">==(</span>  <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+                      <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">!=(</span>  <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+                      <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+  <span class="keyword">void</span> <span class="identifier">swap</span><span class="special">(</span>  <span class="identifier">nary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+              <span class="identifier">nary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">namespace</span> <span class="identifier">inorder</span> <span class="special">{</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="identifier">inorder</span><span class="special">::</span><span class="identifier">iterator</span><span class="special">&lt;</span><span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;::</span><span class="identifier">cursor</span><span class="special">&gt;</span>
+      <span class="identifier">begin</span><span class="special">(</span><span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;&amp;</span> <span class="identifier">h</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="identifier">inorder</span><span class="special">::</span><span class="identifier">iterator</span><span class="special">&lt;</span><span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;::</span><span class="identifier">const_cursor</span><span class="special">&gt;</span>
+      <span class="identifier">cbegin</span><span class="special">(</span><span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Alloc</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">h</span><span class="special">);</span>
+  <span class="special">}</span> <span class="comment">// namespace inorder</span>
+<span class="special">}</span> <span class="comment">// namespace tr2</span>
+<span class="special">}</span> <span class="comment">// namespace std</span>
+</div><p>
+                <span class="bold"><strong>Header <code class="literal">&lt;forest_tree&gt;</code>
+                synopsis</strong></span>
+              </p><div class="programlisting"><span class="keyword">namespace</span> <span class="identifier">std</span> <span class="special">{</span>
+<span class="keyword">namespace</span> <span class="identifier">tr2</span> <span class="special">{</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Hierarchy</span> <span class="special">=</span> <span class="identifier">binary_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span> <span class="special">&gt;</span>
+    <span class="keyword">class</span> <span class="identifier">forest_tree</span><span class="special">;</span>
+
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span>
+    <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">==(</span>  <span class="identifier">forest_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+                      <span class="identifier">forest_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">!=(</span>  <span class="identifier">forest_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+                      <span class="identifier">forest_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span>
+  <span class="keyword">void</span> <span class="identifier">swap</span><span class="special">(</span>  <span class="identifier">forest_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+              <span class="identifier">forest_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">namespace</span> <span class="identifier">inorder</span> <span class="special">{</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span>
+    <span class="identifier">inorder</span><span class="special">::</span><span class="identifier">iterator</span><span class="special">&lt;</span><span class="identifier">forest_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;::</span><span class="identifier">cursor</span><span class="special">&gt;</span>
+      <span class="identifier">begin</span><span class="special">(</span><span class="identifier">forest_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;&amp;</span> <span class="identifier">h</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="identifier">inorder</span><span class="special">::</span><span class="identifier">iterator</span><span class="special">&lt;</span><span class="identifier">forest_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;::</span><span class="identifier">const_cursor</span><span class="special">&gt;</span>
+      <span class="identifier">cbegin</span><span class="special">(</span><span class="identifier">forest_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">h</span><span class="special">);</span>
+  <span class="special">}</span> <span class="comment">// namespace inorder</span>
+<span class="special">}</span> <span class="comment">// namespace tr2</span>
+<span class="special">}</span> <span class="comment">// namespace std</span>
+</div><p>
+                <span class="bold"><strong>Header <code class="literal">&lt;multiway_tree&gt;</code>
+                synopsis</strong></span>
+              </p><div class="programlisting"><span class="keyword">namespace</span> <span class="identifier">std</span> <span class="special">{</span>
+<span class="keyword">namespace</span> <span class="identifier">tr2</span> <span class="special">{</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Hierarchy</span> <span class="special">=</span> <span class="identifier">nary_tree</span><span class="special">&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span> <span class="special">&gt;</span> <span class="special">&gt;</span>
+    <span class="keyword">class</span> <span class="identifier">multiway_tree</span><span class="special">;</span>
+
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span>
+    <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">==(</span>  <span class="identifier">multiway_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+                      <span class="identifier">multiway_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">!=(</span>  <span class="identifier">multiway_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+                      <span class="identifier">multiway_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span>
+    <span class="keyword">void</span> <span class="identifier">swap</span><span class="special">(</span>  <span class="identifier">multiway_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;&amp;</span> <span class="identifier">x</span><span class="special">,</span>
+                <span class="identifier">multiway_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;&amp;</span> <span class="identifier">y</span><span class="special">);</span>
+  <span class="keyword">namespace</span> <span class="identifier">inorder</span> <span class="special">{</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span>
+    <span class="identifier">inorder</span><span class="special">::</span><span class="identifier">iterator</span><span class="special">&lt;</span><span class="identifier">multiway_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;::</span><span class="identifier">cursor</span><span class="special">&gt;</span>
+      <span class="identifier">begin</span><span class="special">(</span><span class="identifier">multiway_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;&amp;</span> <span class="identifier">h</span><span class="special">);</span>
+  <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Alloc</span><span class="special">&gt;</span>
+    <span class="identifier">inorder</span><span class="special">::</span><span class="identifier">iterator</span><span class="special">&lt;</span><span class="identifier">multiway_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;::</span><span class="identifier">const_cursor</span><span class="special">&gt;</span>
+      <span class="identifier">cbegin</span><span class="special">(</span><span class="identifier">multiway_tree</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Hierarchy</span><span class="special">&gt;</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">h</span><span class="special">);</span>
+  <span class="special">}</span> <span class="comment">// namespace inorder</span>
+<span class="special">}</span> <span class="comment">// namespace tr2</span>
+<span class="special">}</span> <span class="comment">// namespace std</span>
+</div></li></ol></div><div class="section tree_proposal_containers_hierarchy_tree_bintree" title="2.1.1.4.1. Template class binary_tree [tr.hierarchy.bintree]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.bintree">2.1.1.4.1. <a class="link" href="#tree.proposal.containers.hierarchy.tree.bintree" title="2.1.1.4.1. Template class binary_tree [tr.hierarchy.bintree]">Template
+            class <code class="literal">binary_tree</code> <span class="tr_section_label">[tr.hierarchy.bintree]</span></a></h6></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_bintree_types" title="2.1.1.4.1.1. binary_tree types [tr.hierarchy.bintree.types]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.bintree.types">2.1.1.4.1.1. <a class="link" href="#tree.proposal.containers.hierarchy.tree.bintree.types" title="2.1.1.4.1.1. binary_tree types [tr.hierarchy.bintree.types]"><code class="literal">binary_tree</code>
+              types <span class="tr_section_label">[tr.hierarchy.bintree.types]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_bintree_cons" title="2.1.1.4.1.2. binary_tree constructors, copy, and assignment [tr.hierarchy.bintree.cons]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.bintree.cons">2.1.1.4.1.2. <a class="link" href="#tree.proposal.containers.hierarchy.tree.bintree.cons" title="2.1.1.4.1.2. binary_tree constructors, copy, and assignment [tr.hierarchy.bintree.cons]"><code class="literal">binary_tree</code>
+              constructors, copy, and assignment <span class="tr_section_label">[tr.hierarchy.bintree.cons]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_bintree_cursors" title="2.1.1.4.1.3. binary_tree cursors [tr.hierarchy.bintree.cursors]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.bintree.cursors">2.1.1.4.1.3. <a class="link" href="#tree.proposal.containers.hierarchy.tree.bintree.cursors" title="2.1.1.4.1.3. binary_tree cursors [tr.hierarchy.bintree.cursors]"><code class="literal">binary_tree</code>
+              cursors <span class="tr_section_label">[tr.hierarchy.bintree.cursors]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_bintree_modifiers" title="2.1.1.4.1.4. binary_tree modifiers [tr.hierarchy.bintree.modifiers]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.bintree.modifiers">2.1.1.4.1.4. <a class="link" href="#tree.proposal.containers.hierarchy.tree.bintree.modifiers" title="2.1.1.4.1.4. binary_tree modifiers [tr.hierarchy.bintree.modifiers]"><code class="literal">binary_tree</code>
+              modifiers <span class="tr_section_label">[tr.hierarchy.bintree.modifiers]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_bintree_special" title="2.1.1.4.1.5. binary_tree specialized algorithms [tr.hierarchy.bintree.special]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.bintree.special">2.1.1.4.1.5. <a class="link" href="#tree.proposal.containers.hierarchy.tree.bintree.special" title="2.1.1.4.1.5. binary_tree specialized algorithms [tr.hierarchy.bintree.special]"><code class="literal">binary_tree</code>
+              specialized algorithms <span class="tr_section_label">[tr.hierarchy.bintree.special]</span></a></h6></div></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_narytree" title="2.1.1.4.2. Template class nary_tree [tr.hierarchy.narytree]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.narytree">2.1.1.4.2. <a class="link" href="#tree.proposal.containers.hierarchy.tree.narytree" title="2.1.1.4.2. Template class nary_tree [tr.hierarchy.narytree]">Template
+            class <code class="literal">nary_tree</code> <span class="tr_section_label">[tr.hierarchy.narytree]</span></a></h6></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_narytree_types" title="2.1.1.4.2.1. nary_tree types [tr.hierarchy.narytree.types]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.narytree.types">2.1.1.4.2.1. <a class="link" href="#tree.proposal.containers.hierarchy.tree.narytree.types" title="2.1.1.4.2.1. nary_tree types [tr.hierarchy.narytree.types]"><code class="literal">nary_tree</code>
+              types <span class="tr_section_label">[tr.hierarchy.narytree.types]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_narytree_cons" title="2.1.1.4.2.2. nary_tree constructors, copy, and assignment [tr.hierarchy.narytree.cons]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.narytree.cons">2.1.1.4.2.2. <a class="link" href="#tree.proposal.containers.hierarchy.tree.narytree.cons" title="2.1.1.4.2.2. nary_tree constructors, copy, and assignment [tr.hierarchy.narytree.cons]"><code class="literal">nary_tree</code>
+              constructors, copy, and assignment <span class="tr_section_label">[tr.hierarchy.narytree.cons]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_narytree_cursors" title="2.1.1.4.2.3. nary_tree cursors [tr.hierarchy.narytree.cursors]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.narytree.cursors">2.1.1.4.2.3. <a class="link" href="#tree.proposal.containers.hierarchy.tree.narytree.cursors" title="2.1.1.4.2.3. nary_tree cursors [tr.hierarchy.narytree.cursors]"><code class="literal">nary_tree</code>
+              cursors <span class="tr_section_label">[tr.hierarchy.narytree.cursors]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_narytree_capacity" title="2.1.1.4.2.4. nary_tree capacity [tr.hierarchy.narytree.capacity]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.narytree.capacity">2.1.1.4.2.4. <a class="link" href="#tree.proposal.containers.hierarchy.tree.narytree.capacity" title="2.1.1.4.2.4. nary_tree capacity [tr.hierarchy.narytree.capacity]"><code class="literal">nary_tree</code>
+              capacity <span class="tr_section_label">[tr.hierarchy.narytree.capacity]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_narytree_modifiers" title="2.1.1.4.2.5. nary_tree modifiers [tr.hierarchy.narytree.modifiers]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.narytree.modifiers">2.1.1.4.2.5. <a class="link" href="#tree.proposal.containers.hierarchy.tree.narytree.modifiers" title="2.1.1.4.2.5. nary_tree modifiers [tr.hierarchy.narytree.modifiers]"><code class="literal">nary_tree</code>
+              modifiers <span class="tr_section_label">[tr.hierarchy.narytree.modifiers]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_narytree_special" title="2.1.1.4.2.6. nary_tree specialized algorithms [tr.hierarchy.narytree.special]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.narytree.special">2.1.1.4.2.6. <a class="link" href="#tree.proposal.containers.hierarchy.tree.narytree.special" title="2.1.1.4.2.6. nary_tree specialized algorithms [tr.hierarchy.narytree.special]"><code class="literal">nary_tree</code>
+              specialized algorithms <span class="tr_section_label">[tr.hierarchy.narytree.special]</span></a></h6></div></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors" title="2.1.1.4.3. Hierarchy adaptors [tr.hierarchy.adaptors]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors">2.1.1.4.3. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors" title="2.1.1.4.3. Hierarchy adaptors [tr.hierarchy.adaptors]">Hierarchy
+            adaptors <span class="tr_section_label">[tr.hierarchy.adaptors]</span></a></h6></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_foresttree" title="2.1.1.4.3.1. Template class forest_tree [tr.hierarchy.foresttree]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree">2.1.1.4.3.1. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.foresttree" title="2.1.1.4.3.1. Template class forest_tree [tr.hierarchy.foresttree]">Template
+              class <code class="literal">forest_tree</code> <span class="tr_section_label">[tr.hierarchy.foresttree]</span></a></h6></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_foresttree_types" title="2.1.1.4.3.1.1. forest_tree types [tr.hierarchy.foresttree.types]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.types">2.1.1.4.3.1.1. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.foresttree.types" title="2.1.1.4.3.1.1. forest_tree types [tr.hierarchy.foresttree.types]"><code class="literal">forest_tree</code>
+                types <span class="tr_section_label">[tr.hierarchy.foresttree.types]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_foresttree_cons" title="2.1.1.4.3.1.2. forest_tree constructors, copy, and assignment [tr.hierarchy.foresttree.cons]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.cons">2.1.1.4.3.1.2. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.foresttree.cons" title="2.1.1.4.3.1.2. forest_tree constructors, copy, and assignment [tr.hierarchy.foresttree.cons]"><code class="literal">forest_tree</code>
+                constructors, copy, and assignment <span class="tr_section_label">[tr.hierarchy.foresttree.cons]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_foresttree_cursors" title="2.1.1.4.3.1.3. forest_tree cursors [tr.hierarchy.foresttree.cursors]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.cursors">2.1.1.4.3.1.3. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.foresttree.cursors" title="2.1.1.4.3.1.3. forest_tree cursors [tr.hierarchy.foresttree.cursors]"><code class="literal">forest_tree</code>
+                cursors <span class="tr_section_label">[tr.hierarchy.foresttree.cursors]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_foresttree_modifiers" title="2.1.1.4.3.1.4. forest_tree modifiers [tr.hierarchy.foresttree.modifiers]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.modifiers">2.1.1.4.3.1.4. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.foresttree.modifiers" title="2.1.1.4.3.1.4. forest_tree modifiers [tr.hierarchy.foresttree.modifiers]"><code class="literal">forest_tree</code>
+                modifiers <span class="tr_section_label">[tr.hierarchy.foresttree.modifiers]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_foresttree_special" title="2.1.1.4.3.1.5. forest_tree specialized algorithms [tr.hierarchy.foresttree.special]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.foresttree.special">2.1.1.4.3.1.5. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.foresttree.special" title="2.1.1.4.3.1.5. forest_tree specialized algorithms [tr.hierarchy.foresttree.special]"><code class="literal">forest_tree</code>
+                specialized algorithms <span class="tr_section_label">[tr.hierarchy.foresttree.special]</span></a></h6></div></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_multiwaytree" title="2.1.1.4.3.2. Template class multiway_tree [tr.hierarchy.multiwaytree]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree">2.1.1.4.3.2. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree" title="2.1.1.4.3.2. Template class multiway_tree [tr.hierarchy.multiwaytree]">Template
+              class <code class="literal">multiway_tree</code> <span class="tr_section_label">[tr.hierarchy.multiwaytree]</span></a></h6></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_multiwaytree_types" title="2.1.1.4.3.2.1. multiway_tree types [tr.hierarchy.multiwaytree.types]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.types">2.1.1.4.3.2.1. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.types" title="2.1.1.4.3.2.1. multiway_tree types [tr.hierarchy.multiwaytree.types]"><code class="literal">multiway_tree</code>
+                types <span class="tr_section_label">[tr.hierarchy.multiwaytree.types]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_multiwaytree_cons" title="2.1.1.4.3.2.2. multiway_tree constructors, copy, and assignment [tr.hierarchy.multiwaytree.cons]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.cons">2.1.1.4.3.2.2. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.cons" title="2.1.1.4.3.2.2. multiway_tree constructors, copy, and assignment [tr.hierarchy.multiwaytree.cons]"><code class="literal">multiway_tree</code>
+                constructors, copy, and assignment <span class="tr_section_label">[tr.hierarchy.multiwaytree.cons]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_multiwaytree_cursors" title="2.1.1.4.3.2.3. multiway_tree cursors [tr.hierarchy.multiwaytree.cursors]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.cursors">2.1.1.4.3.2.3. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.cursors" title="2.1.1.4.3.2.3. multiway_tree cursors [tr.hierarchy.multiwaytree.cursors]"><code class="literal">multiway_tree</code>
+                cursors <span class="tr_section_label">[tr.hierarchy.multiwaytree.cursors]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_multiwaytree_capacity" title="2.1.1.4.3.2.4. multiway_tree capacity [tr.hierarchy.multiwaytree.capacity]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.capacity">2.1.1.4.3.2.4. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.capacity" title="2.1.1.4.3.2.4. multiway_tree capacity [tr.hierarchy.multiwaytree.capacity]"><code class="literal">multiway_tree</code>
+                capacity <span class="tr_section_label">[tr.hierarchy.multiwaytree.capacity]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_multiwaytree_modifiers" title="2.1.1.4.3.2.5. multiway_tree modifiers [tr.hierarchy.multiwaytree.modifiers]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.modifiers">2.1.1.4.3.2.5. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.modifiers" title="2.1.1.4.3.2.5. multiway_tree modifiers [tr.hierarchy.multiwaytree.modifiers]"><code class="literal">multiway_tree</code>
+                modifiers <span class="tr_section_label">[tr.hierarchy.multiwaytree.modifiers]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_multiwaytree_special" title="2.1.1.4.3.2.6. multiway_tree specialized algorithms [tr.hierarchy.multiwaytree.special]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.special">2.1.1.4.3.2.6. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.multiwaytree.special" title="2.1.1.4.3.2.6. multiway_tree specialized algorithms [tr.hierarchy.multiwaytree.special]"><code class="literal">multiway_tree</code>
+                specialized algorithms <span class="tr_section_label">[tr.hierarchy.multiwaytree.special]</span></a></h6></div></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_augment" title="2.1.1.4.3.3. Augmenting hierarchy adaptors [tr.hierarchy.augment]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.augment">2.1.1.4.3.3. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.augment" title="2.1.1.4.3.3. Augmenting hierarchy adaptors [tr.hierarchy.augment]">Augmenting
+              hierarchy adaptors <span class="tr_section_label">[tr.hierarchy.augment]</span></a></h6></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_augment_ranktree" title="2.1.1.4.3.3.1. Template class rank_tree [tr.hierarchy.ranktree]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.augment.ranktree">2.1.1.4.3.3.1. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.augment.ranktree" title="2.1.1.4.3.3.1. Template class rank_tree [tr.hierarchy.ranktree]">Template
+                class <code class="literal">rank_tree</code> <span class="tr_section_label">[tr.hierarchy.ranktree]</span></a></h6></div></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_balance" title="2.1.1.4.3.4. Balancing hierarchy adaptors [tr.hierarchy.balance]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.balance">2.1.1.4.3.4. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.balance" title="2.1.1.4.3.4. Balancing hierarchy adaptors [tr.hierarchy.balance]">Balancing
+              hierarchy adaptors <span class="tr_section_label">[tr.hierarchy.balance]</span></a></h6></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_balance_cons" title="2.1.1.4.3.4.1. Balancing adaptor constructors, copy, and assigment [tr.hierarchy.balance.cons]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.balance.cons">2.1.1.4.3.4.1. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.balance.cons" title="2.1.1.4.3.4.1. Balancing adaptor constructors, copy, and assigment [tr.hierarchy.balance.cons]">Balancing
+                adaptor constructors, copy, and assigment <span class="tr_section_label">[tr.hierarchy.balance.cons]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_balance_map" title="2.1.1.4.3.4.2. Balancing adaptor map operations [tr.hierarchy.balance.map]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.balance.map">2.1.1.4.3.4.2. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.balance.map" title="2.1.1.4.3.4.2. Balancing adaptor map operations [tr.hierarchy.balance.map]">Balancing
+                adaptor map operations <span class="tr_section_label">[tr.hierarchy.balance.map]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_balance_modifiers" title="2.1.1.4.3.4.3. Balancing adaptor modifiers [tr.hierarchy.balance.modifiers]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.balance.modifiers">2.1.1.4.3.4.3. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.balance.modifiers" title="2.1.1.4.3.4.3. Balancing adaptor modifiers [tr.hierarchy.balance.modifiers]">Balancing
+                adaptor modifiers <span class="tr_section_label">[tr.hierarchy.balance.modifiers]</span></a></h6></div></div></div></div><div class="section tree_proposal_containers_hierarchy_tree_adaptors_balance_special" title="2.1.1.4.3.4.4. Balancing adaptor specialized algorithms [tr.hierarchy.balance.special]"><div class="titlepage"><div><div><h6 class="title" id="tree.proposal.containers.hierarchy.tree.adaptors.balance.special">2.1.1.4.3.4.4. <a class="link" href="#tree.proposal.containers.hierarchy.tree.adaptors.balance.special" title="2.1.1.4.3.4.4. Balancing adaptor specialized algorithms [tr.hierarchy.balance.special]">Balancing
+                adaptor specialized algorithms <span class="tr_section_label">[tr.hierarchy.balance.special]</span></a></h6></div></div></div></div></div></div></div></div></div></div><div class="section tree_references" title="3. References"><div class="titlepage"><div><div><h2 class="title" style="clear: both" id="tree.references">3. <a class="link" href="#tree.references" title="3. References">References</a></h2></div></div></div><div class="variablelist" title="References"><div class="variablelist-title">References</div><dl><dt><span class="term">austern</span></dt><dd><p>
             Austern, Matthew H.; Stroustrup, Bjarne; Thorup, Mikkel; Wilikinson,
             John. <span class="emphasis"><em>Untangling the Balancing and Searching of Balanced Binary
             Search Trees</em></span>, Software: Practice and Experience 33(13): 1273-1298
@@ -1138,5 +1574,5 @@
             Peeters, Kasper. <span class="emphasis"><em>tree.hh: an STL-like C++ tree class</em></span>,
             http://www.aei.mpg.de/~peekas/tree/
           </p></dd><dt><span class="term">rivera</span></dt><dd><p>
-            Rivera, René. <span class="emphasis"><em>RankTree.h</em></span>, http://redshift-software.com/~grafik/RankTree.h
+            Rivera, René. <span class="emphasis"><em>RankTree.h</em></span>, http://redshift-software.com/~grafik/RankTree.h
           </p></dd></dl></div></div></div></body></html>

Added: sandbox/tree/libs/tree/proposal/tr-algorithms.qbk
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/tr-algorithms.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,12 @@
+[/
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2011, René Rivera
+ /
+ /  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)
+ /]
+
+[section:tr.containers M Algorithms library]
+
+[endsect] [/tr.algorithms]

Added: sandbox/tree/libs/tree/proposal/tr-containers.qbk
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/tr-containers.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,335 @@
+[/
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2011, René Rivera
+ /
+ /  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)
+ /]
+
+[section:containers Containers library [label tr.containers]]
+
+[section:hierarchy Hierarchy containers [label tr.hierarchy]]
+
+[section:req Hierarchy containers requirements [label tr.hierarchy.req]]
+
+[ordered_list
+
+[A hierarchy is an object that stores a finite set of objects, all of the same type, in a hierarchical manner. Hierarchies introduce a cursor concept for navigation instead of iterators. The library provides two kinds of native hierarchies: =binary_tree=, and =nary_tree=, along with hierarchy-yielding hierarchy adaptors =forest_tree=, and =multiway_tree=.]
+
+[Hierarchy containers conform to the requirements of Containers (\[lib.container.requirements\]), except that the expressions in Table 1 are not required to be valid, where a and b denote values of a type X, and X is a hierarchy container class:
+
+    [table:table1 Container requirements that are not required for hierarchy containers
+        [[unsupported expression]]
+        [[[^X::iterator]]]
+        [[[^X::const_iterator]]]
+        [[[^X::reverse_iterator]]]
+        [[[^X::const_reverse_iterator]]]
+        [[[^a.begin()]]]
+        [[[^a.end()]]]
+        [[[^a.rbegin()]]]
+        [[[^a.rend()]]]
+        [[[^a < b]]]
+        [[[^a > b]]]
+        [[[^a <= b]]]
+        [[[^a >= b]]]
+    ]
+]
+
+[Non-constant complexity requirements in this clause are stated in one of a number of possible different ways: unless specified otherwise, they are expressed in terms of the number of operations =n=, which stands for the total number of elements in the hierarchy; in some cases, however, they are stated in terms of another value.]
+
+[In Table 2: =X= denotes a hierarchy class containing objects of type =T= and =a= denotes a value of type =X=.
+
+    [table:table2 Hierarchy requirements (in addition to container)
+        [[expression]
+         [return type]
+         [assertion/note[br]
+            pre/post-condition]
+         [complexity]]
+        [[[^X::cursor]]
+         [cursor type pointing to =T=]
+         [any cursor category]
+         [compile time]]
+        [[[^X::const_cursor]]
+         [cursor type pointing to =const T=]
+         [any cursor category]
+         [compile time]]
+        [[[^a.root()]]
+         [=iterator= for mutable =a=;[br]
+            =const_iterator= for constant =a=]
+         [__nbsp__]
+         [constant]]
+        [[[^a.croot()]]
+         [=const_iterator=]
+         [__nbsp__]
+         [constant]]
+        [[[^a.shoot()]]
+         [=iterator= for mutable =a=;[br]
+            =const_iterator= for constant =a=]
+         [__nbsp__]
+         [(Note A)]]
+        [[[^a.cshoot()]]
+         [=const_iterator=]
+         [__nbsp__]
+         [(Note A)]]
+        [[[^typename X::template rebind<U>::other]]
+         [=Y=]
+         [For all =U= (including =T=), =Y::template rebind<T>::other= is =X=.]
+         [compile time]]
+    ]
+
+Notes: Those entries marked "(Note A)" should have at worst linear complexity. See the individual hierarchy containers for specific complexity.
+]
+
+[=root()= and =croot()= return a cursor which is the on-top value for the hierarchy. =shoot()= and =cshoot()= return a cursor which is the past-the-end value that is found one past the hierarchy's rightmost element. If the hierarchy is empty, then [^root() == shoot();]]
+
+[Copy constructors for all hierarchy types defined in this clause copy the allocator argument from their respective first parameters. All other constructors for these hierarchy types take an =Allocator&= argument (20.1.5). A copy of this argument is used for any memory allocation performed, by these constructors and by all member functions, during the lifetime of each hierarchy object. In all hierarchy types defined in this clause, the member =get_allocator()= returns a copy of the Allocator object used to construct the hierarchy.
+]
+
+[The member class template =rebind= in the table above is effectively a typedef template: if the name =Hierarchy= is bound to =SomeHierarchy<T>=, then =Hierarchy::rebind<U>::other= is the same type as =SomeHierarchy<U>=. Additionally, because of the related assertion, given =SomeHierarchy<T,R0,...,Rn>= for all template arguments present is bound to the name =Hierarchy=, then =Hierarchy::rebind<U>::other= is the same type as =SomeHierarchy<U,S0,...,Sn>= such that the types =S0= through =Sn= are the same as =R0= through =Rn=, respectively, when =U= is the same type as =T=.
+]
+
+[A hierarchy satisfying the requirements shown in Table 3 is called a /mutable hierarchy/. In Table 3, =X= denotes a hierarchy class, =a= denotes a value of =X=, =c= denotes a valid, non-on-top cursor satisfying input cursor requirements, =p= denotes a valid, non-on-top cursor to =a=, =q= denotes a valid, dereferenceable cursor to =a=, and =t= denotes a value of =X::value_type=.
+
+    [table:table3 Mutable hierarchy requirements
+        [[expression]
+         [return type]
+         [assertion/note[br]
+            pre/post-condition]
+         [complexity]]
+        [[[^a.insert(p,t)]]
+         [=cursor=]
+         [inserts a copy of =t= before =p=]
+         [(Note A)]]
+        [[[^a.clear(q)]]
+         [=void=]
+         [deletes the subtree of =q= and the element =q= points to.[br]
+            pre: =q= is dereferenceable.]
+         [Should be at worst linear in the the number of elements in the subtree of =q= plus the distance to =q='s parent's =end()=.]]
+        [[[^a.clear()]]
+         [=void=]
+         [=while (a.size()) clear(a.begin());=[br]
+            post: [^a.size() == 0]]
+         [(Note A)]]
+    ]
+
+Notes: Those entries marked "(Note A)" should have at worst linear complexity. See the individual hierarchy containers for specific complexity.]
+
+[The cursor returned from =a.insert(p,t)= points to the copy of =t= inserted into =a=. Its parent cursor is the same as that of =p=.]
+
+]
+
+[endsect] [/req]
+
+[section:plain Plain hierarchies [label tr.hierarchy.plain]]
+
+[ordered_list
+
+[A hierarchy is called plain hierarchy if its cursor and const_cursor types satisfy the requirements of a plain cursor.]
+
+[The library provides one native kind of plain hierarchy, nary_tree, and a hierarchy adaptor that in turn yields a plain hierarchy, forest_tree.]
+
+[For a mutable plain hierarchy, the following expressions as shown in Table 4, is additionally required to be valid:
+
+    [table:table4 Plain hierarchy requirements
+        [[expression]
+         [return type]
+         [assertion/note[br]
+            pre/post-condition]
+         [complexity]]
+        [[[^a.insert(p,c)]]
+         [=cursor=]
+         [inserts a copy of the subtree of =c= before =p=.[br]
+            pre: =c= is dereferenceable.]
+         [Should be at worst linear in the the number of elements in the subtree of =c= plus the distance to =p='s parent's =end()=.]]
+        [[[^a.insert_above(p,t)]]
+         [=cursor=]
+         [inserts a copy of =t= as child of =p='s parent and new parent of =p= and its siblings.[br]
+            pre: =c= is dereferenceable.]
+         [Linear in the the number =p='s siblings.]]
+    ]
+]
+
+[The cursor returned from =a.insert(p,c)= points to the copy of the element that =c= points to, inserted into =a=. Its parent cursor is the same as that of =p=.]
+
+]
+
+[endsect] [/plain]
+
+[section:multiway Multiway hierarchies [label tr.hierarchy.multiway]]
+
+[ordered_list
+
+[A hierarchy is called multiway hierarchy if its =cursor= and =const_cursor= types satisfy the requirements of a multiway cursor.]
+
+[The library provides one native kind of multiway hierarchy, =binary_tree=, and a hierarchy adaptor that in turn yields a multiway hierarchy, =multiway_tree=.]
+
+[For a mutable multiway hierarchy, the semantics of some expressions from Table 3 are modified as shown in Table 5.
+
+    [table:table5 Multiway hierarchy requirements
+        [[expression]
+         [return type]
+         [assertion/note[br]
+            pre/post-condition]
+         [complexity]]
+        [[[^a.clear(q)]]
+         [=void=]
+         [deletes the subtree of =q=.[br]
+If =q= is dereferenceable, the expression also deletes the element =q= points to.[br]
+If =q= is past-the-end, the expression deletes the element =q='s predecessor points to.[br]
+If after either of these steps =q= has only a non-empty past-the-end child, that child's children become =q='s children instead. Finally, that child is deleted.[br]
+pre: =q= is internal.]
+         [Should be at worst linear in the the number of elements in the subtree of =c= plus the distance to =p='s parent's =end()=.]]
+    ]
+]
+
+]
+
+[endsect] [/multiway]
+
+[section:tree Trees [label tr.hierarchy.tree]]
+
+[ordered_list
+
+[
+Headers =<binary_tree>=, =<nary_tree>=, =<forest_tree>=, and =<multiway_tree>=.
+
+[*Header =<binary_tree>= synopsis]
+
+``
+namespace std {
+namespace tr2 {
+  template <class T, class Alloc = std::allocator<T> >
+    class binary_tree;
+
+  template <class T, class Alloc>
+    bool operator==(  binary_tree<T, Alloc> const& x,
+                      binary_tree<T, Alloc> const& y);
+  template <class T, class Alloc>
+    bool operator!=(  binary_tree<T, Alloc> const& x,
+                      binary_tree<T, Alloc> const& y);
+  template <class T, class Alloc>
+    void swap(  binary_tree<T, Alloc>& x,
+                binary_tree<T, Alloc>& y);
+  namespace inorder {
+  template <class Tp, class Alloc>
+    inorder::iterator<binary_tree<Tp, Alloc>::cursor>
+      begin(binary_tree<Tp, Alloc>& h);
+  template <class Tp, class Alloc>
+    inorder::iterator<binary_tree<Tp, Alloc>::const_cursor>
+      cbegin(binary_tree<Tp, Alloc> const& h);
+  } // namespace inorder
+
+} // namespace tr2
+} // namespace std
+``
+
+[*Header =<nary_tree>= synopsis]
+
+``
+namespace std {
+namespace tr2 {
+  template <class T, class Alloc = std::allocator<T> >
+    class nary_tree;
+
+  template <class T, class Alloc>
+    bool operator==(  binary_tree<T, Alloc> const& x,
+                      binary_tree<T, Alloc> const& y);
+  template <class T, class Alloc>
+    bool operator!=(  binary_tree<T, Alloc> const& x,
+                      binary_tree<T, Alloc> const& y);
+  template <class T, class Alloc>
+  void swap(  nary_tree<T, Alloc>& x,
+              nary_tree<T, Alloc>& y);
+  namespace inorder {
+  template <class T, class Alloc>
+    inorder::iterator<binary_tree<T, Alloc>::cursor>
+      begin(binary_tree<T, Alloc>& h);
+  template <class T, class Alloc>
+    inorder::iterator<binary_tree<T, Alloc>::const_cursor>
+      cbegin(binary_tree<T, Alloc> const& h);
+  } // namespace inorder
+} // namespace tr2
+} // namespace std
+``
+
+[*Header =<forest_tree>= synopsis]
+
+``
+namespace std {
+namespace tr2 {
+  template <class T, class Hierarchy = binary_tree<T> >
+    class forest_tree;
+
+  template <class T, class Hierarchy>
+    bool operator==(  forest_tree<T, Hierarchy> const& x,
+                      forest_tree<T, Hierarchy> const& y);
+  template <class T, class Alloc>
+    bool operator!=(  forest_tree<T, Hierarchy> const& x,
+                      forest_tree<T, Hierarchy> const& y);
+  template <class T, class Hierarchy>
+  void swap(  forest_tree<T, Hierarchy>& x,
+              forest_tree<T, Hierarchy>& y);
+  namespace inorder {
+  template <class T, class Hierarchy>
+    inorder::iterator<forest_tree<T, Hierarchy>::cursor>
+      begin(forest_tree<T, Hierarchy>& h);
+  template <class T, class Alloc>
+    inorder::iterator<forest_tree<T, Hierarchy>::const_cursor>
+      cbegin(forest_tree<T, Hierarchy> const& h);
+  } // namespace inorder
+} // namespace tr2
+} // namespace std
+
+``
+
+[*Header =<multiway_tree>= synopsis]
+
+``
+namespace std {
+namespace tr2 {
+  template <class T, class Hierarchy = nary_tree< std::vector<T> > >
+    class multiway_tree;
+
+  template <class T, class Hierarchy>
+    bool operator==(  multiway_tree<T, Hierarchy> const& x,
+                      multiway_tree<T, Hierarchy> const& y);
+  template <class T, class Alloc>
+    bool operator!=(  multiway_tree<T, Hierarchy> const& x,
+                      multiway_tree<T, Hierarchy> const& y);
+  template <class T, class Hierarchy>
+    void swap(  multiway_tree<T, Hierarchy>& x,
+                multiway_tree<T, Hierarchy>& y);
+  namespace inorder {
+  template <class T, class Hierarchy>
+    inorder::iterator<multiway_tree<T, Hierarchy>::cursor>
+      begin(multiway_tree<T, Hierarchy>& h);
+  template <class T, class Alloc>
+    inorder::iterator<multiway_tree<T, Hierarchy>::const_cursor>
+      cbegin(multiway_tree<T, Hierarchy> const& h);
+  } // namespace inorder
+} // namespace tr2
+} // namespace std
+
+``
+]
+
+]
+
+[include tr-hierarchy-bintree.qbk]
+[include tr-hierarchy-narytree.qbk]
+
+[section:adaptors Hierarchy adaptors [label tr.hierarchy.adaptors]]
+
+[include tr-hierarchy-foresttree.qbk]
+[include tr-hierarchy-multiwaytree.qbk]
+[include tr-hierarchy-augment.qbk]
+[include tr-hierarchy-balance.qbk]
+
+[endsect] [/adaptors]
+
+[endsect] [/tree]
+
+[endsect] [/hierarchy]
+
+[endsect] [/containers]

Added: sandbox/tree/libs/tree/proposal/tr-hierarchy-augment.qbk
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/tr-hierarchy-augment.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,16 @@
+[/
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2012, René Rivera
+ /
+ /  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)
+ /]
+
+[section:augment Augmenting hierarchy adaptors [label tr.hierarchy.augment]]
+
+[section:ranktree Template class =rank_tree= [label tr.hierarchy.ranktree]]
+
+[endsect] [/ranktree]
+
+[endsect] [/augment]

Added: sandbox/tree/libs/tree/proposal/tr-hierarchy-balance.qbk
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/tr-hierarchy-balance.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,33 @@
+[/
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2012, René Rivera
+ /
+ /  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)
+ /]
+
+[section:balance Balancing hierarchy adaptors [label tr.hierarchy.balance]]
+
+
+[section:cons Balancing adaptor constructors, copy, and assigment [label tr.hierarchy.balance.cons]]
+
+[endsect] [/cons]
+
+
+[section:map Balancing adaptor map operations [label tr.hierarchy.balance.map]]
+
+[endsect] [/map]
+
+
+[section:modifiers Balancing adaptor modifiers [label tr.hierarchy.balance.modifiers]]
+
+[endsect] [/modifiers]
+
+
+[section:special Balancing adaptor specialized algorithms [label tr.hierarchy.balance.special]]
+
+[endsect] [/special]
+
+
+[endsect] [/balance]

Added: sandbox/tree/libs/tree/proposal/tr-hierarchy-bintree.qbk
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/tr-hierarchy-bintree.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,38 @@
+[/
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2012, René Rivera
+ /
+ /  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)
+ /]
+
+[section:bintree Template class =binary_tree=  [label tr.hierarchy.bintree]]
+
+
+[section:types =binary_tree= types [label tr.hierarchy.bintree.types]]
+
+[endsect] [/types]
+
+
+[section:cons =binary_tree= constructors, copy, and assignment [label tr.hierarchy.bintree.cons]]
+
+[endsect] [/cons]
+
+
+[section:cursors =binary_tree= cursors [label tr.hierarchy.bintree.cursors]]
+
+[endsect] [/cursors]
+
+
+[section:modifiers =binary_tree= modifiers [label tr.hierarchy.bintree.modifiers]]
+
+[endsect] [/modifiers]
+
+
+[section:special =binary_tree= specialized algorithms [label tr.hierarchy.bintree.special]]
+
+[endsect] [/special]
+
+
+[endsect] [/bintree]

Added: sandbox/tree/libs/tree/proposal/tr-hierarchy-foresttree.qbk
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/tr-hierarchy-foresttree.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,38 @@
+[/
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2012, René Rivera
+ /
+ /  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)
+ /]
+
+[section:foresttree Template class =forest_tree= [label tr.hierarchy.foresttree]]
+
+
+[section:types =forest_tree= types [label tr.hierarchy.foresttree.types]]
+
+[endsect] [/types]
+
+
+[section:cons =forest_tree= constructors, copy, and assignment [label tr.hierarchy.foresttree.cons]]
+
+[endsect] [/cons]
+
+
+[section:cursors =forest_tree= cursors [label tr.hierarchy.foresttree.cursors]]
+
+[endsect] [/cursors]
+
+
+[section:modifiers =forest_tree= modifiers [label tr.hierarchy.foresttree.modifiers]]
+
+[endsect] [/modifiers]
+
+
+[section:special =forest_tree= specialized algorithms [label tr.hierarchy.foresttree.special]]
+
+[endsect] [/special]
+
+
+[endsect] [/foresttree]

Added: sandbox/tree/libs/tree/proposal/tr-hierarchy-multiwaytree.qbk
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/tr-hierarchy-multiwaytree.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,43 @@
+[/
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2012, René Rivera
+ /
+ /  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)
+ /]
+
+[section:multiwaytree Template class =multiway_tree= [label tr.hierarchy.multiwaytree]]
+
+
+[section:types =multiway_tree= types [label tr.hierarchy.multiwaytree.types]]
+
+[endsect] [/types]
+
+
+[section:cons =multiway_tree= constructors, copy, and assignment [label tr.hierarchy.multiwaytree.cons]]
+
+[endsect] [/cons]
+
+
+[section:cursors =multiway_tree= cursors [label tr.hierarchy.multiwaytree.cursors]]
+
+[endsect] [/cursors]
+
+
+[section:capacity =multiway_tree= capacity [label tr.hierarchy.multiwaytree.capacity]]
+
+[endsect] [/capacity]
+
+
+[section:modifiers =multiway_tree= modifiers [label tr.hierarchy.multiwaytree.modifiers]]
+
+[endsect] [/modifiers]
+
+
+[section:special =multiway_tree= specialized algorithms [label tr.hierarchy.multiwaytree.special]]
+
+[endsect] [/special]
+
+
+[endsect] [/multiwaytree]

Added: sandbox/tree/libs/tree/proposal/tr-hierarchy-narytree.qbk
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/tr-hierarchy-narytree.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,43 @@
+[/
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2012, René Rivera
+ /
+ /  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)
+ /]
+
+[section:narytree Template class =nary_tree= [label tr.hierarchy.narytree]]
+
+
+[section:types =nary_tree= types [label tr.hierarchy.narytree.types]]
+
+[endsect] [/types]
+
+
+[section:cons =nary_tree= constructors, copy, and assignment [label tr.hierarchy.narytree.cons]]
+
+[endsect] [/cons]
+
+
+[section:cursors =nary_tree= cursors [label tr.hierarchy.narytree.cursors]]
+
+[endsect] [/cursors]
+
+
+[section:capacity =nary_tree= capacity [label tr.hierarchy.narytree.capacity]]
+
+[endsect] [/capacity]
+
+
+[section:modifiers =nary_tree= modifiers [label tr.hierarchy.narytree.modifiers]]
+
+[endsect] [/modifiers]
+
+
+[section:special =nary_tree= specialized algorithms [label tr.hierarchy.narytree.special]]
+
+[endsect] [/special]
+
+
+[endsect] [/narytree]

Added: sandbox/tree/libs/tree/proposal/tr-iterators.qbk
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/tr-iterators.qbk	2012-01-15 01:16:46 EST (Sun, 15 Jan 2012)
@@ -0,0 +1,12 @@
+[/
+ /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2011, René Rivera
+ /
+ /  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)
+ /]
+
+[section:tr.containers S Iterators library]
+
+[endsect] [/tr.iterators]