Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r76482 - in sandbox/tree: . libs/tree/proposal libs/tree/proposal/html libs/tree/proposal/single
From: grafikrobot_at_[hidden]
Date: 2012-01-14 01:42:11

Next message: barend.gehrels_at_[hidden]: "[Boost-commit] svn:boost r76483 - in trunk/boost/geometry/multi: . io/dsv"
Previous message: grafikrobot_at_[hidden]: "[Boost-commit] svn:boost r76481 - trunk/tools/boostbook/xsl"

Author: grafik
Date: 2012-01-14 01:42:10 EST (Sat, 14 Jan 2012)
New Revision: 76482
URL: http://svn.boost.org/trac/boost/changeset/76482

Log:
Progress towards a single+standalone HTML TR proposal direct from Quickbook/BoostBook.
Added:
   sandbox/tree/jamroot.jam (contents, props changed)
   sandbox/tree/libs/tree/proposal/proposal.css.xml (contents, props changed)
   sandbox/tree/libs/tree/proposal/single/
   sandbox/tree/libs/tree/proposal/single/proposal.html (contents, props changed)
Removed:
   sandbox/tree/libs/tree/proposal/html/
Text files modified:
   sandbox/tree/libs/tree/proposal/Jamfile.v2 | 110 ++++++++++++-------
   sandbox/tree/libs/tree/proposal/proposal.qbk | 219 +++++++++++++++++++++++++++++++++++----
   2 files changed, 265 insertions(+), 64 deletions(-)

Added: sandbox/tree/jamroot.jam
==============================================================================
--- (empty file)
+++ sandbox/tree/jamroot.jam 2012-01-14 01:42:10 EST (Sat, 14 Jan 2012)
@@ -0,0 +1,10 @@
+# Copyright Rene Rivera 2012
+# 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)
+
+project tree
+ : build-dir bin
+ ;
+
+path-constant BOOST_TREE_ROOT : . ;

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-14 01:42:10 EST (Sat, 14 Jan 2012)
@@ -4,7 +4,6 @@
# (See accompanying file LICENSE_1_0.txt or copy at
# http:#www.boost.org/LICENSE_1_0.txt)

-using doxygen ;
using quickbook ;

if ! $(BOOST_ROOT)
@@ -12,46 +11,77 @@
         BOOST_ROOT = [ modules.peek : BOOST_ROOT ] ;
}

-doxygen autodoc
- :
- [ glob ../../../boost/tree/*.hpp ]
- #[ glob ../../../boost/tree/detail/augmentors/*.hpp ]
- #[ glob ../../../boost/tree/detail/balancers/*.hpp ]
- :
- <doxygen:param>"PREDEFINED=\"BOOST_PROCESS_DOXYGEN\""
- # add some macro for enabling use of differentiated comments
- # (for doc or proposal use)
-
- # Include documentation for the code in the detail namespace?
- #<xsl:param>boost.doxygen.detailns=documenteverything
- ;
-
-xml proposalqbk
+xml proposal
         :
                 proposal.qbk
         ;
+explicit proposal ;

-boostbook proposal
- :
- proposalqbk
- :
- <dependency>autodoc
- <xsl:param>boost.libraries=$(BOOST_ROOT)/libs/libraries.htm
- #<xsl:param>boost.root=../../../../
- <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.image.srcimages/my_project_logo.png
- #<xsl:param>boost.image.alt"\"My Project\""
- #<xsl:param>boost.image.w=100
- #<xsl:param>boost.image.h=50
- #<xsl:param>nav.layout=none
-
-
- ;
\ No newline at end of file
+boostbook proposal-standalone
+ :
+ proposal
+ :
+ <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
+ <xsl:param>chunk.first.sections=1
+ <xsl:param>generate.id.attributes=1
+ #<xsl:param>generate.css.headers=1
+
+ <dependency>proposal-standalone-images
+ <dependency>proposal-standalone-callouts
+ <dependency>proposal-standalone-css
+ ;
+explicit proposal-standalone ;
+
+install proposal-standalone-images
+ : [ glob $(BOOST_ROOT)/doc/src/images/*.png ]
+ : <location>html/images ;
+explicit proposal-standalone-images ;
+
+install proposal-standalone-callouts
+ : [ glob $(BOOST_ROOT)/doc/src/images/callouts/*.png ]
+ : <location>html/images/callouts ;
+explicit proposal-standalone-callouts ;
+
+install proposal-standalone-css
+ : [ glob $(BOOST_ROOT)/doc/src/*.css ]
+ : <location>html ;
+explicit proposal-standalone-css ;
+
+boostbook proposal-single
+ :
+ proposal
+ :
+ #<xsl:param>html.stylesheet=proposal.css
+ #<xsl:param>html.stylesheet=
+ <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>section.autolabel=1
+ <xsl:param>section.autolabel.max.depth=100
+ <xsl:param>chapter.autolabel=0
+ <xsl:param>generate.section.toc.level=0
+ <xsl:param>chunk.section.depth=0
+ <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>make.clean.html=1
+
+ <location>single
+ <format>onehtml
+ <dependency>proposal.css.xml
+ ;
+
\ No newline at end of file

Added: sandbox/tree/libs/tree/proposal/proposal.css.xml
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/proposal.css.xml 2012-01-14 01:42:10 EST (Sat, 14 Jan 2012)
@@ -0,0 +1,600 @@
+<?xml version="1.0"?>
+<style>
+/*=============================================================================
+ Copyright (c) 2004 Joel de Guzman
+ Copyright (c) 2011-2012 Rene Rivera
+
+ Use, modification and distribution is subject to 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)
+=============================================================================*/
+
+/*=============================================================================
+ Body defaults
+=============================================================================*/
+body {
+ margin: 1em;
+ font-family: sans-serif;
+}
+
+/*=============================================================================
+ Paragraphs
+=============================================================================*/
+p {
+ text-align: left;
+ font-size: 10pt;
+ line-height: 1.15;
+}
+
+/*=============================================================================
+ Program listings
+=============================================================================*/
+
+/* Code on paragraphs */
+p tt.computeroutput {
+ font-size: 9pt;
+}
+
+pre.synopsis {
+ 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;
+}
+
+/* Program listings in tables don't get borders */
+td .programlisting,td .screen {
+ 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;
+}
+
+h1 {
+ font: 140%
+}
+
+h2 {
+ font: bold 140%
+}
+
+h3 {
+ font: bold 130%
+}
+
+h4 {
+ font: bold 120%
+}
+
+h5 {
+ font: italic 110%
+}
+
+h6 {
+ 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;
+}
+
+h1.title {
+ font-size: 140%
+}
+
+h2.title {
+ font-size: 140%
+}
+
+h3.title {
+ font-size: 130%
+}
+
+h4.title {
+ font-size: 120%
+}
+
+h5.title {
+ font-size: 110%
+}
+
+h6.title {
+ font-size: 100%
+}
+
+.section h1 {
+ margin: 0em 0em 0.5em 0em;
+ font-size: 140%;
+}
+
+.section h2 {
+ font-size: 140%
+}
+
+.section h3 {
+ font-size: 130%
+}
+
+.section h4 {
+ font-size: 120%
+}
+
+.section h5 {
+ font-size: 110%
+}
+
+.section h6 {
+ font-size: 100%
+}
+
+/* Code on titles */
+h1 tt.computeroutput {
+ font-size: 140%
+}
+
+h2 tt.computeroutput {
+ font-size: 140%
+}
+
+h3 tt.computeroutput {
+ font-size: 130%
+}
+
+h4 tt.computeroutput {
+ font-size: 120%
+}
+
+h5 tt.computeroutput {
+ font-size: 110%
+}
+
+h6 tt.computeroutput {
+ font-size: 100%
+}
+
+/*=============================================================================
+ Author
+=============================================================================*/
+h3.author {
+ font-size: 100%
+}
+
+/*=============================================================================
+ Lists
+=============================================================================*/
+li {
+ font-size: 10pt;
+ line-height: 1.3;
+}
+
+/* Unordered lists */
+ul {
+ text-align: left;
+}
+
+/* Ordered lists */
+ol {
+ text-align: left;
+}
+
+/*=============================================================================
+ Links
+=============================================================================*/
+a {
+ text-decoration: none; /* no underline */
+}
+
+a:hover {
+ text-decoration: underline;
+}
+
+/*=============================================================================
+ Spirit style navigation
+=============================================================================*/
+.spirit-nav {
+ text-align: right;
+}
+
+.spirit-nav a {
+ color: white;
+ padding-left: 0.5em;
+}
+
+.spirit-nav img {
+ 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;
+}
+
+.boost-toc {
+ float: right;
+ padding: 0.5pc;
+}
+
+/*=============================================================================
+ Tables
+=============================================================================*/
+.table-title,div.table p.title {
+ margin-left: 4%;
+ padding-right: 0.5em;
+ padding-left: 0.5em;
+}
+
+.informaltable table,.table table {
+ width: 92%;
+ margin-left: 4%;
+ margin-right: 4%;
+}
+
+div.informaltable table,div.table table {
+ padding: 4px;
+}
+
+/* Table Cells */
+div.informaltable table tr td,div.table table tr td {
+ 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%;
+}
+
+/*=============================================================================
+ 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;
+}
+
+p.blurb img {
+ padding: 1pt;
+}
+
+/*=============================================================================
+ Variable Lists
+=============================================================================*/
+
+/* Make the terms in definition lists bold */
+div.variablelist dl dt,span.term {
+ 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;
+}
+
+div.variablelist dl dt {
+ margin-bottom: 0.2em;
+}
+
+div.variablelist dl dd {
+ 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;
+}
+
+/*=============================================================================
+ Misc
+=============================================================================*/
+
+/* Title of books and articles in bibliographies */
+span.title {
+ font-style: italic;
+}
+
+span.underline {
+ text-decoration: underline;
+}
+
+span.strikethrough {
+ text-decoration: line-through;
+}
+
+/* Copyright, Legal Notice */
+div div.legalnotice p {
+ 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;
+ }
+}
+
+@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;
+ }
+}
+
+.tree_proposal>.section {
+ font-family: serif;
+}
+
+.tree_proposal>.section {
+ margin: 1em;
+ padding: 1em 0em 1em 1.5em;
+ border-top: 1px solid #888888;
+ border-bottom: 1px solid #888888;
+}
+
+.tree_proposal ol {
+ margin: 0em;
+ padding: 0em;
+}
+
+.tree_proposal ol li {
+ 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;
+}
+
+.tree_proposal .table .title,
+.tree_proposal .table-title {
+ 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;
+}
+.tree_proposal table th p {
+ 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;
+}
+
+.tree_proposal .docref {
+ float: right;
+}
+
+.tree_proposal .docref dt {
+ float: left;
+ font-style: italic;
+}
+
+.tree_proposal .docref dd {
+ margin-left: 8em;
+}
+
+.tree_proposal h1,
+.tree_proposal h2,
+.tree_proposal h3,
+.tree_proposal h4,
+.tree_proposal h5,
+.tree_proposal h6 {
+ clear: both;
+}
+
+.tree_proposal .byline {
+ text-align: center;
+}
+
+.tree_proposal .note {
+ background: #EEEEEE;
+ border: 1px solid #AAAAAA;
+ padding: 0.25em;
+}
+.tree_proposal .note .title {
+ display: none;
+}
+.tree_proposal .note p {
+ margin: 0.25em 0em 0.25em 0em;
+}
+.tree_proposal .note table {
+ border: none;
+ margin: 0em;
+ padding: 0em;
+}
+.tree_proposal .note table td,
+.tree_proposal .note table th {
+ border: none !important;
+}
+
+.tree_proposal .add {
+ text-decoration: overline;
+}
+
+.tree_proposal h2 {
+ font-size: 150%
+}
+
+.tree_proposal h3,
+.tree_proposal h4,
+.tree_proposal h5,
+.tree_proposal h6 {
+ font-size: 100%;
+}
+
+.tree_proposal .section-id {
+ float: right;
+ position: relative;
+ top: -1.25em;
+}
+</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-14 01:42:10 EST (Sat, 14 Jan 2012)
@@ -14,24 +14,25 @@
[/ TODO: The generated docs should contain boostinspect:nolicense ]

[library Hierarchical Data Structures and Related Concepts for the C++ Standard Library
- [quickbook 1.4]
+ [quickbook 1.6]
     [authors [Reiter, Bernhard], [Rivera, RenÃ©]]
     [copyright 2006-2009 Bernhard Reiter and 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])
-
+
+ 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) '''™''']
-[def __code_rep__ [@https://svn.boost.org/svn/boost/sandbox/SOC/2006/tree]]
-[def __browse_rep__ [@http://svn.boost.org/trac/boost/browser/sandbox/SOC/2006/tree]]
+[def __code_rep__ [@http://svn.boost.org/svn/boost/sandbox/tree]]
+[template tr[id] \[tr.[id]\]]

-[section Hierarchical Data Structures and Related Concepts for the
+[section:preamble Hierarchical Data Structures and Related Concepts for the
C++ Standard Library]

[*Bernhard Reiter and RenÃ© Rivera]
@@ -46,38 +47,47 @@

[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.
+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
@@ -85,29 +95,34 @@
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__.
-Alternatively, the source code can be viewed in a web browser at
-__browse_rep__.
-[endsect]
+
+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
@@ -119,11 +134,14 @@
containers (before the comparison functor) would require changes in existing code; making
it the last parameter (after the allocator) would allow existing code to remain
unchanged, but seems somewhat irritating when compared to [^unordered] containers.
+
[endsect]

[section Can it be implemented using today's compilers, or does it
-require language features that will only be available as part of C++0x?]
+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
@@ -131,12 +149,15 @@
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]
+
+[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
@@ -145,21 +166,23 @@
of different kinds of trees. On the other hand, this abstraction achieves independence of
implementation details, such as nodes for storage in many cases, allowing the underlying
concepts to be applicable to other possible implementations as well.
+
[endsect]

[section What alternatives did you consider, and what are the
tradeoffs?]

-[section Trees of trees]
+[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.
-[endsect]

-[section Augmentors/balancers as policies]
+[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
@@ -169,35 +192,40 @@
its possible applications; also, balancing and augmenting metadata would inevitably have
been much more visible. It seemed more appropriate to have different balancing adaptors
and augmenting adaptors that would replicate the interface to do that work.
-[endsect]

[endsect]

[section What are the consequences of your choices, for users and
implementors?]
+
As focus was put on versatility and comprehensiveness, we hope users will find this a
powerful framework that covers most important aspects of dealing with hierarchical data
structures in a rather intuitive way, once they have adapted to the notion of cursors
which, although being the interface relevant portion of the well-known node
implementation of trees, partly diverge in their usage from plain node objects.
+
Wherever reasonably possible, strong time complexity guarantees are given, which mostly,
while trying not to require much space overhead, demand implementations that make use of
any time and space saving techniques available (e.g. using arrays for both children of a
binary tree node, see e.g. [link austern \[austern\]]), which may partly restrict
implementors to one "proper" way of doing things.
+
[endsect]

[section What decisions are left up to implementors?]
+
Most of the requirements for the library components presented in this proposal are rather
tightly formulated in order to allow for them being both efficient and general enough. It
is however hoped that the conceptual abstraction of hierarchies and cursors may be of
general use, also allowing for more specific implementations where required (although
probably not as part of the library; ideally comparable to the role of containers and
iterators in modern C++ code).
+
[endsect]

[section If there are any similar libraries in use, how do their
design decisions compare to yours?]
+
Trees, having attracted much attention in the C++ community, are found in various
implementations and as subjects of a number of papers. Contrary to the present proposal,
practically all of them deal either with trees as used for sorted associative containers
@@ -208,27 +236,170 @@
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]

+[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]
+
+[endsect] [/Future Directions]

[endsect] [/Title]

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

Added: sandbox/tree/libs/tree/proposal/single/proposal.html
==============================================================================
--- (empty file)
+++ sandbox/tree/libs/tree/proposal/single/proposal.html 2012-01-14 01:42:10 EST (Sat, 14 Jan 2012)
@@ -0,0 +1,1142 @@
+<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">
+
+/********************************/
+/* start of styles in block.xsl */
+
+.formalpara-title {
+ font-weight: bold;
+}
+
+div.blockquote-title {
+ font-weight: bold;
+ margin-top: 1em;
+ margin-bottom: 1em;
+}
+
+span.msgmain-title {
+ font-weight: bold;
+}
+
+span.msgsub-title {
+ font-weight: bold;
+}
+
+span.msgrel-title {
+ font-weight: bold;
+}
+
+div.msglevel, div.msgorig, div.msgaud {
+ margin-top: 1em;
+ margin-bottom: 1em;
+}
+
+span.msglevel-title, span.msgorig-title, span.msgaud-title {
+ font-weight: bold;
+}
+
+div.msgexplan {
+ margin-top: 1em;
+ margin-bottom: 1em;
+}
+
+span.msgexplan-title {
+ font-weight: bold;
+}
+
+/* end of styles in block.xsl */
+/********************************/
+
+/********************************/
+/* start of styles in autotoc.xsl */
+
+ font-weight: bold;
+ margin-top: 1em;
+ margin-bottom: 1em;
+}
+
+
+/* end of styles in autotoc.xsl */
+/********************************/
+
+/********************************/
+/* start of styles in formal.xsl */
+
+div.figure-title {
+ font-weight: bold;
+}
+
+div.example-title {
+ font-weight: bold;
+}
+
+div.equation-title {
+ font-weight: bold;
+}
+
+div.table-title {
+ font-weight: bold;
+}
+
+div.sidebar-title {
+ font-weight: bold;
+}
+
+
+/* end of styles in formal.xsl */
+/********************************/
+
+/********************************/
+/* start of styles in verbatim.xsl */
+
+div.programlisting {
+ white-space: pre;
+ font-family: monospace;
+}
+
+div.screen {
+ white-space: pre;
+ font-family: monospace;
+}
+
+div.synopsis {
+ white-space: pre;
+ font-family: monospace;
+}
+
+/* end of styles in verbatim.xsl */
+/********************************/
+</style><style type="text/css">
+/*=============================================================================
+ Copyright (c) 2004 Joel de Guzman
+ Copyright (c) 2011-2012 Rene Rivera
+
+ Use, modification and distribution is subject to 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)
+=============================================================================*/
+
+/*=============================================================================
+ Body defaults
+=============================================================================*/
+body {
+ margin: 1em;
+ font-family: sans-serif;
+}
+
+/*=============================================================================
+ Paragraphs
+=============================================================================*/
+p {
+ text-align: left;
+ font-size: 10pt;
+ line-height: 1.15;
+}
+
+/*=============================================================================
+ Program listings
+=============================================================================*/
+
+/* Code on paragraphs */
+p tt.computeroutput {
+ font-size: 9pt;
+}
+
+pre.synopsis {
+ 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;
+}
+
+/* Program listings in tables don't get borders */
+td .programlisting,td .screen {
+ 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;
+}
+
+h1 {
+ font: 140%
+}
+
+h2 {
+ font: bold 140%
+}
+
+h3 {
+ font: bold 130%
+}
+
+h4 {
+ font: bold 120%
+}
+
+h5 {
+ font: italic 110%
+}
+
+h6 {
+ 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;
+}
+
+h1.title {
+ font-size: 140%
+}
+
+h2.title {
+ font-size: 140%
+}
+
+h3.title {
+ font-size: 130%
+}
+
+h4.title {
+ font-size: 120%
+}
+
+h5.title {
+ font-size: 110%
+}
+
+h6.title {
+ font-size: 100%
+}
+
+.section h1 {
+ margin: 0em 0em 0.5em 0em;
+ font-size: 140%;
+}
+
+.section h2 {
+ font-size: 140%
+}
+
+.section h3 {
+ font-size: 130%
+}
+
+.section h4 {
+ font-size: 120%
+}
+
+.section h5 {
+ font-size: 110%
+}
+
+.section h6 {
+ font-size: 100%
+}
+
+/* Code on titles */
+h1 tt.computeroutput {
+ font-size: 140%
+}
+
+h2 tt.computeroutput {
+ font-size: 140%
+}
+
+h3 tt.computeroutput {
+ font-size: 130%
+}
+
+h4 tt.computeroutput {
+ font-size: 120%
+}
+
+h5 tt.computeroutput {
+ font-size: 110%
+}
+
+h6 tt.computeroutput {
+ font-size: 100%
+}
+
+/*=============================================================================
+ Author
+=============================================================================*/
+h3.author {
+ font-size: 100%
+}
+
+/*=============================================================================
+ Lists
+=============================================================================*/
+li {
+ font-size: 10pt;
+ line-height: 1.3;
+}
+
+/* Unordered lists */
+ul {
+ text-align: left;
+}
+
+/* Ordered lists */
+ol {
+ text-align: left;
+}
+
+/*=============================================================================
+ Links
+=============================================================================*/
+a {
+ text-decoration: none; /* no underline */
+}
+
+a:hover {
+ text-decoration: underline;
+}
+
+/*=============================================================================
+ Spirit style navigation
+=============================================================================*/
+.spirit-nav {
+ text-align: right;
+}
+
+.spirit-nav a {
+ color: white;
+ padding-left: 0.5em;
+}
+
+.spirit-nav img {
+ 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;
+}
+
+.boost-toc {
+ float: right;
+ padding: 0.5pc;
+}
+
+/*=============================================================================
+ Tables
+=============================================================================*/
+.table-title,div.table p.title {
+ margin-left: 4%;
+ padding-right: 0.5em;
+ padding-left: 0.5em;
+}
+
+.informaltable table,.table table {
+ width: 92%;
+ margin-left: 4%;
+ margin-right: 4%;
+}
+
+div.informaltable table,div.table table {
+ padding: 4px;
+}
+
+/* Table Cells */
+div.informaltable table tr td,div.table table tr td {
+ 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%;
+}
+
+/*=============================================================================
+ 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;
+}
+
+p.blurb img {
+ padding: 1pt;
+}
+
+/*=============================================================================
+ Variable Lists
+=============================================================================*/
+
+/* Make the terms in definition lists bold */
+div.variablelist dl dt,span.term {
+ 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;
+}
+
+div.variablelist dl dt {
+ margin-bottom: 0.2em;
+}
+
+div.variablelist dl dd {
+ 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;
+}
+
+/*=============================================================================
+ Misc
+=============================================================================*/
+
+/* Title of books and articles in bibliographies */
+span.title {
+ font-style: italic;
+}
+
+span.underline {
+ text-decoration: underline;
+}
+
+span.strikethrough {
+ text-decoration: line-through;
+}
+
+/* Copyright, Legal Notice */
+div div.legalnotice p {
+ 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;
+ }
+}
+
+@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;
+ }
+}
+
+.tree_proposal>.section {
+ font-family: serif;
+}
+
+.tree_proposal>.section {
+ margin: 1em;
+ padding: 1em 0em 1em 1.5em;
+ border-top: 1px solid #888888;
+ border-bottom: 1px solid #888888;
+}
+
+.tree_proposal ol {
+ margin: 0em;
+ padding: 0em;
+}
+
+.tree_proposal ol li {
+ 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;
+}
+
+.tree_proposal .table .title,
+.tree_proposal .table-title {
+ 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;
+}
+.tree_proposal table th p {
+ 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;
+}
+
+.tree_proposal .docref {
+ float: right;
+}
+
+.tree_proposal .docref dt {
+ float: left;
+ font-style: italic;
+}
+
+.tree_proposal .docref dd {
+ margin-left: 8em;
+}
+
+.tree_proposal h1,
+.tree_proposal h2,
+.tree_proposal h3,
+.tree_proposal h4,
+.tree_proposal h5,
+.tree_proposal h6 {
+ clear: both;
+}
+
+.tree_proposal .byline {
+ text-align: center;
+}
+
+.tree_proposal .note {
+ background: #EEEEEE;
+ border: 1px solid #AAAAAA;
+ padding: 0.25em;
+}
+.tree_proposal .note .title {
+ display: none;
+}
+.tree_proposal .note p {
+ margin: 0.25em 0em 0.25em 0em;
+}
+.tree_proposal .note table {
+ border: none;
+ margin: 0em;
+ padding: 0em;
+}
+.tree_proposal .note table td,
+.tree_proposal .note table th {
+ border: none !important;
+}
+
+.tree_proposal .add {
+ text-decoration: overline;
+}
+
+.tree_proposal h2 {
+ font-size: 150%
+}
+
+.tree_proposal h3,
+.tree_proposal h4,
+.tree_proposal h5,
+.tree_proposal h6 {
+ font-size: 100%;
+}
+
+.tree_proposal .section-id {
+ float: right;
+ position: relative;
+ top: -1.25em;
+}
+</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>
+ 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
+ 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
+ to support?</a></span></dt><dt><span class="section"><a href="#tree.preamble.motivation_and_scope.is_it_based_on_existing_practice">1.2.3. Is
+ it based on existing practice?</a></span></dt><dt><span class="section"><a href="#tree.preamble.motivation_and_scope.is_there_a_reference_implementat">1.2.4. Is
+ there a reference implementation?</a></span></dt></dl></dd><dt><span class="section">1.3. Impact on the Standard</span></dt><dd><dl><dt><span class="section"><a href="#tree.preamble.impact_on_the_standard.what_does_it_depend_on_and_what_">1.3.1. What
+ does it depend on, and what depends on it?</a></span></dt><dt><span class="section"><a href="#tree.preamble.impact_on_the_standard.is_it_a_pure_extension_or_does_i">1.3.2. Is
+ it a pure extension, or does it require changes to standard components?</a></span></dt><dt><span class="section"><a href="#tree.preamble.impact_on_the_standard.can_it_be_implemented_using_toda">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</a></span></dt></dl></dd><dt><span class="section"><a href="#tree.preamble.important_design_decisions">1.4. Important Design
+ Decisions</a></span></dt><dd><dl><dt><span class="section"><a href="#tree.preamble.important_design_decisions.why_did_you_choose_the_specific_">1.4.1. Why
+ did you choose the specific design that you did?</a></span></dt><dt><span class="section"><a href="#tree.preamble.important_design_decisions.what_alternatives_did_you_consid">1.4.2. What
+ alternatives did you consider, and what are the tradeoffs?</a></span></dt><dt><span class="section"><a href="#tree.preamble.important_design_decisions.what_are_the_consequences_of_you">1.4.3. What
+ 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
+ Concepts for the C++ Standard Library</a></h2></div></div></div><p>
+ <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/N2101=J16/06-0171
+ </p></dd><dt><span class="term">Date</span></dt><dd><p>
+ 2006-11-05
+ </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 <<a href="mailto:ockham_at_[hidden]" target="_top">ockham_at_[hidden]></a>,
+ René Rivera <<a href="mailto:rrivera_at_[hidden]" target="_top">rrivera_at_[hidden]</a>>
+ </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
+ 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
+ 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.
+ </p><p>
+ 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 <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
+ 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
+ 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.
+ </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™ 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
+ 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
+ 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
+ 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>
+ Some extensions <code class="literal"><algorithm></code> and some extensions
+ to <code class="literal"><iterator></code> are proposed.
+ </p><p>
+ Additionally, while not proposed herein, it has sometimes been suggested
+ to add a template parameter to the STL associative containers <code class="literal">set</code>,
+ <code class="literal">multiset</code>, <code class="literal">map</code>, and <code class="literal">multimap</code>
+ (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 <code class="literal">unordered</code> 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 <code class="literal">unordered</code>
+ 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
+ <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
+ 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]
+ 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
+ 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
+ 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.
+ </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>
+ </h6><p>
+ 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 <a class="link" href="#">[haas]</a>). 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.
+ </p><h6><a name="tree.preamble.important_design_decisions.what_alternatives_did_you_consid.h1"></a>
+ <span><a name="tree.preamble.important_design_decisions.what_alternatives_did_you_consid.augmentors_balancers_as_policies"></a></span><a class="link" href="#tree.preamble.important_design_decisions.what_alternatives_did_you_consid.augmentors_balancers_as_policies">Augmentors/balancers
+ as policies</a>
+ </h6><p>
+ Inspired by <a class="link" href="#">[austern]</a> and <a class="link" href="#">[dreizin]</a>,
+ the original approach undertaken when working on the reference implementation
+ was to pass policy template arguments to template class <code class="literal">binary_tree</code>.
+ 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.
+ </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
+ 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.
+ </p><p>
+ 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. <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
+ 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
+ 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).
+ </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
+ 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 <a class="link" href="#">[dreizin]</a>, <a class="link" href="#">[ekman]</a>
+ and <a class="link" href="#">[karas]</a>; 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. <a class="link" href="#">[gottschlich]</a>, <a class="link" href="#">[haas]</a>,
+ <a class="link" href="#">[parent]</a> and <a class="link" href="#">[peeters]</a>),
+ but rarely both fields of application.
+ </p><p>
+ Approaches as found in <a class="link" href="#">[austern]</a> or <a class="link" href="#">[mirwaisi]</a> 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.
+ </p><p>
+ The 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.
+ </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>
+ 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">
+ 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">
+ 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 < b</code>
+ </p>
+ </td></tr><tr><td>
+ <p>
+ <code class="literal">a > b</code>
+ </p>
+ </td></tr><tr><td>
+ <p>
+ <code class="literal">a <= b</code>
+ </p>
+ </td></tr><tr><td>
+ <p>
+ <code class="literal">a >= b</code>
+ </p>
+ </td></tr></tbody></table></div></div><br class="table-break">
+ </li><li class="listitem">
+ 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
+ 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<U>::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<T>::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>
+ 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
+ (2003) Electronic Appendix: http://www.research.att.com/~bs/tree-appendix.pdf
+ </p></dd><dt><span class="term">cormen</span></dt><dd><p>
+ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford.
+ <span class="emphasis"><em>Introduction to Algorithms</em></span>. Second Edition (MIT
+ Press, 2001)
+ </p></dd><dt><span class="term">dreizin</span></dt><dd><p>
+ Dreizin, Vladimir; Kosnik, Benjamin; Tavory, Ami. <span class="emphasis"><em>Policy-Based
+ Data Structures</em></span>, http://gcc.gnu.org/onlinedocs/libstdc++ class="emphasis"><em>ext/pb_ds</em></span>
+ </p></dd><dt><span class="term">ekman</span></dt><dd><p>
+ Ekman, Rasmus. <span class="emphasis"><em>Structured Associative Containers</em></span>,
+ http://www.abc.se/~re/code/tst
+ </p></dd><dt><span class="term">gottschlich</span></dt><dd><p>
+ Gottschlich, Justin. <span class="emphasis"><em>C++ Trees</em></span>, http://www.gamedev.net/reference/articles/article2192.asp
+ and http://www.gamedev.net/reference/articles/article2233.asp
+ </p></dd><dt><span class="term">haas</span></dt><dd><p>
+ Haas, Mitchell. <span class="emphasis"><em>Tree Container Library</em></span>, http://www.datasoftsolutions.net/tree_container_library/overview.php
+ </p></dd><dt><span class="term">karas</span></dt><dd><p>
+ Karas, Walt. <span class="emphasis"><em>C++ AVL Tree Template</em></span>, http://us.geocities.com/wkaras/gen_cpp/avl_tree.html
+ </p></dd><dt><span class="term">knuth97</span></dt><dd><p>
+ Knuth, Donald E. <span class="emphasis"><em>The Art of Computer Programming</em></span>.
+ Volume 1: Fundamental Algorithms. Third Edition (Reading, Massachusetts:
+ Addison-Wesley, 1997)
+ </p></dd><dt><span class="term">knuth98</span></dt><dd><p>
+ Knuth, Donald E. <span class="emphasis"><em>The Art of Computer Programming</em></span>.
+ Volume 3: Sorting and Searching. Second Edition (Reading, Massachusetts:
+ Addison-Wesley, 1998)
+ </p></dd><dt><span class="term">mirwaisi</span></dt><dd><p>
+ Mirwaisi, Jeff. <span class="emphasis"><em>treelib</em></span>, https://boost-consulting.com:8443/trac/soc/attachment/wiki/tree/resources/trees/treelib.tar.bz2
+ </p></dd><dt><span class="term">parent</span></dt><dd><p>
+ Parent, Sean et al. <span class="emphasis"><em>forest</em></span>, http://opensource.adobe.com/group__forest__related.html
+ </p></dd><dt><span class="term">peeters</span></dt><dd><p>
+ 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
+ </p></dd></dl></div></div></div></body></html>

Next message: barend.gehrels_at_[hidden]: "[Boost-commit] svn:boost r76483 - in trunk/boost/geometry/multi: . io/dsv"
Previous message: grafikrobot_at_[hidden]: "[Boost-commit] svn:boost r76481 - trunk/tools/boostbook/xsl"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk