Rework as esp-idf component

Fix typo

.travis.yml

@@ -0,0 +1,151 @@
+# Copyright 2016, 2017 Peter Dimov
+# Distributed under the Boost Software License, Version 1.0.
+# (See accompanying file LICENSE_1_0.txt or copy at http://boost.org/LICENSE_1_0.txt)
+
+language: cpp
+
+sudo: false
+
+python: "2.7"
+
+branches:
+  only:
+    - master
+    - develop
+    - /feature\/.*/
+
+env:
+  matrix:
+    - BOGUS_JOB=true
+
+matrix:
+
+  exclude:
+    - env: BOGUS_JOB=true
+
+  include:
+    - os: linux
+      compiler: g++
+      env: TOOLSET=gcc CXXSTD=03,11
+
+    - os: linux
+      compiler: g++-4.4
+      env: TOOLSET=gcc-4.4 CXXSTD=98,0x
+      addons:
+        apt:
+          packages:
+            - g++-4.4
+          sources:
+            - ubuntu-toolchain-r-test
+
+    - os: linux
+      compiler: g++-4.6
+      env: TOOLSET=gcc-4.6 CXXSTD=03,0x
+      addons:
+        apt:
+          packages:
+            - g++-4.6
+          sources:
+            - ubuntu-toolchain-r-test
+
+    - os: linux
+      compiler: g++-5
+      env: TOOLSET=gcc-5 CXXSTD=03,11
+      addons:
+        apt:
+          packages:
+            - g++-5
+          sources:
+            - ubuntu-toolchain-r-test
+
+    - os: linux
+      compiler: g++-5
+      env: TOOLSET=gcc-5 CXXSTD=14,1z
+      addons:
+        apt:
+          packages:
+            - g++-5
+          sources:
+            - ubuntu-toolchain-r-test
+
+    - os: linux
+      compiler: g++-6
+      env: TOOLSET=gcc-6 CXXSTD=03,11
+      addons:
+        apt:
+          packages:
+            - g++-6
+          sources:
+            - ubuntu-toolchain-r-test
+
+    - os: linux
+      compiler: g++-6
+      env: TOOLSET=gcc-6 CXXSTD=14,1z
+      addons:
+        apt:
+          packages:
+            - g++-6
+          sources:
+            - ubuntu-toolchain-r-test
+
+    - os: linux
+      compiler: g++-7
+      env: TOOLSET=gcc-7 CXXSTD=03,11
+      addons:
+        apt:
+          packages:
+            - g++-7
+          sources:
+            - ubuntu-toolchain-r-test
+
+    - os: linux
+      compiler: g++-7
+      env: TOOLSET=gcc-7 CXXSTD=14,17
+      addons:
+        apt:
+          packages:
+            - g++-7
+          sources:
+            - ubuntu-toolchain-r-test
+
+    - os: linux
+      compiler: clang++
+      env: TOOLSET=clang CXXSTD=03,11
+
+    - os: linux
+      compiler: clang++
+      env: TOOLSET=clang CXXSTD=14,1z
+      addons:
+        apt:
+          packages:
+            - libstdc++-4.9-dev
+          sources:
+            - ubuntu-toolchain-r-test
+
+    - os: osx
+      compiler: clang++
+      env: TOOLSET=clang CXXSTD=03,11
+
+    - os: osx
+      compiler: clang++
+      env: TOOLSET=clang CXXSTD=14,1z
+
+install:
+  - BOOST_BRANCH=develop && [ "$TRAVIS_BRANCH" == "master" ] && BOOST_BRANCH=master || true
+  - cd ..
+  - git clone -b $BOOST_BRANCH https://github.com/boostorg/boost.git boost-root
+  - cd boost-root
+  - git submodule update --init tools/build
+  - git submodule update --init libs/config
+  - git submodule update --init tools/boostdep
+  - cp -r $TRAVIS_BUILD_DIR/* libs/range
+  - python tools/boostdep/depinst/depinst.py range
+  - ./bootstrap.sh
+  - ./b2 headers
+
+script:
+  - ./b2 -j 3 libs/range/test toolset=$TOOLSET cxxstd=$CXXSTD
+
+notifications:
+  email:
+    on_success: always

CMakeLists.txt

@@ -0,0 +1,73 @@
+# Generated by `boostdep --cmake range`
+# Copyright 2020 Peter Dimov
+# Distributed under the Boost Software License, Version 1.0.
+# https://www.boost.org/LICENSE_1_0.txt
+
+if(NOT DEFINED IDF_TARGET)
+
+cmake_minimum_required(VERSION 3.5...3.16)
+
+project(boost_range VERSION "${BOOST_SUPERPROJECT_VERSION}" LANGUAGES CXX)
+
+add_library(boost_range INTERFACE)
+add_library(Boost::range ALIAS boost_range)
+
+target_include_directories(boost_range INTERFACE include)
+
+target_link_libraries(boost_range
+  INTERFACE
+    Boost::array
+    Boost::assert
+    Boost::concept_check
+    Boost::config
+    Boost::container_hash
+    Boost::conversion
+    Boost::core
+    Boost::detail
+    Boost::iterator
+    Boost::mpl
+    Boost::optional
+    Boost::preprocessor
+    Boost::regex
+    Boost::static_assert
+    Boost::tuple
+    Boost::type_traits
+    Boost::utility
+)
+
+if(BUILD_TESTING AND EXISTS "${CMAKE_CURRENT_SOURCE_DIR}/test/CMakeLists.txt")
+
+  add_subdirectory(test)
+
+endif()
+
+else()
+
+FILE(GLOB_RECURSE headers include/*.h include/*.hpp)
+
+idf_component_register(
+    SRCS
+        ${headers}
+    INCLUDE_DIRS
+        include
+    REQUIRES
+        boost_array
+        boost_assert
+        boost_concept_check
+        boost_config
+        boost_container_hash
+        boost_conversion
+        boost_core
+        boost_detail
+        boost_iterator
+        boost_mpl
+        boost_optional
+        boost_preprocessor
+        boost_regex
+        boost_static_assert
+        boost_tuple
+        boost_type_traits
+        boost_utility
+)
+
+endif()

doc/.gitignore

@@ -0,0 +1 @@
+*.html

doc/Jamfile.v2

@@ -0,0 +1,35 @@
+#// Boost.Range library
+#//
+#//  Copyright Thorsten Ottosen 2003-2008. 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)
+#//
+#// For more information, see http://www.boost.org/libs/range/
+#//
+
+project boost/libs/range/doc ;
+using boostbook ;
+using quickbook ;
+
+path-constant images_location : html ;
+
+boostbook quickbook
+  :
+    boost_range.qbk
+  :
+    <xsl:param>boost.root=../../../..
+    <xsl:param>chunk.section.depth=4
+    <xsl:param>chunk.first.sections=1
+    <xsl:param>toc.section.depth=3
+    <xsl:param>toc.max.depth=3
+    <xsl:param>generate.section.toc.level=4
+    <format>pdf:<xsl:param>boost.url.prefix=http://www.boost.org/doc/libs/release/doc/html
+    <format>pdf:<xsl:param>img.src.path=$(images_location)/
+  ;
+
+###############################################################################
+alias boostdoc ;
+explicit boostdoc ;
+alias boostrelease : quickbook ;
+explicit boostrelease ;

doc/boost_range.html

@@ -1,168 +0,0 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><title> Collection Traits </title><meta http-equiv="Content-Type"content="text/html; charset=iso-8859-1"></head> <body><table  ><tr  ><td  ><img src="cboost.gif" width="100%" border="0"></td><td  ><h1  ><br> Collection Traits </h1></td></tr></table><ul  ><li  ><a href="#Introduction" >Introduction</a></li><li  ><a href="#Reference" >Reference</a></li><ul  ><li  ><a href="#Synopsis" >Synopsis</a></li><li  ><a href="#Library headers" >Library headers</a></li><li  ><a href="#Semantics" >Semantics</a></li></ul><li  ><a href="#Examples" >Examples</a></li><li  ><a href="#Portability" >Portability</a></li><li  ><a href="#FAQ" >FAQ</a></li><li  ><a href="#History" >History</a></li></ul><hr size="1" ><h2  >Introduction</h2><a name="Introduction" ></a><p  >This library makes it possible to treat different types as if they have 
-                     implemented a subset of the container requirements 
-                     (see &sect;23.1of the C++ standard). Formally, that subset is defined by
-                     the  <a href="Collection.htm" target="_self" >CollectionConcept.</a>  
-                    The subset deals mostly with
-                     iterator returning functions and nested <code  >typedef</code>s.
-                    The main goal is to treat built-in arrays, standard containers,
-                     pairs of iterators and some iterators uniformly. Formally, this library is an implementation
-                    of the <a href="#ExternalCollectionConcept" >ExternalCollectionConcept</a> (see also this explanation of  <a href="external_concepts.html" target="_self" >External Concepts</a> ).</p><p  >The main advantages are <ul  ><li  >safe use of built-in arrays</li><li  >simpler implementation of generic container algorithms</li><li  >more flexible client code</li><li  >correct handling of null-terminated strings</li></ul></p><p  >Below are given a small example (the complete example can be found <a href="../test/algorithm_example.cpp" target="_self" >here</a> ):<pre  >
-       //
-       // Example: extracting bounds in generic algorithms
-       //                
-                       
-       template&lt; typename ExternalCollection, typename T &gt;
-       inline typename boost::iterator_of&lt;ExternalCollection&gt;::type
-       find( ExternalCollection& c, const T& value )
-       {
-           return std::find( boost::begin( c ), boost::end( c ), value );
-       }
-
-       template&lt; typename ExternalCollection, typename T &gt;
-       inline typename boost::const_iterator_of&lt;ExternalCollection&gt;::type 
-       find( const ExternalCollection& c, const T& value )
-       {
-           return std::find( boost::begin( c ), boost::end( c ), value );
-       }
-                       
-       // 
-       // replace first value and return its index
-       //                                
-       template&lt; typename EC, typename T &gt;
-       inline typename boost::size_type_of&lt; EC &gt;::type
-       my_generic_replace( EC& c, const T& value, const T& replacement )
-       {
-           typename boost::const_iterator_of&lt;EC&gt;::type found = find( c, value );
-           *found = replacement;
-           return std::distance( boost::begin( c ), found );
-       }                  
-                       
-       // 
-       // usage
-       //                                
-       std::vector&lt;int&gt;              my_vector;
-       typedef vector&lt;int&gt;::iterator iterator;
-       std::pair&lt;iterator,iterator&gt;  my_view( my_vector.begin(), my_vector.begin() + N );
-       char str[] = "a string";
-       // ...
-       std::cout &lt;&lt; my_generic_replace( my_vector, 4, 2 )
-                 &lt;&lt; my_generic_replace( my_view, 4, 2 )
-                 &lt;&lt; my_generic_replace( str, 'a', 'b' );
-       </pre>By using the free-standing functions and type-generators, the code automatically 
-         works for all the types supported by this library. Notice that we have to provide
-         two version of <code  >find()</code> since we cannot 
-         forward a non-const rvalue with reference arguments (see this article about  <a href="http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1385.htm" target="_self" >The Forwarding Problem</a> ).</p><hr size="1" ><h2  >Reference</h2><a name="Reference" ></a><p  ><pre  >#include &lt;boost/collection_traits.hpp&gt;</pre></p><p  >Five types of objects are currently supported by the library:<ul  ><li  >standard containers</li><li  >built-in arrays</li><li  >null terminated strings (this includes <code  >char[]</code>,<code  >wchar_t[]</code>,<code  >char*</code>, and <code  >wchar_t*</code>)</li><li  ><code  >std::pair&lt;iterator,iterator&gt;</code></li><li  >iterators which when default constructed denotes the end of the range</li></ul>It is worth noticing that some functionality requires partial template specialization, in particular,
-                    full array support does (remark: this is a very small problem since one would use <code>boost::array<></code>
-                     anyway). Also note that arrays and pointers of <code  >char</code> or <code  >whar_t</code> are treated special because of their use in string algorithms.</p><h3  >ExternalCollectionConcept</h3><a name="ExternalCollectionConcept" ></a><p  >The concept is defined by the type-generators and the
-                                      functions below. Even though these functions are defined in
-                                      namespace <code>boost</code>, there is no such general requirement, that is,
-                                     if one wants to extend the list of supported types, it can be done in any
-                                     namespace.</p><h3  >Synopsis</h3><a name="Synopsis" ></a><p  ><pre>
-    namespace boost 
-    {
-        //             
-        // type generators
-        //              
-        
-        template< typename EC >                                     
-        struct <a href="#value_type_of" >value_type_of</a>
-        {
-            typedef ... type; // type of stored objects 
-        };
-                     
-        template< typename EC >                                     
-        struct <a href="#iterator_of" >iterator_of</a> 
-        {
-            typedef ... type; // iterator over stored objects
-        };
-        
-        template< typename EC >                                     
-        struct <a href="#const_iterator_of" >const_iterator_of</a>      
-        {
-            typedef ... type; // iterator over immutable stored objects 
-        };
-
-        template< typename EC >                                     
-        struct <a href="#difference_type_of" >difference_type_of</a>
-        {
-            typedef ... type; 
-            BOOST_STATIC_ASSERT( boost::is_signed< type >::value );
-            //
-            // remark: if std::iterator_traits<> works for the type, this assertion must hold
-            //
-            BOOST_STATIC_ASSERT( boost::is_same< type, std::iterator_traits< typename 
-                                                       <a href="#iterator_of" >iterator_of</a>< EC >::type >::difference_type>::value );         
-        };
-
-        template< typename EC >                                     
-        struct <a href="#size_type_of" >size_type_of</a>
-        {
-            typedef ... type;
-            BOOST_STATIC_ASSERT( boost::is_unsigned< type >::value );
-            BOOST_STATIC_ASSERT( sizeof( type ) >= sizeof( <a href="#difference_type_of" >difference_type_of</a>< EC >::type ) );                   
-        };
-
-        template< typename EC >                                     
-        struct <a href="#result_iterator_of" >result_iterator_of</a>     
-        {
-            typedef ... type; 
-            // <a href="#iterator_of" >iterator_of</a>< EC >::type if EC is non-const, <a href="#const_iterator_of" >const_iterator_of</a>< EC >::type otherwise         
-        };
-                     
-        //
-        // funtions
-        //
-        
-        template< typename EC >
-        inline typename iterator_of<EC>::type
-        <a href="#begin" >begin</a>( EC& c );               
-    
-        template< typename EC >
-        inline typename const_iterator_of< EC >::type
-        <a href="#begin" >begin</a>( const EC& c );                       
-            
-        template< typename EC >
-        inline typename iterator_of< EC >::type
-        <a href="#end" >end</a>( EC& c );  
-                          
-        template< typename EC >
-        inline typename const_iterator_of< EC >::type
-        <a href="#end" >end</a>( const EC& c );
-        
-        template< typename EC >
-        inline bool
-        <a href="#empty" >empty</a>( const EC& c );         
-                   
-        template< typename EC >
-        inline typename size_type_of< EC >::type
-        <a href="#size" >size</a>( const EC& c );
-                     
-     } // namespace 'boost' </pre></p><h3  >Library headers</h3><a name="Library headers" ></a><table cellpadding=5 border=1 > <tr  ><th  >Header</th><th  >Includes</th></tr><tr  ><td  ><code  >&lt;boost/collection_traits.hpp&gt;</code></td><td  >everything</td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/types.hpp&gt;</code></td><td  >every type-generator</td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/functions.hpp&gt;</code></td><td  >every function</td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/value_type.hpp&gt;</code></td><td  ><a href="#value_type_of" >value_type_of</a></td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/iterator.hpp&gt;</code></td><td  ><a href="#iterator_of" >iterator_of</a></td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/const_iterator.hpp&gt;</code></td><td  ><a href="#const_iterator_of" >const_iterator_of</a></td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/difference_type.hpp&gt;</code></td><td  ><a href="#difference_type_of" >difference_type_of</a></td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/size_type.hpp&gt;</code></td><td  ><a href="#size_type_of" >size_type_of</a></td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/result_iterator.hpp&gt;</code></td><td  ><a href="#result_iterator_of" >result_iterator_of</a></td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/begin.hpp&gt;</code></td><td  ><a href="#begin" >begin</a></td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/end.hpp&gt;</code></td><td  ><a href="#end" >end</a></td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/empty.hpp&gt;</code></td><td  ><a href="#empty" >empty</a></td></tr><tr  ><td  ><code  >&lt;boost/collection_traits/size.hpp&gt;</code></td><td  ><a href="#size" >size</a></td></tr> </table><br><h3  >Semantics</h3><a name="Semantics" ></a><p  >In the table <code  >C</code> is a type that conforms to the ExternalCollectionConcept and <code  >c</code> is an object of that type.<code  > SC</code> will denote a standard
-                  container, <code  > T[sz]</code> will denote an array of type <code  >T</code> of size <code  >sz</code>, <code  >P</code> will denote <code  >std::pair&lt;&gt;</code>, <code  > I</code> means an iterator which default construction
-                  denotes the end of the range and <code  >sc,t,p,i</code> are objects of these types, 
-                  respectively. Special cases for <code  >char*</code> and <code  >wchar_t*</code> are described explicitly. </p><table border=1 cellpadding=5 > <tr  ><th  >Expression</th><th  >Return type</th><th  >Complexity</th></tr><tr  ><a name="value_type_of" ></a><td  ><code  >value_type_of&lt;C&gt;::type</code></td><td  ><code  >SC::value_type</code><br><code  >T</code><br><code  >std::iterator_traits&lt;P::first_type&gt;::value_type</code><br><code  >std::iterator_traits&lt;I&gt;::value_type</code></td><td  >compile time</td></tr><tr  ><a name="iterator_of" ></a><td  ><code  >iterator_of&lt;C&gt;::type</code></td><td  ><code  >SC::iterator</code><br><code  >T*</code><br><code  >P::first_type</code><br><code  >I</code></td><td  >compile time</td></tr><tr  ><a name="const_iterator_of" ></a><td  ><code  >const_iterator_of&lt;C&gt;::type</code></td><td  ><code  >SC::const_iterator</code><br><code  >const T*</code><br><code  >P::first_type</code><br><code  >I</code></td><td  >compile time</td></tr><tr  ><a name="difference_type_of" ></a><td  ><code  >difference_type_of&lt;C&gt;::type</code></td><td  ><code  >SC::difference_type</code><br><code  >std::ptrdiff_t</code><br><code  >std::iterator_traits&lt;P::first_type&gt;::difference_type</code><br><code  >std::iterator_traits&lt;I&gt;::difference_type</code></td><td  >compile time</td></tr><tr  ><a name="size_type_of" ></a><td  ><code  >size_type_of&lt;C&gt;::type</code></td><td  ><code  >SC::size_type</code><br><code  >std::size_t</code><br><code  >std::size_t</code><br><code  >std::size_t</code></td><td  >compile time</td></tr><tr  ><a name="result_iterator_of" ></a><td  ><code  >result_iterator_of&lt;C&gt;::type</code></td><td  ><code  >const_iterator_of&lt;C&gt;::type</code> if <code  >C</code> is <code  >const</code><br><code  >iterator_of&lt;C&gt;::type</code> otherwise </td><td  >compile time</td></tr> </table> <br> <table border=1 cellpadding=5 > <tr  ><th  >Expression</th><th  >Return type</th><th  >Effects</th><th  >Complexity</th></tr><tr  ><a name="begin" ></a><td  ><code  >begin( c )</code></td><td  ><code  >result_iterator_of&lt;C&gt;::type</code></td><td  ><code  >sc.begin()</code><br><code  >t</code><br><code  >p.first</code><br><code  >i</code></td><td  >constant time</td></tr><tr  ><a name="end" ></a><td  ><code  >end( c )</code></td><td  ><code  >result_iterator_of&lt;C&gt;::type</code></td><td  ><code  >sc.end()</code><br><code  >t + std::char_traits&lt;C&gt;::length( t )</code> if <code  >C</code> is <code  >char*</code> or <code  >wchar_t*</code><br><code  >t + sz - 1</code> if <code  >C</code> is <code  >char[sz]</code> or <code  >wchar_t[sz]</code><br><code  >t + sz</code> otherwise <br><code  >p.second</code><br><code  >I()</code></td><td  >linear if <code  >C</code> is <code  >char*</code> or <code  >wchar_t*</code><br>constant time otherwise</td></tr><tr  ><a name="empty" ></a><td  ><code  >empty( c )</code></td><td  >Convertible to <code  >bool</code></td><td  ><code  >sc.empty()</code><br><code  >size( t ) == 0</code><br><code  >p.first == p.second</code><br><code  >begin( i ) == end( i )</code></td><td  >linear if <code  >C</code> is <code  >char*</code> or <code  >wchar_t*</code><br>constant time otherwise<br></td></tr><tr  ><a name="size" ></a><td  ><code  >size( c )</code></td><td  ><code  >size_type_of&lt;C&gt;::type</code></td><td  ><code  >sc.size()</code><br><code  >end( t ) - begin( t )</code><br><code  >distance( p.first, p.second )</code><br><code  >not available for iterators</code></td><td  >linear if <code  >C</code> is <code  >char*</code> or <code  >wchar_t*</code><br> or if <code  >std::distance()</code> is linear <br>constant time otherwise</td></tr> </table><p  >Please note that <code  >char*</code>,<code  >whar_t*</code>,<code  >char[]</code>, and <code  >wchar_t[]</code> behaves differently from
-               normal arrays only for <code  >size()</code> and <code  >end()</code>. 
-              Note that the null pointer is allowed as an argument in these cases.</p><br><hr size="1" ><h2  >Examples</h2><a name="Examples" ></a><p  >Some examples are given in the accompanying test
-                      files:</p><ul  ><li  > <a href="../test/iterator.cpp" target="_self" ><code  >iterator.cpp</code></a> </li> shows how to implement a container version of <code  >std::copy()</code> that works with <code  >std::ifstream_iterator&lt;&gt;.</code><li  > <a href="../test/string.cpp" target="_self" ><code  >string.cpp</code></a> </li> shows how to implement a container version of <code  >std::find()</code> that works with <code  >char[],wchar_t[],char*,wchar_t*.</code><li  > <a href="../test/algorithm_example.cpp" target="_self" ><code  >algorithm_example.cpp</code></a> </li> shows the replace example from the introduction. </ul><hr size="1" ><h2  >Portability</h2><a name="Portability" ></a><p  >Full support for built-in arrays require that the
-                        compiler supports class template partial specialization.</p><p  >Notice that some compilers cannot do function template ordering
-                        properly. In that case one cannot rely of <code  >result_iterator_of&lt;&gt;</code> and a single function definition; instead one needs to supply
-                        a function overloaded for const and non-const arguments if it is required.</p><p  >Full support for iterators like <code  >std::istream_iterator&lt;&gt;</code> depends very
-                        much on a conforming standard library.</p><p  >Most of the tests have been run successfully on these compilers<ul  ><li  >vc7.1</li><li  >gcc3.2</li><li  >como4.3.0.1</li><li  >bcc6</li></ul></p><hr size="1" ><h2  >FAQ</h2><a name="FAQ" ></a><ol  ><li  >Why is there no difference between <code  >iterator_of&lt;C&gt;::type</code> and <code  >const_iterator_of&lt;C&gt;::type</code> for <code  >std::pair&lt;iterator,iterator&gt;</code> or iterators which default construction denotes the end of the range?</li><p  >In general it is not possible nor desirable to find a corresponding <code  >const_iterator</code>. When it is possible to come up with
-               one, the client might choose to
-               construct a <code  >std::pair&lt;const_iterator,const_iterator&gt;</code> object. </p><li  >Why does the traits not supply more types or more functions?<p  >The traits class have been kept small because its current interface 
-                    will serve most purposes. If and when a genuine need arises for
-                    more functionality, it can be implemented.</p></li><li  >How should I implement generic algorithms for external collections?<p  >One should always start with a generic algorithm that takes two iterators as input. Then use the 
-                     collection traits to build handier versions on top of the base algorithm.</p></li></ol><hr size="1" ><h2  >History</h2><a name="History" ></a><p  >The library have been under way for a long time. Dietmar K<>hl originally
-     intended to submit an <code  >array_traits&lt;&gt;</code> class template which had most 
-     of the functionality present now, but only for arrays and standard containers.
-      Meanwhile work on container algorithms
-     in various context showed the need for handling pairs of iterators, and 
-     string libraries needed special treatment of character arrays. 
-     Thorsten Ottosen wrote everything from the ground up including the first
-     work-around for missing partial template specialization. Pavol Droba helped to
-     improve the work-around for handicapped compilers and the special character support.
-     The naming scheme of type-generators was suggested by Peter Dimov. </p><hr size="1" ><p  >&copy; Thorsten Ottosen 2003-2004 (nesotto_AT_cs.auc.dk).
-    Permission to copy, use, modify, sell and distribute this software is granted provided this copyright notice appears
-     in all copies. This software is provided "as is" without express or implied warranty, and with no
-         claim as to its suitability for any purpose.</p><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br></body></html>
- <!-- Copyright Dezide Aps 2003-2004 -->

doc/boost_range.qbk

@@ -0,0 +1,199 @@
+[/==============================================================================
+    Copyright (C) 2003-2010 Thorsten Ottosen, Neil Groves
+
+    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
+==============================================================================/]
+[library Range
+    [quickbook 1.5]
+    [version 2.0]
+    [authors [Ottosen, Thorsten], [Groves, Neil]]
+    [copyright 2003-2010 Thorsten Ottosen, Neil Groves]
+    [purpose Half-open range 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])
+    ]
+]
+
+[/ Converted to Quickbook format by Darren Garvey, 2007]
+
+[def __note__                   [$images/note.png]]
+[def __alert__                  [$images/alert.png]]
+[def __tip__                    [$images/tip.png]]
+[def __caution__                [$images/caution.png]]
+
+[def __boost_range_home__       [link range Boost.Range]]
+[def __ranges__                 [link range.concepts Ranges]]
+[def __range_concepts__         [link range.concepts Range concepts]]
+[def __forward_range__          [link range.concepts.forward_range Forward Range]]
+[def __single_pass_range__      [link range.concepts.single_pass_range Single Pass Range]]
+[def __bidirectional_range__    [link range.concepts.bidirectional_range Bidirectional Range]]
+[def __random_access_range__    [link range.concepts.random_access_range Random Access Range]]
+
+[def __iterator_range__         [link range.reference.utilities.iterator_range `iterator_range`]]
+[def __sub_range__              [link range.reference.utilities.sub_range `sub_range`]]
+[def __minimal_interface__      [link range.reference.extending minimal interface]]
+[def __range_result_iterator__  [link range.reference.concept_implementation.semantics.metafunctions `range_result_iterator`]]
+[def __extending_for_udts__ [link range.reference.extending Extending the library for UDTs]]
+[def __implementation_of_metafunctions__ [link range.reference.concept_implementation.semantics.metafunctions Implementation of metafunctions]]
+[def __implementation_of_functions__     [link range.reference.concept_implementation.semantics.functions Implementation of functions]]
+
+[def __range_value__            [link range.reference.concept_implementation.semantics.metafunctions `range_value`]]
+[def __range_iterator__         [link range.reference.concept_implementation.semantics.metafunctions `range_iterator`]]
+[def __range_difference__       [link range.reference.concept_implementation.semantics.metafunctions `range_difference`]]
+[def __range_pointer__          [link range.reference.concept_implementation.semantics.metafunctions `range_pointer`]]
+[def __range_category__         [link range.reference.concept_implementation.semantics.metafunctions `range_category`]]
+[def __range_reverse_iterator__ [link range.reference.concept_implementation.semantics.metafunctions `range_reverse_iterator`]]
+[def __begin__                  [link range.reference.concept_implementation.semantics.functions `begin`]]
+[def __const_begin__            [link range.reference.concept_implementation.semantics.functions `const_begin`]]
+[def __end__                    [link range.reference.concept_implementation.semantics.functions `end`]]
+[def __const_end__              [link range.reference.concept_implementation.semantics.functions `const_end`]]
+[def __empty__                  [link range.reference.concept_implementation.semantics.functions `empty`]]
+[def __distance__               [link range.reference.concept_implementation.semantics.functions `distance`]]
+[def __size__                   [link range.reference.concept_implementation.semantics.functions `size`]]
+[def __rbegin__                 [link range.reference.concept_implementation.semantics.functions `rbegin`]]
+[def __const_rbegin__           [link range.reference.concept_implementation.semantics.functions `const_rbegin`]]
+[def __rend__                   [link range.reference.concept_implementation.semantics.functions `rend`]]
+[def __const_rend__             [link range.reference.concept_implementation.semantics.functions `const_rend`]]
+[def __as_array__               [link range.reference.concept_implementation.semantics.functions `as_array`]]
+[def __as_literal__             [link range.reference.concept_implementation.semantics.functions `as_literal`]]
+[def __counting_range__         [link range.reference.ranges.counting_range `counting_range`]]
+[def __irange__                 [link range.reference.ranges.irange `irange`]]
+[def __istream_range__          [link range.reference.ranges.istream_range `istream_range`]]
+[def __combine__                [link range.reference.utilities.combine `combine`]]
+[def __join__                   [link range.reference.utilities.join `join`]]
+
+[def __range_adaptors__                   [link range.reference.adaptors Range adaptors]]
+[def __range_adaptors_adjacent_filtered__ [link range.reference.adaptors.reference.adjacent_filtered adjacent_filtered]]
+[def __range_adaptors_copied__            [link range.reference.adaptors.reference.copied copied]]
+[def __range_adaptors_filtered__          [link range.reference.adaptors.reference.filtered filtered]]
+[def __range_adaptors_formatted__         [link.range.reference.adaptors.reference.formatted formatted]]
+[def __range_adaptors_indexed__           [link range.reference.adaptors.reference.indexed indexed]]
+[def __range_adaptors_indirected__        [link range.reference.adaptors.reference.indirected indirected]]
+[def __range_adaptors_map_keys__          [link range.reference.adaptors.reference.map_keys map_keys]]
+[def __range_adaptors_map_values__        [link range.reference.adaptors.reference.map_values map_values]]
+[def __range_adaptors_replaced__          [link range.reference.adaptors.reference.replaced replaced]]
+[def __range_adaptors_replaced_if__       [link range.reference.adaptors.reference.replaced_if replaced_if]]
+[def __range_adaptors_reversed__          [link range.reference.adaptors.reference.reversed reversed]]
+[def __range_adaptors_sliced__            [link range.reference.adaptors.reference.sliced sliced]]
+[def __range_adaptors_strided__           [link range.reference.adaptors.reference.strided strided]]
+[def __range_adaptors_type_erased__       [link range.reference.adaptors.reference.type_erased type_erased]]
+[def __range_adaptors_tokenized__         [link range.reference.adaptors.reference.tokenized tokenized]]
+[def __range_adaptors_transformed__       [link range.reference.adaptors.reference.transformed transformed]]
+[def __range_adaptors_uniqued__           [link range.reference.adaptors.reference.uniqued uniqued]]
+
+
+[def __range_algorithms__                         [link range.reference.algorithms Range algorithms]]
+[def __range_algorithms_adjacent_find__           [link range.reference.algorithms.non_mutating.adjacent_find adjacent_find]]
+[def __range_algorithms_binary_search__           [link range.reference.algorithms.non_mutating.binary_search binary_search]]
+[def __range_algorithms_count__                   [link range.reference.algorithms.non_mutating.count count]]
+[def __range_algorithms_count_if__                [link range.reference.algorithms.non_mutating.count_if count_if]]
+[def __range_algorithms_equal__                   [link range.reference.algorithms.non_mutating.equal equal]]
+[def __range_algorithms_equal_range__             [link range.reference.algorithms.non_mutating.equal_range equal_range]]
+[def __range_algorithms_for_each__                [link range.reference.algorithms.non_mutating.for_each for_each]]
+[def __range_algorithms_find__                    [link range.reference.algorithms.non_mutating.find find]]
+[def __range_algorithms_find_end__                [link range.reference.algorithms.non_mutating.find_end find_end]]
+[def __range_algorithms_find_first_of__           [link range.reference.algorithms.non_mutating.find_first_of find_first_of]]
+[def __range_algorithms_find_if__                 [link range.reference.algorithms.non_mutating.find_if find_if]]
+[def __range_algorithms_lexicographical_compare__ [link range.reference.algorithms.non_mutating.lexicographical_compare lexicographical_compare]]
+[def __range_algorithms_lower_bound__             [link range.reference.algorithms.non_mutating.lower_bound lower_bound]]
+[def __range_algorithms_max_element__             [link range.reference.algorithms.non_mutating.max_element max_element]]
+[def __range_algorithms_min_element__             [link range.reference.algorithms.non_mutating.min_element min_element]]
+[def __range_algorithms_mismatch__                [link range.reference.algorithms.non_mutating.mismatch mismatch]]
+[def __range_algorithms_search__                  [link range.reference.algorithms.non_mutating.search search]]
+[def __range_algorithms_search_n__                [link range.reference.algorithms.non_mutating.search_n search_n]]
+[def __range_algorithms_upper_bound__             [link range.reference.algorithms.non_mutating.upper_bound upper_bound]]
+
+[def __range_algorithms_copy__                    [link range.reference.algorithms.mutating.copy copy]]
+[def __range_algorithms_copy_backward__           [link range.reference.algorithms.mutating.copy_backward copy_backward]]
+[def __range_algorithms_fill__                    [link range.reference.algorithms.mutating.fill fill]]
+[def __range_algorithms_fill_n__                  [link range.reference.algorithms.mutating.fill_n fill_n]]
+[def __range_algorithms_generate__                [link range.reference.algorithms.mutating.generate generate]]
+[def __range_algorithms_inplace_merge__           [link range.reference.algorithms.mutating.inplace_merge inplace_merge]]
+[def __range_algorithms_merge__                   [link range.reference.algorithms.mutating.merge merge]]
+[def __range_algorithms_nth_element__             [link range.reference.algorithms.mutating.nth_element nth_element]]
+[def __range_algorithms_partial_sort__            [link range.reference.algorithms.mutating.partial_sort partial_sort]]
+[def __range_algorithms_partition__               [link range.reference.algorithms.mutating.partition partition]]
+[def __range_algorithms_random_shuffle__          [link range.reference.algorithms.mutating.random_shuffle random_shuffle]]
+[def __range_algorithms_remove__                  [link range.reference.algorithms.mutating.remove remove]]
+[def __range_algorithms_remove_copy__             [link range.reference.algorithms.mutating.remove_copy remove_copy]]
+[def __range_algorithms_remove_copy_if__          [link range.reference.algorithms.mutating.remove_copy_if remove_copy_if]]
+[def __range_algorithms_remove_if__               [link range.reference.algorithms.mutating.remove_if remove_if]]
+[def __range_algorithms_replace__                 [link range.reference.algorithms.mutating.replace replace]]
+[def __range_algorithms_replace_copy__            [link range.reference.algorithms.mutating.replace_copy replace_copy]]
+[def __range_algorithms_replace_copy_if__         [link range.reference.algorithms.mutating.replace_copy_if replace_copy_if]]
+[def __range_algorithms_replace_if__              [link range.reference.algorithms.mutating.replace_if replace_if]]
+[def __range_algorithms_reverse__                 [link range.reference.algorithms.mutating.reverse reverse]]
+[def __range_algorithms_reverse_copy__            [link range.reference.algorithms.mutating.reverse_copy reverse_copy]]
+[def __range_algorithms_rotate__                  [link range.reference.algorithms.mutating.rotate rotate]]
+[def __range_algorithms_rotate_copy__             [link range.reference.algorithms.mutating.rotate_copy rotate_copy]]
+[def __range_algorithms_sort__                    [link range.reference.algorithms.mutating.sort sort]]
+[def __range_algorithms_stable_partition__        [link range.reference.algorithms.mutating.stable_partition stable_partition]]
+[def __range_algorithms_stable_sort__             [link range.reference.algorithms.mutating.stable_sort stable_sort]]
+[def __range_algorithms_swap_ranges__             [link range.reference.algorithms.mutating.swap_ranges swap_ranges]]
+[def __range_algorithms_transform__               [link range.reference.algorithms.mutating.transform transform]]
+[def __range_algorithms_unique__                  [link range.reference.algorithms.mutating.unique unique]]
+[def __range_algorithms_unique_copy__             [link range.reference.algorithms.mutating.unique_copy unique_copy]]
+
+[def __range_algorithms_includes__                 [link range.reference.algorithms.set.includes includes]]
+[def __range_algorithms_set_union__                [link range.reference.algorithms.set.set_union set_union]]
+[def __range_algorithms_set_intersection__         [link range.reference.algorithms.set.set_intersection set_intersection]]
+[def __range_algorithms_set_difference__           [link range.reference.algorithms.set.set_difference set_difference]]
+[def __range_algorithms_set_symmetric_difference__ [link range.reference.algorithms.set.set_symmetric_difference set_symmetric_difference]]
+
+[def __range_algorithms_push_heap__         [link range.reference.algorithms.heap.push_heap push_heap]]
+[def __range_algorithms_pop_heap__          [link range.reference.algorithms.heap.pop_heap pop_heap]]
+[def __range_algorithms_make_heap__         [link range.reference.algorithms.heap.make_heap make_heap]]
+[def __range_algorithms_sort_heap__         [link range.reference.algorithms.heap.sort_heap sort_heap]]
+
+[def __range_algorithms_next_permutation__  [link range.reference.algorithms.permutation.next_permutation next_permutation]]
+[def __range_algorithms_prev_permutation__ [link range.reference.algorithms.permutation.prev_permutation prev_permutation]]
+
+[def __range_algorithm_ext_copy_n__         [link range.reference.algorithms.new.copy_n copy_n]]
+[def __range_algorithm_ext_erase__          [link range.reference.algorithms.new.erase erase]]
+[def __range_algorithm_ext_for_each__       [link range.reference.algorithms.new.for_each for_each]]
+[def __range_algorithm_ext_insert__         [link range.reference.algorithms.new.insert insert]]
+[def __range_algorithm_ext_iota__           [link range.reference.algorithms.new.iota iota]]
+[def __range_algorithm_ext_is_sorted__      [link range.reference.algorithms.new.is_sorted is_sorted]]
+[def __range_algorithm_ext_overwrite__      [link range.reference.algorithms.new.overwrite overwrite]]
+[def __range_algorithm_ext_push_back__      [link range.reference.algorithms.new.push_back push_back]]
+[def __range_algorithm_ext_push_front__     [link range.reference.algorithms.new.push_front push_front]]
+
+[def __single_pass_iterator__   [@boost:/libs/iterator/doc/new-iter-concepts.html#singls-pass-iterators-lib-single-pass-iterators Single Pass Iterator]]
+[def __forward_traversal_iterator__ [@boost:/libs/iterator/doc/new-iter-concepts.html#forward-traversal-iterators-lib-forward-traversal-iterators Forward Traversal Iterator]]
+[def __bidirectional_traversal_iterator__ [@boost:/libs/iterator/doc/new-iter-concepts.html#bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators Bidirectional Traversal Iterator]]
+[def __random_access_traversal_iterator__ [@boost:/libs/iterator/doc/new-iter-concepts.html#random-access-traversal-iterators-lib-random-access-traversal-iterators Random Access Traversal Iterator]]
+[def __new_style_iterators__    [@boost:/libs/iterator/doc/new-iter-concepts.html new style iterators]]
+[def __iterator_concepts__      [@boost:/libs/iterator/doc/iterator_concepts.html Iterator concepts]]
+
+[def __container__              [@http://www.sgi.com/Technology/STL/Container.html Container]]
+[def __metafunctions__          [@boost:/libs/mpl/doc/refmanual/metafunction.html metafunctions]]
+[def __concept_check__          [@boost:/libs/concept_check/index.html Boost Concept Check library]]
+[def __boost_array__            [@boost:/libs/array/index.html boost::array]]
+[def __the_forwarding_problem__ [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1385.htm The Forwarding Problem]]
+
+[def __sgi_inner_product__      [@http://www.sgi.com/tech/stl/inner_product.html inner_product]]
+[def __sgi_partial_sum__        [@http://www.sgi.com/tech/stl/partial_sum.html partial_sum]]
+[def __type_erasure_article__   [@http://www.artima.com/cppsource/type_erasure.html type erasure article]]
+
+Boost.Range is a collection of concepts and utilities, range-based algorithms,
+as well as range adaptors that allow for efficient and expressive code.
+
+Using Boost.Range inplace of the standard library alternatives results in more
+readable code and in many cases greater efficiency.
+
+[include introduction.qbk]
+[include concepts.qbk]
+[include reference.qbk]
+[include style.qbk]
+[include headers.qbk]
+[include examples.qbk]
+[include mfc_atl.qbk]
+[include upgrade.qbk]
+[include portability.qbk]
+[include faq.qbk]
+[include history_ack.qbk]
+

doc/concepts.qbk

@@ -0,0 +1,255 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:concepts Range Concepts]
+
+[section Overview]
+
+A Range is a [*/concept/] similar to the STL [@http://www.sgi.com/tech/stl/Container.html Container] concept. A Range provides iterators for accessing a half-open range `[first,one_past_last)` of elements and provides information about the number of elements in the Range. However, a Range has fewer requirements than a Container.
+
+The motivation for the Range concept is that there are many useful Container-like types that do not meet the full requirements of Container, and many algorithms that can be written with this reduced set of requirements. In particular, a Range does not necessarily
+
+* own the elements that can be accessed through it,
+* have copy semantics,
+
+Because of the second requirement, a Range object must be passed by (const or non-const) reference in generic code.
+
+The operations that can be performed on a Range is dependent on the [@boost:/libs/iterator/doc/new-iter-concepts.html#iterator-traversal-concepts-lib-iterator-traversal traversal category] of the underlying iterator type. Therefore the range concepts are named to reflect which traversal category its iterators support. See also terminology and style guidelines. for more information about naming of ranges.
+
+The concepts described below specifies associated types as [@boost:/libs/mpl/doc/refmanual/metafunction.html metafunctions] and all functions as free-standing functions to allow for a layer of indirection.
+
+[endsect]
+
+
+[section Single Pass Range]
+
+[heading Notation]
+
+[table
+    []
+    [[`X`] [A type that is a model of __single_pass_range__.]]
+    [[`a`] [Object of type X.]]
+]
+
+[heading Description]
+
+A range `X` where `boost::range_iterator<X>::type` is a model of __single_pass_iterator__.
+
+[heading Associated types]
+
+[table
+  []
+  [[Iterator type      ] [`boost::range_iterator<X>::type`      ] [The type of iterator used to iterate through a Range's elements. The iterator's value type is expected to be the Range's value type. A conversion from the iterator type to the `const` iterator type must exist.]]
+  [[Const iterator type] [`boost::range_iterator<const X>::type`] [A type of iterator that may be used to examine, but not to modify, a Range's elements.]]
+]
+
+[heading Valid expressions]
+
+The following expressions must be valid.
+
+[table
+  [[Name              ] [Expression       ] [Return type        ]]
+  [[Beginning of range] [`boost::begin(a)`] [`boost::range_iterator<X>::type` if `a` is mutable, `boost::range_iterator<const X>::type` otherwise]]
+  [[End of range      ] [`boost::end(a)`  ] [`boost::range_iterator<X>::type` if `a` is mutable, `boost::range_iterator<const X>::type` otherwise]]
+]
+
+[heading Expression semantics]
+
+[table
+  [[Expression       ] [Semantics                                                               ] [Postcondition]]
+  [[`boost::begin(a)`] [Returns an iterator pointing to the first element in the Range.         ] [`boost::begin(a)` is either dereferenceable or past-the-end. It is past-the-end if and only if `boost::distance(a) == 0`.]]
+  [[`boost::end(a)`  ] [Returns an iterator pointing one past the last element in the Range.    ] [`boost::end(a)` is past-the-end.]]
+]
+
+[heading Complexity guarantees]
+
+`boost::end(a)` is at most amortized linear time, `boost::begin(a)` is amortized constant time. For most practical purposes, one can expect both to be amortized constant time.
+
+[heading Invariants]
+
+[table
+  []
+  [[Valid range ] [For any Range `a`, `[boost::begin(a),boost::end(a))` is a valid range, that is, `boost::end(a)` is reachable from `boost::begin(a)` in a finite number of increments.]]
+
+  [[Completeness] [An algorithm that iterates through the range `[boost::begin(a),boost::end(a))` will pass through every element of `a`.]]
+]
+
+[heading See also]
+
+__extending_for_udts__
+
+__implementation_of_metafunctions__
+
+__implementation_of_functions__
+
+__container__
+
+[endsect]
+
+
+[section Forward Range]
+
+[heading Notation]
+
+[table
+    []
+    [[`X`] [A type that is a model of __forward_range__.]]
+    [[`a`] [Object of type X.]]
+]
+
+[heading Description]
+
+A range `X` where `boost::range_iterator<X>::type` is a model of __forward_traversal_iterator__.
+
+[heading Refinement of]
+
+__single_pass_range__
+
+[heading Associated types]
+
+[table
+  []
+  [[Distance type] [`boost::range_difference<X>::type`] [A signed integral type used to represent the distance between two of the Range's iterators. This type must be the same as the iterator's distance type.]]
+  [[Size type    ] [`boost::range_size<X>::type`      ] [An unsigned integral type that can represent any nonnegative value of the Range's distance type.]]
+]
+
+[heading See also]
+
+__implementation_of_metafunctions__
+
+__implementation_of_functions__
+
+[endsect]
+
+
+[section Bidirectional Range]
+
+[heading Notation]
+
+[table
+    []
+    [[`X`] [A type that is a model of __bidirectional_range__.]]
+    [[`a`] [Object of type X.]]
+]
+
+[heading Description]
+
+This concept provides access to iterators that traverse in both directions (forward and reverse). The `boost::range_iterator<X>::type` iterator must meet all of the requirements of __bidirectional_traversal_iterator__.
+
+[heading Refinement of]
+
+__forward_range__
+
+[heading Associated types]
+
+[table
+  []
+  [[Reverse Iterator type      ] [`boost::range_reverse_iterator<X>::type`      ] [The type of iterator used to iterate through a Range's elements in reverse order. The iterator's value type is expected to be the Range's value type. A conversion from the reverse iterator type to the const reverse iterator type must exist.]]
+
+  [[Const reverse iterator type] [`boost::range_reverse_iterator<const X>::type`] [A type of reverse iterator that may be used to examine, but not to modify, a Range's elements.]]
+]
+
+[heading Valid expressions]
+
+[table
+  [[Name              ] [Expression        ] [Return type] [Semantics]]
+  [[Beginning of range] [`boost::rbegin(a)`] [`boost::range_reverse_iterator<X>::type` if `a` is mutable `boost::range_reverse_iterator<const X>::type` otherwise.] [Equivalent to `boost::range_reverse_iterator<X>::type(boost::end(a))`.]]
+
+  [[End of range      ] [`boost::rend(a)`  ] [`boost::range_reverse_iterator<X>::type` if `a` is mutable, `boost::range_reverse_iterator<const X>::type` otherwise.] [Equivalent to `boost::range_reverse_iterator<X>::type(boost::begin(a))`.]]
+]
+
+[heading Complexity guarantees]
+
+`boost::rbegin(a)` has the same complexity as `boost::end(a)` and `boost::rend(a)` has the same complexity as `boost::begin(a)` from __forward_range__.
+
+[heading Invariants]
+
+[table
+  []
+  [[Valid reverse range] [For any Bidirectional Range a, `[boost::rbegin(a),boost::rend(a))` is a valid range, that is, `boost::rend(a)` is reachable from `boost::rbegin(a)` in a finite number of increments.]]
+
+  [[Completeness       ] [An algorithm that iterates through the range `[boost::rbegin(a),boost::rend(a))` will pass through every element of `a`.]]
+]
+
+[heading See also]
+
+__implementation_of_metafunctions__
+
+__implementation_of_functions__
+
+[endsect]
+
+
+[section Random Access Range]
+
+[heading Description]
+
+A range `X` where `boost::range_iterator<X>::type` is a model of __random_access_traversal_iterator__.
+
+[heading Refinement of]
+
+__bidirectional_range__
+
+[heading Valid expressions]
+
+[table
+  [[Name         ] [Expression      ] [Return type                 ]]
+  [[Size of range] [`boost::size(a)`] [`boost::range_size<X>::type`]]
+]
+
+[heading Expression semantics]
+
+[table
+  [[Expression      ] [Semantics] [Postcondition]]
+  [[`boost::size(a)`] [Returns the size of the Range, that is, its number of elements. Note `boost::size(a) == 0u` is equivalent to `boost::empty(a)`.] [`boost::size(a) >= 0`]]
+]
+
+[heading Complexity guarantees]
+
+`boost::size(a)` completes in amortized constant time.
+
+[heading Invariants]
+
+[table
+  []
+  [[Range size] [`boost::size(a)` is equal to the `boost::end(a)` - `boost::begin(a)`.]]
+]
+
+[endsect]
+
+
+[section Concept Checking]
+
+Each of the range concepts has a corresponding concept checking class in the file [@boost:/boost/range/concepts.hpp `<boost/range/concepts.hpp>`]. These classes may be used in conjunction with the __concept_check__ to ensure that the type of a template parameter is compatible with a range concept. If not, a meaningful compile time error is generated. Checks are provided for the range concepts related to iterator traversal categories. For example, the following line checks that the type `T` models the __forward_range__ concept.
+
+``
+BOOST_CONCEPT_ASSERT(( ForwardRangeConcept<T> ));
+``
+
+An additional concept check is required for the value access property of the range based on the range's iterator type. For example to check for a ForwardReadableRange, the following code is required.
+
+``
+BOOST_CONCEPT_ASSERT(( ForwardRangeConcept<T> ));
+BOOST_CONCEPT_ASSERT(( ReadableIteratorConcept<typename range_iterator<T>::type> ));
+``
+
+The following range concept checking classes are provided.
+
+* Class SinglePassRangeConcept checks for __single_pass_range__
+* Class ForwardRangeConcept checks for __forward_range__
+* Class BidirectionalRangeConcept checks for __bidirectional_range__
+* Class RandomAccessRangeConcept checks for __random_access_range__
+
+[heading See also]
+
+[link range.style_guide Range Terminology and style guidelines]
+
+__iterator_concepts__
+
+__concept_check__
+
+[endsect]
+[endsect]
+

doc/example.cpp

@@ -0,0 +1,151 @@
+// Boost.Range library
+//
+//  Copyright Thorsten Ottosen 2003-2008. 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)
+//
+// For more information, see http://www.boost.org/libs/range/
+//
+
+#include <boost/range.hpp>
+#include <iterator>         // for std::iterator_traits, std::distance()
+
+namespace Foo
+{
+        //
+        // Our sample UDT. A 'Pair'
+        // will work as a range when the stored
+        // elements are iterators.
+        //
+        template< class T >
+        struct Pair
+        {
+                T first, last;
+        };
+
+} // namespace 'Foo'
+
+namespace boost
+{
+        //
+        // Specialize metafunctions. We must include the range.hpp header.
+        // We must open the 'boost' namespace.
+        //
+        /*
+        template< class T >
+        struct range_value< Foo::Pair<T> >
+        {
+                typedef typename std::iterator_traits<T>::value_type type;
+        };
+        */
+
+        template< class T >
+        struct range_iterator< Foo::Pair<T> >
+        {
+                typedef T type;
+        };
+
+        template< class T >
+        struct range_const_iterator< Foo::Pair<T> >
+        {
+                //
+                // Remark: this is defined similar to 'range_iterator'
+                //         because the 'Pair' type does not distinguish
+                //         between an iterator and a const_iterator.
+                //
+                typedef T type;
+        };
+
+        /*
+    template< class T >
+        struct range_difference< Foo::Pair<T> >
+        {
+                typedef typename std::iterator_traits<T>::difference_type type;
+        };
+        */
+
+        template< class T >
+    struct range_size< Foo::Pair<T> >
+        {
+                int static_assertion[ sizeof( std::size_t ) >=
+                          sizeof( typename range_difference< Foo::Pair<T> >::type ) ];
+                typedef std::size_t type;
+        };
+
+} // namespace 'boost'
+
+namespace Foo
+{
+        //
+        // The required functions. These should be defined in
+        // the same namespace as 'Pair', in this case
+        // in namespace 'Foo'.
+        //
+
+        template< class T >
+        inline T boost_range_begin( Pair<T>& x )
+        {
+                return x.first;
+        }
+
+    template< class T >
+        inline T boost_range_begin( const Pair<T>& x )
+        {
+                return x.first;
+        }
+
+        template< class T >
+    inline T boost_range_end( Pair<T>& x )
+        {
+                return x.last;
+        }
+
+        template< class T >
+    inline T boost_range_end( const Pair<T>& x )
+        {
+                return x.last;
+        }
+
+        template< class T >
+        inline typename boost::range_size< Pair<T> >::type
+        boost_range_size( const Pair<T>& x )
+        {
+                return std::distance(x.first,x.last);
+        }
+
+} // namespace 'Foo'
+
+#include <vector>
+
+int main()
+{
+        typedef std::vector<int>::iterator  iter;
+        std::vector<int>                    vec;
+        vec.push_back( 42 );
+        Foo::Pair<iter>                     pair  = { vec.begin(), vec.end() };
+        const Foo::Pair<iter>&              cpair = pair;
+        //
+        // Notice that we call 'begin' etc with qualification.
+        //
+        iter i = boost::begin( pair );
+        iter e = boost::end( pair );
+        i      = boost::begin( cpair );
+        e      = boost::end( cpair );
+        boost::range_size< Foo::Pair<iter> >::type s = boost::size( pair );
+        s      = boost::size( cpair );
+        boost::range_const_reverse_iterator< Foo::Pair<iter> >::type
+        ri     = boost::rbegin( cpair ),
+        re         = boost::rend( cpair );
+
+        //
+        // Test metafunctions
+        //
+
+        boost::range_value< Foo::Pair<iter> >::type
+        v = *boost::begin(pair);
+
+        boost::range_difference< Foo::Pair<iter> >::type
+        d = boost::end(pair) - boost::begin(pair);
+}
+

doc/examples.qbk

@@ -0,0 +1,28 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:examples Examples]
+
+Some examples are given in the accompanying test files:
+
+* [@http://www.boost.org/libs/range/test/string.cpp string.cpp] shows how to implement a container version of `std::find()` that works with `char[]`,`wchar_t[]`,`char*`,`wchar_t*`.
+
+* [@http://www.boost.org/libs/range/test/algorithm_example.cpp algorithm_example.cpp] shows the replace example from the introduction.
+
+* [@http://www.boost.org/libs/range/test/iterator_range.cpp iterator_range.cpp]
+
+* [@http://www.boost.org/libs/range/test/sub_range.cpp sub_range.cpp]
+
+* [@http://www.boost.org/libs/range/test/iterator_pair.cpp iterator_pair.cpp]
+
+* [@http://www.boost.org/libs/range/test/reversible_range.cpp reversible_range.cpp]
+
+* [@http://www.boost.org/libs/range/test/std_container.cpp std_container.cpp]
+
+* [@http://www.boost.org/libs/range/test/array.cpp array.cpp]
+
+[endsect]
+
+

doc/external_concepts.html

@@ -1,38 +0,0 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><title> Concepts and External Concepts </title><meta http-equiv="Content-Type"content="text/html; charset=iso-8859-1"></head> <body><table  ><tr  ><td  ><img src="cboost.gif" width="100%" border="0"></td><td  ><h1  >Concepts and External Concepts</h1></td></tr></table><p  >Generic programming in C++ is characterized by the use of function and class templates where
-                the template parameter(s) must satisfy certain requirements.Often these
-                requirements are so important that we give them a name: we call
-                such a set of type requirements a <b>concept</b>. We say that a type <i>
-                conforms to a concept</i> or that it <i>is a model of a concept</i> if it
-                satisfies all of those requirements. The concept can be specified as a set
-                of member functions with well-defined semantics
-                and a set of nested typedefs with well-defined properties.</p><p  >Often it much more flexible to provide free-standing functions and typedefs
-            which provides the exact same semantics (but a different syntax) as
-            specified
-            by the concept. This allows generic code to treat different types <i> as if
-            </i> they fulfilled the concept. In this case we say that the concept has
-            been <b> externalized </b> or that the new requirements constitutes an <b>external
-            concept </b>. We say that a type <i> conforms to an external concept </i>
-            or that it <i> is a model of an external concept </i>. A concept may exist
-            without a corresponding external concept and conversely.</p><p  >Whenever a concept specifies a member function, the corresponding  external
-            concept
-            must specify a free-standing function of the same name, same return type and
-            the same argument list except there is an extra first argument which must
-            be of the type (or a reference to that type) that is to fulfill the external
-            concept. If the corresonding member function has any cv-qulifiers, the
-            first argument must have the same cv-qualifiers. Whenever a concept
-            specifies a nested typedef, the corresponding external concept
-            specifies a <b>type-generator</b>, that is, a type with a nested typedef
-            named <code>type</code>. The type-generator has the name as the nested typedef with
-            <code>_of</code> appended.
-            The converse relationship of an external concept and its corresponding concept
-            also holds.</p><p  ><b  ><i  >Example:</i></b></p><p  >A type <code>T</code> fulfills the FooConcept if it
-            has the follwing public members:</p><code> void T::foo( int ) const; <br>
-                 int T::bar(); <br> 
-               typedef <i>implementation defined </i> foo_type;</code><p  >The corresponding external concept is the ExternalFooConcept.</p><p  >A type <code>T</code> fullfills the ExternalFooConcept if these
-            free-standing functions and type-generators exists:</p><code>void foo( const T&, int ); <br>
-                int bar( T& ); <br>
-             foo_type_of< T >::type;</code> <br> <br><hr size="1" ><h3  >Literature</h3><ul  ><li  > <a href="http://www.boost.org/more/generic_programming.html#type_generator" target="_self" >Type Generators</a> </li><li  > <a href="http://www.boost.org/more/generic_programming.html#concept" target="_self" >Concepts</a> </li><li  > <a href="http://www.sgi.com/tech/stl/stl_introduction.html" target="_self" >Concepts and SGI STL</a> </li></ul><hr size="1" ><p  >&copy; Thorsten Ottosen 2003-2004 (nesotto_AT_cs.auc.dk).
-    Permission to copy, use, modify, sell and distribute this software is granted provided this copyright notice appears
-     in all copies. This software is provided "as is" without express or implied warranty, and with no
-         claim as to its suitability for any purpose.</p><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br></body></html>
- <!-- Copyright Dezide Aps 2003-2004 -->

doc/faq.qbk

@@ -0,0 +1,30 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:faq FAQ]
+
+1. ['[*Why is there no difference between `range_iterator<C>::type`  and `range_const_iterator<C>::type` for `std::pair<iterator, iterator>`?]]
+
+[:In general it is not possible nor desirable to find a corresponding `const_iterator`. When it is possible to come up with one, the client might choose to construct a `std::pair<const_iterator,const_iterator>` object.]
+
+[:Note that an __iterator_range__ is somewhat more convenient than a `pair` and that a __sub_range__ does propagate const-ness.]
+
+2. ['[*Why is there not supplied more types or more functions?]]
+
+[:The library has been kept small because its current interface will serve most purposes. If and when a genuine need arises for more functionality, it can be implemented.]
+
+3. ['[*How should I implement generic algorithms for ranges?]]
+
+[:One should always start with a generic algorithm that takes two iterators (or more) as input. Then use Boost.Range to build handier versions on top of the iterator based algorithm. Please notice that once the range version of the algorithm is done, it makes sense not to expose the iterator version in the public interface.]
+
+4. ['[*Why is there no Incrementable Range concept?]]
+
+[:Even though we speak of incrementable iterators, it would not make much sense for ranges; for example, we cannot determine the size and emptiness of a range since we cannot even compare its iterators.]
+
+[:Note also that incrementable iterators are derived from output iterators and so there exist no output range.]
+
+[endsect]
+
+

doc/headers.qbk

@@ -0,0 +1,143 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:headers Library Headers]
+
+[section:general General]
+[table
+    [[Header                              ] [Includes                   ] [Related Concept         ]]
+    [[`<boost/range.hpp>`                 ] [everything from Boost.Range version 1 (Boost versions 1.42 and below). Includes the core range functions and metafunctions, but excludes Range Adaptors and Range Algorithms. ] [-                       ]]
+    [[`<boost/range/metafunctions.hpp>`   ] [every metafunction         ] [-                       ]]
+    [[`<boost/range/functions.hpp>`       ] [every function             ] [-                       ]]
+    [[`<boost/range/value_type.hpp>`      ] [__range_value__            ] [__single_pass_range__   ]]
+    [[`<boost/range/iterator.hpp>`        ] [__range_iterator__         ] [__single_pass_range__   ]]
+    [[`<boost/range/difference_type.hpp>` ] [__range_difference__       ] [__forward_range__       ]]
+    [[`<boost/range/pointer.hpp>`         ] [__range_pointer__          ] [-]]
+    [[`<boost/range/category.hpp>`        ] [__range_category__         ] [-]]
+    [[`<boost/range/reverse_iterator.hpp>`] [__range_reverse_iterator__ ] [__bidirectional_range__ ]]
+    [[`<boost/range/begin.hpp>`           ] [__begin__ and __const_begin__ ] [__single_pass_range__   ]]
+    [[`<boost/range/end.hpp>`             ] [__end__ and __const_end__  ] [__single_pass_range__   ]]
+    [[`<boost/range/empty.hpp>`           ] [__empty__                  ] [__single_pass_range__   ]]
+    [[`<boost/range/distance.hpp>`        ] [__distance__               ] [__forward_range__       ]]
+    [[`<boost/range/size.hpp>`            ] [__size__                   ] [__random_access_range__ ]]
+    [[`<boost/range/rbegin.hpp>`          ] [__rbegin__ and __const_rbegin__] [__bidirectional_range__ ]]
+    [[`<boost/range/rend.hpp>`            ] [__rend__ and __const_rend__ ] [__bidirectional_range__ ]]
+    [[`<boost/range/as_array.hpp>`        ] [__as_array__               ] [-                       ]]
+    [[`<boost/range/as_literal.hpp>`      ] [__as_literal__             ] [-                       ]]
+    [[`<boost/range/iterator_range.hpp>`  ] [__iterator_range__         ] [-                       ]]
+    [[`<boost/range/sub_range.hpp>`       ] [__sub_range__              ] [-                       ]]
+    [[`<boost/range/concepts.hpp>`        ] [__range_concepts__         ] [-                       ]]
+    [[`<boost/range/adaptors.hpp>`        ] [every range adaptor        ] [-                       ]]
+    [[`<boost/range/algorithm.hpp>`       ] [every range equivalent of an STL algorithm ] [-                       ]]
+    [[`<boost/range/algorithm_ext.hpp>`   ] [every range algorithm that is an extension of the STL algorithms ] [-                       ]]
+    [[`<boost/range/counting_range.hpp>`  ] [ __counting_range__ ] [-]]
+    [[`<boost/range/istream_range.hpp>`   ] [ __istream_range__ ] [-]]
+    [[`<boost/range/irange.hpp>`          ] [ __irange__ ] [-]]
+    [[`<boost/range/join.hpp>`            ] [ __join__ ] [-]]
+]
+[endsect]
+
+[section:adaptors Adaptors]
+[table
+    [[Header                                        ][Includes                                           ]]
+    [[`<boost/range/adaptor/adjacent_filtered.hpp>`] [__range_adaptors_adjacent_filtered__ ]]
+    [[`<boost/range/adaptor/copied.hpp>`]            [__range_adaptors_copied__]]
+    [[`<boost/range/adaptor/filtered.hpp>`]          [__range_adaptors_filtered__]]
+    [[`<boost/range/adaptor/indexed.hpp>`]           [__range_adaptors_indexed__]]
+    [[`<boost/range/adaptor/indirected.hpp>`]        [__range_adaptors_indirected__]]
+    [[`<boost/range/adaptor/map.hpp>`]               [__range_adaptors_map_keys__ __range_adaptors_map_values__]]
+    [[`<boost/range/adaptor/replaced.hpp>`]          [__range_adaptors_replaced__]]
+    [[`<boost/range/adaptor/replaced_if.hpp>`]       [__range_adaptors_replaced_if__]]
+    [[`<boost/range/adaptor/reversed.hpp>`]          [__range_adaptors_reversed__]]
+    [[`<boost/range/adaptor/sliced.hpp>`]            [__range_adaptors_sliced__]]
+    [[`<boost/range/adaptor/strided.hpp>`]           [__range_adaptors_strided__]]
+    [[`<boost/range/adaptor/tokenized.hpp>`]         [__range_adaptors_tokenized__]]
+    [[`<boost/range/adaptor/transformed.hpp>`]       [__range_adaptors_transformed__]]
+    [[`<boost/range/adaptor/uniqued.hpp>`]           [__range_adaptors_uniqued__]]
+]
+[endsect]
+
+[section:algorithm Algorithm]
+[table
+    [[Header                                        ][Includes                                           ]]
+    [[`<boost/range/algorithm/adjacent_find.hpp>`]           [__range_algorithms_adjacent_find__]]
+    [[`<boost/range/algorithm/binary_search.hpp>`]           [__range_algorithms_binary_search__]]
+    [[`<boost/range/algorithm/copy.hpp>`]                    [__range_algorithms_copy__]]
+    [[`<boost/range/algorithm/copy_backward.hpp>`]           [__range_algorithms_copy_backward__]]
+    [[`<boost/range/algorithm/count.hpp>`]                   [__range_algorithms_count__]]
+    [[`<boost/range/algorithm/count_if.hpp>`]                [__range_algorithms_count_if__]]
+    [[`<boost/range/algorithm/equal.hpp>`]                   [__range_algorithms_equal__]]
+    [[`<boost/range/algorithm/equal_range.hpp>`]             [__range_algorithms_equal_range__]]
+    [[`<boost/range/algorithm/fill.hpp>`]                    [__range_algorithms_fill__]]
+    [[`<boost/range/algorithm/fill_n.hpp>`]                  [__range_algorithms_fill_n__]]
+    [[`<boost/range/algorithm/find.hpp>`]                    [__range_algorithms_find__]]
+    [[`<boost/range/algorithm/find_end.hpp>`]                [__range_algorithms_find_end__]]
+    [[`<boost/range/algorithm/find_first_of.hpp>`]           [__range_algorithms_find_first_of__]]
+    [[`<boost/range/algorithm/find_if.hpp>`]                 [__range_algorithms_find_if__]]
+    [[`<boost/range/algorithm/for_each.hpp>`]                [__range_algorithms_for_each__]]
+    [[`<boost/range/algorithm/generate.hpp>`]                [__range_algorithms_generate__]]
+    [[`<boost/range/algorithm/heap_algorithm.hpp>`]          [__range_algorithms_push_heap__
+                                                              __range_algorithms_pop_heap__
+                                                              __range_algorithms_make_heap__
+                                                              __range_algorithms_sort_heap__]]
+    [[`<boost/range/algorithm/inplace_merge.hpp>`]           [__range_algorithms_inplace_merge__]]
+    [[`<boost/range/algorithm/lexicographical_compare.hpp>`] [__range_algorithms_lexicographical_compare__]]
+    [[`<boost/range/algorithm/lower_bound.hpp>`]             [__range_algorithms_lower_bound__]]
+    [[`<boost/range/algorithm/max_element.hpp>`]             [__range_algorithms_max_element__]]
+    [[`<boost/range/algorithm/merge.hpp>`]                   [__range_algorithms_merge__]]
+    [[`<boost/range/algorithm/min_element.hpp>`]             [__range_algorithms_min_element__]]
+    [[`<boost/range/algorithm/mismatch.hpp>`]                [__range_algorithms_mismatch__]]
+    [[`<boost/range/algorithm/nth_element.hpp>`]             [__range_algorithms_nth_element__]]
+    [[`<boost/range/algorithm/partial_sort.hpp>`]            [__range_algorithms_partial_sort__]]
+    [[`<boost/range/algorithm/partition.hpp>`]               [__range_algorithms_partition__]]
+    [[`<boost/range/algorithm/permutation.hpp>`]             [__range_algorithms_next_permutation__
+                                                              __range_algorithms_prev_permutation__]]
+    [[`<boost/range/algorithm/random_shuffle.hpp>`]          [__range_algorithms_random_shuffle__]]
+    [[`<boost/range/algorithm/remove.hpp>`]                  [__range_algorithms_remove__]]
+    [[`<boost/range/algorithm/remove_copy.hpp>`]             [__range_algorithms_remove_copy__]]
+    [[`<boost/range/algorithm/remove_copy_if.hpp>`]          [__range_algorithms_remove_copy_if__]]
+    [[`<boost/range/algorithm/remove_if.hpp>`]               [__range_algorithms_remove_if__]]
+    [[`<boost/range/algorithm/replace.hpp>`]                 [__range_algorithms_replace__]]
+    [[`<boost/range/algorithm/replace_copy.hpp>`]            [__range_algorithms_replace_copy__]]
+    [[`<boost/range/algorithm/replace_copy_if.hpp>`]         [__range_algorithms_replace_copy_if__]]
+    [[`<boost/range/algorithm/replace_if.hpp>`]              [__range_algorithms_replace_if__]]
+    [[`<boost/range/algorithm/reverse.hpp>`]                 [__range_algorithms_reverse__]]
+    [[`<boost/range/algorithm/reverse_copy.hpp>`]            [__range_algorithms_reverse_copy__]]
+    [[`<boost/range/algorithm/rotate.hpp>`]                  [__range_algorithms_rotate__]]
+    [[`<boost/range/algorithm/rotate_copy.hpp>`]             [__range_algorithms_rotate_copy__]]
+    [[`<boost/range/algorithm/search.hpp>`]                  [__range_algorithms_search__]]
+    [[`<boost/range/algorithm/search_n.hpp>`]                [__range_algorithms_search_n__]]
+    [[`<boost/range/algorithm/set_algorithm.hpp>`]           [__range_algorithms_includes__
+                                                              __range_algorithms_set_union__
+                                                              __range_algorithms_set_intersection__
+                                                              __range_algorithms_set_difference__
+                                                              __range_algorithms_set_symmetric_difference__]]
+    [[`<boost/range/algorithm/sort.hpp>`]                    [__range_algorithms_sort__]]
+    [[`<boost/range/algorithm/stable_partition.hpp>`]        [__range_algorithms_stable_partition__]]
+    [[`<boost/range/algorithm/swap_ranges.hpp>`]             [__range_algorithms_swap_ranges__]]
+    [[`<boost/range/algorithm/transform.hpp>`]               [__range_algorithms_transform__]]
+    [[`<boost/range/algorithm/unique.hpp>`]                  [__range_algorithms_unique__]]
+    [[`<boost/range/algorithm/unique_copy.hpp>`]             [__range_algorithms_unique_copy__]]
+    [[`<boost/range/algorithm/upper_bound.hpp>`]             [__range_algorithms_upper_bound__]]
+]
+[endsect]
+
+[section:algorithm_ext Algorithm Extensions]
+[table
+    [[Header                                        ][Includes                                           ]]
+    [[`<boost/range/algorithm_ext/copy_n.hpp>`]     [__range_algorithm_ext_copy_n__]]
+    [[`<boost/range/algorithm_ext/erase.hpp>`]      [__range_algorithm_ext_erase__]]
+    [[`<boost/range/algorithm_ext/for_each.hpp>`]   [__range_algorithm_ext_for_each__]]
+    [[`<boost/range/algorithm_ext/insert.hpp>`]     [__range_algorithm_ext_insert__]]
+    [[`<boost/range/algorithm_ext/iota.hpp>`]       [__range_algorithm_ext_iota__]]
+    [[`<boost/range/algorithm_ext/is_sorted.hpp>`]  [__range_algorithm_ext_is_sorted__]]
+    [[`<boost/range/algorithm_ext/overwrite.hpp>`]  [__range_algorithm_ext_overwrite__]]
+    [[`<boost/range/algorithm_ext/push_back.hpp>`]  [__range_algorithm_ext_push_back__]]
+    [[`<boost/range/algorithm_ext/push_front.hpp>`] [__range_algorithm_ext_push_front__]]
+]
+[endsect]
+
+[endsect]
+

doc/history_ack.qbk

@@ -0,0 +1,58 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:history_ack History and Acknowledgement]
+
+[heading Version 1 - before Boost 1.43]
+The library have been under way for a long time. Dietmar Kühl originally intended to submit an `array_traits` class template which had most of the functionality present now, but only for arrays and standard containers.
+
+Meanwhile work on algorithms for containers in various contexts showed the need for handling pairs of iterators, and string libraries needed special treatment of character arrays. In the end it made sense to formalize the minimal requirements of these similar concepts. And the results are the Range concepts found in this library.
+
+The term Range was adopted because of paragraph 24.1/7 from the C++ standard:
+
+Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. A range [i, i) is an empty range; in general, a range [i, j) refers to the elements in the data structure starting with the one pointed to by i and up to but not including the one pointed to by j. Range [i, j) is valid if and only if j is reachable from i. The result of the application of functions in the library to invalid ranges is undefined.
+
+Special thanks goes to
+
+* Pavol Droba for help with documentation and implementation
+* Pavel Vozenilek for help with porting the library
+* Jonathan Turkanis and John Torjo for help with documentation
+* Hartmut Kaiser for being review manager
+* Jonathan Turkanis for porting the lib (as far as possible) to vc6 and vc7.
+
+The concept checks and their documentation was provided by Daniel Walker.
+
+[heading Version 2 - Boost 1.43 and beyond]
+This version introduced Range Adaptors and Range Algorithms. This version 2 is
+the result of a merge of all of the RangeEx features into Boost.Range.
+
+There were an enormous number of very significant contributors through all
+stages of this library.
+
+Prior to Boost.RangeEx there had been a number of Range library implementations,
+these include library implementations by Eric Niebler, Adobe,
+Shunsuke Sogame etc. Eric Niebler contributed the Range Adaptor idea which is
+arguably the single biggest innovation in this library. Inevitably a great deal
+of commonality evolved in each of these libraries, but a considerable amount
+of effort was expended to learn from all of the divergent techniques.
+
+The people in the following list all made contributions in the form of reviews,
+user feedback, design suggestions, or defect detection:
+
+* Thorsten Ottosen: review management, design advice, documentation feedback
+* Eric Niebler:     early implementation, and review feedback
+* Joel de Guzman:   review
+* Mathias Gaunard:  review
+* David Abrahams:   implementation advice
+* Robert Jones:     defect reports, usage feedback
+* Sean Parent:      contributed experience from the Adobe range library
+* Arno Schoedl:     implementations, and review
+* Rogier van Dalen: review
+* Vincente Botet:   review, documentation feedback
+
+Regardless of how I write this section it will never truly fairly capture the
+gratitude that I feel to all who have contributed. Thank you everyone.
+
+[endsect]

doc/introduction.qbk

@@ -0,0 +1,43 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:introduction Introduction]
+
+Generic algorithms have so far been specified in terms of two or more iterators. Two iterators would together form a range of values that the algorithm could work on. This leads to a very general interface, but also to a somewhat clumsy use of the algorithms with redundant specification of container names. Therefore we would like to raise the abstraction level for algorithms so they specify their interface in terms of __ranges__ as much as possible.
+
+The most common form of ranges used throughout the C++ community are standard library containers. When writing algorithms however, one often finds it desirable for the algorithm to accept other types that offer enough functionality to satisfy the needs of the generic code [*/if a suitable layer of indirection is applied/] . For example, raw arrays are often suitable for use with generic code that works with containers, provided a suitable adapter is used. Likewise, null terminated strings can be treated as containers of characters, if suitably adapted.
+
+This library therefore provides the means to adapt standard-like containers, null terminated strings, `std::pairs` of iterators, and raw arrays (and more), such that the same generic code can work with them all. The basic idea is to add another layer of indirection using __metafunctions__ and free-standing functions so syntactic and/or semantic differences can be removed.
+
+The main advantages are
+
+* simpler implementation and specification of generic range algorithms
+* more flexible, compact and maintainable client code
+* safe use of built-in arrays (for legacy code; why else would you use built-in arrays?)
+
+[heading Example - Iterate over the values in a map]
+``
+using namespace boost;
+using namespace boost::adaptors;
+for_each( my_map | map_values, fn );
+``
+
+[heading Example - Iterate over the keys in a map]
+``
+using namespace boost;
+using namespace boost::adaptors;
+for_each( my_map | map_keys, fn );
+``
+
+[heading Example - Push the even values from a map in reverse order into the container `target`]
+``
+using namespace boost;
+using namespace boost::adaptors;
+// Assume that is_even is a predicate that has been implemented elsewhere...
+push_back(target, my_map | map_values | filtered(is_even()) | reversed);
+``
+
+[endsect]
+

doc/mfc_atl.qbk

@@ -0,0 +1,148 @@
+[/
+    Copyright 2010 Neil Groves
+    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 __mfc_collections__ [@http://msdn.microsoft.com/en-us/library/942860sh.aspx MFC Collection Classes]]
+[def __atl_collections__ [@http://msdn.microsoft.com/en-us/library/15e672bd.aspx ATL Collection Classes]]
+
+[section:mfc_atl MFC/ATL (courtesy of Shunsuke Sogame)]
+
+[h4 Introduction]
+This implementation was kindly donated by Shunsuke Sogame. This header adapts MFC and ATL containers to the appropriate Range concepts.
+
+[table
+    []
+    [[[*Author:]]    [Shunsuke Sogame]]
+    [[[*Contact:]]   [mb2act@yahoo.co.jp]]
+    [[[*Date:]]      [26th of May 2006]]
+    [[[*Copyright:]] [Shunsuke Sogame 2005-2006. Use, modification and distribution is subject to the Boost Software License, Version 1.0]]
+]
+
+[h4 Overview]
+
+Boost.Range MFC/ATL Extension provides Boost.Range support for MFC/ATL collection and string types.
+
+``
+CTypedPtrArray<CPtrArray, CList<CString> *> myArray;
+...
+BOOST_FOREACH (CList<CString> *theList, myArray)
+{
+    BOOST_FOREACH (CString& str, *theList)
+    {
+        boost::to_upper(str);
+        std::sort(boost::begin(str), boost::end(str));
+        ...
+    }
+}
+``
+
+[section:requirements Requirements]
+
+* Boost C++ Libraries Version 1.34.0 or later (no compilation required)
+* Visual C++ 7.1 or later (for MFC and ATL)
+
+[endsect]
+
+[section:mfc_ranges MFC Ranges]
+If the `<boost/range/mfc.hpp>` is included before or after Boost.Range headers, the MFC collections and strings become models of Range. The table below lists the Traversal Category and `range_reference` of MFC ranges.
+
+[table
+    [[Range] [Traversal Category] [`range_reference<Range>::type`]]
+    [[`CArray<T,A>`]           [__random_access_range__]   [`T&`]]
+    [[`CList<T,A>`]            [__bidirectional_range__]   [`T&`]]
+    [[`CMap<K,AK,M,AM>`]       [__forward_range__]         [`Range::CPair&`]]
+    [[`CTypedPtrArray<B,T*>`]  [__random_access_range__]   [`T* const`]]
+    [[`CTypedPtrList<B,T*>`]   [__bidirectional_range__]   [`T* const`]]
+    [[`CTypedPtrMap<B,T*,V*>`] [__forward_range__]         [`std::pair<T*,V*> const`]]
+    [[`CByteArray`]            [__random_access_range__]   [`BYTE&`]]
+    [[`CDWordArray`]           [__random_access_range__]   [`DWORD&`]]
+    [[`CObArray`]              [__random_access_range__]   [`CObject*&`]]
+    [[`CPtrArray`]             [__random_access_range__]   [`void*&`]]
+    [[`CStringArray`]          [__random_access_range__]   [`CString&`]]
+    [[`CUIntArray`]            [__random_access_range__]   [`UINT&`]]
+    [[`CWordArray`]            [__random_access_range__]   [`WORD&`]]
+    [[`CObList`]               [__bidirectional_range__]   [`CObject*&`]]
+    [[`CPtrList`]              [__bidirectional_range__]   [`void*&`]]
+    [[`CStringList`]           [__bidirectional_range__]   [`CString&`]]
+    [[`CMapPtrToWord`]         [__forward_range__]         [`std::pair<void*,WORD> const`]]
+    [[`CMapPtrToPtr`]          [__forward_range__]         [`std::pair<void*,void*> const`]]
+    [[`CMapStringToOb`]        [__forward_range__]         [`std::pair<String,CObject*> const`]]
+    [[`CMapStringToString`]    [__forward_range__]         [`Range::CPair&`]]
+    [[`CMapWordToOb`]          [__forward_range__]         [`std::pair<WORD,CObject*> const`]]
+    [[`CMapWordToPtr`]         [__forward_range__]         [`std::pair<WORD,void*> const`]]
+]
+
+Other Boost.Range metafunctions are defined by the following. Let `Range` be any type listed above and `Ref` be the same as `range_reference<Range>::type`. `range_value<Range>::type` is the same as `remove_reference<remove_const<Ref>::type>::type`, `range_difference<Range>::type` is the same as `std::ptrdiff_t`, and `range_pointer<Range>::type` is the same as `add_pointer<remove_reference<Ref>::type>::type`. As for `const Range`, see below.
+
+Adam Walling has provided the header `<boost/range/mfc_map.hpp>` to add support
+for the map adaptor with MFC map types.
+
+[endsect]
+
+[section:atl_ranges ATL Ranges]
+
+If the `<boost/range/atl.hpp>` is included before or after Boost.Range headers, the ATL collections and strings become models of Range. The table below lists the Traversal Category and `range_reference` of ATL ranges.
+
+[table
+    [[Range]                    [Traversal Category]      [`range_reference<Range>::type`]]
+    [[`CAtlArray<E,ET>`]        [__random_access_range__] [`E&`]]
+    [[`CAutoPtrArray<E>`]       [__random_access_range__] [`E&`]]
+    [[`CInterfaceArray<I,pi>`]  [__random_access_range__] [`CComQIPtr<I,pi>&`]]
+    [[`CAtlList<E,ET>`]         [__bidirectional_range__] [`E&`]]
+    [[`CAutoPtrList<E>`]        [__bidirectional_range__] [`E&`]]
+    [[`CHeapPtrList<E,A>`]      [__bidirectional_range__] [`E&`]]
+    [[`CInterfaceList<I,pi>`]   [__bidirectional_range__] [`CComQIPtr<I,pi>&`]]
+    [[`CAtlMap<K,V,KT,VT>`]     [__forward_range__]       [`Range::CPair&`]]
+    [[`CRBTree<K,V,KT,VT>`]     [__bidirectional_range__] [`Range::CPair&`]]
+    [[`CRBMap<K,V,KT,VT>`]      [__bidirectional_range__] [`Range::CPair&`]]
+    [[`CRBMultiMap<K,V,KT,VT>`] [__bidirectional_range__] [`Range::CPair&`]]
+    [[`CSimpleStringT<B,b>`]    [__random_access_range__] [`B&`]]
+    [[`CStringT<B,ST>`]         [__random_access_range__] [`B&`]]
+    [[`CFixedStringT<S,n>`]     [__random_access_range__] [`range_reference<S>::type`]]
+    [[`CComBSTR`]               [__random_access_range__] [`OLECHAR&`]]
+    [[`CSimpleArray<T,TE>`]     [__random_access_range__] [`T&`]]
+]
+
+Other __boost_range_home__ metafunctions are defined by the following. Let `Range` be any type listed above and `Ref` be the same as `range_reference<Range>::type`. `range_value<Range>::type` is the same as `remove_reference<Ref>::type`, `range_difference<Range>::type` is the same as `std::ptrdiff_t`, and `range_pointer<Range>::type` is the same as `add_pointer<remove_reference<Ref>::type>::type`. As for `const Range`, see below.
+
+[endsect]
+
+[section:const_ranges const Ranges]
+
+`range_reference<const Range>::type` is defined by the following algorithm. Let `Range` be any type listed above and `Ref` be the same as `range_reference<Range>::type`.
+
+``
+if (Range is CObArray || Range is CObList)
+    return CObject const * &
+else if (Range is CPtrArray || Range is CPtrList)
+    return void const * &
+else if (there is a type X such that X& is the same as Ref)
+    return X const &
+else if (there is a type X such that X* const is the same as Ref)
+    return X const * const
+else
+    return Ref
+``
+
+
+Other Boost.Range metafunctions are defined by the following.
+
+[table
+    [[Range metafunction]                    [Result]]
+    [[`range_value<const Range>::type`]      [`range_value<Range>::type`]]
+    [[`range_difference<const Range>::type`] [`std::ptrdiff_t`]]
+    [[`range_pointer<const Range>::type`]    [`add_pointer<remove_reference<range_reference<const Range>::type>::type>::type`]]
+]
+
+[endsect]
+
+[section:references References]
+
+# __boost_range_home__
+# __mfc_collections__
+# __atl_collections__
+
+[endsect]
+
+[endsect]

doc/mfc_atl.rst

@@ -0,0 +1,232 @@
+
+++++++++++++++++++++++++++++++++
+ |Boost| Range MFC/ATL Extension
+++++++++++++++++++++++++++++++++
+
+.. |Boost| image:: http://www.boost.org/libs/ptr_container/doc/boost.png
+
+
+
+:Author:        Shunsuke Sogame
+:Contact:       mb2act@yahoo.co.jp
+:date:          26th of May 2006
+:copyright:     Shunsuke Sogame 2005-2006. Use, modification and distribution is subject to the Boost Software License, Version 1.0 (see LICENSE_1_0.txt__).
+
+__ http://www.boost.org/LICENSE_1_0.txt
+
+
+
+========
+Overview
+========
+
+Boost.Range MFC/ATL Extension provides `Boost.Range`_ support for MFC/ATL collection and string types.
+
+
+.. parsed-literal::
+
+        CTypedPtrArray<CPtrArray, CList<CString> \*> myArray;
+        ...
+        BOOST_FOREACH (CList<CString> \*theList, myArray)
+        {
+            BOOST_FOREACH (CString& str, \*theList)
+            {
+                boost::to_upper(str);
+                std::sort(boost::begin(str), boost::end(str));
+                ...
+            }
+        }
+
+
+
+* `Requirements`_
+* `MFC Ranges`_
+* `ATL Ranges`_
+* `const Ranges`_
+* `References`_
+
+
+
+============
+Requirements
+============
+
+- `Boost C++ Libraries Version 1.34.0`__ or later (no compilation required)
+- Visual C++ 7.1 or Visual C++ 8.0
+
+__ Boost_
+
+
+
+==========
+MFC Ranges
+==========
+
+If the ``<boost/range/mfc.hpp>`` is included before or after `Boost.Range`_ headers,
+the MFC collections and strings become models of Range.
+The table below lists the Traversal Category and ``range_reference`` of MFC ranges.
+
+
+============================= ================== =======================================
+``Range``                     Traversal Category ``range_reference<Range>::type``
+============================= ================== =======================================
+``CArray<T,A>``               Random Access      ``T&``
+----------------------------- ------------------ ---------------------------------------
+``CList<T,A>``                Bidirectional      ``T&``
+----------------------------- ------------------ ---------------------------------------
+``CMap<K,AK,M,AM>``           Forward            ``Range::CPair&``
+----------------------------- ------------------ ---------------------------------------
+``CTypedPtrArray<B,T*>``      Random Access      ``T* const``
+----------------------------- ------------------ ---------------------------------------
+``CTypedPtrList<B,T*>``       Bidirectional      ``T* const``
+----------------------------- ------------------ ---------------------------------------
+``CTypedPtrMap<B,T*,V*>``     Forward            ``std::pair<T*,V*> const``
+----------------------------- ------------------ ---------------------------------------
+``CByteArray``                Random Access      ``BYTE&``
+----------------------------- ------------------ ---------------------------------------
+``CDWordArray``               Random Access      ``DWORD&``
+----------------------------- ------------------ ---------------------------------------
+``CObArray``                  Random Access      ``CObject* &``
+----------------------------- ------------------ ---------------------------------------
+``CPtrArray``                 Random Access      ``void* &``
+----------------------------- ------------------ ---------------------------------------
+``CStringArray``              Random Access      ``CString&``
+----------------------------- ------------------ ---------------------------------------
+``CUIntArray``                Random Access      ``UINT&``
+----------------------------- ------------------ ---------------------------------------
+``CWordArray``                Random Access      ``WORD&``
+----------------------------- ------------------ ---------------------------------------
+``CObList``                   Bidirectional      ``CObject* &``
+----------------------------- ------------------ ---------------------------------------
+``CPtrList``                  Bidirectional      ``void* &``
+----------------------------- ------------------ ---------------------------------------
+``CStringList``               Bidirectional      ``CString&``
+----------------------------- ------------------ ---------------------------------------
+``CMapPtrToWord``             Forward            ``std::pair<void*,WORD> const``
+----------------------------- ------------------ ---------------------------------------
+``CMapPtrToPtr``              Forward            ``std::pair<void*,void*> const``
+----------------------------- ------------------ ---------------------------------------
+``CMapStringToOb``            Forward            ``std::pair<String,CObject*> const``
+----------------------------- ------------------ ---------------------------------------
+``CMapStringToString``        Forward            ``Range::CPair&``
+----------------------------- ------------------ ---------------------------------------
+``CMapWordToOb``              Forward            ``std::pair<WORD,CObject*> const``
+----------------------------- ------------------ ---------------------------------------
+``CMapWordToPtr``             Forward            ``std::pair<WORD,void*> const``
+============================= ================== =======================================
+
+
+Other `Boost.Range`_ metafunctions are defined by the following.
+Let ``Range`` be any type listed above and ``ReF`` be the same as ``range_reference<Range>::type``.
+``range_value<Range>::type`` is the same as ``remove_reference<remove_const<Ref>::type>::type``,
+``range_difference<Range>::type`` is the same as ``std::ptrdiff_t``, and
+``range_pointer<Range>::type`` is the same as ``add_pointer<remove_reference<Ref>::type>::type``.
+As for ``const Range``, see `const Ranges`_.
+
+
+
+==========
+ATL Ranges
+==========
+
+If the ``<boost/range/atl.hpp>`` is included before or after `Boost.Range`_ headers,
+the ATL collections and strings become models of Range.
+The table below lists the Traversal Category and ``range_reference`` of ATL ranges.
+
+
+============================= ================== =======================================
+``Range``                     Traversal Category ``range_reference<Range>::type``
+============================= ================== =======================================
+``CAtlArray<E,ET>``           Random Access      ``E&``
+----------------------------- ------------------ ---------------------------------------
+``CAutoPtrArray<E>``          Random Access      ``E&``
+----------------------------- ------------------ ---------------------------------------
+``CInterfaceArray<I,pi>``     Random Access      ``CComQIPtr<I,pi>&``
+----------------------------- ------------------ ---------------------------------------
+``CAtlList<E,ET>``            Bidirectional      ``E&``
+----------------------------- ------------------ ---------------------------------------
+``CAutoPtrList<E>``           Bidirectional      ``E&``
+----------------------------- ------------------ ---------------------------------------
+``CHeapPtrList<E,A>``         Bidirectional      ``E&``
+----------------------------- ------------------ ---------------------------------------
+``CInterfaceList<I,pi>``      Bidirectional      ``CComQIPtr<I,pi>&``
+----------------------------- ------------------ ---------------------------------------
+``CAtlMap<K,V,KT,VT>``        Forward            ``Range::CPair&``
+----------------------------- ------------------ ---------------------------------------
+``CRBTree<K,V,KT,VT>``        Bidirectional      ``Range::CPair&``
+----------------------------- ------------------ ---------------------------------------
+``CRBMap<K,V,KT,VT>``         Bidirectional      ``Range::CPair&``
+----------------------------- ------------------ ---------------------------------------
+``CRBMultiMap<K,V,KT,VT>``    Bidirectional      ``Range::CPair&``
+----------------------------- ------------------ ---------------------------------------
+``CSimpleStringT<B,b>``       Random Access      ``B&``
+----------------------------- ------------------ ---------------------------------------
+``CStringT<B,ST>``            Random Access      ``B&``
+----------------------------- ------------------ ---------------------------------------
+``CFixedStringT<S,n>``        Random Access      ``range_reference<S>::type``
+----------------------------- ------------------ ---------------------------------------
+``CStringT<B,ST>``            Random Access      ``B&``
+----------------------------- ------------------ ---------------------------------------
+``CComBSTR``                  Random Access      ``OLECHAR&``
+----------------------------- ------------------ ---------------------------------------
+``CSimpleArray<T,TE>``        Random Access      ``T&``
+============================= ================== =======================================
+
+
+Other `Boost.Range`_ metafunctions are defined by the following.
+Let ``Range`` be any type listed above and ``ReF`` be the same as ``range_reference<Range>::type``.
+``range_value<Range>::type`` is the same as ``remove_reference<Ref>::type``,
+``range_difference<Range>::type`` is the same as ``std::ptrdiff_t``, and
+``range_pointer<Range>::type`` is the same as ``add_pointer<remove_reference<Ref>::type>::type``.
+As for ``const Range``, see `const Ranges`_.
+
+
+
+============
+const Ranges
+============
+
+``range_reference<const Range>::type`` is defined by the following algorithm.
+Let ``Range`` be any type listed above and ``ReF`` be the same as ``range_reference<Range>::type``.
+
+
+.. parsed-literal::
+
+    if (Range is CObArray || Range is CObList)
+        return CObject const \* &
+    else if (Range is CPtrArray || Range is CPtrList)
+        return void const \* &
+    else if (there is a type X such that X& is the same as ReF)
+        return X const &
+    else if (there is a type X such that X* const is the same as ReF)
+        return X const \* const
+    else
+        return ReF
+
+
+Other `Boost.Range`_ metafunctions are defined by the following.
+``range_value<const Range>::type`` is the same as ``range_value<Range>::type``,
+``range_difference<const Range>::type`` is the same as ``std::ptrdiff_t``, and
+``range_pointer<const Range>::type`` is the same as ``add_pointer<remove_reference<range_reference<const Range>::type>::type>::type``.
+
+
+
+==========
+References
+==========
+- `Boost.Range`_
+- `MFC Collections`__
+- `ATL Collection Classes`__
+
+__ http://msdn2.microsoft.com/en-us/library/942860sh.aspx
+__ http://msdn2.microsoft.com/en-US/library/15e672bd.aspx
+
+
+
+.. _Boost C++ Libraries: http://www.boost.org/
+.. _Boost: `Boost C++ Libraries`_
+.. _Boost.Range: ../index.html
+.. _forward: range.html#forward_range
+.. _bidirectional: range.html#forward_range
+.. _random access: range.html#random_access_range
+

doc/portability.qbk

@@ -0,0 +1,27 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:portability Portability]
+
+A huge effort has been made to port the library to as many compilers as possible.
+
+Full support for built-in arrays require that the compiler supports class template partial specialization. For non-conforming compilers there might be a chance that it works anyway thanks to workarounds in the type traits library.
+Visual C++ 6/7.0 has a limited support for arrays: as long as the arrays are of built-in type it should work.
+
+Notice also that some compilers cannot do function template ordering properly. In that case one must rely of __range_iterator__ and a single function definition instead of overloaded versions for const and non-const arguments. So if one cares about old compilers, one should not pass rvalues to the functions.
+
+For maximum portability you should follow these guidelines:
+
+# do not use built-in arrays,
+# do not pass rvalues to __begin__`()`, __end__`()` and __iterator_range__ Range constructors and assignment operators,
+# use __const_begin__`()` and __const_end__`()` whenever your code by intention is read-only; this will also solve most rvalue problems,
+# do not rely on ADL:
+  * if you overload functions, include that header before the headers in this library,
+  * put all overloads in namespace boost.
+
+
+
+[endsect]
+

doc/range.htm

@@ -1,612 +0,0 @@
-<HTML>
-<!--
-  -- Copyright (c) Jeremy Siek 2000
-  --
-  -- Permission to use, copy, modify, distribute and sell this software
-  -- and its documentation for any purpose is hereby granted without fee,
-  -- provided that the above copyright notice appears in all copies and
-  -- that both that copyright notice and this permission notice appear
-  -- in supporting documentation.  Silicon Graphics makes no
-  -- representations about the suitability of this software for any
-  -- purpose.  It is provided "as is" without express or implied warranty.
-  -->
-<Head>
-<Title>Collection</Title>
-</HEAD>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
-	ALINK="#ff0000"> 
-<IMG SRC="cboost.gif" 
-     ALT="C++ Boost"> 
-<IMG SRC="/Images/stat.gif" ALT="" BORDER=0   WIDTH = "6"  HEIGHT = "6" >
-
-<BR Clear>
-<H1>Collection</H1>
-
-
-<h3>Description</h3>
-
-A Collection is a <i>concept</i> similar to the STL <a
-href="http://www.sgi.com/Technology/STL/Container.html">Container</a>
-concept.  A Collection provides iterators for accessing a range of
-elements and provides information about the number of elements in the
-Collection.  However, a Collection has fewer requirements than a
-Container. The motivation for the Collection concept is that there are
-many useful Container-like types that do not meet the full
-requirements of Container, and many algorithms that can be written
-with this reduced set of requirements. To summarize the reduction
-in requirements:
-
-<UL>
-<LI>It is not required to &quot;own&quot; its elements: the lifetime
-of an element in a Collection does not have to match the lifetime of
-the Collection object, though the lifetime of the element should cover
-the lifetime of the Collection object.
-<LI>The semantics of copying a Collection object is not defined (it
-could be a deep or shallow copy or not even support copying). 
-<LI>The associated reference type of a Collection does
-not have to be a real C++ reference.
-</UL>
-
-
-Because of the reduced requirements, some care must be taken when
-writing code that is meant to be generic for all Collection types.
-In particular, a Collection object should be passed by-reference
-since assumptions can not be made about the behaviour of the
-copy constructor.
-
-<p>
-
-<h3>Associated types</h3>
-
-<Table border>
-<TR>
-<TD VAlign=top>
-Value type
-</TD>
-<TD VAlign=top>
-<tt>X::value_type</tt>
-</TD>
-<TD VAlign=top>
-The type of the object stored in a Collection.  
-If the Collection is <i>mutable</i> then
-the value type must be <A
-href="http://www.sgi.com/Technology/STL/Assignable.html">Assignable</A>.
-Otherwise the value type must be <a href="./CopyConstructible.html">CopyConstructible</a>.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Iterator type
-</TD>
-<TD VAlign=top>
-<tt>X::iterator</tt>
-</TD>
-<TD VAlign=top>
-The type of iterator used to iterate through a Collection's
-   elements.  The iterator's value type is expected to be the
-   Collection's value type.  A conversion
-   from the iterator type to the const iterator type must exist.
-   The iterator type must be an <A href="http://www.sgi.com/Technology/STL/InputIterator.html">InputIterator</A>.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Const iterator type
-</TD>
-<TD VAlign=top>
-<tt>X::const_iterator</tt>
-</TD>
-<TD VAlign=top>
-A type of iterator that may be used to examine, but not to modify,
-   a Collection's elements.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Reference type
-</TD>
-<TD VAlign=top>
-<tt>X::reference</tt>
-</TD>
-<TD VAlign=top>
-A type that behaves like a reference to the Collection's value type.
-<a href="#1">[1]</a>
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Const reference type
-</TD>
-<TD VAlign=top>
-<tt>X::const_reference</tt>
-</TD>
-<TD VAlign=top>
-A type that behaves like a const reference to the Collection's value type.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Pointer type
-</TD>
-<TD VAlign=top>
-<tt>X::pointer</tt>
-</TD>
-<TD VAlign=top>
-A type that behaves as a pointer to the Collection's value type.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Distance type
-</TD>
-<TD VAlign=top>
-<tt>X::difference_type</tt>
-</TD>
-<TD VAlign=top>
-A signed integral type used to represent the distance between two
-   of the Collection's iterators.  This type must be the same as 
-   the iterator's distance type.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Size type
-</TD>
-<TD VAlign=top>
-<tt>X::size_type</tt>
-</TD>
-<TD VAlign=top>
-An unsigned integral type that can represent any nonnegative value
-   of the Collection's distance type.
-</TD>
-</tr>
-</table>
-<h3>Notation</h3>
-<Table>
-<TR>
-<TD VAlign=top>
-<tt>X</tt>
-</TD>
-<TD VAlign=top>
-A type that is a model of Collection.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-<tt>a</tt>, <tt>b</tt>
-</TD>
-<TD VAlign=top>
-Object of type <tt>X</tt>.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-<tt>T</tt>
-</TD>
-<TD VAlign=top>
-The value type of <tt>X</tt>.
-</TD>
-</tr>
-</table>
-
-<h3>Valid expressions</h3>
-
-The following expressions must be valid.
-<p>
-
-<Table border>
-<TR>
-<TH>
-Name
-</TH>
-<TH>
-Expression
-</TH>
-<TH>
-Return type
-</TH>
-</TR>
-<TR>
-<TD VAlign=top>
-Beginning of range
-</TD>
-<TD VAlign=top>
-<tt>a.begin()</tt>
-</TD>
-<TD VAlign=top>
-<tt>iterator</tt> if <tt>a</tt> is mutable, <tt>const_iterator</tt> otherwise
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-End of range
-</TD>
-<TD VAlign=top>
-<tt>a.end()</tt>
-</TD>
-<TD VAlign=top>
-<tt>iterator</tt> if <tt>a</tt> is mutable, <tt>const_iterator</tt> otherwise
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Size
-</TD>
-<TD VAlign=top>
-<tt>a.size()</tt>
-</TD>
-<TD VAlign=top>
-<tt>size_type</tt>
-</TD>
-</TR>
-<!--
-<TR>
-<TD VAlign=top>
-Maximum size
-</TD>
-<TD VAlign=top>
-<tt>a.max_size()</tt>
-</TD>
-<TD VAlign=top>
-<tt>size_type</tt>
-</TD>
-</TR>
-<TR>
--->
-<TD VAlign=top>
-Empty Collection
-</TD>
-<TD VAlign=top>
-<tt>a.empty()</tt>
-</TD>
-<TD VAlign=top>
-Convertible to <tt>bool</tt>
-</TD>
-</TR>
-<TR>
-    <!--
-<TD VAlign=top>
-Swap
-</TD>
-<TD VAlign=top>
-<tt>a.swap(b)</tt>
-</TD>
-<TD VAlign=top>
-<tt>void</tt>
-</TD> -->
-</tr>
-</table>
-<h3>Expression semantics</h3>
-
-<Table border>
-<TR>
-<TH>
-Name
-</TH>
-<TH>
-Expression
-</TH>
-<TH>
-Semantics
-</TH>
-<TH>
-Postcondition
-</TH>
-</TR>
-<TD VAlign=top>
-<TR>
-<TD VAlign=top>
-Beginning of range
-</TD>
-<TD VAlign=top>
-<tt>a.begin()</tt>
-</TD>
-<TD VAlign=top>
-Returns an iterator pointing to the first element in the Collection.
-</TD>
-<TD VAlign=top>
-<tt>a.begin()</tt> is either dereferenceable or past-the-end.  It is
-   past-the-end if and only if <tt>a.size() == 0</tt>.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-End of range
-</TD>
-<TD VAlign=top>
-<tt>a.end()</tt>
-</TD>
-<TD VAlign=top>
-Returns an iterator pointing one past the last element in the
-   Collection.
-</TD>
-<TD VAlign=top>
-<tt>a.end()</tt> is past-the-end.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Size
-</TD>
-<TD VAlign=top>
-<tt>a.size()</tt>
-</TD>
-<TD VAlign=top>
-Returns the size of the Collection, that is, its number of elements.
-</TD>
-<TD VAlign=top>
-<tt>a.size() &gt;= 0 
-</TD>
-</TR>
-<!--
-<TR>
-<TD VAlign=top>
-Maximum size
-</TD>
-<TD VAlign=top>
-<tt>a.max_size()</tt>
-</TD>
-<TD VAlign=top>
-&nbsp;
-</TD>
-<TD VAlign=top>
-Returns the largest size that this Collection can ever have. <A href="#8">[8]</A>
-</TD>
-<TD VAlign=top>
-<tt>a.max_size() &gt;= 0 &amp;&amp; a.max_size() &gt;= a.size()</tt>
-</TD>
-</TR>
- -->
-<TR>
-<TD VAlign=top>
-Empty Collection
-</TD>
-<TD VAlign=top>
-<tt>a.empty()</tt>
-</TD>
-<TD VAlign=top>
-Equivalent to <tt>a.size() == 0</tt>.  (But possibly faster.)
-</TD>
-<TD VAlign=top>
-&nbsp;
-</TD>
-</TR>
-<TR>
-    <!--
-<TD VAlign=top>
-Swap
-</TD>
-    
-<TD VAlign=top>
-<tt>a.swap(b)</tt>
-</TD>
-<TD VAlign=top>
-Equivalent to <tt>swap(a,b)</tt>
-</TD> 
-<TD VAlign=top>
-&nbsp;
-</TD>
-    -->
-</tr>
-</table>
-<h3>Complexity guarantees</h3>
-
-<tt>begin()</tt> and <tt>end()</tt> are amortized constant time.
-<P>
-<tt>size()</tt> is at most linear in the Collection's
-size. <tt>empty()</tt> is amortized constant time.
-<!-- <P>
-<tt>swap()</tt> is at most linear in the size of the two collections. -->
-<h3>Invariants</h3>
-<Table border>
-<TR>
-<TD VAlign=top>
-Valid range
-</TD>
-<TD VAlign=top>
-For any Collection <tt>a</tt>, <tt>[a.begin(), a.end())</tt> is a valid
-   range.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Range size
-</TD>
-<TD VAlign=top>
-<tt>a.size()</tt> is equal to the distance from <tt>a.begin()</tt> to <tt>a.end()</tt>.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-Completeness
-</TD>
-<TD VAlign=top>
-An algorithm that iterates through the range <tt>[a.begin(), a.end())</tt>
-   will pass through every element of <tt>a</tt>.
-</TD>
-</tr>
-</table>
-
-
-<h3>Models</h3>
-<UL>
-<!-- <LI> <tt>array</tt> -->
-<!--<LI> <tt>array_ptr</tt> -->
-<LI> <tt>vector&lt;bool&gt;</tt>
-</UL>
-
-<!--
-<h3>Collection Refinements</h3>
-
-There are quite a few concepts that refine the Collection concept,
-similar to the concepts that refine the Container concept. Here
-is a brief overview of the refining concepts.
-
-<h4>ForwardCollection</h4>
-The elements are arranged in some order that
-does not change spontaneously from one iteration to the next. As
-a result, a ForwardCollection is 
-<A
-href="http://www.sgi.com/Technology/STL/EqualityComparable.html">EqualityComparable</A>
-and 
-<A
-href="http://www.sgi.com/Technology/STL/LessThanComparable.html">LessThanComparable</A>.
-In addition, the iterator type of a ForwardCollection is a
-MultiPassInputIterator which is just an InputIterator with the added
-requirements that the iterator can be used to make multiple passes
-through a range, and that if <tt>it1 == it2</tt> and <tt>it1</tt> is
-dereferenceable then <tt>++it1 == ++it2</tt>. The ForwardCollection
-also has a <tt>front()</tt> method.
-
-<p>
-<Table border>
-<TR>
-<TH>
-Name
-</TH>
-<TH>
-Expression
-</TH>
-<TH>
-Return type
-</TH>
-<TH>
-Semantics
-</TH>
-</TR>
-
-<TR>
-<TD VAlign=top>
-Font
-</TD>
-<TD VAlign=top>
-<tt>a.front()</tt>
-</TD>
-<TD VAlign=top>
-<tt>reference</tt> if <tt>a</tt> is mutable, <br> <tt>const_reference</tt>
-otherwise.
-</TD>
-<TD VAlign=top>
-Equivalent to <tt>*(a.first())</tt>.
-</TD>
-</TR>
-
-</table>
-
-
-<h4>ReversibleCollection</h4>
-
-The container provides access to iterators that traverse in both
-directions (forward and reverse). The iterator type must meet all of
-the requirements of <a
-href="http://www.sgi.com/Technology/STL/BidirectionalIterator.html">BidirectionalIterator</a>
-except that the reference type does not have to be a real C++
-reference. The ReversibleCollection adds the following requirements
-to those of ForwardCollection.
-<p>
-
-<Table border>
-<TR>
-<TH>
-Name
-</TH>
-<TH>
-Expression
-</TH>
-<TH>
-Return type
-</TH>
-<TH>
-Semantics
-</TH>
-</TR>
-<TR>
-<TD VAlign=top>
-Beginning of range
-</TD>
-<TD VAlign=top>
-<tt>a.rbegin()</tt>
-</TD>
-<TD VAlign=top>
-<tt>reverse_iterator</tt> if <tt>a</tt> is mutable,
-<tt>const_reverse_iterator</tt> otherwise.
-</TD>
-<TD VAlign=top>
-Equivalent to <tt>X::reverse_iterator(a.end())</tt>.
-</TD>
-</TR>
-<TR>
-<TD VAlign=top>
-End of range
-</TD>
-<TD VAlign=top>
-<tt>a.rend()</tt>
-</TD>
-<TD VAlign=top>
-<tt>reverse_iterator</tt> if <tt>a</tt> is mutable,
-<tt>const_reverse_iterator</tt> otherwise.
-</TD>
-<TD VAlign=top>
-Equivalent to <tt>X::reverse_iterator(a.begin())</tt>.
-</TD>
-</tr>
-
-<TR>
-<TD VAlign=top>
-Back
-</TD>
-<TD VAlign=top>
-<tt>a.back()</tt>
-</TD>
-<TD VAlign=top>
-<tt>reference</tt> if <tt>a</tt> is mutable, <br> <tt>const_reference</tt>
-otherwise.
-</TD>
-<TD VAlign=top>
-Equivalent to <tt>*(--a.end())</tt>.
-</TD>
-</TR>
-
-</table>
-
-<h4>SequentialCollection</h4>
-
-The elements are arranged in a strict linear order. No extra methods
-are required.
--->
-
-<h3>Notes</h3>
-
-<P><A name="1">[1]</A> 
-
-The reference type does not have to be a real C++ reference. The
-requirements of the reference type depend on the context within which
-the Collection is being used. Specifically it depends on the
-requirements the context places on the value type of the Collection.
-The reference type of the Collection must meet the same requirements
-as the value type. In addition, the reference objects must be
-equivalent to the value type objects in the collection (which is
-trivially true if they are the same).  Also, in a mutable Collection,
-an assignment to the reference object must result in an assignment to
-the object in the Collection (again, which is trivially true if they
-are the same object, but non-trivial if the reference type is a proxy
-class).
-
-<h3>See also</h3>
-<A href="http://www.sgi.com/Technology/STL/Container.html">Container</A>
-
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 2000</TD><TD>
-<A HREF=http://www.boost.org/people/jeremy_siek.htm>Jeremy Siek</A>, Univ.of Notre Dame and C++ Library & Compiler Group/SGI (<A HREF="mailto:jsiek@engr.sgi.com">jsiek@engr.sgi.com</A>)
-</TD></TR>
-<tr >
-<TD nowrap>Copyright &copy 2004</TD><TD>
-Thorsten Ottosen.
-</TABLE>
-
-</BODY>
-</HTML> 

doc/reference.qbk

@@ -0,0 +1,21 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:reference Reference]
+
+[include reference/overview.qbk]
+
+[section:concept_implementation Range concept implementation]
+[include reference/synopsis.qbk]
+[include reference/semantics.qbk]
+[endsect]
+
+[include reference/adaptors.qbk]
+[include reference/algorithms.qbk]
+[include reference/ranges.qbk]
+[include reference/utilities.qbk]
+[include reference/extending.qbk]
+
+[endsect]

doc/reference/adaptors.qbk

@@ -0,0 +1,188 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:adaptors Range Adaptors]
+
+[section:introduction Introduction and motivation]
+
+A [*Range Adaptor] is a class that wraps an existing Range to provide a new Range with different behaviour. Since the behaviour of Ranges is determined by their associated iterators, a Range Adaptor simply wraps the underlying iterators with new special iterators. In this example
+
+``
+#include <boost/range/adaptors.hpp>
+#include <boost/range/algorithm.hpp>
+#include <iostream>
+#include <vector>
+
+std::vector<int> vec;
+boost::copy( vec | boost::adaptors::reversed,
+             std::ostream_iterator<int>(std::cout) );
+``
+
+the iterators from `vec` are wrapped `reverse_iterator`s. The type of the underlying Range Adapter is not documented because you do not need to know it. All that is relevant is that the expression
+
+``
+vec | boost::adaptors::reversed
+``
+
+returns a Range Adaptor where the iterator type is now the iterator type of the range `vec` wrapped in `reverse_iterator`. The expression `boost::adaptors::reversed` is called an *Adaptor Generator*.
+
+There are two ways of constructing a range adaptor. The first is by using `operator|()`. This is my preferred technique, however while discussing range adaptors with others it became clear that some users of the library strongly prefer a more familiar function syntax, so equivalent functions of the present tense form have been added as an alternative syntax. The equivalent to `rng | reversed` is `adaptors::reverse(rng)` for example.
+
+Why do I prefer the `operator|` syntax? The answer is readability:
+
+``
+std::vector<int> vec;
+boost::copy( boost::adaptors::reverse(vec),
+             std::ostream_iterator<int>(std::cout) );
+``
+
+This might not look so bad, but when we apply several adaptors, it becomes much worse. Just compare
+
+``
+std::vector<int> vec;
+boost::copy( boost::adaptors::unique( boost::adaptors::reverse( vec ) ),
+             std::ostream_iterator<int>(std::cout) );
+``
+
+to
+
+``
+std::vector<int> vec;
+boost::copy( vec | boost::adaptors::reversed
+                 | boost::adaptors::uniqued,
+             std::ostream_iterator<int>(std::cout) );
+``
+
+Furthermore, some of the adaptor generators take arguments themselves and these arguments are expressed with function call notation too. In those situations, you will really appreciate the succinctness of `operator|()`.
+
+[heading Composition of Adaptors]
+
+Range Adaptors are a powerful complement to Range algorithms. The reason is that adaptors are ['*orthogonal*] to algorithms. For example, consider these Range algorithms:
+
+* `boost::copy( rng, out )`
+* `boost::count( rng, pred )`
+
+What should we do if we only want to copy an element `a` if it satisfies some predicate, say `pred(a)`? And what if we only want to count the elements that satisfy the same predicate? The naive answer would be to use these algorithms:
+
+* `boost::copy_if( rng, pred, out )`
+* `boost::count_if( rng, pred )`
+
+These algorithms are only defined to maintain a one to one relationship with the standard library algorithms. This approach of adding algorithm suffers a combinatorial explosion. Inevitably many algorithms are missing `_if` variants and there is redundant development overhead for each new algorithm. The Adaptor Generator is the design solution to this problem. It is conceivable that some algorithms are capable of optimization by tightly coupling the filter with the algorithm. The adaptors provide a more general solution with superior separation of orthogonal concerns.
+
+[heading Range Adaptor alternative to copy_if algorithm]
+``
+boost::copy_if( rng, pred, out );
+``
+can be expressed as
+``
+boost::copy( rng | boost::adaptors::filtered(pred), out );
+``
+
+[heading Range Adaptor alternative to count_if algorithm]
+``
+boost::count_if( rng, pred );
+``
+can be expressed as
+``
+boost::size( rng | boost::adaptors::filtered(pred) );
+``
+
+What this means is that many algorithms no longer require nor benefit from an optimized implementation with an `_if` suffix. Furthermore, it turns out that algorithms with the `_copy` suffix are often not needed either. Consider `replace_copy_if()` which may be used as
+
+``
+std::vector<int> vec;
+boost::replace_copy_if( rng, std::back_inserter(vec), pred, new_value );
+``
+
+With adaptors and algorithms we can express this as
+
+``
+std::vector<int> vec;
+boost::push_back(vec, rng | boost::adaptors::replaced_if(pred, new_value));
+``
+
+The latter code has several benefits:
+
+1. it is more ['*efficient*] because we avoid extra allocations as might happen with `std::back_inserter`
+
+2. it is ['*flexible*] as we can subsequently apply even more adaptors, for example: ``
+boost::push_back(vec, rng | boost::adaptors::replaced_if(pred, new_value)
+                          | boost::adaptors::reversed);
+``
+
+3. it is ['*safer*] because there is no use of an unbounded output iterator.
+
+In this manner, the ['*composition*] of Range Adaptors has the following consequences:
+
+1. we no longer need many of the `_if`, `_copy`, `_copy_if` and `_n` variants of algorithms.
+
+2. we can generate a multitude of new algorithms on the fly, for example, above we generated `reverse_replace_copy_if()`
+
+In other words:
+
+[*Range Adaptors are to algorithms what algorithms are to containers]
+
+[endsect]
+
+[section:general_requirements General Requirements]
+
+In the description of generator expressions, the following notation is used:
+
+* `fwdRng` is an expression of a type `R` that models `ForwardRange`
+* `biRng` is an expression of a type `R` that models `BidirectionalRange`
+* `rndRng` is an expression of a type `R` that models `RandomAccessRange`
+* `pred` is an expression of a type that models `UnaryPredicate`
+* `bi_pred` is an expression of a type that models `BinaryPredicate`
+* `fun` is an expression of a type that models `UnaryFunction`
+* `value`, `new_value` and `old_value` are objects convertible to `boost::range_value<R>::type`
+* `n,m` are integer expressions convertible to `range_difference<R>::type`
+
+Also note that `boost::range_value<R>::type` must be implicitly convertible to the type arguments to `pred`, `bi_pred` and `fun`.
+
+Range Category in the following adaptor descriptions refers to the minimum range concept required by the range passed to the adaptor. The resultant range is a model of the same range concept as the input range unless specified otherwise.
+
+Returned Range Category is the concept of the returned range. In some cases the returned range is of a lesser category than the range passed to the adaptor. For example, the `filtered` adaptor returns only a `ForwardRange` regardless of the input.
+
+Furthermore, the following rules apply to any expression of the form
+``
+rng | boost::adaptors::adaptor_generator
+``
+
+1. Applying `operator|()` to a range `R` (always left argument) and a range adapter `RA` (always right argument) yields a new range type which may not conform to the same range concept as `R`.
+
+2. The return-type of `operator|()` is otherwise unspecified.
+
+3. `operator|()` is found by Argument Dependent Lookup (ADL) because a range adaptor is implemented in namespace `boost::adaptors`.
+
+4. `operator|()` is used to add new behaviour ['*lazily*] and never modifies its left argument.
+
+5. All iterators extracted from the left argument are extracted using qualified calls to `boost::begin()` and `boost::end()`.
+
+6. In addition to the `throw`-clauses below, `operator|()` may throw exceptions as a result of copying iterators. If such copying cannot throw an exception, then neither can the whole expression.
+
+[endsect]
+
+[section:reference Reference]
+[include adaptors/adjacent_filtered.qbk]
+[include adaptors/copied.qbk]
+[include adaptors/filtered.qbk]
+[include adaptors/indexed.qbk]
+[include adaptors/indirected.qbk]
+[include adaptors/map_keys.qbk]
+[include adaptors/map_values.qbk]
+[include adaptors/ref_unwrapped.qbk]
+[include adaptors/replaced.qbk]
+[include adaptors/replaced_if.qbk]
+[include adaptors/reversed.qbk]
+[include adaptors/sliced.qbk]
+[include adaptors/strided.qbk]
+[include adaptors/type_erased.qbk]
+[include adaptors/tokenized.qbk]
+[include adaptors/transformed.qbk]
+[include adaptors/uniqued.qbk]
+[endsect]
+
+[endsect]
+

doc/reference/adaptors/adjacent_filtered.qbk

@@ -0,0 +1,32 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:adjacent_filtered adjacent_filtered]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::adjacent_filtered(bi_pred)`]]
+    [[Function] [`boost::adaptors::adjacent_filter(rng, bi_pred)`]]
+]
+
+* [*Precondition:]  The `value_type` of the range is convertible to both argument types of `bi_pred`.
+* [*Postcondition:] For all adjacent elements `[x,y]` in the returned range, `bi_pred(x,y)` is `true`.
+* [*Throws:] Whatever the copy constructor of `bi_pred` might throw.
+* [*Range Category:] __forward_range__
+* [*Return Type:] `boost::adjacent_filtered_range<decltype(rng), decltype(bi_pred)>`
+* [*Returned Range Category:] The minimum of the range category of `rng` and __forward_range__
+
+[section:adjacent_filtered_example adjacent_filtered example]
+[import ../../../test/adaptor_test/adjacent_filtered_example.cpp]
+[adjacent_filtered_example]
+[endsect]
+
+This would produce the output:
+``
+1,2,3,4,5,6,
+``
+[endsect]
+
+

doc/reference/adaptors/copied.qbk

@@ -0,0 +1,30 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:copied copied]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::copied(n, m)`]]
+    [[Function] [`boost::adaptors::copy(rng, n, m)`]]
+]
+
+* [*Precondition:]  `0 <= n && n <= m && m < distance(rng)`
+* [*Returns:] A new `iterator_range` that holds the sliced range `[n,m)` of the original range.
+* [*Range Category:] __random_access_range__
+* [*Returned Range Category:] __random_access_range__
+
+[section:copied_example copied example]
+[import ../../../test/adaptor_test/copied_example.cpp]
+[copied_example]
+[endsect]
+
+This would produce the output:
+``
+2,3,4,5,
+``
+[endsect]
+
+

doc/reference/adaptors/examples/indirected.cpp

@@ -0,0 +1,32 @@
+// Boost.Range library
+//
+//  Copyright Thorsten Ottosen 2003-2004. 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)
+//
+// For more information, see http://www.boost.org/libs/range/
+//
+#include <boost/range/adaptor/indirected.hpp>
+#include <boost/range/algorithm/copy.hpp>
+#include <boost/shared_ptr.hpp>
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int main(int argc, const char* argv[])
+{
+    using namespace boost::adaptors;
+    
+    std::vector<boost::shared_ptr<int> > input;
+    
+    for (int i = 0; i < 10; ++i)
+        input.push_back(boost::shared_ptr<int>(new int(i)));
+        
+    boost::copy(
+        input | indirected,
+        std::ostream_iterator<int>(std::cout, ","));
+        
+    return 0;
+}
+

doc/reference/adaptors/filtered.qbk

@@ -0,0 +1,32 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:filtered filtered]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::filtered(pred)`]]
+    [[Function] [`boost::adaptors::filter(rng, pred)`]]
+]
+
+* [*Precondition:]  The `value_type` of the range is convertible to the argument type of `pred`.
+* [*Postcondition:] For all elements `[x]` in the returned range, `pred(x)` is `true`.
+* [*Throws:] Whatever the copy constructor of `pred` might throw.
+* [*Range Category:] __singlepass_range__
+* [*Range Return Type:] `boost::filtered_range<decltype(rng)>`
+* [*Returned Range Category:] The minimum of the range category of `rng` and __bidirectional_range__
+
+[section:filtered_example filtered example]
+[import ../../../test/adaptor_test/filtered_example.cpp]
+[filtered_example]
+[endsect]
+
+This would produce the output:
+``
+2,4,6,8,
+``
+[endsect]
+
+

doc/reference/adaptors/formatted.qbk

@@ -0,0 +1,51 @@
+[/
+    Copyright 2014 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:formatted formatted]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::formatted()`]]
+    [[Pipe] [`rng | boost::adaptors::formatted(sep)`]]
+    [[Pipe] [`rng | boost::adaptors::formatted(sep, prefix)`]]
+    [[Pipe] [`rng | boost::adaptors::formatted(sep, prefix, postfix)`]]
+    [[Function] [`boost::adaptors::format(rng)`]]
+    [[Function] [`boost::adaptors::format(rng, sep)`]]
+    [[Function] [`boost::adaptors::format(rng, sep, prefix)`]]
+    [[Function] [`boost::adaptors::format(rng, sep, prefix, postfix)`]]
+]
+
+This adaptor produces a range that can be output streamed to a
+`std::basic_ostream` to produce the output string formatted output. With the
+default paramters given numbers 1 to 5 inclusively in a range the output when
+streamed would be "{0,1,2,3,4,5}". The prefix, separator and postfix may be
+passed as parameters.
+
+The general format of the output is thus:
+<prefix><element_1><sep><element_2><sep>...<element_n><postfix>
+
+* [*Precondition:]
+    * `0 <= n`.
+    * `sep` has a type that is CopyConstructible and able to be streamed to `std::basic_ostream<Char,Traits>`
+    * `prefix` has a type that is CopyConstructible and able to be streamed to `std::basic_ostream<Char,Traits>`
+    * `postfix` has a type that is CopyConstructible and able to be streamed to `std::basic_ostream<Char,Traits>`
+* [*Returns:] `boost::range::formatted_range<Iter, Sep, Prefix, Postfix>` where
+`Iter` is `typename boost::range_iterator<Rng>::type`, `Sep` is the separator
+type, `Prefix` is the prefix type and `Postfix` is the postfix type.
+* [*Range Category:] __single_pass_range__
+* [*Returned Range Category:] The range category of `rng`.
+
+[section:formatted_example formatted example]
+[import ../../../test/adaptor_test/formatted_example.cpp]
+[separated_example]
+[endsect]
+
+This would produce the output:
+``
+{1,2,3,4,5}
+``
+[endsect]
+
+

doc/reference/adaptors/indexed.qbk

@@ -0,0 +1,84 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:indexed indexed]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::indexed()`]]
+    [[Pipe] [`rng | boost::adaptors::indexed(start_index)`]]
+    [[Function] [`boost::adaptors::index(rng)`]]
+    [[Function] [`boost::adaptors::index(rng, start_index)`]]
+]
+
+[heading Description]
+The index within each returned `boost::range::index_value` is equal to
+`start_index` + the offset of the element from the beginning of the range. In
+the versions of the functions that omit `start_index` the starting index is
+taken to be `0`.
+
+* [*Purpose:] Adapt `rng` to return elements that have the corresponding value
+from `rng` and a numeric index.
+* [*Returns:] A range adapted to return both the element and the associated
+index. The returned range has elements of type:
+
+``
+boost::range::index_value<
+    typename boost::range_reference<decltype(rng)>::type,
+    typename boost::range_difference<decltype(rng)>::type
+>
+``
+
+The synopsis of index_value is as follows:
+``
+template<class T, class Indexable=std::ptrdiff_t>
+class index_value : public boost::tuple<Indexable, T>
+{
+public:
+
+    typedef ...unspecified...       index_type;
+    typedef ...unspecified...       const_index_type;
+
+    typedef ...unspecified...       value_type;
+    typedef ...unspecified...       const_value_type;
+
+    // ...unspecified... constructors
+
+    index_type index();
+    const_index_type index() const;
+
+    value_type value();
+    const_value_type value() const;
+};
+``
+
+* [*Range Category:] __single_pass_range__
+* [*Range Return Type:] `boost::indexed_range<decltype(rng)>`
+* [*Returned Range Category:] The range category of `rng` if and only if `rng`
+is not a __bidirectional_range__. If `rng` is a __bidirectional_range__ then the
+returned range category is __forward_range__. The rationale for the demotion of
+__bidirectional_range__ inputs to __forward_range__ is to avoid slow calculation
+of indices for `boost::end(rng)`.
+
+[section:indexed_example indexed example]
+[import ../../../test/adaptor_test/indexed_example.cpp]
+[indexed_example]
+[endsect]
+
+This would produce the output:
+``
+Element = 10 Index = 0
+Element = 20 Index = 1
+Element = 30 Index = 2
+Element = 40 Index = 3
+Element = 50 Index = 4
+Element = 60 Index = 5
+Element = 70 Index = 6
+Element = 80 Index = 7
+Element = 90 Index = 8
+``
+[endsect]
+
+

doc/reference/adaptors/indirected.qbk

@@ -0,0 +1,31 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:indirected indirected]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::indirected`]]
+    [[Function] [`boost::adaptors::indirect(rng)`]]
+]
+
+* [*Precondition:] The `value_type` of the range defines unary `operator*()`
+* [*Postcondition:] For all elements `x` in the returned range, `x` is the result of `*y` where `y` is the corresponding element in the original range.
+* [*Range Category:] __single_pass_range__
+* [*Range Return Type:] `boost::indirected_range<decltype(rng)>`
+* [*Returned Range Category:] The range category of `rng`
+
+[section:indirected_example indirected example]
+[import ../../../test/adaptor_test/indirected_example.cpp]
+[indirected_example]
+[endsect]
+
+This would produce the output:
+``
+0,1,2,3,4,5,6,7,8,9,
+``
+[endsect]
+
+

doc/reference/adaptors/map_keys.qbk

@@ -0,0 +1,31 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:map_keys map_keys]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::map_keys`]]
+    [[Function] [`boost::adaptors::keys(rng)`]]
+]
+
+* [*Precondition:] The `value_type` of the range is an instantiation of `std::pair`.
+* [*Postcondition:] For all elements `x` in the returned range, `x` is the result of `y.first` where `y` is the corresponding element in the original range.
+* [*Range Category:] __single_pass_range__
+* [*Range Return Type:] `boost::select_first_range<decltype(rng)>`
+* [*Returned Range Category:] The range category of `rng`.
+
+[section:map_keys_example map_keys example]
+[import ../../../test/adaptor_test/map_keys_example.cpp]
+[map_keys_example]
+[endsect]
+
+This would produce the output:
+``
+0,1,2,3,4,5,6,7,8,9,
+``
+[endsect]
+
+

doc/reference/adaptors/map_values.qbk

@@ -0,0 +1,31 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:map_values map_values]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::map_values`]]
+    [[Function] [`boost::adaptors::values(rng)`]]
+]
+
+* [*Precondition:] The `value_type` of the range is an instantiation of `std::pair`.
+* [*Postcondition:] For all elements `x` in the returned range, `x` is the result of `y.second` where `y` is the corresponding element in the original range.
+* [*Range Category:] __single_pass_range__
+* [*Range Return Type:] for constant ranges, `boost::select_second_const<decltype(rng)>` otherwise `boost::select_second_mutable<decltype(rng)>`
+* [*Returned Range Category:] The range category of `rng`.
+
+[section:map_values_example map_values example]
+[import ../../../test/adaptor_test/map_values_example.cpp]
+[map_values_example]
+[endsect]
+
+This would produce the output:
+``
+0,10,20,30,40,50,60,70,80,90,
+``
+[endsect]
+
+

doc/reference/adaptors/ref_unwrapped.qbk

@@ -0,0 +1,32 @@
+[/
+    Copyright 2015 Robin Eckert
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:ref_unwrapped ref_unwrapped]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::ref_unwrapped`]]
+    [[Function] [`boost::adaptors::ref_unwrap(rng)`]]
+]
+
+This adaptor produces a range than applies `.get()` on all values in
+the range. It is useful for iterating ranges of
+`std::reference_wrapper` values or values using similar semantics.
+
+The adaptor is C++11 (and above) only.
+
+* [*Precondition:] The `value_type` of the range has a `.get() const`.
+* [*Postcondition:] For all elements `x` in the returned range, `x` is the result of `y.get()` where `y` is the corresponding element in the original range.
+* [*Range Category:] __single_pass_range__
+* [*Range Return Type:] `boost::unwrap_ref_range<decltype(rng)>`
+* [*Returned Range Category:] The range category of `rng`.
+
+[section:ref_unwrapped_example ref_unwrapped example]
+[import ../../../test/adaptor_test/ref_unwrapped_example.cpp]
+[ref_unwrapped_example]
+[endsect]
+
+This would produce the output `123`.
+[endsect]

doc/reference/adaptors/replaced.qbk

@@ -0,0 +1,33 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:replaced replaced]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::replaced(old_value, new_value)`]]
+    [[Function] [`boost::adaptors::replace(rng, old_value, new_value)`]]
+]
+
+* [*Precondition:]
+    * `new_value` is convertible to the `value_type` of the range.
+    * `old_value` is convertible to the `value_type` of the range.
+* [*Postcondition:] For all elements `x` in the returned range, the value `x` is equal to the value of `(y == old_value) ? new_value : y` where `y` is the corresponding element in the original range.
+* [*Range Category:] __single_pass_range__
+* [*Range Return Type:] `boost::replaced_range<decltype(rng)>`
+* [*Returned Range Category:] The range category of `rng`.
+
+[section:replaced_example replaced example]
+[import ../../../test/adaptor_test/replaced_example.cpp]
+[replaced_example]
+[endsect]
+
+This would produce the output:
+``
+1,10,3,10,5,10,7,10,9,
+``
+[endsect]
+
+

doc/reference/adaptors/replaced_if.qbk

@@ -0,0 +1,33 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:replaced_if replaced_if]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::replaced_if(pred, new_value)`]]
+    [[Function] [`boost::adaptors::replace_if(rng, pred, new_value)`]]
+]
+
+* [*Precondition:]
+    * The range `value_type` is convertible to the argument type of `pred`.
+    * `new_value` is convertible to the `value_type` of the range.
+* [*Postconditions:] For all elements `x` in the returned range, the value `x` is equal to the value of `pred(y) ? new_value : y` where `y` is the corresponding element in the original range.
+* [*Range Category:] __single_pass_range__
+* [*Range Return Type:] `boost::replaced_if_range<decltype(rng)>`
+* [*Returned Range Category:] The range category of `rng`.
+
+[section:replaced_if_example replaced_if example]
+[import ../../../test/adaptor_test/replaced_if_example.cpp]
+[replaced_if_example]
+[endsect]
+
+This would produce the output:
+``
+1,10,3,10,5,10,7,10,9,
+``
+[endsect]
+
+

doc/reference/adaptors/reversed.qbk

@@ -0,0 +1,30 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:reversed reversed]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::reversed`]]
+    [[Function] [`boost::adaptors::reverse(rng)`]]
+]
+
+* [*Returns:] A range whose iterators behave as if they were the original iterators wrapped in `reverse_iterator`.
+* [*Range Category:] __bidirectional_range__
+* [*Range Return Type:] `boost::reversed_range<decltype(rng)>`
+* [*Returned Range Category:] The range category of `rng`.
+
+[section:reversed_example reversed example]
+[import ../../../test/adaptor_test/reversed_example.cpp]
+[reversed_example]
+[endsect]
+
+This would produce the output:
+``
+9,8,7,6,5,4,3,2,1,
+``
+[endsect]
+
+

doc/reference/adaptors/sliced.qbk

@@ -0,0 +1,31 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:sliced sliced]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::sliced(n, m)`]]
+    [[Function] [`boost::adaptors::slice(rng, n, m)`]]
+]
+
+* [*Precondition:] `0 <= n && n <= m && m < distance(rng)`
+* [*Returns:] `make_range(rng, n, m)`
+* [*Range Category:] __random_access_range__
+* [*Range Return Type:] `boost::sliced_range<decltype(rng)>`
+* [*Returned Range Category:] __random_access_range__
+
+[section:sliced_example sliced example]
+[import ../../../test/adaptor_test/sliced_example.cpp]
+[sliced_example]
+[endsect]
+
+This would produce the output:
+``
+3,4,5,
+``
+[endsect]
+
+

doc/reference/adaptors/strided.qbk

@@ -0,0 +1,30 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:strided strided]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::strided(n)`]]
+    [[Function] [`boost::adaptors::stride(rng, n)`]]
+]
+
+* [*Precondition:] `0 <= n`.
+* [*Returns:] A new range based on `rng` where traversal is performed in steps of `n`.
+* [*Range Category:] __single_pass_range__
+* [*Returned Range Category:] The range category of `rng`.
+
+[section:strided_example strided example]
+[import ../../../test/adaptor_test/strided_example.cpp]
+[strided_example]
+[endsect]
+
+This would produce the output:
+``
+1,3,5,7,9,
+``
+[endsect]
+
+

doc/reference/adaptors/tokenized.qbk

@@ -0,0 +1,67 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:tokenized tokenized]
+
+[table
+    [[Syntax] [Code]]
+    [
+        [Pipe]
+        [
+            ``
+            rng | boost::adaptors::tokenized(regex)
+            rng | boost::adaptors::tokenized(regex, i)
+            rng | boost::adaptors::tokenized(regex, rndRng)
+            rng | boost::adaptors::tokenized(regex, i, flags)
+            rng | boost::adaptors::tokenized(regex, rndRng, flags)
+            ``
+        ]
+    ]
+    [
+        [Function]
+        [
+            ``
+            boost::adaptors::tokenize(rng, regex)
+            boost::adaptors::tokenize(rng, regex, i)
+            boost::adaptors::tokenize(rng, regex, rndRng)
+            boost::adaptors::tokenize(rng, regex, i, flags)
+            boost::adaptors::tokenize(rng, regex, rndRng, flags)
+            ``
+        ]
+    ]
+]
+
+* [*Precondition:]
+    * Let `T` denote `typename range_value<decltype(rng)>::type`, then `regex` has the type `basic_regex<T>` or is implicitly convertible to one of these types.
+    * `i` has the type `int`.
+    * the `value_type` of `rndRng` is `int`.
+    * `flags` has the type `regex_constants::syntax_option_type`.
+* [*Returns:] A range whose iterators behave as if they were the original iterators wrapped in `regex_token_iterator`. The first iterator in the range would be constructed by forwarding all the arguments of `tokenized()` to the `regex_token_iterator` constructor.
+* [*Throws:] Whatever constructing and copying equivalent `regex_token_iterator`s might throw.
+* [*Range Category:] __random_access_range__
+* [*Range Return Type:] `boost::tokenized_range<decltype(rng)>`
+* [*Returned Range Category:] __random_access_range__
+
+[section:tokenized_example tokenized_example]
+[import ../../../test/adaptor_test/tokenized_example.cpp]
+[tokenized_example]
+[endsect]
+
+This would produce the output:
+``
+a
+b
+c
+d
+e
+f
+g
+hijklmnopqrstuvwxyz
+
+``
+
+[endsect]
+
+

doc/reference/adaptors/transformed.qbk

@@ -0,0 +1,32 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:transformed transformed]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::transformed(fun)`]]
+    [[Function] [`boost::adaptors::transform(rng, fun)`]]
+]
+
+* [*Precondition:] The `value_type` of the range is convertible to the argument type of `fun`.
+* [*Postcondition:] For all elements `x` in the returned range, `x` is the result of `fun(y)` where `y` is the corresponding element in the original range.
+* [*Throws:] Whatever the copy-constructor of `fun` might throw.
+* [*Range Category:] __single_pass_range__
+* [*Range Return Type:] `boost::transformed_range<decltype(rng)>`
+* [*Returned Range Category:] The range category of `rng`.
+
+[section:transformed_example transformed example]
+[import ../../../test/adaptor_test/transformed_example.cpp]
+[transformed_example]
+[endsect]
+
+This would produce the output:
+``
+2,4,6,8,10,12,14,16,18,20,
+``
+[endsect]
+
+

doc/reference/adaptors/type_erased.qbk

@@ -0,0 +1,65 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:type_erased type_erased]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::type_erased<Value, Traversal, Reference, Difference, Buffer>()`]]
+    [[Function] [`boost::adaptors::type_erase(rng, boost::adaptors::type_erased<Value, Traversal, Reference, Difference, Buffer>)`]]
+]
+
+Please note that it is frequently unnecessary to use the `type_erased` adaptor. It is often better to use the implicit conversion to `any_range`.
+
+Let `Rng` be the type of `rng`.
+
+* [*Template parameters:]
+    * `Value` is the `value_type` for the `any_range`. If this is set to boost::use_default, `Value` will be calculated from the
+        range type when the adaptor is applied.
+    * `Traversal` is the tag used to identify the traversal of the resultant range. Frequently it is desirable to set a traversal category lower than the source container or range to maximize the number of ranges that can convert to the `any_range`. If this is left as boost::use_default then `Traversal` will be `typename boost::iterator_traversal<boost::range_iterator<Rng>::type>::type`
+    * `Reference` is the `reference` for the `any_range`. `boost::use_default` will equate to `typename range_reference<Rng>::type`.
+    * `Difference` is the `difference_type` for the any_range. `boost::use_default` will equate to `typename boost::range_difference<Rng>::type`
+    * `Buffer` is the storage used to allocate the underlying iterator wrappers. This can typically be ignored, but is available as a template parameter for customization. Buffer must be a model of the `AnyIteratorBufferConcept`.
+* [*Precondition:]  `Traversal` is one of `{ boost::use_default, boost::single_pass_traversal_tag, boost::forward_traversal_tag, boost::bidirectional_traversal_tag, boost::random_access_traversal_tag }`
+* [*Returns:] The returned value is the same as `typename any_range_type_generator< Rng, Value, Traversal, Reference, Difference, Buffer >` that represents `rng` in a type-erased manner.
+* [*Range Category:] __single_pass_range__
+* [*Returned Range Category:] if `Traversal` was specified as `boost::use_default` then `typename boost::iterator_traversal<boost::range_iterator<Rng>::type>::type`, otherwise `Traversal`.
+
+[heading AnyIteratorBufferConcept]
+``
+class AnyIteratorBufferConcept
+{
+public:
+    AnyIteratorBufferConcept();
+    ~AnyIteratorBufferConcept();
+
+    // bytes is the requested size to allocate. This function
+    // must return a pointer to an adequate area of memory.
+    // throws: bad_alloc
+    //
+    // The buffer will only ever have zero or one
+    // outstanding memory allocations.
+    void* allocate(std::size_t bytes);
+
+    // deallocate this buffer
+    void deallocate();
+};
+``
+
+[section:type_erased_example type-erased example]
+[import ../../../test/adaptor_test/type_erased_example.cpp]
+[type_erased_example]
+[endsect]
+
+This would produce the output:
+``
+1,2,3,4,5,
+6,7,8,9,10,
+11,12,13,14,15,
+11,12,13,14,15,
+``
+[endsect]
+
+

doc/reference/adaptors/uniqued.qbk

@@ -0,0 +1,31 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:uniqued uniqued]
+
+[table
+    [[Syntax] [Code]]
+    [[Pipe] [`rng | boost::adaptors::uniqued`]]
+    [[Function] [`boost::adaptors::unique(rng)`]]
+]
+
+* [*Precondition:] The `value_type` of the range is comparable with `operator==()`.
+* [*Postcondition:] For all adjacent elements `[x,y]` in the returned range, `x==y` is false.
+* [*Range Category:] __forward_range__
+* [*Range Return Type:] `boost::uniqued_range<decltype(rng)>`
+* [*Returned Range Category:] The minimum of the range concept of `rng` and __forward_range__.
+
+[section:uniqued_example uniqued example]
+[import ../../../test/adaptor_test/uniqued_example.cpp]
+[uniqued_example]
+[endsect]
+
+This would produce the output:
+``
+1,2,3,4,5,6,
+``
+[endsect]
+
+

doc/reference/algorithm/adjacent_find.qbk

@@ -0,0 +1,85 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:adjacent_find adjacent_find]
+
+[heading Prototype]
+
+``
+template<class ForwardRange>
+typename range_iterator<ForwardRange>::type
+adjacent_find(ForwardRange& rng);
+
+template<class ForwardRange>
+typename range_iterator<const ForwardRange>::type
+adjacent_find(const ForwardRange& rng);
+
+template<class ForwardRange, class BinaryPredicate>
+typename range_iterator<ForwardRange>::type
+adjacent_find(ForwardRange& rng, BinaryPred pred);
+
+template<class ForwardRange, class BinaryPredicate>
+typename range_iterator<const ForwardRange>::type
+adjacent_find(const ForwardRange& rng, BinaryPred pred);
+
+template<range_return_value_re, class ForwardRange>
+typename range_return<ForwardRange, re>::type
+adjacent_find(ForwardRange& rng);
+
+template<range_return_value_re, class ForwardRange>
+typename range_return<const ForwardRange, re>::type
+adjacent_find(const ForwardRange& rng);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class BinaryPredicate
+    >
+typename range_return<ForwardRange, re>::type
+adjacent_find(ForwardRange& rng, BinaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class BinaryPredicate
+    >
+typename range_return<const ForwardRange, re>::type
+adjacent_find(const ForwardRange& rng, BinaryPredicate pred);
+``
+
+[heading Description]
+
+[*Non-predicate versions:]
+
+`adjacent_find` finds the first adjacent elements `[x,y]` in `rng` where `x == y`
+
+[*Predicate versions:]
+
+`adjacent_find` finds the first adjacent elements `[x,y]` in `rng` where `pred(x,y)` is `true`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/adjacent_find.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions of adjacent_find:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange`'s value type is a model of the `EqualityComparableConcept`.
+
+[*For the predicate versions of adjacent_find:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `ForwardRange`'s value type is convertible to `BinaryPredicate`'s first argument type and to `BinaryPredicate`'s second argument type.
+
+[heading Complexity]
+
+Linear. If `empty(rng)` then no comparisons are performed; otherwise, at most `distance(rng) - 1` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/binary_search.qbk

@@ -0,0 +1,60 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:binary_search binary_search]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class Value>
+bool binary_search(const ForwardRange& rng, const Value& val);
+
+template<class ForwardRange, class Value, class BinaryPredicate>
+bool binary_search(const ForwardRange& rng, const Value& val, BinaryPredicate pred);
+``
+
+[heading Description]
+
+`binary_search` returns `true` if and only if the value `val` exists in the range `rng`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/binary_search.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions of binary_search:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `Value` is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `Value` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+* `ForwardRange`'s value type is the same type as `Value`.
+
+[*For the predicate versions of binary_search:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `ForwardRange`'s value type is the same type as `Value`.
+* `ForwardRange`'s value type is convertible to `BinaryPredicate`'s argument type.
+
+[heading Precondition:]
+
+[*For the non-predicate version:]
+
+`rng` is ordered in ascending order according to `operator<`.
+
+[*For the predicate version:]
+
+`rng` is ordered in ascending order according to the function object `pred`.
+
+[heading Complexity]
+
+For non-random-access ranges, the complexity is `O(N)` where `N` is `distance(rng)`.
+
+For random-access ranges, the complexity is `O(log N)` where `N` is `distance(rng)`.
+
+[endsect]
+
+

doc/reference/algorithm/copy.qbk

@@ -0,0 +1,41 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:copy copy]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange, class OutputIterator>
+OutputIterator copy(const SinglePassRange& source_rng, OutputIterator out_it);
+``
+
+[heading Description]
+
+`copy` copies all elements from `source_rng` to the range `[out_it, out_it + distance(source_rng))`.
+The return value is `out_it + distance(source_rng)`
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/copy.hpp`
+
+[heading Requirements]
+
+* `SinglePassRange` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* The `value_type` of __single_pass_range__ Concept is convertible to a type in `OutputIterator`'s set of value types.
+
+[heading Precondition:]
+
+* `out_it` is not an iterator within the `source_rng`.
+* `[out_it, out_it + distance(source_rng))` is a valid range.
+
+[heading Complexity]
+
+Linear. Exactly `distance(source_rng)` assignments are performed.
+
+[endsect]
+
+

doc/reference/algorithm/copy_backward.qbk

@@ -0,0 +1,46 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:copy_backward copy_backward]
+
+[heading Prototype]
+
+``
+template<class BidirectionalRange, class BidirectionalOutputIterator>
+    BidirectionalOutputIterator
+        copy_backward(const BidirectionalRange& source_rng,
+                      BidirectionalOutputIterator out_it);
+``
+
+[heading Description]
+
+`copy_backward` copies all elements from `source_rng` to the range `[out_it - distance(source_rng), out_it)`.
+
+The values are copied in reverse order. The return value is `out_it - distance(source_rng)`.
+
+Note well that unlike all other standard algorithms `out_it` denotes the *end* of the output sequence.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/copy_backward.hpp`
+
+[heading Requirements]
+
+* `BidirectionalRange` is a model of __bidirectional_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* The `value_type` of __bidirectional_range__ Concept is convertible to a type in `OutputIterator`'s set of value types.
+
+[heading Precondition:]
+
+* `out_it` is not an iterator within the `source_rng`.
+* `[out_it, out_it + distance(source_rng))` is a valid range.
+
+[heading Complexity]
+
+Linear. Exactly `distance(source_rng)` assignments are performed.
+
+[endsect]
+
+

doc/reference/algorithm/count.qbk

@@ -0,0 +1,41 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:count count]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange, class Value>
+typename range_difference<SinglePassRange>::type
+count(SinglePassRange& rng, const Value& val);
+
+template<class SinglePassRange, class Value>
+typename range_difference<const SinglePassRange>::type
+count(const SinglePassRange& rng, const Value& val);
+``
+
+[heading Description]
+
+`count` returns the number of elements `x` in `rng` where `x == val` is `true`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/count.hpp`
+
+[heading Requirements]
+
+* `SinglePassRange` is a model of the __single_pass_range__ Concept.
+* `Value` is a model of the `EqualityComparableConcept`.
+* `SinglePassRange`'s value type is a model of the `EqualityComparableConcept`.
+* An object of `SinglePassRange`'s value type can be compared for equality with an object of type `Value`.
+
+[heading Complexity]
+
+Linear. Exactly `distance(rng)` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/count_if.qbk

@@ -0,0 +1,37 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:count_if count_if]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange, class UnaryPredicate>
+typename range_difference<const SinglePassRange>::type
+count_if(const SinglePassRange& rng, UnaryPredicate pred);
+``
+
+[heading Description]
+
+`count_if` returns the number of elements `x` in `rng` where `pred(x)` is `true`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/count_if.hpp`
+
+[heading Requirements]
+
+* `SinglePassRange` is a model of the __single_pass_range__ Concept.
+* `UnaryPredicate` is a model of the `UnaryPredicateConcept`.
+* `SinglePassRange`'s value type is a model of the `EqualityComparableConcept`.
+* The value type of `SinglePassRange` is convertible to the argument type of `UnaryPredicate`.
+
+[heading Complexity]
+
+Linear. Exactly `distance(rng)` invocations of `pred`.
+
+[endsect]
+
+

doc/reference/algorithm/equal.qbk

@@ -0,0 +1,64 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:equal equal]
+
+[heading Prototype]
+
+``
+template<
+    class SinglePassRange1,
+    class SinglePassRange2
+>
+bool equal(const SinglePassRange1& rng1,
+           const SinglePassRange2& rng2);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class BinaryPredicate
+>
+bool equal(const SinglePassRange1& rng1,
+           const SinglePassRange2& rng2,
+           BinaryPredicate         pred);
+``
+
+[heading Description]
+
+`equal` returns `true` if `distance(rng1)` is equal to the `distance(rng2)` and for each element `x` in `rng1`, the corresponding element `y` in `rng2` is equal. Otherwise `false` is returned.
+
+In this range version of `equal` it is perfectly acceptable to pass in two ranges of unequal lengths.
+
+Elements are considered equal in the non-predicate version if `operator==` returns `true`. Elements are considered equal in the predicate version if `pred(x,y)` is `true`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/equal.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange1`'s value type is a model of the `EqualityComparableConcept`.
+* `SinglePassRange2`'s value type is a model of the `EqualityComparableConcept`.
+* `SinglePassRange1`'s value type can be compared for equality with `SinglePassRange2`'s value type.
+
+[*For the predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `SinglePassRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `SinglePassRange2`'s value type is convertible to `BinaryPredicate`'s second argument type.
+
+[heading Complexity]
+
+Linear. At most `min(distance(rng1), distance(rng2))` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/equal_range.qbk

@@ -0,0 +1,83 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:equal_range equal_range]
+
+[heading Prototype]
+
+``
+template<
+    class ForwardRange,
+    class Value
+    >
+std::pair<typename range_iterator<ForwardRange>::type,
+          typename range_iterator<ForwardRange>::type>
+equal_range(ForwardRange& rng, const Value& val);
+
+template<
+    class ForwardRange,
+    class Value
+    >
+std::pair<typename range_iterator<const ForwardRange>::type,
+          typename range_iterator<const ForwardRange>::type>
+equal_range(const ForwardRange& rng, const Value& val);
+
+template<
+    class ForwardRange,
+    class Value,
+    class SortPredicate
+    >
+std::pair<typename range_iterator<ForwardRange>::type,
+          typename range_iterator<ForwardRange>::type>
+equal_range(ForwardRange& rng, const Value& val, SortPredicate pred);
+
+template<
+    class ForwardRange,
+    class Value,
+    class SortPredicate
+    >
+std::pair<typename range_iterator<const ForwardRange>::type,
+          typename range_iterator<const ForwardRange>::type>
+equal_range(const ForwardRange& rng, const Value& val, SortPredicate pred);                      
+ ``
+
+[heading Description]
+
+`equal_range` returns a range in the form of a pair of iterators where all of the elements are equal to `val`. If no values are found that are equal to `val`, then an empty range is returned, hence `result.first == result.second`. For the non-predicate versions of `equal_range`  the equality of elements is determined by `operator<`.
+For the predicate versions of `equal_range` the equality of elements is determined by `pred`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/equal_range.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `Value` is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `Value` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+* `ForwardRange`'s value type is the same type as `Value`.
+
+[*For the predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `SortPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `ForwardRange`'s value type is the same as `Value`.
+* `ForwardRange`'s value type is convertible to both of `SortPredicate`'s argument types.
+
+[heading Precondition:]
+
+For the non-predicate versions: `rng` is ordered in ascending order according to `operator<`.
+
+For the predicate versions: `rng` is ordered in ascending order according to `pred`.
+
+[heading Complexity]
+
+For random-access ranges, the complexity is `O(log N)`, otherwise the complexity is `O(N)`. 
+
+[endsect]
+
+

doc/reference/algorithm/fill.qbk

@@ -0,0 +1,36 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:fill fill]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class Value>
+ForwardRange& fill( ForwardRange& rng, const Value& val );
+``
+
+[heading Description]
+
+`fill` assigns the value `val` to every element in the range `rng`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/fill.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `Value` is a model of the `AssignableConcept`.
+* `Value` is convertible to `ForwardRange`'s value type.
+
+[heading Complexity]
+
+Linear. Exactly `distance(rng)` assignments are performed.
+
+[endsect]
+
+

doc/reference/algorithm/fill_n.qbk

@@ -0,0 +1,36 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:fill_n fill_n]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class Size, class Value>
+ForwardRange& fill( ForwardRange& rng, Size n, const Value& val );
+``
+
+[heading Description]
+
+`fill_n` assigns the value `val` to `n` elements in the range `rng` beginning with `boost::begin(rng)`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/fill_n.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `Value` is a model of the `AssignableConcept`.
+* `Value` is convertible to `ForwardRange`'s value type.
+
+[heading Complexity]
+
+Linear. Exactly `n` assignments are performed.
+
+[endsect]
+
+

doc/reference/algorithm/find.qbk

@@ -0,0 +1,45 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:find find]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange, class Value>
+typename range_iterator<SinglePassRange>::type
+find(SinglePassRange& rng, Value val);
+
+template<
+    range_return_value re,
+    class SinglePassRange,
+    class Value
+    >
+typename range_return<SinglePassRange, re>::type
+find(SinglePassRange& rng, Value val);
+``
+
+[heading Description]
+
+The versions of `find` that return an iterator, returns the first iterator in the range `rng` such that `*i == value`. `end(rng)` is returned if no such iterator exists.
+The versions of find that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/find.hpp`
+
+[heading Requirements]
+
+* `SinglePassRange` is a model of the __single_pass_range__ Concept.
+* `Value` is a model of the `EqualityComparableConcept`.
+* The `operator==` is defined for type `Value` to be compared with the `SinglePassRange`'s value type.
+
+[heading Complexity]
+
+Linear. At most `distance(rng)` comparisons for equality.
+
+[endsect]
+
+

doc/reference/algorithm/find_end.qbk

@@ -0,0 +1,74 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:find_end find_end]
+
+[heading Prototype]
+
+``
+template<class ForwardRange1, class ForwardRange2>
+typename range_iterator<ForwardRange1>::type
+find_end(ForwardRange1& rng1, const ForwardRange2& rng2);
+
+template<
+    class ForwardRange1,
+    class ForwardRange2,
+    class BinaryPredicate
+    >
+typename range_iterator<ForwardRange1>::type
+find_end(ForwardRange1& rng1, const ForwardRange2& rng2, BinaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange1,
+    class ForwardRange2
+    >
+typename range_return<ForwardRange1, re>::type
+find_end(ForwardRange1& rng1, const ForwardRange2& rng2);
+
+template<
+    range_return_value re,
+    class ForwardRange1,
+    class ForwardRange2,
+    class BinaryPredicate
+    >
+typename range_return<ForwardRange1, re>::type
+find_end(ForwardRange1& rng1, const ForwardRange2& rng2, BinaryPredicate pred);
+``
+
+[heading Description]
+
+The versions of `find_end` that return an iterator, return an iterator to the beginning of the last sub-sequence equal to `rng2` within `rng1`.
+Equality is determined by `operator==` for non-predicate versions of `find_end`, and by satisfying `pred` in the predicate versions. The versions of `find_end` that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/find_end.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `ForwardRange1` is a model of the __forward_range__ Concept.
+* `ForwardRange2` is a model of the __forward_range__ Concept.
+* `ForwardRange1`'s value type is a model of the `EqualityComparableConcept`.
+* `ForwardRange2`'s value type is a model of the `EqualityComparableConcept`.
+* Objects of `ForwardRange1`'s value type can be compared for equality with objects of `ForwardRange2`'s value type.
+
+[*For the predicate versions:]
+
+* `ForwardRange1` is a model of the __forward_range__ Concept.
+* `ForwardRange2` is a model of the __forward_range__ Concept.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `ForwardRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `ForwardRange2`'s value type is convertible to `BinaryPredicate`'s second argument type.
+
+[heading Complexity]
+
+The number of comparisons is proportional to `distance(rng1) * distance(rng2)`. If both `ForwardRange1` and `ForwardRange2` are models of `BidirectionalRangeConcept` then the average complexity is linear and the worst case is `distance(rng1) * distance(rng2)`.
+
+[endsect]
+
+

doc/reference/algorithm/find_first_of.qbk

@@ -0,0 +1,74 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:find_first_of find_first_of]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange1, class ForwardRange2>
+typename range_iterator<SinglePassRange1>::type
+find_first_of(SinglePassRange1& rng1, const ForwardRange2& rng2);
+
+template<
+    class SinglePassRange1,
+    class ForwardRange2,
+    class BinaryPredicate
+    >
+typename range_iterator<SinglePassRange1>::type
+find_first_of(SinglePassRange1& rng1, const ForwardRange2& rng2, BinaryPredicate pred);
+
+template<
+    range_return_value re,
+    class SinglePassRange1,
+    class ForwardRange2
+    >
+typename range_return<SinglePassRange1, re>::type
+find_first_of(SinglePassRange1& rng1, const ForwardRange2& rng2);
+
+template<
+    range_return_value re,
+    class SinglePassRange1,
+    class ForwardRange2,
+    class BinaryPredicate
+    >
+typename range_return<SinglePassRange1, re>::type
+find_first_of(SinglePassRange1& rng1, const ForwardRange2& rng2, BinaryPredicate pred);
+``
+
+[heading Description]
+
+The versions of `find_first_of` that return an iterator, return an iterator to the first occurrence in `rng1` of any of the elements in `rng2`.
+Equality is determined by `operator==` for non-predicate versions of `find_first_of`, and by satisfying `pred` in the predicate versions.
+
+The versions of `find_first_of` that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/find_first_of.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `ForwardRange2` is a model of the __forward_range__ Concept.
+* `SinglePassRange1`'s value type is a model of the `EqualityComparableConcept`, and can be compared for equality with `ForwardRange2`'s value type.
+
+[*For the predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `ForwardRange2` is a model of the __forward_range__ Concept.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `SinglePassRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `ForwardRange2`'s value type is convertible to `BinaryPredicate`'s second argument type.
+
+[heading Complexity]
+
+At most `distance(rng1) * distance(rng2)` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/find_if.qbk

@@ -0,0 +1,50 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:find_if find_if]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange, class UnaryPredicate>
+typename range_iterator<SinglePassRange>::type
+find_if(SinglePassRange& rng, UnaryPredicate pred);
+
+template<
+    range_return_value re,
+    class SinglePassRange,
+    class UnaryPredicate
+    >
+typename range_return<SinglePassRange, re>::type
+find_if(SinglePassRange& rng, UnaryPredicate pred);
+``
+
+[heading Description]
+
+The versions of `find_if` that return an iterator, returns the first iterator in the range `rng` such that `pred(*i)` is `true`. `end(rng)` is returned if no such iterator exists.
+
+The versions of `find_if` that return a `range_return`, defines found in the same manner as the returned iterator described above.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/find_if.hpp`
+
+[heading Requirements]
+
+* `SinglePassRange` is a model of the __single_pass_range__ Concept.
+* `UnaryPredicate` is a model of the `PredicateConcept`.
+* The value type of `SinglePassRange` is convertible to the argument type of `UnaryPredicate`.
+
+[heading Precondition:]
+
+For each iterator `i` in `rng`, `*i` is in the domain of `UnaryPredicate`.
+
+[heading Complexity]
+
+Linear. At most `distance(rng)` invocations of `pred`.
+
+[endsect]
+
+

doc/reference/algorithm/for_each.qbk

@@ -0,0 +1,45 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:for_each for_each]
+
+[heading Prototype]
+
+``
+template<
+    class SinglePassRange,
+    class UnaryFunction
+    >
+UnaryFunction for_each(SinglePassRange& rng, UnaryFunction fun);
+
+template<
+    class SinglePassRange,
+    class UnaryFunction
+    >
+UnaryFunction for_each(const SinglePassRange& rng, UnaryFunction fun);    
+``
+
+[heading Description]
+
+`for_each` traverses forward through `rng` and for each element `x` it invokes `fun(x)`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/for_each.hpp`
+
+[heading Requirements]
+
+* `SinglePassRange` is a model of the __single_pass_range__ Concept.
+* `UnaryFunction` is a model of the `UnaryFunctionConcept`.
+* `UnaryFunction` does not apply any non-constant operation through its argument.
+* `SinglePassRange`'s value type is convertible to `UnaryFunction`'s argument type.
+
+[heading Complexity]
+
+Linear. Exactly `distance(rng)` applications of `UnaryFunction`.
+
+[endsect]
+
+

doc/reference/algorithm/generate.qbk

@@ -0,0 +1,44 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:generate generate]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class Generator>
+ForwardRange& generate( ForwardRange& rng, Generator gen );
+
+template<class ForwardRange, class Generator>
+const ForwardRange& generate( const ForwardRange& rng, Generator gen );
+``
+
+[heading Description]
+
+`generate` assigns the result of `gen()` to each element in range `rng`. Returns the resultant range.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/generate.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `Generator` is a model of the `GeneratorConcept`.
+* The `value_type` of `SinglePassRange` is convertible to a type in `OutputIterator`'s set of value types.
+
+[heading Precondition:]
+
+* `out_it` is not an iterator within `rng`.
+* `[out_it, out_it + distance(rng))` is a valid range.
+
+[heading Complexity]
+
+Linear. Exactly `distance(rng)` assignments are performed.
+
+[endsect]
+
+

doc/reference/algorithm/includes.qbk

@@ -0,0 +1,69 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:includes includes]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange1, class SinglePassRange2>
+bool includes(const SinglePassRange1& rng1, const SinglePassRange2& rng2);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class BinaryPredicate
+    >
+bool includes(const SinglePassRange1& rng1, const SinglePassRange2& rng2,
+              BinaryPredicate pred);    
+``
+
+[heading Description]
+
+`includes` returns `true` if and only if, for every element in `rng2`, an equivalent element is also present in `rng1`.
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions. 
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/set_algorithm.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange1` and `SinglePassRange2` have the same value type.
+* `SinglePassRange1`'s value type is a model of the `LessThanComparableConcept`.
+* `SinglePassRange2`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `SinglePassRange1`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+* The ordering of objects of type `SinglePassRange2`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange1` and `SinglePassRange2` have the same value type.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `SinglePassRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `SinglePassRange2`'s value type is convertible to `BinaryPredicate`'s second argument types.
+
+[heading Precondition:]
+
+[*For the non-predicate versions:]
+
+`rng1` and `rng2` are sorted in ascending order according to `operator<`.
+
+[*For the predicate versions:]
+
+`rng1` and `rng2` are sorted in ascending order according to `pred`.
+
+[heading Complexity]
+
+Linear. `O(N)`, where `N` is `distance(rng1) + distance(rng2)`.
+
+[endsect]
+
+

doc/reference/algorithm/inplace_merge.qbk

@@ -0,0 +1,77 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:inplace_merge inplace_merge]
+
+[heading Prototype]
+
+``
+template<class BidirectionalRange>
+BidirectionalRange&
+inplace_merge( BidirectionalRange& rng,
+               typename range_iterator<BidirectionalRange>::type middle );
+
+template<class BidirectionalRange>
+const BidirectionalRange&
+inplace_merge( const BidirectionalRange& rng,
+               typename range_iterator<const BidirectionalRange>::type middle );
+
+template<class BidirectionalRange, class BinaryPredicate>
+BidirectionalRange&
+inplace_merge( BidirectionalRange& rng,
+               typename range_iterator<BidirectionalRange>::type middle,
+               BinaryPredicate pred );
+
+template<class BidirectionalRange, class BinaryPredicate>
+const BidirectionalRange&
+inplace_merge( const BidirectionalRange& rng,
+               typename range_iterator<const BidirectionalRange>::type middle,
+               BinaryPredicate pred );
+``
+
+[heading Description]
+
+`inplace_merge` combines two consecutive sorted ranges `[begin(rng), middle)` and `[middle, end(rng))` into a single sorted range `[begin(rng), end(rng))`. That is, it starts with a range `[begin(rng), end(rng))` that consists of two pieces each of which is in ascending order, and rearranges it so that the entire range is in ascending order. `inplace_merge` is stable, meaning both that the relative order of elements within each input range is preserved.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/inplace_merge.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate version:]
+
+* `BidirectionalRange` is a model of the __bidirectional_range__ Concept.
+* `BidirectionalRange` is mutable.
+* `range_value<BidirectionalRange>::type` is a model of `LessThanComparableConcept`
+* The ordering on objects of `range_type<BidirectionalRange>::type` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate version:]
+* `BidirectionalRange` is a model of the __bidirectional_range__ Concept.
+* `BidirectionalRange` is mutable.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `BidirectionalRange`'s value type is convertible to both `BinaryPredicate`'s argument types.
+
+[heading Precondition:]
+
+[heading For the non-predicate version:]
+
+* `middle` is in the range `rng`.
+* `[begin(rng), middle)` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `y < x` is `false`.
+* `[middle, end(rng))` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `y < x` is `false`.
+
+[heading For the predicate version:]
+
+* `middle` is in the range `rng`.
+* `[begin(rng), middle)` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `pred(y,x) == false`.
+* `[middle, end(rng))` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `pred(y,x) == false`.
+
+[heading Complexity]
+
+Worst case: `O(N log(N))`
+
+[endsect]
+
+

doc/reference/algorithm/lexicographical_compare.qbk

@@ -0,0 +1,60 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:lexicographical_compare lexicographical_compare]
+
+[heading Prototype]
+
+``
+template<
+    class SinglePassRange1,
+    class SinglePassRange2
+    >
+bool lexicographical_compare(const SinglePassRange1& rng1,
+                             const SinglePassRange2& rng2);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class BinaryPredicate
+    >
+bool lexicographical_compare(const SinglePassRange1& rng1,
+                             const SinglePassRange2& rng2,
+                             BinaryPredicate pred);    
+``
+
+[heading Description]
+
+`lexicographical_compare` compares element by element `rng1` against `rng2`. If the element from `rng1` is less than the element from `rng2` then `true` is returned. If the end of `rng1` without reaching the end of `rng2` this also causes the return value to be `true`. The return value is `false` in all other circumstances. The elements are compared using `operator<` in the non-predicate versions of `lexicographical_compare` and using `pred` in the predicate versions.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/lexicographical_compare.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions of lexicographical_compare:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange1`'s value type is a model of the `LessThanComparableConcept`.
+* `SinglePassRange2`'s value type is a model of the `LessThanComparableConcept`.
+* Let `x` be an object of `SinglePassRange1`'s value type. Let `y` be an object of `SinglePassRange2`'s value type. `x < y` must be valid. `y < x` must be valid.
+
+[*For the predicate versions of lexicographical_compare:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `SinglePassRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `SinglePassRange2`'s value type is convertible to `BinaryPredicate`'s second argument type.
+
+[heading Complexity]
+
+Linear. At most `2 * min(distance(rng1), distance(rng2))` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/lower_bound.qbk

@@ -0,0 +1,93 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:lower_bound lower_bound]
+
+[heading Prototype]
+
+``
+template<
+    class ForwardRange, 
+    class Value
+    >
+typename range_iterator<ForwardRange>::type
+lower_bound(ForwardRange& rng, Value val);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class Value
+    >
+typename range_return<ForwardRange, re>::type
+lower_bound(ForwardRange& rng, Value val);
+
+template<
+    class ForwardRange,
+    class Value,
+    class SortPredicate
+    >
+typename range_iterator<ForwardRange>::type
+lower_bound(ForwardRange& rng, Value val, SortPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class Value,
+    class SortPredicate
+    >
+typename range_return<ForwardRange,re>::type
+lower_bound(ForwardRange& rng, Value val, SortPredicate pred);
+``
+
+[heading Description]
+
+The versions of `lower_bound` that return an iterator, returns the first iterator in the range `rng` such that:
+without predicate - `*i < value` is `false`,
+with predicate - `pred(*i, value)` is `false`.
+
+`end(rng)` is returned if no such iterator exists.
+
+The versions of `lower_bound` that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/lower_bound.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `Value` is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `Value` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+* `ForwardRange`'s value type is the same type as `Value`.
+
+[*For the predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `ForwardRange`'s value type is the same type as `Value`.
+* `ForwardRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
+
+[heading Precondition:]
+
+[*For the non-predicate versions:]
+
+`rng` is sorted in ascending order according to `operator<`.
+
+[*For the predicate versions:]
+
+`rng` is sorted in ascending order according to `pred`.
+
+[heading Complexity]
+
+For ranges that model the __random_access_range__ concept the complexity is `O(log N)`, where `N` is `distance(rng)`.
+
+For all other range types the complexity is `O(N)`.
+
+
+[endsect]
+
+

doc/reference/algorithm/make_heap.qbk

@@ -0,0 +1,56 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:make_heap make_heap]
+
+[heading Prototype]
+
+``
+template<class RandomAccessRange>
+RandomAccessRange& make_heap(RandomAccessRange& rng);
+
+template<class RandomAccessRange>
+const RandomAccessRange& make_heap(const RandomAccessRange& rng);
+
+template<class RandomAccessRange, class Compare>
+RandomAccessRange& make_heap(RandomAccessRange& rng, Compare pred);
+
+template<class RandomAccessRange, class Compare>
+const RandomAccessRange& make_heap(const RandomAccessRange& rng, Compare pred);
+``
+
+[heading Description]
+
+`make_heap` turns `rng` into a heap.
+
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/heap_algorithm.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `RandomAccessRange`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `RandomAccessRange`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `Compare` is a model of the `StrictWeakOrderingConcept`.
+* `RandomAccessRange`'s value type is convertible to both of `Compare`'s argument types.
+
+[heading Complexity]
+
+Linear. At most `3 * distance(rng)` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/max_element.qbk

@@ -0,0 +1,86 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:max_element max_element]
+
+[heading Prototype]
+
+``
+template<class ForwardRange>
+typename range_iterator<ForwardRange>::type
+max_element(ForwardRange& rng);
+
+template<class ForwardRange>
+typename range_iterator<const ForwardRange>::type
+max_element(const ForwardRange& rng);
+
+template<class ForwardRange, class BinaryPredicate>
+typename range_iterator<ForwardRange>::type
+max_element(ForwardRange& rng, BinaryPredicate pred);
+
+template<class ForwardRange, class BinaryPredicate>
+typename range_iterator<const ForwardRange>::type
+max_element(const ForwardRange& rng, BinaryPredicate pred);
+
+
+template<
+    range_return_value re,
+    class ForwardRange
+    >
+typename range_return<ForwardRange, re>::type
+max_element(ForwardRange& rng);
+
+template<
+    range_return_value_re,
+    class ForwardRange
+    >
+typename range_return<const ForwardRange, re>::type
+max_element(const ForwardRange& rng);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class BinaryPredicate
+    >
+typename range_return<ForwardRange, re>::type
+max_element(ForwardRange& rng, BinaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class BinaryPredicate
+    >
+typename range_return<const ForwardRange, re>::type
+max_element(const ForwardRange& rng, BinaryPredicate pred);
+``
+
+[heading Description]
+
+The versions of `max_element` that return an iterator, return the iterator to the maximum value as determined by using `operator<` if a predicate is not supplied. Otherwise the predicate `pred` is used to determine the maximum value. The versions of `max_element` that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/max_element.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange`'s value type is a model of the `LessThanComparableConcept`.
+
+[*For the predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `ForwardRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
+
+[heading Complexity]
+
+Linear. Zero comparisons if `empty(rng)`, otherwise `distance(rng) - 1` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/merge.qbk

@@ -0,0 +1,88 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:merge merge]
+
+[heading Prototype]
+
+``
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator
+    >
+OutputIterator merge(const SinglePassRange1& rng1,
+                     const SinglePassRange2& rng2,
+                     OutputIterator          out);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator,
+    class BinaryPredicate
+    >
+OutputIterator merge(const SinglePassRange1& rng1,
+                     const SinglePassRange2& rng2,
+                     OutputIterator          out,
+                     BinaryPredicate         pred);
+``
+
+[heading Description]
+
+`merge` combines two sorted ranges `rng1` and `rng2` into a single sorted range by copying elements. `merge` is stable. The return value is `out + distance(rng1) + distance(rng2)`.
+
+The two versions of `merge` differ by how they compare the elements.
+
+The non-predicate version uses the `operator<()` for the range value type. The predicate version uses the predicate instead of `operator<()`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/merge.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate version:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `range_value<SinglePassRange1>::type` is the same as `range_value<SinglePassRange2>::type`.
+* `range_value<SinglePassRange1>::type` is a model of the `LessThanComparableConcept`.
+* The ordering on objects of `range_value<SinglePassRange1>::type` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+* `range_value<SinglePassRange1>::type` is convertible to a type in `OutputIterator`'s set of value types.
+
+[*For the predicate version:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `range_value<SinglePassRange1>::type` is the same as `range_value<SinglePassRange2>::type`.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `SinglePassRange1`'s value type is convertible to both `BinaryPredicate`'s argument types.
+* `range_value<SinglePassRange1>::type` is convertible to a type in `OutputIterator`'s set of value types.
+
+[heading Precondition:]
+
+[heading For the non-predicate version:]
+
+* The elements of `rng1` are in ascending order. That is, for each adjacent element pair `[x,y]` of `rng1`, `y < x == false`.
+* The elements of `rng2` are in ascending order. That is, for each adjacent element pair `[x,y]` of `rng2`, `y < x == false`.
+* The ranges `rng1` and `[out, out + distance(rng1) + distance(rng2))` do not overlap.
+* The ranges `rng2` and `[out, out + distance(rng1) + distance(rng2))` do not overlap.
+* `[out, out + distance(rng1) + distance(rng2))` is a valid range.
+
+[heading For the predicate version:]
+
+* The elements of `rng1` are in ascending order. That is, for each adjacent element pair `[x,y]`, of `rng1`, `pred(y, x) == false`.
+* The elements of `rng2` are in ascending order. That is, for each adjacent element pair `[x,y]`, of `rng2`, `pred(y, x) == false`.
+* The ranges `rng1` and `[out, out + distance(rng1) + distance(rng2))` do not overlap.
+* The ranges `rng2` and `[out, out + distance(rng1) + distance(rng2))` do not overlap.
+* `[out, out + distance(rng1) + distance(rng2))` is a valid range.
+
+[heading Complexity]
+
+Linear. There are no comparisons if both `rng1` and `rng2` are empty, otherwise at most `distance(rng1) + distance(rng2) - 1` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/min_element.qbk

@@ -0,0 +1,86 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:min_element min_element]
+
+[heading Prototype]
+
+``
+template<class ForwardRange>
+typename range_iterator<ForwardRange>::type
+min_element(ForwardRange& rng);
+
+template<class ForwardRange>
+typename range_iterator<const ForwardRange>::type
+min_element(const ForwardRange& rng);
+
+template<class ForwardRange, class BinaryPredicate>
+typename range_iterator<ForwardRange>::type
+min_element(ForwardRange& rng, BinaryPredicate pred);
+
+template<class ForwardRange, class BinaryPredicate>
+typename range_iterator<const ForwardRange>::type
+min_element(const ForwardRange& rng, BinaryPredicate pred);
+
+
+template<
+    range_return_value re,
+    class ForwardRange
+    >
+typename range_return<ForwardRange, re>::type
+min_element(ForwardRange& rng);
+
+template<
+    range_return_value_re,
+    class ForwardRange
+    >
+typename range_return<const ForwardRange, re>::type
+min_element(const ForwardRange& rng);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class BinaryPredicate
+    >
+typename range_return<ForwardRange, re>::type
+min_element(ForwardRange& rng, BinaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class BinaryPredicate
+    >
+typename range_return<const ForwardRange, re>::type
+min_element(const ForwardRange& rng, BinaryPredicate pred);
+``
+
+[heading Description]
+
+The versions of `min_element` that return an iterator, return the iterator to the minimum value as determined by using `operator<` if a predicate is not supplied. Otherwise the predicate `pred` is used to determine the minimum value. The versions of `min_element` that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/min_element.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange`'s value type is a model of the `LessThanComparableConcept`.
+
+[*For the predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `ForwardRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
+
+[heading Complexity]
+
+Linear. Zero comparisons if `empty(rng)`, otherwise `distance(rng) - 1` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/mismatch.qbk

@@ -0,0 +1,119 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:mismatch mismatch]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange1, class SinglePassRange2>
+std::pair<
+    typename range_iterator<SinglePassRange1>::type,
+    typename range_iterator<const SinglePassRange2>::type >
+mismatch(SinglePassRange1& rng1, const SinglePassRange2& rng2);
+
+template<class SinglePassRange1, class SinglePassRange2>
+std::pair<
+    typename range_iterator<const SinglePassRange1>::type,
+    typename range_iterator<const SinglePassRange2>::type >
+mismatch(const SinglePassRange1& rng1, const SinglePassRange2& rng2);
+
+template<class SinglePassRange1, class SinglePassRange2>
+std::pair<
+    typename range_iterator<SinglePassRange1>::type,
+    typename range_iterator<SinglePassRange2>::type >
+mismatch(SinglePassRange1& rng1, SinglePassRange2& rng2);
+
+template<class SinglePassRange1, class SinglePassRange2>
+std::pair<
+    typename range_iterator<const SinglePassRange1>::type,
+    typename range_iterator<SinglePassRange2>::type >
+mismatch(const SinglePassRange1& rng1, SinglePassRange2& rng2);
+
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class BinaryPredicate
+    >
+std::pair<
+    typename range_iterator<SinglePassRange1>::type,
+    typename range_iterator<const SinglePassRange2>::type >
+mismatch(SinglePassRange1& rng1, const SinglePassRange2& rng2,
+         BinaryPredicate pred);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class BinaryPredicate
+    >
+std::pair<
+    typename range_iterator<const SinglePassRange1>::type,
+    typename range_iterator<const SinglePassRange2>::type >
+mismatch(const SinglePassRange1& rng1, const SinglePassRange2& rng2,
+         BinaryPredicate pred);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class BinaryPredicate
+    >
+std::pair<
+    typename range_iterator<SinglePassRange1>::type,
+    typename range_iterator<SinglePassRange2>::type >
+mismatch(SinglePassRange1& rng1, SinglePassRange2& rng2,
+         BinaryPredicate pred);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class BinaryPredicate
+    >
+std::pair<
+    typename range_iterator<const SinglePassRange1>::type,
+    typename range_iterator<SinglePassRange2>::type >
+mismatch(const SinglePassRange1& rng1, SinglePassRange2& rng2,
+         BinaryPredicate pred);
+``
+
+[heading Description]
+
+`mismatch` finds the first position where the corresponding elements from the two ranges `rng1` and `rng2` are not equal.
+
+Equality is determined by `operator==` for non-predicate versions of `mismatch`, and by satisfying `pred` in the predicate versions.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/mismatch.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange1`'s value type is a model of the `EqualityComparableConcept`.
+* `SinglePassRange2`'s value type is a model of the `EqualityComparableConcept`.
+* `SinglePassRange1`s value type can be compared for equality with `SinglePassRange2`'s value type.
+
+[*For the predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `SinglePassRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `SinglePassRange2`'s value type is convertible to `BinaryPredicate`'s second argument type.
+
+[heading Precondition:]
+
+`distance(rng2) >= distance(rng1)`
+
+[heading Complexity]
+
+Linear. At most `distance(rng1)` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/next_permutation.qbk

@@ -0,0 +1,56 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:next_permutation next_permutation]
+
+[heading Prototype]
+
+``
+template<class BidirectionalRange>
+bool next_permutation(BidirectionalRange& rng);
+
+template<class BidirectionalRange>
+bool next_permutation(const BidirectionalRange& rng);
+
+template<class BidirectionalRange, class Compare>
+bool next_permutation(BidirectionalRange& rng, Compare pred);
+
+template<class BidirectionalRange, class Compare>
+bool next_permutation(const BidirectionalRange& rng, Compare pred);
+``
+
+[heading Description]
+
+`next_permutation` transforms the range of elements `rng` into the lexicographically next greater permutation of the elements if such a permutation exists. If one does not exist then the range is transformed into the lexicographically smallest permutation and `false` is returned. `true` is returned when the next greater permutation is successfully generated.
+
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/permutation.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `BidirectionalRange` is a model of the __bidirectional_range__ Concept.
+* `BidirectionalRange` is mutable.
+* `BidirectionalRange`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `BidirectionalRange`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `BidirectionalRange` is a model of the __bidirectional_range__ Concept.
+* `BidirectionalRange` is mutable.
+* `Compare` is a model of the `StrictWeakOrderingConcept`.
+* `BidirectionalRange`'s value type is convertible to both of `Compare`'s argument types.
+
+[heading Complexity]
+
+Linear. At most `distance(rng) / 2` swaps.
+
+[endsect]
+
+

doc/reference/algorithm/nth_element.qbk

@@ -0,0 +1,67 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:nth_element nth_element]
+
+[heading Prototype]
+
+``
+template<class RandomAccessRange>
+RandomAccessRange& nth_element(
+    RandomAccessRange& rng,
+    typename range_iterator<RandomAccessRange>::type nth);
+
+template<class RandomAccessRange>
+const RandomAccessRange& nth_element(
+    const RandomAccessRange& rng,
+    typename range_iterator<const RandomAccessRange>::type nth);
+
+template<class RandomAccessRange>
+RandomAccessRange& nth_element(
+    RandomAccessRange& rng,
+    typename range_iterator<RandomAccessRange>::type nth,
+    BinaryPredicate sort_pred);
+
+template<class RandomAccessRange>
+const RandomAccessRange& nth_element(
+    const RandomAccessRange& rng,
+    typename range_iterator<const RandomAccessRange>::type nth,
+    BinaryPredicate sort_pred);
+``
+
+[heading Description]
+
+`nth_element` partially orders a range of elements. `nth_element` arranges the range `rng` such that the element corresponding with the iterator `nth` is the same as the element that would be in that position if `rng` has been sorted.
+
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/nth_element.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate version:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `RandomAccessRange`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering relation on `RandomAccessRange`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+
+[*For the predicate version:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `RandomAccessRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
+
+
+[heading Complexity]
+
+On average, linear in `distance(rng)`.
+
+[endsect]
+
+

doc/reference/algorithm/partial_sort.qbk

@@ -0,0 +1,69 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:partial_sort partial_sort]
+
+[heading Prototype]
+
+``
+template<class RandomAccessRange>
+RandomAccessRange& partial_sort(
+    RandomAccessRange& rng,
+    typename range_iterator<RandomAccessRange>::type middle);
+
+template<class RandomAccessRange>
+const RandomAccessRange& partial_sort(
+    const RandomAccessRange& rng,
+    typename range_iterator<const RandomAccessRange>::type middle);
+
+template<class RandomAccessRange>
+RandomAccessRange& partial_sort(
+    RandomAccessRange& rng,
+    typename range_iterator<RandomAccessRange>::type middle,
+    BinaryPredicate sort_pred);
+
+template<class RandomAccessRange>
+const RandomAccessRange& partial_sort(
+    const RandomAccessRange& rng,
+    typename range_iterator<const RandomAccessRange>::type middle,
+    BinaryPredicate sort_pred);
+``
+
+[heading Description]
+
+`partial_sort` rearranges the elements in `rng`. It places the smallest `distance(begin(rng), middle)` elements, sorted in ascending order, into the range `[begin(rng), middle)`. The remaining elements are placed in an unspecified order into `[middle, last)`.
+
+The non-predicative versions of this function specify that one element is less than another by using `operator<()`. The predicate versions use the predicate instead.
+
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/partial_sort.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate version:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `RandomAccessRange`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering relation on `RandomAccessRange`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+
+[*For the predicate version:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `RandomAccessRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
+
+
+[heading Complexity]
+
+Approximately `distance(rng) * log(distance(begin(rng), middle))` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/partition.qbk

@@ -0,0 +1,63 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:partition partition]
+
+[heading Prototype]
+
+``
+template<
+    class ForwardRange,
+    class UnaryPredicate
+    >
+typename range_iterator<ForwardRange>::type
+partition(ForwardRange& rng, UnaryPredicate pred);
+
+template<
+    class ForwardRange,
+    class UnaryPredicate
+    >
+typename range_iterator<const ForwardRange>::type
+partition(const ForwardRange& rng, UnaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class UnaryPredicate
+    >
+typename range_return<ForwardRange, re>::type
+partition(ForwardRange& rng, UnaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class UnaryPredicate
+    >
+typename range_return<const ForwardRange, re>::type
+partition(const ForwardRange& rng, UnaryPredicate pred);
+``
+
+[heading Description]
+
+`partition` orders the elements in `rng` based on `pred`, such that the elements that satisfy `pred` precede the elements that do not. In the versions that return a single iterator, the return value is the middle iterator. In the versions that have a configurable range_return, `found` corresponds to the middle iterator.
+
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/partition.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept. For C++ versions prior to C++11 the underlying std::partition requires Bidirectional Iterators, hence the requirement for older library versions is for a __bidirectional_range__.
+* `UnaryPredicate` is a model of the `PredicateConcept`.
+* `ForwardRange`'s value type is convertible to `UnaryPredicate`'s argument type.
+
+[heading Complexity]
+
+Linear. Exactly `distance(rng)` applications of `pred`, and at most `distance(rng) / 2` swaps.
+
+[endsect]
+
+

doc/reference/algorithm/pop_heap.qbk

@@ -0,0 +1,61 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:pop_heap pop_heap]
+
+[heading Prototype]
+
+``
+template<class RandomAccessRange>
+RandomAccessRange& pop_heap(RandomAccessRange& rng);
+
+template<class RandomAccessRange>
+const RandomAccessRange& pop_heap(const RandomAccessRange& rng);
+
+template<class RandomAccessRange, class Compare>
+RandomAccessRange& pop_heap(RandomAccessRange& rng, Compare pred);
+
+template<class RandomAccessRange, class Compare>
+const RandomAccessRange& pop_heap(const RandomAccessRange& rng, Compare pred);
+``
+
+[heading Description]
+
+`pop_heap` removes the largest element from the heap. It is assumed that `begin(rng), prior(end(rng))` is already a heap (and therefore the largest element is `*begin(rng)`).
+
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/heap_algorithm.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `RandomAccessRange`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `RandomAccessRange`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `Compare` is a model of the `StrictWeakOrderingConcept`.
+* `RandomAccessRange`'s value type is convertible to both of `Compare`'s argument types.
+
+[heading Precondition:]
+
+* `!empty(rng)`
+* `rng` is a heap.
+
+[heading Complexity]
+
+Logarithmic. At most `2 * log(distance(rng))` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/prev_permutation.qbk

@@ -0,0 +1,56 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:prev_permutation prev_permutation]
+
+[heading Prototype]
+
+``
+template<class BidirectionalRange>
+bool prev_permutation(BidirectionalRange& rng);
+
+template<class BidirectionalRange>
+bool prev_permutation(const BidirectionalRange& rng);
+
+template<class BidirectionalRange, class Compare>
+bool prev_permutation(BidirectionalRange& rng, Compare pred);
+
+template<class BidirectionalRange, class Compare>
+bool prev_permutation(const BidirectionalRange& rng, Compare pred);
+``
+
+[heading Description]
+
+`prev_permutation` transforms the range of elements `rng` into the lexicographically next smaller permutation of the elements if such a permutation exists. If one does not exist then the range is transformed into the lexicographically largest permutation and `false` is returned. `true` is returned when the next smaller permutation is successfully generated.
+
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/permutation.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `BidirectionalRange` is a model of the __bidirectional_range__ Concept.
+* `BidirectionalRange` is mutable.
+* `BidirectionalRange`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `BidirectionalRange`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `BidirectionalRange` is a model of the __bidirectional_range__ Concept.
+* `BidirectionalRange` is mutable.
+* `Compare` is a model of the `StrictWeakOrderingConcept`.
+* `BidirectionalRange`'s value type is convertible to both of `Compare`'s argument types.
+
+[heading Complexity]
+
+Linear. At most `distance(rng) / 2` swaps.
+
+[endsect]
+
+

doc/reference/algorithm/push_heap.qbk

@@ -0,0 +1,61 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:push_heap push_heap]
+
+[heading Prototype]
+
+``
+template<class RandomAccessRange>
+RandomAccessRange& push_heap(RandomAccessRange& rng);
+
+template<class RandomAccessRange>
+const RandomAccessRange& push_heap(const RandomAccessRange& rng);
+
+template<class RandomAccessRange, class Compare>
+RandomAccessRange& push_heap(RandomAccessRange& rng, Compare pred);
+
+template<class RandomAccessRange, class Compare>
+const RandomAccessRange& push_heap(const RandomAccessRange& rng, Compare pred);
+``
+
+[heading Description]
+
+`push_heap` adds an element to a heap. It is assumed that `begin(rng)`, `prior(end(rng))` is already a heap and that the element to be added is `*prior(end(rng))`.
+
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/heap_algorithm.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `RandomAccessRange`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `RandomAccessRange`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `Compare` is a model of the `StrictWeakOrderingConcept`.
+* `RandomAccessRange`'s value type is convertible to both of `Compare`'s argument types.
+
+[heading Precondition:]
+
+* `!empty(rng)`
+* `[begin(rng), prior(end(rng)))` is a heap.
+
+[heading Complexity]
+
+Logarithmic. At most `log(distance(rng))` comparisons.
+
+[endsect]
+
+

doc/reference/algorithm/random_shuffle.qbk

@@ -0,0 +1,55 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:random_shuffle random_shuffle]
+
+[heading Prototype]
+
+``
+template<class RandomAccessRange>
+RandomAccessRange& random_shuffle(RandomAccessRange& rng);
+
+template<class RandomAccessRange>
+const RandomAccessRange& random_shuffle(const RandomAccessRange& rng);
+
+template<class RandomAccessRange, class Generator>
+RandomAccessRange& random_shuffle(RandomAccessRange& rng, Generator& gen);
+
+template<class RandomAccessRange, class Generator>
+const RandomAccessRange& random_shuffle(const RandomAccessRange& rng, Generator& gen);
+``
+
+[heading Description]
+
+`random_shuffle` randomly rearranges the elements in `rng`. The versions of `random_shuffle` that do not specify a `Generator` use an internal random number generator. The versions of `random_shuffle` that do specify a `Generator` use this instead. Returns the shuffles range.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/random_shuffle.hpp`
+
+[heading Requirements]
+
+[*For the version without a Generator:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+
+[*For the version with a Generator:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `Generator` is a model of the `RandomNumberGeneratorConcept`.
+* `RandomAccessRange`'s distance type is convertible to `Generator`'s argument type.
+
+[heading Precondition:]
+
+* `distance(rng)` is less than `gen`'s maximum value.
+
+
+[heading Complexity]
+
+Linear. If `!empty(rng)`, exactly `distance(rng) - 1` swaps are performed.
+
+[endsect]
+
+

doc/reference/algorithm/remove.qbk

@@ -0,0 +1,60 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:remove remove]
+[heading Prototype]
+
+``
+template<
+    class ForwardRange,
+    class Value
+    >
+typename range_iterator<ForwardRange>::type
+remove(ForwardRange& rng, const Value& val);
+
+template<
+    class ForwardRange,
+    class Value
+    >
+typename range_iterator<const ForwardRange>::type
+remove(const ForwardRange& rng, const Value& val);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class Value
+    >
+typename range_return<ForwardRange,re>::type
+remove(ForwardRange& rng, const Value& val);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class Value
+    >
+typename range_return<const ForwardRange,re>::type
+remove(const ForwardRange& rng, const Value& val);
+``
+
+[heading Description]
+
+`remove` removes from `rng` all of the elements `x` for which `x == val` is `true`. The versions of `remove` that return an iterator, return an iterator `new_last` such that the range `[begin(rng), new_last)` contains no elements equal to `val`. The `range_return` versions of `remove` defines `found` as the new last element. The iterators in the range `[new_last, end(rng))` are dereferenceable, but the elements are unspecified.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/remove.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `Value` is a model of the `EqualityComparableConcept`.
+* Objects of type `Value` can be compared for equality with objects of `ForwardRange`'s value type.
+
+[heading Complexity]
+
+Linear. `remove` performs exactly `distance(rng)` comparisons for equality.
+
+[endsect]

doc/reference/algorithm/remove_copy.qbk

@@ -0,0 +1,39 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:remove_copy remove_copy]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class Outputiterator, class Value>
+OutputIterator
+remove_copy(ForwardRange& rng, OutputIterator out, const Value& val);
+
+template<class ForwardRange, class OutputIterator, class Value>
+OutputIterator
+remove_copy(const ForwardRange& rng, OutputIterator out, const Value& val);
+``
+
+[heading Description]
+
+`remove_copy` copied all of the elements `x` from `rng` for which `x == val` is `false`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/remove_copy.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `Value` is a model of the `EqualityComparableConcept`.
+* Objects of type `Value` can be compared for equality with objects of `ForwardRange`'s value type.
+
+[heading Complexity]
+
+Linear. `remove_copy` performs exactly `distance(rng)` comparisons for equality.
+
+[endsect]

doc/reference/algorithm/remove_copy_if.qbk

@@ -0,0 +1,38 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:remove_copy_if remove_copy_if]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class Outputiterator, class UnaryPred>
+OutputIterator
+remove_copy_if(ForwardRange& rng, OutputIterator out, UnaryPred pred);
+
+template<class ForwardRange, class OutputIterator, class UnaryPred>
+OutputIterator
+remove_copy_if(const ForwardRange& rng, OutputIterator out, UnaryPred pred);
+``
+
+[heading Description]
+
+`remove_copy_if` copied all of the elements `x` from `rng` for which `pred(x)` is `false`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/remove_copy_if.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `UnaryPred` is a model of the `UnaryPredicateConcept`.
+
+[heading Complexity]
+
+Linear. `remove_copy_if` performs exactly `distance(rng)` comparisons with UnaryPred.
+
+[endsect]

doc/reference/algorithm/remove_if.qbk

@@ -0,0 +1,63 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:remove_if remove_if]
+
+[heading Prototype]
+
+``
+template<
+    class ForwardRange,
+    class UnaryPredicate
+    >
+typename range_iterator<ForwardRange>::type
+remove_if(ForwardRange& rng, UnaryPredicate pred);
+
+template<
+    class ForwardRange,
+    class UnaryPredicate
+    >
+typename range_iterator<const ForwardRange>::type
+remove_if(const ForwardRange& rng, UnaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class UnaryPredicate
+    >
+typename range_return<ForwardRange,re>::type
+remove_if(ForwardRange& rng, UnaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class UnaryPredicate
+    >
+typename range_return<const ForwardRange,re>::type
+remove_if(const ForwardRange& rng, UnaryPredicate pred);
+``
+
+[heading Description]
+
+`remove_if` removes from `rng` all of the elements `x` for which `pred(x)` is `true`. The versions of `remove_if` that return an iterator, return an iterator `new_last` such that the range `[begin(rng), new_last)` contains no elements where `pred(x)` is `true`. The iterators in the range `[new_last, end(rng))` are dereferenceable, but the elements are unspecified.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/remove_if.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `UnaryPredicate` is a model of the `PredicateConcept`.
+* `ForwardRange`'s value type is convertible to `UnaryPredicate`'s argument type.
+
+[heading Complexity]
+
+Linear. `remove_if` performs exactly `distance(rng)` applications of `pred`.
+
+[endsect]
+
+

doc/reference/algorithm/replace.qbk

@@ -0,0 +1,46 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:replace replace]
+
+[heading Prototype]
+
+``
+template<
+    class ForwardRange,
+    class Value
+    >
+ForwardRange& replace(ForwardRange& rng, const Value& what, const Value& with_what);
+
+template<
+    class ForwardRange,
+    class UnaryPredicate
+    >
+const ForwardRange& replace(const ForwardRange& rng, const Value& what, const Value& with_what);
+``
+
+[heading Description]
+
+`replace` every element in `rng` equal to `what` with `with_what`. Return a reference to `rng`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/replace.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `Value` is convertible to `ForwardRange`'s value type.
+* `Value` is a model of the `AssignableConcept`.
+* `Value` is a model of the `EqualityComparableConcept`, and may be compared for equality with objects of `ForwardRange`'s value type.
+
+[heading Complexity]
+
+Linear. `replace` performs exactly `distance(rng)` comparisons for equality and at most `distance(rng)` assignments.
+
+[endsect]
+
+

doc/reference/algorithm/replace_copy.qbk

@@ -0,0 +1,38 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:replace_copy replace_copy]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class OutputIterator, class Value>
+OutputIterator replace_copy(const ForwardRange& rng, OutputIterator out,
+                            const Value& what, const Value& with_what);
+``
+
+[heading Description]
+
+`replace_copy` copy every element `x` in `rng` such that the corresponding element in the output range `y` is `x == what ? with_what : x`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/replace_copy.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `Value` is convertible to `ForwardRange`'s value type.
+* `Value` is a model of the `AssignableConcept`.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+
+[heading Complexity]
+
+Linear. `replace_copy` performs exactly `distance(rng)`.
+
+[endsect]
+
+

doc/reference/algorithm/replace_copy_if.qbk

@@ -0,0 +1,39 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:replace_copy_if replace_copy_if]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class OutputIterator, class UnaryPredicate, class Value>
+OutputIterator replace_copy_if(const ForwardRange& rng, OutputIterator out,
+                               UnaryPredicate pred, const Value& with_what);
+``
+
+[heading Description]
+
+`replace_copy_if` copy every element `x` in `rng` such that the corresponding element in the output range `y` is `pred(x) ? with_what : x`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/replace_copy_if.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `Value` is convertible to `ForwardRange`'s value type.
+* `Value` is a model of the `AssignableConcept`.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `UnaryPredicate` is a model of the `UnaryPredicateConcept`.
+
+[heading Complexity]
+
+Linear. `replace_copy_if` performs exactly `distance(rng)` evaluations of `pred`.
+
+[endsect]
+
+

doc/reference/algorithm/replace_if.qbk

@@ -0,0 +1,41 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:replace_if replace_if]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class UnaryPredicate, class Value>
+ForwardRange& replace_if(ForwardRange& rng, UnaryPredicate pred, const Value& with_what);
+
+template<class ForwardRange, class UnaryPredicate, class Value>
+const ForwardRange& replace_if(const ForwardRange& rng, UnaryPredicate pred, const Value& with_what);
+``
+
+[heading Description]
+
+`replace_if` replaces every element `x` in `rng` for which `pred(x) == true` with `with_what`. Returns a reference to `rng`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/replace_if.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `UnaryPredicate` is a model of the `PredicateConcept`
+* `ForwardRange`'s value type is convertible to `UnaryPredicate`'s argument type.
+* `Value` is convertible to `ForwardRange`'s value type.
+* `Value` is a model of the `AssignableConcept`.
+
+[heading Complexity]
+
+Linear. `replace_if` performs exactly `distance(rng)` applications of `pred`, and at most `distance(rng)` assignments.
+
+[endsect]
+
+

doc/reference/algorithm/reverse.qbk

@@ -0,0 +1,37 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:reverse reverse]
+
+[heading Prototype]
+
+``
+template<class BidirectionalRange>
+BidirectionalRange& reverse(BidirectionalRange& rng);
+
+template<class BidirectionalRange>
+const BidirectionalRange& reverse(const BidirectionalRange& rng);
+``
+
+[heading Description]
+
+`reverse` reverses a range. Returns a reference to the reversed range.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/reverse.hpp`
+
+[heading Requirements]
+
+* `BidirectionalRange` is a model of the __bidirectional_range__ Concept.
+* `BidirectionalRange` is mutable.
+
+[heading Complexity]
+
+Linear. `reverse` makes `distance(rng)/2` calls to `iter_swap`.
+
+[endsect]
+
+

doc/reference/algorithm/reverse_copy.qbk

@@ -0,0 +1,36 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:reverse_copy reverse_copy]
+
+[heading Prototype]
+
+``
+template<class BidirectionalRange, class OutputIterator>
+OutputIterator reverse_copy(const BidirectionalRange& rng, OutputIterator out);
+``
+
+[heading Description]
+
+`reverse_copy` copies the elements from `rng` in reverse order to `out`.
+Returns the output iterator one passed the last copied element.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/reverse_copy.hpp`
+
+[heading Requirements]
+
+* `BidirectionalRange` is a model of the __bidirectional_range__ Concept.
+* `BidirectionalRange` is mutable.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+
+[heading Complexity]
+
+Linear. `reverse_copy` makes `distance(rng)` copies.
+
+[endsect]
+
+

doc/reference/algorithm/rotate.qbk

@@ -0,0 +1,44 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:rotate rotate]
+
+[heading Prototype]
+
+``
+template<class ForwardRange>
+ForwardRange& rotate(ForwardRange& rng,
+                     typename range_iterator<ForwardRange>::type middle);
+
+template<class ForwardRange>
+const ForwardRange& rotate(const ForwardRange& rng,
+                           typename range_iterator<const ForwardRange>::type middle);
+``
+
+[heading Description]
+
+`rotate` rotates the elements in a range. It exchanges the two ranges `[begin(rng), middle)` and `[middle, end(rng))`. Returns a reference to `rng`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/rotate.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+
+[heading Precondition:]
+
+* `[begin(rng), middle)` is a valid range.
+* `[middle, end(rng))` is a valid range.
+
+[heading Complexity]
+
+Linear. At most `distance(rng)` swaps are performed.
+
+[endsect]
+
+

doc/reference/algorithm/rotate_copy.qbk

@@ -0,0 +1,43 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:rotate_copy rotate_copy]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class OutputIterator>
+OutputIterator rotate_copy(
+    const ForwardRange& rng,
+    typename range_iterator<ForwardRange>::type middle,
+    OutputIterator out);
+``
+
+[heading Description]
+
+`rotate_copy` rotates the elements in a range. It copies the two ranges `[begin(rng), middle)` and `[middle, end(rng))` to `out`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/rotate_copy.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+
+[heading Precondition:]
+
+* `[begin(rng), middle)` is a valid range.
+* `[middle, end(rng))` is a valid range.
+
+[heading Complexity]
+
+Linear. Exactly `distance(rng)` elements are copied.
+
+[endsect]
+
+

doc/reference/algorithm/search.qbk

@@ -0,0 +1,106 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:search search]
+
+[heading Prototype]
+
+``
+template<class ForwardRange1, class ForwardRange2>
+typename range_iterator<ForwardRange1>::type
+search(ForwardRange1& rng1, const ForwardRange2& rng2);
+
+template<class ForwardRange1, class ForwardRange2>
+typename range_iterator<const ForwardRange1>::type
+search(const ForwardRange1& rng1, const ForwardRange2& rng2);
+
+template<
+    class ForwardRange1,
+    class ForwardRange2,
+    class BinaryPredicate
+    >
+typename range_iterator<ForwardRange1>::type,
+search(ForwardRange1& rng1, const ForwardRange2& rng2, BinaryPredicate pred);
+
+template<
+    class ForwardRange1,
+    class ForwardRange2,
+    class BinaryPredicate
+    >
+typename range_iterator<const ForwardRange1>::type
+search(const ForwardRange1& rng1, ForwardRange2& rng2, BinaryPredicate pred);
+
+
+template<
+    range_return_value re,
+    class ForwardRange1,
+    class ForwardRange2
+    >
+typename range_return<ForwardRange1, re>::type
+search(ForwardRange1& rng1, const ForwardRange2& rng2);
+
+template<
+    range_return_value re,
+    class ForwardRange1,
+    class ForwardRange2
+    >
+typename range_return<const ForwardRange1, re>::type
+search(const ForwardRange1& rng1, const ForwardRange2& rng2);
+
+template<
+    range_return_value re,
+    class ForwardRange1,
+    class ForwardRange2,
+    class BinaryPredicate
+    >
+typename range_return<ForwardRange1, re>::type,
+search(ForwardRange1& rng1, const ForwardRange2& rng2, BinaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange1,
+    class ForwardRange2,
+    class BinaryPredicate
+    >
+typename range_return<const ForwardRange1, re>::type
+search(const ForwardRange1& rng1, const ForwardRange2& rng2, BinaryPredicate pred);
+``
+
+[heading Description]
+
+The versions of `search` that return an iterator, return an iterator to the start of the first subsequence in `rng1` that is equal to the subsequence `rng2`. The `end(rng1)` is returned if no such subsequence exists in `rng1`.
+Equality is determined by `operator==` for non-predicate versions of `search`, and by satisfying `pred` in the predicate versions.
+
+The versions of `search` that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
+ 
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/search.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `ForwardRange1` is a model of the __forward_range__ Concept.
+* `ForwardRange2` is a model of the __forward_range__ Concept.
+* `ForwardRange1`'s value type is a model of the `EqualityComparableConcept`.
+* `ForwardRange2`'s value type is a model of the `EqualityComparableConcept`.
+* `ForwardRange1`s value type can be compared for equality with `ForwardRange2`'s value type.
+
+[*For the predicate versions:]
+
+* `ForwardRange1` is a model of the __forward_range__ Concept.
+* `ForwardRange2` is a model of the __forward_range__ Concept.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `ForwardRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `ForwardRange2`'s value type is convertible to `BinaryPredicate`'s second argument type.
+
+[heading Complexity]
+
+Average complexity is Linear. Worst-case complexity is quadratic.
+
+[endsect]
+
+

doc/reference/algorithm/search_n.qbk

@@ -0,0 +1,63 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:search_n search_n]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class Integer, class Value>
+typename range_iterator<ForwardRange>::type
+search_n(ForwardRange& rng, Integer n, const Value& value);
+
+template<class ForwardRange, class Integer, class Value>
+typename range_iterator<const ForwardRange>::type
+search_n(const ForwardRange& rng, Integer n, const Value& value);
+
+template<class ForwardRange, class Integer, class Value, class BinaryPredicate>
+typename range_iterator<ForwardRange>::type
+search_n(ForwardRange& rng, Integer n, const Value& value,
+         BinaryPredicate binary_pred);
+
+template<class ForwardRange, class Integer, class Value, class BinaryPredicate>
+typename range_iterator<const ForwardRange>::type
+search_n(const ForwardRange& rng, Integer n, const Value& value,
+         BinaryPredicate binary_pred);
+``
+
+[heading Description]
+
+`search_n` searches `rng` for a sequence of length `n` equal to `value` where
+equality is determined by operator== in the non-predicate case, and by a
+predicate when one is supplied.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/search_n.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange`'s value type is a model of the `EqualityComparableConcept`.
+* `ForwardRange`s value type can be compared for equality with `Value`.
+* `Integer` is a model of the `IntegerConcept`.
+
+[*For the predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `ForwardRange`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `Value` is convertible to `BinaryPredicate`'s second argument type.
+* `Integer` is a model of the `IntegerConcept`.
+
+[heading Complexity]
+
+Average complexity is Linear. Worst-case complexity is quadratic.
+
+[endsect]
+
+

doc/reference/algorithm/set_difference.qbk

@@ -0,0 +1,81 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:set_difference set_difference]
+
+[heading Prototype]
+
+``
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator
+    >
+OutputIterator set_difference(const SinglePassRange1& rng1,
+                              const SinglePassRange2& rng2,
+                              OutputIterator          out);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator,
+    class BinaryPredicate
+    >
+OutputIterator set_difference(const SinglePassRange1& rng1,
+                              const SinglePassRange2& rng2,
+                              OutputIterator          out,
+                              BinaryPredicate         pred);
+``
+
+[heading Description]
+
+`set_difference` constructs a sorted range that is the set difference of the sorted ranges `rng1` and `rng2`. The return value is the end of the output range.
+
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions.
+ 
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/set_algorithm.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `SinglePassRange1` and `SinglePassRange2` have the same value type.
+* `SinglePassRange1`'s value type is a model of the `LessThanComparableConcept`.
+* `SinglePassRange2`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `SinglePassRange1`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+* The ordering of objects of type `SinglePassRange2`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `SinglePassRange1` and `SinglePassRange2` have the same value type.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `SinglePassRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `SinglePassRange2`'s value type is convertible to `BinaryPredicate`'s second argument types.
+
+[heading Precondition:]
+
+[*For the non-predicate versions:]
+
+`rng1` and `rng2` are sorted in ascending order according to `operator<`.
+
+[*For the predicate versions:]
+
+`rng1` and `rng2` are sorted in ascending order according to `pred`.
+
+[heading Complexity]
+
+Linear. `O(N)`, where `N` is `distance(rng1) + distance(rng2)`.
+
+[endsect]
+
+

doc/reference/algorithm/set_intersection.qbk

@@ -0,0 +1,81 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:set_intersection set_intersection]
+
+[heading Prototype]
+
+``
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator
+    >
+OutputIterator set_intersection(const SinglePassRange1& rng1,
+                                const SinglePassRange2& rng2,
+                                OutputIterator          out);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator,
+    class BinaryPredicate
+    >
+OutputIterator set_intersection(const SinglePassRange1& rng1,
+                                const SinglePassRange2& rng2,
+                                OutputIterator          out,
+                                BinaryPredicate         pred);    
+``
+
+[heading Description]
+
+`set_intersection` constructs a sorted range that is the intersection of the sorted ranges `rng1` and `rng2`. The return value is the end of the output range.
+
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions.
+ 
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/set_algorithm.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `SinglePassRange1` and `SinglePassRange2` have the same value type.
+* `SinglePassRange1`'s value type is a model of the `LessThanComparableConcept`.
+* `SinglePassRange2`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `SinglePassRange1`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+* The ordering of objects of type `SinglePassRange2`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `SinglePassRange1` and `SinglePassRange2` have the same value type.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `SinglePassRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `SinglePassRange2`'s value type is convertible to `BinaryPredicate`'s second argument types.
+
+[heading Precondition:]
+
+[*For the non-predicate versions:]
+
+`rng1` and `rng2` are sorted in ascending order according to `operator<`.
+
+[*For the predicate versions:]
+
+`rng1` and `rng2` are sorted in ascending order according to `pred`.
+
+[heading Complexity]
+
+Linear. `O(N)`, where `N` is `distance(rng1) + distance(rng2)`.
+
+[endsect]
+
+

doc/reference/algorithm/set_symmetric_difference.qbk

@@ -0,0 +1,83 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:set_symmetric_difference set_symmetric_difference]
+
+[heading Prototype]
+
+``
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator
+    >
+OutputIterator
+set_symmetric_difference(const SinglePassRange1& rng1,
+                         const SinglePassRange2& rng2,
+                         OutputIterator          out);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator,
+    class BinaryPredicate
+    >
+OutputIterator
+set_symmetric_difference(const SinglePassRange1& rng1,
+                         const SinglePassRange2& rng2,
+                         OutputIterator          out,
+                         BinaryPredicate         pred);    
+``
+
+[heading Description]
+
+`set_symmetric_difference` constructs a sorted range that is the set symmetric difference of the sorted ranges `rng1` and `rng2`. The return value is the end of the output range.
+
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions. 
+ 
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/set_algorithm.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `SinglePassRange1` and `SinglePassRange2` have the same value type.
+* `SinglePassRange1`'s value type is a model of the `LessThanComparableConcept`.
+* `SinglePassRange2`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `SinglePassRange1`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+* The ordering of objects of type `SinglePassRange2`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `SinglePassRange1` and `SinglePassRange2` have the same value type.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `SinglePassRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `SinglePassRange2`'s value type is convertible to `BinaryPredicate`'s second argument types.
+
+[heading Precondition:]
+
+[*For the non-predicate versions:]
+
+`rng1` and `rng2` are sorted in ascending order according to `operator<`.
+
+[*For the predicate versions:]
+
+`rng1` and `rng2` are sorted in ascending order according to `pred`.
+
+[heading Complexity]
+
+Linear. `O(N)`, where `N` is `distance(rng1) + distance(rng2)`.
+
+[endsect]
+
+

doc/reference/algorithm/set_union.qbk

@@ -0,0 +1,80 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:set_union set_union]
+
+[heading Prototype]
+
+``
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator
+    >
+OutputIterator set_union(const SinglePassRange1& rng1,
+                         const SinglePassRange2& rng2,
+                         OutputIterator          out);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator,
+    class BinaryPredicate
+    >
+OutputIterator set_union(const SinglePassRange1& rng1,
+                         const SinglePassRange2& rng2,
+                         OutputIterator          out,
+                         BinaryPredicate         pred);    
+ ``
+
+[heading Description]
+
+`set_union` constructs a sorted range that is the union of the sorted ranges `rng1` and `rng2`. The return value is the end of the output range.
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions. 
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/set_algorithm.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `SinglePassRange1` and `SinglePassRange2` have the same value type.
+* `SinglePassRange1`'s value type is a model of the `LessThanComparableConcept`.
+* `SinglePassRange2`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `SinglePassRange1`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+* The ordering of objects of type `SinglePassRange2`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `SinglePassRange1` and `SinglePassRange2` have the same value type.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `SinglePassRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
+* `SinglePassRange2`'s value type is convertible to `BinaryPredicate`'s second argument types.
+
+[heading Precondition:]
+
+[*For the non-predicate versions:]
+
+`rng1` and `rng2` are sorted in ascending order according to `operator<`.
+
+[*For the predicate versions:]
+
+`rng1` and `rng2` are sorted in ascending order according to `pred`.
+
+[heading Complexity]
+
+Linear. `O(N)`, where `N` is `distance(rng1) + distance(rng2)`.
+
+[endsect]
+
+

doc/reference/algorithm/sort.qbk

@@ -0,0 +1,58 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:sort sort]
+
+[heading Prototype]
+
+``
+template<class RandomAccessRange>
+RandomAccessRange& sort(RandomAccessRange& rng);
+
+template<class RandomAccessRange>
+const RandomAccessRange& sort(const RandomAccessRange& rng);
+
+template<class RandomAccessRange, class BinaryPredicate>
+RandomAccessRange& sort(RandomAccessRange& rng, BinaryPredicate pred);
+
+template<class RandomAccessRange, class BinaryPredicate>
+const RandomAccessRange& sort(const RandomAccessRange& rng, BinaryPredicate pred);
+``
+
+[heading Description]
+
+`sort` sorts the elements in `rng` into ascending order. `sort` is not guaranteed to be stable. Returns the sorted range.
+
+For versions of the `sort` function without a predicate, ascending order is defined by `operator<()` such that for all adjacent elements `[x,y]`, `y < x == false`.
+
+For versions of the `sort` function with a predicate, ascending order is defined by `pred` such that for all adjacent elements `[x,y]`, `pred(y, x) == false`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/sort.hpp`
+
+[heading Requirements]
+
+[*For versions of sort without a predicate:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `RandomAccessRange`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering relation on `RandomAccessRange`'s value type is a [*strict weak ordering], as defined in the `LessThanComparableConcept` requirements.
+
+[*For versions of sort with a predicate]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `RandomAccessRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
+
+[heading Complexity]
+
+`O(N log(N))` comparisons (both average and worst-case), where `N` is `distance(rng)`.
+
+[endsect]
+
+

doc/reference/algorithm/sort_heap.qbk

@@ -0,0 +1,60 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:sort_heap sort_heap]
+
+[heading Prototype]
+
+``
+template<class RandomAccessRange>
+RandomAccessRange& sort_heap(RandomAccessRange& rng);
+
+template<class RandomAccessRange>
+const RandomAccessRange& sort_heap(const RandomAccessRange& rng);
+
+template<class RandomAccessRange, class Compare>
+RandomAccessRange& sort_heap(RandomAccessRange& rng, Compare pred);
+
+template<class RandomAccessRange, class Compare>
+const RandomAccessRange& sort_heap(const RandomAccessRange& rng, Compare pred);
+``
+
+[heading Description]
+
+`sort_heap` turns a heap into a sorted range.
+
+The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/heap_algorithm.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `RandomAccessRange`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `RandomAccessRange`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+
+[*For the predicate versions:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `Compare` is a model of the `StrictWeakOrderingConcept`.
+* `RandomAccessRange`'s value type is convertible to both of `Compare`'s argument types.
+
+[heading Precondition:]
+
+`rng` is a heap.
+
+[heading Complexity]
+
+At most `N * log(N)` comparisons, where `N` is `distance(rng)`.
+
+[endsect]
+
+

doc/reference/algorithm/stable_partition.qbk

@@ -0,0 +1,61 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:stable_partition stable_partition]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class UnaryPredicate>
+typename range_iterator<ForwardRange>::type
+stable_partition(ForwardRange& rng, UnaryPredicate pred);
+
+template<class ForwardRange, class UnaryPredicate>
+typename range_iterator<const ForwardRange>::type
+stable_partition(const ForwardRange& rng, UnaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class UnaryPredicate
+>
+typename range_return<ForwardRange, re>::type
+stable_partition(ForwardRange& rng, UnaryPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class UnaryPredicate
+>
+typename range_return<const ForwardRange, re>::type
+stable_partition(const ForwardRange& rng, UnaryPredicate pred);
+``
+
+[heading Description]
+
+`stable_partition` reorders the elements in the range `rng` base on the function object `pred`. Once this function has completed all of the elements that satisfy `pred` appear before all of the elements that fail to satisfy it. `stable_partition` differs from `partition` because it preserves relative order. It is stable.
+
+For the versions that return an iterator, the return value is the iterator to the first element that fails to satisfy `pred`.
+
+For versions that return a `range_return`, the `found` iterator is the iterator to the first element that fails to satisfy `pred`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/stable_partition.hpp`
+
+[heading Requirements]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `UnaryPredicate` is a model of the `PredicateConcept`.
+
+[heading Complexity]
+
+Best case: `O(N)` where `N` is `distance(rng)`.
+Worst case: `N * log(N)` swaps, where `N` is `distance(rng)`.
+
+[endsect]
+
+

doc/reference/algorithm/stable_sort.qbk

@@ -0,0 +1,59 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:stable_sort stable_sort]
+
+[heading Prototype]
+
+``
+template<class RandomAccessRange>
+RandomAccessRange& stable_sort(RandomAccessRange& rng);
+
+template<class RandomAccessRange>
+const RandomAccessRange& stable_sort(const RandomAccessRange& rng);
+
+template<class RandomAccessRange, class BinaryPredicate>
+RandomAccessRange& stable_sort(RandomAccessRange& rng, BinaryPredicate pred);
+
+template<class RandomAccessRange, class BinaryPredicate>
+const RandomAccessRange& stable_sort(const RandomAccessRange& rng, BinaryPredicate pred);
+``
+
+[heading Description]
+
+`stable_sort` sorts the elements in `rng` into ascending order. `stable_sort` is guaranteed to be stable. The order is preserved for equivalent elements.
+
+For versions of the `stable_sort` function without a predicate ascending order is defined by `operator<()` such that for all adjacent elements `[x,y]`, `y < x == false`.
+
+For versions of the `stable_sort` function with a predicate, ascending order is designed by `pred` such that for all adjacent elements `[x,y]`, `pred(y,x) == false`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/stable_sort.hpp`
+
+[heading Requirements]
+
+[*For versions of stable_sort without a predicate]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `RandomAccessRange`'s value type is a model of the `LessThanComparableConcept`.
+* The ordering relation on `RandomAccessRange`'s value type is a [*strict weak ordering], as defined in the `LessThanComparableConcept` requirements.
+
+[*For versions of stable_sort with a predicate:]
+
+* `RandomAccessRange` is a model of the __random_access_range__ Concept.
+* `RandomAccessRange` is mutable.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `RandomAccessRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
+
+[heading Complexity]
+
+Best case: `O(N)` where `N` is `distance(rng)`.
+Worst case: `O(N log(N)^2)` comparisons, where `N` is `distance(rng)`.
+
+[endsect]
+
+

doc/reference/algorithm/swap_ranges.qbk

@@ -0,0 +1,37 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:swap_ranges swap_ranges]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange1, class SinglePassRange2>
+SinglePassRange2& swap_ranges(SinglePassRange1& rng1, SinglePassRange& rng2);
+``
+
+[heading Description]
+
+`swap_ranges` swaps each element `x` in `rng1` with the corresponding element `y` in `rng2`.
+Returns a reference to `rng2`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/swap_ranges.hpp`
+
+[heading Requirements]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange1` is mutable.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is mutable.
+
+[heading Complexity]
+
+Linear. Exactly `distance(rng1)` elements are swapped.
+
+[endsect]
+
+

doc/reference/algorithm/transform.qbk

@@ -0,0 +1,88 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:transform transform]
+
+[heading Prototype]
+
+``
+template<
+    class SinglePassRange1,
+    class OutputIterator,
+    class UnaryOperation
+>
+OutputIterator transform(const SinglePassRange1& rng,
+                         OutputIterator out,
+                         UnaryOperation fun);
+
+template<
+    class SinglePassRange1,
+    class SinglePassRange2,
+    class OutputIterator,
+    class BinaryOperation
+>
+OutputIterator transform(const SinglePassRange1& rng1,
+                         const SinglePassRange2& rng2,
+                         OutputIterator out,
+                         BinaryOperation fun);
+``
+
+[heading Description]
+
+[*UnaryOperation version:]
+
+`transform` assigns the value `y` to each element `[out, out + distance(rng)), y = fun(x)` where `x` is the corresponding value to `y` in `rng1`. The return value is `out + distance(rng)`.
+
+[*BinaryOperation version:]
+
+`transform` assigns the value `z` to each element `[out, out + min(distance(rng1), distance(rng2))), z = fun(x,y)` where `x` is the corresponding value in `rng1` and `y` is the corresponding value in `rng2`. This version of `transform` stops upon reaching either the end of `rng1`, or the end of `rng2`. Hence there isn't a requirement for `distance(rng1) == distance(rng2)` since there is a safe guaranteed behaviour, unlike with the iterator counterpart in the standard library.
+
+The return value is `out + min(distance(rng1), distance(rng2))`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/transform.hpp`
+
+[heading Requirements]
+
+[*For the unary versions of transform:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `UnaryOperation` is a model of the `UnaryFunctionConcept`.
+* `SinglePassRange1`'s value type must be convertible to `UnaryFunction`'s argument type.
+* `UnaryFunction`'s result type must be convertible to a type in `OutputIterator`'s set of value types.
+
+[*For the binary versions of transform:]
+
+* `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+* `BinaryOperation` is a model of the `BinaryFunctionConcept`.
+* `SinglePassRange1`'s value type must be convertible to `BinaryFunction`'s first argument type.
+* `SinglePassRange2`'s value type must be convertible to `BinaryFunction`'s second argument type.
+* `BinaryOperation`'s result type must be convertible to a type in `OutputIterator`'s set of value types.
+
+[heading Precondition:]
+
+[*For the unary version of transform:]
+
+* `out` is not an iterator within the range `[begin(rng1) + 1, end(rng1))`.
+* `[out, out + distance(rng1))` is a valid range.
+
+[*For the binary version of transform:]
+
+* `out` is not an iterator within the range `[begin(rng1) + 1, end(rng1))`.
+* `out` is not an iterator within the range `[begin(rng2) + 1, end(rng2))`.
+* `[out, out + min(distance(rng1), distance(rng2)))` is a valid range.
+
+
+[heading Complexity]
+
+Linear. The operation is applied exactly `distance(rng1)` for the unary version and `min(distance(rng1), distance(rng2))` for the binary version.
+
+[endsect]
+
+

doc/reference/algorithm/unique.qbk

@@ -0,0 +1,77 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:unique unique]
+
+[heading Prototype]
+
+``
+template<class ForwardRange>
+typename range_return<ForwardRange, return_begin_found>::type
+unique(ForwardRange& rng);
+
+template<class ForwardRange>
+typename range_return<const ForwardRange, return_begin_found>::type
+unique(const ForwardRange& rng);
+
+template<class ForwardRange, class BinaryPredicate>
+typename range_return<ForwardRange, return_begin_found>::type
+unique(ForwardRange& rng, BinaryPredicate pred);
+
+template<class ForwardRange, class BinaryPredicate>
+typename range_return<const ForwardRange, return_begin_found>::type
+unique(const ForwardRange& rng, BinaryPredicate pred);
+
+template<range_return_value re, class ForwardRange>
+typename range_return<ForwardRange, re>::type
+unique(ForwardRange& rng);
+
+template<range_return_value re, class ForwardRange>
+typename range_return<const ForwardRange, re>::type
+unique(const ForwardRange& rng);
+
+template<range_return_value re, class ForwardRange, class BinaryPredicate>
+typename range_return<ForwardRange, re>::type
+unique(ForwardRange& rng, BinaryPredicate pred);
+
+template<range_return_value re, class ForwardRange, class BinaryPredicate>
+typename range_return<const ForwardRange, re>::type
+unique(const ForwardRange& rng, BinaryPredicate pred);
+``
+
+[heading Description]
+
+`unique` removes all but the first element of each sequence of duplicate encountered in `rng`.
+
+Elements in the range `[new_last, end(rng))` are dereferenceable but undefined.
+
+Equality is determined by the predicate if one is supplied, or by `operator==()` for `ForwardRange`'s value type.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/unique.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions of unique:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `ForwardRange`'s value type is a model of the `EqualityComparableConcept`.
+
+[*For the predicate versions of unique:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `ForwardRange` is mutable.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `ForwardRange`'s value type is convertible to `BinaryPredicate`'s first argument type and to `BinaryPredicate`'s second argument type.
+
+[heading Complexity]
+
+Linear. `O(N)` where `N` is `distance(rng)`. Exactly `distance(rng)` comparisons are performed.
+
+[endsect]
+
+

doc/reference/algorithm/unique_copy.qbk

@@ -0,0 +1,49 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:unique_copy unique_copy]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange, class OutputIterator>
+OutputIterator unique_copy(const SinglePassRange& rng, OutputIterator out);
+
+template<class SinglePassRange, class OutputIterator, class BinaryPredicate>
+OutputIterator unique_copy(const SinglePassRange& rng, OutputIterator out, BinaryPredicate pred);
+``
+
+[heading Description]
+
+`unique_copy` copies the first element of each sequence of duplicates encountered in `rng` to `out`.
+
+Equality is determined by the predicate if one is supplied, or by `operator==()` for `SinglePassRange`'s value type.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/unique_copy.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions of unique:]
+
+* `SinglePassRange` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange` is mutable.
+* `SinglePassRange`'s value type is a model of the `EqualityComparableConcept`.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+
+[*For the predicate versions of unique:]
+
+* `SinglePassRange` is a model of the __single_pass_range__ Concept.
+* `SinglePassRange` is mutable.
+* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
+* `SinglePassRange`'s value type is convertible to `BinaryPredicate`'s first argument type and to `BinaryPredicate`'s second argument type.
+* `OutputIterator` is a model of the `OutputIteratorConcept`.
+
+[heading Complexity]
+
+Linear. `O(N)` where `N` is `distance(rng)`. Exactly `distance(rng)` comparisons are performed.
+
+[endsect]

doc/reference/algorithm/upper_bound.qbk

@@ -0,0 +1,90 @@
+[/
+    Copyright 2010 Neil Groves
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:upper_bound upper_bound]
+
+[heading Prototype]
+
+``
+template<
+    class ForwardRange, 
+    class Value
+    >
+typename range_iterator<ForwardRange>::type
+upper_bound(ForwardRange& rng, Value val);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class Value
+    >
+typename range_return<ForwardRange, re>::type
+upper_bound(ForwardRange& rng, Value val);
+
+template<
+    class ForwardRange,
+    class Value,
+    class SortPredicate
+    >
+typename range_iterator<ForwardRange>::type
+upper_bound(ForwardRange& rng, Value val, SortPredicate pred);
+
+template<
+    range_return_value re,
+    class ForwardRange,
+    class Value,
+    class SortPredicate
+    >
+typename range_return<ForwardRange,re>::type
+upper_bound(ForwardRange& rng, Value val, SortPredicate pred);
+``
+
+[heading Description]
+
+The versions of `upper_bound` that return an iterator, returns the first iterator in the range `rng` such that:
+without predicate - `val < *i` is `true`,
+with predicate - `pred(val, *i)` is `true`.
+
+`end(rng)` is returned if no such iterator exists.
+
+The versions of `upper_bound` that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm/upper_bound.hpp`
+
+[heading Requirements]
+
+[*For the non-predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `Value` is a model of the `LessThanComparableConcept`.
+* The ordering of objects of type `Value` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
+* `ForwardRange`'s value type is the same type as `Value`.
+
+[*For the predicate versions:]
+
+* `ForwardRange` is a model of the __forward_range__ Concept.
+* `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
+* `ForwardRange`'s value type is the same type as `Value`.
+* `ForwardRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
+
+[heading Precondition:]
+
+[*For the non-predicate versions:]
+
+`rng` is sorted in ascending order according to `operator<`.
+
+[*For the predicate versions:]
+
+`rng` is sorted in ascending order according to `pred`.
+
+[heading Complexity]
+
+For ranges that model the __random_access_range__ Concept the complexity is `O(log N)`, where `N` is `distance(rng)`. For all other range types the complexity is `O(N)`.
+
+[endsect]
+
+