Squashed 'third_party/boostorg/range/' content from commit 4cfd4d8
Change-Id: I641c49f21039952b16f888223a952503e43a28a9
git-subtree-dir: third_party/boostorg/range
git-subtree-split: 4cfd4d8287ca949d7f29256adf3e796a0d1775ec
diff --git a/doc/reference/algorithm/adjacent_find.qbk b/doc/reference/algorithm/adjacent_find.qbk
new file mode 100644
index 0000000..67d78d4
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/binary_search.qbk b/doc/reference/algorithm/binary_search.qbk
new file mode 100644
index 0000000..42031b3
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/copy.qbk b/doc/reference/algorithm/copy.qbk
new file mode 100644
index 0000000..e40f1b1
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/copy_backward.qbk b/doc/reference/algorithm/copy_backward.qbk
new file mode 100644
index 0000000..8fdac5a
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/count.qbk b/doc/reference/algorithm/count.qbk
new file mode 100644
index 0000000..a84af3c
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/count_if.qbk b/doc/reference/algorithm/count_if.qbk
new file mode 100644
index 0000000..b95cc91
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/equal.qbk b/doc/reference/algorithm/equal.qbk
new file mode 100644
index 0000000..37d1c02
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/equal_range.qbk b/doc/reference/algorithm/equal_range.qbk
new file mode 100644
index 0000000..2d6c342
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/fill.qbk b/doc/reference/algorithm/fill.qbk
new file mode 100644
index 0000000..4df2c0f
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/fill_n.qbk b/doc/reference/algorithm/fill_n.qbk
new file mode 100644
index 0000000..1375d4e
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/find.qbk b/doc/reference/algorithm/find.qbk
new file mode 100644
index 0000000..ba57637
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/find_end.qbk b/doc/reference/algorithm/find_end.qbk
new file mode 100644
index 0000000..dff17cd
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/find_first_of.qbk b/doc/reference/algorithm/find_first_of.qbk
new file mode 100644
index 0000000..d10d986
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/find_if.qbk b/doc/reference/algorithm/find_if.qbk
new file mode 100644
index 0000000..12ff91b
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/for_each.qbk b/doc/reference/algorithm/for_each.qbk
new file mode 100644
index 0000000..3661368
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/generate.qbk b/doc/reference/algorithm/generate.qbk
new file mode 100644
index 0000000..3d19664
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/includes.qbk b/doc/reference/algorithm/includes.qbk
new file mode 100644
index 0000000..5f1ca5f
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/inplace_merge.qbk b/doc/reference/algorithm/inplace_merge.qbk
new file mode 100644
index 0000000..015d9bb
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/lexicographical_compare.qbk b/doc/reference/algorithm/lexicographical_compare.qbk
new file mode 100644
index 0000000..8160b15
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/lower_bound.qbk b/doc/reference/algorithm/lower_bound.qbk
new file mode 100644
index 0000000..2917d26
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/make_heap.qbk b/doc/reference/algorithm/make_heap.qbk
new file mode 100644
index 0000000..df47fac
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/max_element.qbk b/doc/reference/algorithm/max_element.qbk
new file mode 100644
index 0000000..01101a5
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/merge.qbk b/doc/reference/algorithm/merge.qbk
new file mode 100644
index 0000000..e838358
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/min_element.qbk b/doc/reference/algorithm/min_element.qbk
new file mode 100644
index 0000000..3895532
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/mismatch.qbk b/doc/reference/algorithm/mismatch.qbk
new file mode 100644
index 0000000..3599733
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/next_permutation.qbk b/doc/reference/algorithm/next_permutation.qbk
new file mode 100644
index 0000000..4a8dc21
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/nth_element.qbk b/doc/reference/algorithm/nth_element.qbk
new file mode 100644
index 0000000..9bd785e
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/partial_sort.qbk b/doc/reference/algorithm/partial_sort.qbk
new file mode 100644
index 0000000..e2b8876
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/partition.qbk b/doc/reference/algorithm/partition.qbk
new file mode 100644
index 0000000..a97a893
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/pop_heap.qbk b/doc/reference/algorithm/pop_heap.qbk
new file mode 100644
index 0000000..9008de4
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/prev_permutation.qbk b/doc/reference/algorithm/prev_permutation.qbk
new file mode 100644
index 0000000..6d20431
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/push_heap.qbk b/doc/reference/algorithm/push_heap.qbk
new file mode 100644
index 0000000..8aff8c2
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/random_shuffle.qbk b/doc/reference/algorithm/random_shuffle.qbk
new file mode 100644
index 0000000..b092c36
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/remove.qbk b/doc/reference/algorithm/remove.qbk
new file mode 100644
index 0000000..f26b277
--- /dev/null
+++ b/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]
\ No newline at end of file
diff --git a/doc/reference/algorithm/remove_copy.qbk b/doc/reference/algorithm/remove_copy.qbk
new file mode 100644
index 0000000..b98da47
--- /dev/null
+++ b/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]
diff --git a/doc/reference/algorithm/remove_copy_if.qbk b/doc/reference/algorithm/remove_copy_if.qbk
new file mode 100644
index 0000000..d56647b
--- /dev/null
+++ b/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]
diff --git a/doc/reference/algorithm/remove_if.qbk b/doc/reference/algorithm/remove_if.qbk
new file mode 100644
index 0000000..64b6ac3
--- /dev/null
+++ b/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(ForwardRange& rng, UnaryPredicate pred);
+
+template<
+ class ForwardRange,
+ class UnaryPredicate
+ >
+typename range_iterator<const ForwardRange>::type
+remove(const ForwardRange& rng, UnaryPredicate pred);
+
+template<
+ range_return_value re,
+ class ForwardRange,
+ class UnaryPredicate
+ >
+typename range_return<ForwardRange,re>::type
+remove(ForwardRange& rng, UnaryPredicate pred);
+
+template<
+ range_return_value re,
+ class ForwardRange,
+ class UnaryPredicate
+ >
+typename range_return<const ForwardRange,re>::type
+remove(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]
+
+
diff --git a/doc/reference/algorithm/replace.qbk b/doc/reference/algorithm/replace.qbk
new file mode 100644
index 0000000..27b6c1b
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/replace_copy.qbk b/doc/reference/algorithm/replace_copy.qbk
new file mode 100644
index 0000000..e936fc0
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/replace_copy_if.qbk b/doc/reference/algorithm/replace_copy_if.qbk
new file mode 100644
index 0000000..13305a7
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/replace_if.qbk b/doc/reference/algorithm/replace_if.qbk
new file mode 100644
index 0000000..18480a9
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/reverse.qbk b/doc/reference/algorithm/reverse.qbk
new file mode 100644
index 0000000..6ecb31b
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/reverse_copy.qbk b/doc/reference/algorithm/reverse_copy.qbk
new file mode 100644
index 0000000..b19ed9f
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/rotate.qbk b/doc/reference/algorithm/rotate.qbk
new file mode 100644
index 0000000..e28641b
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/rotate_copy.qbk b/doc/reference/algorithm/rotate_copy.qbk
new file mode 100644
index 0000000..0f11bdc
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/search.qbk b/doc/reference/algorithm/search.qbk
new file mode 100644
index 0000000..5c2c2a8
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/search_n.qbk b/doc/reference/algorithm/search_n.qbk
new file mode 100644
index 0000000..ad8cbd2
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/set_difference.qbk b/doc/reference/algorithm/set_difference.qbk
new file mode 100644
index 0000000..8ab5091
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/set_intersection.qbk b/doc/reference/algorithm/set_intersection.qbk
new file mode 100644
index 0000000..3d46109
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/set_symmetric_difference.qbk b/doc/reference/algorithm/set_symmetric_difference.qbk
new file mode 100644
index 0000000..9110cf0
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/set_union.qbk b/doc/reference/algorithm/set_union.qbk
new file mode 100644
index 0000000..679ec71
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/sort.qbk b/doc/reference/algorithm/sort.qbk
new file mode 100644
index 0000000..3027c89
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/sort_heap.qbk b/doc/reference/algorithm/sort_heap.qbk
new file mode 100644
index 0000000..b065ce5
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/stable_partition.qbk b/doc/reference/algorithm/stable_partition.qbk
new file mode 100644
index 0000000..a820bcd
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/stable_sort.qbk b/doc/reference/algorithm/stable_sort.qbk
new file mode 100644
index 0000000..502551f
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/swap_ranges.qbk b/doc/reference/algorithm/swap_ranges.qbk
new file mode 100644
index 0000000..9dcb764
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/transform.qbk b/doc/reference/algorithm/transform.qbk
new file mode 100644
index 0000000..d1e5ac4
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/unique.qbk b/doc/reference/algorithm/unique.qbk
new file mode 100644
index 0000000..bc2cdce
--- /dev/null
+++ b/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]
+
+
diff --git a/doc/reference/algorithm/unique_copy.qbk b/doc/reference/algorithm/unique_copy.qbk
new file mode 100644
index 0000000..f10a85f
--- /dev/null
+++ b/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]
diff --git a/doc/reference/algorithm/upper_bound.qbk b/doc/reference/algorithm/upper_bound.qbk
new file mode 100644
index 0000000..d636a77
--- /dev/null
+++ b/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]
+
+