[Boost-commit] svn:boost r55340 - in sandbox/SOC/2006/tree/trunk: boost/tree libs/tree/doc libs/tree/doc/html libs/tree/proposal libs/tree/test

Subject: [Boost-commit] svn:boost r55340 - in sandbox/SOC/2006/tree/trunk: boost/tree libs/tree/doc libs/tree/doc/html libs/tree/proposal libs/tree/test
From: ockham_at_[hidden]
Date: 2009-08-01 08:35:15

Author: bernhard.reiter
Date: 2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
New Revision: 55340
URL: http://svn.boost.org/trac/boost/changeset/55340

Log:
More proposal (the next generation)
Added:
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/boostbook.css   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/libs/tree/proposal/
   sandbox/SOC/2006/tree/trunk/libs/tree/proposal/Jamfile.v2   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/libs/tree/proposal/proposal.qbk   (contents, props changed)
      - copied, changed from r54595, /sandbox/SOC/2006/tree/trunk/libs/tree/doc/proposal.qbk
Removed:
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/proposal.qbk
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp              |     6 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp          |    67 ++++++++++++++------------------------- 
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2            |    32 +++++++++++++++---                      
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html    |     1                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk              |    10 +++--                                   
   sandbox/SOC/2006/tree/trunk/libs/tree/proposal/proposal.qbk     |    31 +++++++++++++++--                       
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp |    13 +++++++                                 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp       |     7 +--                                     
   8 files changed, 103 insertions(+), 64 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
@@ -183,10 +183,10 @@
                             typename metadata<value_type>::type > data_type;
     typedef typename Hierarchy::template rebind<data_type>::other hierarchy_type;
 
- protected:
+protected:
     hierarchy_type h;
 
- private:
+private:
     typedef balance<Hierarchy, Balance> self_type;
     
     typedef typename hierarchy_type::cursor cursor;
@@ -243,7 +243,7 @@
      */      
     iterator begin()
     {
-        return iterator(h.inorder_first());
+        return iterator(first(inorder(), h.root()));
 
     }
     

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
@@ -352,13 +352,12 @@
      }
      
     // splice operations
-    
-    //TODO: check for equal allocators...
+
     /**
-     * @brief  Insert contents of another %binary_tree.
-     * @param  position  Empty cursor that is going to be the root of the newly
-     *                   inserted subtree.
-     * @param  x  Source binary_tree.
+     * @brief   Insert contents of another %binary_tree.
+     * @param   position    Empty cursor that is going to be the root of the newly
+     *                      inserted subtree.
+     * @param   x   Source binary_tree.
      * 
      * The elements of @a x are inserted in constant time as the subtree whose
      * root is referenced by @a position.  @a x becomes an empty
@@ -366,45 +365,29 @@
      */
     void splice(cursor position, binary_tree& x)
     {
-        if (!x.empty()) {
-//            if (position == inorder_first()) // Readjust inorder_first to x's
-//                m_header.m_children[1] = x.m_header.m_children[1];
-                
-            position.base_node()->m_children[position.m_pos] = x.m_header.m_children[0];
-            //TODO: replace the following by some temporary-swapping?
-            x.m_header.m_children[0] = 0;
-            x.m_header.m_children[1] = &x.m_header;
-            x.m_header.m_parent = &x.m_header;
-        }
+        splice(position, x, x.root());
     }
-    
-    // Does this splice *p or the subtree?
-    // Maybe only *p, as the subtree would require knowledge about
-    // inorder_first in order to remain O(1)
-    // But what if p has children?... Then this would require some defined
-    // re-linking (splicing-out, actually) in turn!
-//    void splice(cursor pos, binary_tree& x, cursor p)
-//    {
-//    }
 
-    void splice(cursor position, binary_tree& x, 
-                cursor root, cursor inorder_first)
+    /**
+     * @brief   Insert contents of another %binary_tree's subtree.
+     * @param   position    Empty cursor that is going to be the root of the newly
+     *                      inserted subtree.
+     * @param   x           Source binary_tree.
+     * @param   root        The source subtree.
+     * 
+     * The elements of @a root (which is subtree of @a x) are inserted in
+     * constant time as the subtree whose root is referenced by @a position.
+     * @a x becomes an empty binary_tree.
+     */
+    void splice(cursor position, binary_tree& x, cursor root)
     {
-        if (!x.is_leaf()) {
-            if (inorder_first == x.inorder_first())
-                x.m_header.m_children[1] = inorder_first.base_node();
-            if (position == inorder_first()) // Readjust inorder_first to x's
-                m_header.m_children[1] = inorder_first.base_node();
-                
-            position.base_node()->node_base_type::operator[](position.m_pos) = root.base_node();
-            
-            root.base_node()->m_children[0] = 0;
-            if (root == x.root()) {
-                x.m_header.m_children[1] = &x.m_header;
-                x.m_header.m_parent = &x.m_header;            
-            } else
-                root.base_node()->m_children[1] = 0;
-        }        
+        static_cast<node_base_pointer>(root.base_node()->m_children[position.m_pos])->m_parent
+        = position.base_node();
+
+        position.base_node()->m_children[position.m_pos]
+        = root.base_node()->m_children[position.m_pos];
+        
+        root.base_node()->m_children[position.m_pos] = 0;       
     }
 
     /**

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
@@ -12,6 +12,8 @@
         BOOST_ROOT = [ modules.peek : BOOST_ROOT ] ;
 }
 
+#path-constant boost-images : ../../../doc/src/images ;
+
 doxygen autodoc
         :
                 [ glob ../../../boost/tree/*.hpp ]
@@ -24,11 +26,6 @@
                 #<xsl:param>boost.doxygen.detailns=documenteverything
         ;
 
-#doxygen proposal
-#	:
-#		<dependency>autodoc
-#	;
-
 xml tree
         :
                 tree.qbk
@@ -48,5 +45,28 @@
                 <xsl:param>section.autolabel=1
                 <xsl:param>section.autolabel.max.depth=3
                 <xsl:param>chapter.autolabel=0
-		<xsl:param>navig.graphics=0		
+		<xsl:param>navig.graphics=0
+		
+        # PDF Options:
+        <format>pdf:<xsl:param>xep.extensions=1
+        # TOC generation: this is needed for FOP 0.2, but must not be set to zero for FOP-0.9!
+        <format>pdf:<xsl:param>fop.extensions=0
+        <format>pdf:<xsl:param>fop1.extensions=0
+        # No indent on body text:
+        <format>pdf:<xsl:param>body.start.indent=0pt
+        # Margin size:
+        <format>pdf:<xsl:param>page.margin.inner=0.5in
+        # Margin size:
+        <format>pdf:<xsl:param>page.margin.outer=0.5in
+        # Paper type = A4
+        <format>pdf:<xsl:param>paper.type=A4
+        # Yes, we want graphics for admonishments:
+        <xsl:param>admon.graphics=1
+        # Set this one for PDF generation *only*:
+        # default pnd graphics are awful in PDF form,
+        # better use SVG's instead:
+        <format>pdf:<xsl:param>admon.graphics.extension=".svg"
+        <format>pdf:<xsl:param>use.role.for.mediaobject=1 
+        <format>pdf:<xsl:param>preferred.mediaobject.role=print
+        <format>pdf:<xsl:param>admon.graphics.path=$(boost-images)/
         ;

Added: sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/boostbook.css
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/boostbook.css	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
@@ -0,0 +1,511 @@
+/*=============================================================================
+    Copyright (c) 2004 Joel de Guzman
+    http://spirit.sourceforge.net/
+
+    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;
+        }
+    }

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
@@ -2,6 +2,7 @@
 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
     "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
 <!-- boostinspect:nolink -->
+<!-- boostinspect:nolicense -->
 
 <html xmlns="http://www.w3.org/1999/xhtml">
 <head>

Deleted: sandbox/SOC/2006/tree/trunk/libs/tree/doc/proposal.qbk
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/proposal.qbk	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
+++ (empty file)
@@ -1,213 +0,0 @@
-[/
- /  Copyright (c) 2006-2009, Bernhard Reiter
- /
- /  Distributed under the Boost Software License, Version 1.0.
- /  (See accompanying file LICENSE_1_0.txt or copy at
- /  http://www.boost.org/LICENSE_1_0.txt)
- /
- //////////////////////////////////////////////////////////////////////////////////////////////
- /
- / Boost.Tree
- / Proposal documentation file.
- /]
-
-
-[section Hierarchical Data Structures and Related Concepts for the
-C++ Standard Library]
-
-[heading 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 CodeTM 2006], so at the time of this
-writing, implementation work is still unfinished and, however inspired by and striving to
-avoid past issues and such ones arising from current implementation efforts (see below)
-it is, it has not been used in practice yet.
-[endsect]
-
-[section Is there a reference implementation?]
-Yes; the current state is available from svn from 
-[@http://svn.boost.org/svn/boost/sandbox/SOC/2006/tree/trunk].
-Alternatively, the source code can be viewed in a web browser at
-[@https://svn.boost.org/trac/boost/browser/sandbox/SOC/2006/tree/trunk].
-[endsect]
-
-[endsect]
-
-[section Impact on the Standard]
-
-[section What does it depend on, and what depends on it?]
-It depends on some standard library components, such as [^std::allocator] which is used
-as the default allocator template argument at some points. Concepts like allocators or
-iterators are reused and in some cases adapted.
-[endsect]
-
-[section Is it a pure extension, or does it require changes to
-standard components?]
-Most of the proposed library is a pure extension.
-Some extensions [^<algorithm>] and some extensions to [^<iterator>] are proposed.
-Additionally, while not proposed herein, it has sometimes been suggested to add a
-template parameter to the STL associative containers [^set], [^multiset], [^map], and
-[^multimap] (and possibly an argument to their constructors) specifying a policy for
-storing elements, or, more concretely, what tree. The balancers presented in this
-proposal would lend themselves to such use. Indicating what type of balanced hierarchy to
-use for associative containers would create some amount of symmetry to TR1's [^unordered]
-containers that allow specification of a hash functor; it is however a momentous decision
-in which position to put such a parameter. The same position as for [^unordered]
-containers (before the comparison functor) would require changes in existing code; making
-it the last parameter (after the allocator) would allow existing code to remain
-unchanged, but seems somewhat irritating when compared to [^unordered] containers.
-[endsect]
-
-[section Can it be implemented using today's compilers, or does it
-require language features that will only be available as part of C++0x?]
-It can be, and partly has been, implemented with today's compilers.
-Note that it might be worthwhile to investigate if the present Container concept should
-be modified so that it only covers the requirements as of paragraph 2 of section
-[@#tr.hierarchy.req [tr.hierarchy.req]] of this proposal, which correspond to the current
-Container concept with the exception of any expressions that implicitly assume linear
-internal structure and outsource those to a "Linear Container" concept as similarly
-formalized in the [@http://boost.org/libs/range/doc/range.html Boost Range concept]
-([@http://boost.org/libs/range/doc/range.html]) externally to the Standard.
-[endsect]
-
-[endsect]
-[section Important Design Decisions]
-
-[section Why did you choose the specific design that you did?]
-One of the most important assets of the present design is the cursor concept as a
-hierarchical continuation to the STL's iterator concept, and the externally defined range
-concept. Among their benefits, cursors allow to handle both client data access, by
-dereference, and subtree access while hiding the normally underlying node structure and
-providing a uniform interface to algorithms that are thus enabled to deal with a number
-of different kinds of trees. On the other hand, this abstraction achieves independence of
-implementation details, such as nodes for storage in many cases, allowing the underlying
-concepts to be applicable to other possible implementations as well.
-[endsect]
-
-[section What alternatives did you consider, and what are the
-tradeoffs?]
-
-[section Trees of trees]
-Trees, being recursively defined data structures, seem to somewhat lend themselves to
-recursive implementation, i.e. declaring them in a way so they consist of a client value
-part and a certain number of trees in turn (as e.g. in case of [link haas \[haas\]]). Such
-an approach would allow for uniform treatment of the subtrees, but would duplicate
-allocators and imply structure that need not be present. The tree, like existing STL
-containers, should be responsible for data representation and storage.
-[endsect]
-
-[section Augmentors/balancers as policies]
-Inspired by [link austern \[austern\]] and [link dreizin \[dreizin\]], the original
-approach undertaken when working on the reference implementation was to pass policy
-template arguments to template class [^binary_tree]. While reproducing the (otherwise
-unbalanced) tree/cursor interface seemed logical at first, it turned out that this was
-conceptually not entirely clean, as e.g. it preferred one type of linear order, namely
-inorder, over the others by putting such strong focus on inorder-invariant balancing and
-its possible applications; also, balancing and augmenting metadata would inevitably have
-been much more visible. It seemed more appropriate to have different balancing adaptors
-and augmenting adaptors that would replicate the interface to do that work.
-[endsect]
-
-[endsect]
-
-[section What are the consequences of your choices, for users and
-implementors?]
-As focus was put on versatility and comprehensiveness, we hope users will find this a
-powerful framework that covers most important aspects of dealing with hierarchical data
-structures in a rather intuitive way, once they have adapted to the notion of cursors
-which, although being the interface relevant portion of the well-known node
-implementation of trees, partly diverge in their usage from plain node objects.
-Wherever reasonably possible, strong time complexity guarantees are given, which mostly,
-while trying not to require much space overhead, demand implementations that make use of
-any time and space saving techniques available (e.g. using arrays for both children of a
-binary tree node, see e.g. [link austern \[austern\]]), which may partly restrict
-implementors to one "proper" way of doing things.
-[endsect]
-
-[section What decisions are left up to implementors?]
-Most of the requirements for the library components presented in this proposal are rather
-tightly formulated in order to allow for them being both efficient and general enough. It
-is however hoped that the conceptual abstraction of hierarchies and cursors may be of
-general use, also allowing for more specific implementations where required (although
-probably not as part of the library; ideally comparable to the role of containers and
-iterators in modern C++ code).
-[endsect]
-
-[section If there are any similar libraries in use, how do their
-design decisions compare to yours?]
-Trees, having attracted much attention in the C++ community, are found in various
-implementations and as subjects of a number of papers. Contrary to the present proposal,
-practically all of them deal either with trees as used for sorted associative containers
-(with logarithmic time complexity for more relevant operations, achieved by some sort of
-balancing; examples are [link dreizin \[dreizin\]], [link ekman \[ekman\]] and 
-[link karas \[karas\]]; plus, most current STL implementations use a red-black tree as their
-associative containers' base) or with what we call "external" hierarchies in the
-following (whose structure is dictated e.g. by a file system directory tree, an XML file
-or an AST; see e.g. [link gottschlich \[gottschlich\]], [link haas \[haas\]], 
-[link parent \[parent\]] and [link peeters \[peeters\]]), but rarely both fields of application.
-Approaches as found in [link austern \[austern\]] or [link mirwaisi \[mirwaisi\]] go some
-steps further and have provided valuable inspiration for this project, but still do not
-formalize anything similar as the cursor-based interface in this proposal for dealing
-with a tree's contents.
-The [@http://www.boost.org/libs/graph/ BGL], finally, deals with graphs that are even
-more general than hierarchical ones, which does not allow them to profit from specific
-hierarchy properties as much as the ones presented in this proposal. Making cursors
-logical extensions of iterators would probably also have been more difficult with a
-BGL-based approach.
-[endsect]
-
-[endsect]
-
-[section Future Directions]
-While it is hoped that the current proposal somewhat reunites balanced binary trees,
-B-trees and "external" hierarchies, which should also facilitate work with some
-higher-level structures (e.g. n-ary trees to implement tries), some of those higher-level
-components might be an interesting feature to add to the library, such as patricia tries
-or ternary search tries.
-[endsect]
-
-[endsect] [/Title]

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/tree.qbk	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
@@ -26,6 +26,8 @@
 ]
 
 [def (tm) '''&#8482;''']
+[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]]
 
 [section Introduction]
 
@@ -51,10 +53,10 @@
 [section Download]
 
 This library's current state is only available via [@http://subversion.tigris.org/ svn] from the
-Boost Sandbox repository at [@https://svn.boost.org/svn/boost/sandbox/SOC/2006/tree]
+Boost Sandbox repository at __code_rep__.
 (This obsoletes the old Boost Consulting repository for Google Summer of Code 2006(tm) at
-https://www.boost-consulting.com/svn/main/boost/soc/2006.) The source code can be 
-browsed online at [@http://svn.boost.org/trac/boost/browser/sandbox/SOC/2006/tree].
+ https://www.boost-consulting.com/svn/main/boost/soc/2006.) The source code can be 
+browsed online at __browse_rep__.
 
 A [@http://boost-consulting.com/vault/index.php?action=downloadfile&filename=tree-soc2006.zip&directory=Containers& snapshot]
  of the final GSoC 2006 state (kindly provided by René Rivera) can be found at the 
@@ -87,7 +89,7 @@
 [include concepts.qbk]
 [include algorithms.qbk]
 
-[include proposal.qbk]
+[/include proposal.qbk]
 [include implementation.qbk]
 [include glossary.qbk]
 [include references.qbk]

Added: sandbox/SOC/2006/tree/trunk/libs/tree/proposal/Jamfile.v2
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/proposal/Jamfile.v2	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
@@ -0,0 +1,57 @@
+#  Copyright (c) 2006-2009, Bernhard Reiter
+#
+#  Distributed under the Boost Software License, Version 1.0.
+#  (See accompanying file LICENSE_1_0.txt or copy at
+#  http:#www.boost.org/LICENSE_1_0.txt)
+
+using doxygen ;
+using quickbook ;
+
+if ! $(BOOST_ROOT)
+{
+	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
+	:
+		proposal.qbk
+	;
+
+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

Copied: sandbox/SOC/2006/tree/trunk/libs/tree/proposal/proposal.qbk (from r54595, /sandbox/SOC/2006/tree/trunk/libs/tree/doc/proposal.qbk)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/libs/tree/doc/proposal.qbk	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/proposal/proposal.qbk	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
@@ -1,5 +1,5 @@
 [/
- /  Copyright (c) 2006-2009, Bernhard Reiter
+ /  Copyright (c) 2006-2009, Bernhard Reiter and René Rivera
  /
  /  Distributed under the Boost Software License, Version 1.0.
  /  (See accompanying file LICENSE_1_0.txt or copy at
@@ -11,11 +11,30 @@
  / Proposal documentation file.
  /]
 
+[/ TODO: The generated docs should contain boostinspect:nolicense ]
+
+[library Hierarchical Data Structures and Related Concepts for the C++ Standard Library
+    [quickbook 1.4]
+    [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])
+
+    ]
+]
+
+[def (tm) '''&#8482;''']
+[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]]
 
 [section Hierarchical Data Structures and Related Concepts for the
 C++ Standard Library]
 
-[heading Bernhard Reiter and René Rivera]
+[*Bernhard Reiter and René Rivera]
 
 [variablelist
 [[Document No.] [WG21/N2101=J16/06-0171]]
@@ -62,7 +81,7 @@
 No; this proposal originates in an effort to create a generic tree container component
 for [@http://www.boost.org Boost] in the course of 
 [@http://code.google.com/soc/2006/boost/appinfo.html?csaid=E17EA7C7C537C131
-Google Summer of CodeTM 2006], so at the time of this
+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.
@@ -70,9 +89,9 @@
 
 [section Is there a reference implementation?]
 Yes; the current state is available from svn from 
-[@http://svn.boost.org/svn/boost/sandbox/SOC/2006/tree/trunk].
+__code_rep__.
 Alternatively, the source code can be viewed in a web browser at
-[@https://svn.boost.org/trac/boost/browser/sandbox/SOC/2006/tree/trunk].
+__browse_rep__.
 [endsect]
 
 [endsect]
@@ -211,3 +230,5 @@
 [endsect]
 
 [endsect] [/Title]
+
+[xinclude autodoc.xml]
\ No newline at end of file

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
@@ -362,6 +362,19 @@
     BOOST_CHECK(bt == bt2);
 }
 
+BOOST_AUTO_TEST_CASE( splice_subtree_test )
+{
+    binary_tree<int> bt0;
+    bt0.insert(bt0.root(), 8);
+    bt0.splice(bt0.root().begin(), bt, bt.root().begin());
+    BOOST_CHECK(bt.root().begin().is_leaf());
+    bt0.splice(bt0.root().end(), bt, bt.root().end());
+    BOOST_CHECK(bt.root().end().is_leaf());
+
+    BOOST_CHECK_EQUAL(*bt.root().begin(), 8);
+    validate_test_dataset1_tree(bt0.root());
+}
+
 BOOST_AUTO_TEST_CASE( splice_test )
 {
     binary_tree<int> bt0;

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp	2009-08-01 08:35:14 EDT (Sat, 01 Aug 2009)
@@ -4,6 +4,7 @@
 //  (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
 
+#include <boost/tree/balance.hpp>
 #include <boost/tree/binary_tree.hpp>
 #include <boost/tree/detail/balancers/treap.hpp>
 #include <boost/tree/detail/augmentors/unaugmented.hpp>
@@ -15,8 +16,6 @@
 //#define BOOST_TEST_DYN_LINK
 #include <boost/test/included/unit_test.hpp>
 
-
-
 //TODO: Make this a test suite.
 
 BOOST_AUTO_TEST_CASE( treap_test )
@@ -26,7 +25,7 @@
     std::vector<int> my_vector;
     typedef binary_tree<int> tree_t;
     //typedef test_searcher<false, tree_t> searcher_t;
-    typedef test_balancer<binary_tree<int>, balancers::treap> treap_t;
+    typedef balance<binary_tree<int>, balancers::treap> treap_t;
     
     //searcher_t my_searcher;
     treap_t my_balancer;
@@ -34,7 +33,7 @@
     
     //create_test_data_searcher(my_searcher);
     create_test_data_sequence(my_balancer);
-    create_test_data_sequence(my_vector);
+    //create_test_data_sequence(my_vector);
 
 //    Segfaults:    
 //    BOOST_CHECK(std::equal(my_balancer.begin(), my_balancer.end(), my_vector.begin()));