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_ext/copy_n.qbk b/doc/reference/algorithm_ext/copy_n.qbk
new file mode 100644
index 0000000..6b34c7b
--- /dev/null
+++ b/doc/reference/algorithm_ext/copy_n.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:copy_n copy_n]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange, class Size, class OutputIterator>
+OutputIterator copy_n(const SinglePassRange& rng, Size n, OutputIterator out);
+``
+
+[heading Description]
+
+`copy_n` is provided to completely replicate the standard algorithm header,
+it is preferable to use Range Adaptors and the extension functions to achieve
+the same result with greater safety.
+
+`copy_n` copies elements from `[boost::begin(rng), boost::begin(rng) + n)` to the range `[out, out + n)`
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/copy_n.hpp`
+
+[heading Requirements]
+
+# `SinglePassRange` is a model of the __single_pass_range__ Concept.
+# `Size` is a model of the `Integer` Concept.
+# `OutputIterator` is a model of the `OutputIteratorConcept`.
+
+[heading Complexity]
+
+Linear. Exactly `n` elements are copied.
+
+[endsect]
diff --git a/doc/reference/algorithm_ext/erase.qbk b/doc/reference/algorithm_ext/erase.qbk
new file mode 100644
index 0000000..5b640a2
--- /dev/null
+++ b/doc/reference/algorithm_ext/erase.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:erase erase]
+
+[heading Prototype]
+
+``
+template<class Container>
+Container& erase(
+ Container& target,
+ iterator_range<typename Container::iterator> to_erase);
+``
+
+[heading Description]
+
+`erase` the iterator range `to_erase` from the container `target`.
+
+`remove_erase` performs the frequently used combination equivalent to `target.erase(std::remove(target.begin(), target.end(), value), target.end());`
+
+`remove_erase_if` performs the frequently used combination equivalent to `target.erase(std::remove_if(target.begin(), target.end(), pred), target.end());`
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/erase.hpp`
+
+[heading Requirements]
+
+# `Container` supports erase of an iterator range.
+
+[heading Complexity]
+
+Linear. Proprotional to `distance(to_erase)`.
+
+[endsect]
diff --git a/doc/reference/algorithm_ext/for_each.qbk b/doc/reference/algorithm_ext/for_each.qbk
new file mode 100644
index 0000000..fdfcb99
--- /dev/null
+++ b/doc/reference/algorithm_ext/for_each.qbk
@@ -0,0 +1,73 @@
+[/
+ 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 SinglePassRange1,
+ class SinglePassRange2,
+ class BinaryFunction
+ >
+BinaryFunction for_each(const SinglePassRange1& rng1,
+ const SinglePassRange2& rng2,
+ BinaryFunction fn);
+
+template<
+ class SinglePassRange1,
+ class SinglePassRange2,
+ class BinaryFunction
+ >
+BinaryFunction for_each(const SinglePassRange1& rng1,
+ SinglePassRange2& rng2,
+ BinaryFunction fn);
+
+template<
+ class SinglePassRange1,
+ class SinglePassRange2,
+ class BinaryFunction
+ >
+BinaryFunction for_each(SinglePassRange1& rng1,
+ const SinglePassRange2& rng2,
+ BinaryFunction fn);
+
+template<
+ class SinglePassRange1,
+ class SinglePassRange2,
+ class BinaryFunction
+ >
+BinaryFunction for_each(SinglePassRange1& rng1,
+ SinglePassRange2& rng2,
+ BinaryFunction fn);
+``
+
+[heading Description]
+
+`for_each` traverses forward through `rng1` and `rng2` simultaneously.
+For each iteration, the element `x` is used from `rng1` and the corresponding
+element `y` is used from `rng2` to invoke `fn(x,y)`.
+
+Iteration is stopped upon reaching the end of the shorter of `rng1`, or `rng2`.
+It is safe to call this function with unequal length ranges.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/for_each.hpp`
+
+[heading Requirements]
+
+# `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+# `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+# `BinaryFunction` is a model of the `BinaryFunctionConcept`.
+# `SinglePassRange1`'s value type is convertible to `BinaryFunction`'s first argument type.
+# `SinglepassRange2`'s value type is convertible to `BinaryFunction`'s second argument type.
+
+[heading Complexity]
+
+Linear. Exactly `min(distance(rng1), distance(rng2))` applications of `BinaryFunction`.
+
+[endsect]
diff --git a/doc/reference/algorithm_ext/insert.qbk b/doc/reference/algorithm_ext/insert.qbk
new file mode 100644
index 0000000..e9f48eb
--- /dev/null
+++ b/doc/reference/algorithm_ext/insert.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:insert insert]
+
+[heading Prototype]
+
+``
+template<
+ class Container,
+ class SinglePassRange
+>
+Container& insert(Container& target,
+ typename Container::iterator before,
+ const SinglePassRange& from);
+
+// This overload is for target containers that do not require an insertion
+// position e.g. set/map
+template<
+ class Container,
+ class SinglePassRange
+>
+Container& insert(Container& target, const SinglePassRange& from);
+``
+
+[heading Description]
+
+`insert` all of the elements in the range `from` before the `before` iterator into `target`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/insert.hpp`
+
+[heading Requirements]
+
+# `SinglePassRange` is a model of the __single_pass_range__ Concept.
+# `Container` supports insert at a specified position.
+# `SinglePassRange`'s value type is convertible to `Container`'s value type.
+
+[heading Complexity]
+
+Linear. `distance(from)` assignments are performed.
+
+[endsect]
diff --git a/doc/reference/algorithm_ext/iota.qbk b/doc/reference/algorithm_ext/iota.qbk
new file mode 100644
index 0000000..0a5f799
--- /dev/null
+++ b/doc/reference/algorithm_ext/iota.qbk
@@ -0,0 +1,33 @@
+[/
+ Copyright 2010 Neil Groves
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:iota iota]
+
+[heading Prototype]
+
+``
+template<class ForwardRange, class Value>
+ForwardRange& iota(ForwardRange& rng, Value x);
+``
+
+[heading Description]
+
+`iota` traverses forward through `rng`, each element `y` in `rng` is assigned a value equivalent
+to `x + boost::distance(boost::begin(rng), it)`
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/iota.hpp`
+
+[heading Requirements]
+
+# `ForwardRange` is a model of the __forward_range__ Concept.
+# `Value` is a model of the `Incrementable` Concept.
+
+[heading Complexity]
+
+Linear. Exactly `distance(rng)` assignments into `rng`.
+
+[endsect]
diff --git a/doc/reference/algorithm_ext/is_sorted.qbk b/doc/reference/algorithm_ext/is_sorted.qbk
new file mode 100644
index 0000000..f9c07b4
--- /dev/null
+++ b/doc/reference/algorithm_ext/is_sorted.qbk
@@ -0,0 +1,40 @@
+[/
+ 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:is_sorted is_sorted]
+
+[heading Prototype]
+
+``
+template<class SinglePassRange>
+bool is_sorted(const SinglePassRange& rng);
+
+template<class SinglePassRange, class BinaryPredicate>
+bool is_sorted(const SinglePassRange& rng, BinaryPredicate pred);
+``
+
+[heading Description]
+
+`is_sorted` determines if a range is sorted.
+For the non-predicate version the return value is `true` if and only if for
+each adjacent elements `[x,y]` the expression `x < y` is `true`.
+For the predicate version the return value is `true` is and only if for each
+adjacent elements `[x,y]` the expression `pred(x,y)` is `true`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/is_sorted.hpp`
+
+[heading Requirements]
+
+# `SinglePassRange` is a model of the __single_pass_range__ Concept.
+# `BinaryPredicate` is a model of the `BinaryPredicate` Concept.
+# The value type of `SinglePassRange` is convertible to both argument types of `BinaryPredicate`.
+
+[heading Complexity]
+
+Linear. A maximum of `distance(rng)` comparisons are performed.
+
+[endsect]
diff --git a/doc/reference/algorithm_ext/overwrite.qbk b/doc/reference/algorithm_ext/overwrite.qbk
new file mode 100644
index 0000000..a265833
--- /dev/null
+++ b/doc/reference/algorithm_ext/overwrite.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:overwrite overwrite]
+
+[heading Prototype]
+
+``
+template<
+ class SinglePassRange1,
+ class SinglePassRange2
+ >
+void overwrite(const SinglePassRange1& from,
+ SinglePassRange2& to);
+``
+
+[heading Description]
+
+`overwrite` assigns the values from the range `from` into the range `to`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/overwrite.hpp`
+
+[heading Requirements]
+
+# `SinglePassRange1` is a model of the __single_pass_range__ Concept.
+# `SinglePassRange2` is a model of the __single_pass_range__ Concept.
+# `SinglePassRange2` is mutable.
+# `distance(SinglePassRange1) <= distance(SinglePassRange2)`
+# `SinglePassRange1`'s value type is convertible to `SinglePassRange2`'s value type.
+
+[heading Complexity]
+
+Linear. `distance(rng1)` assignments are performed.
+
+[endsect]
diff --git a/doc/reference/algorithm_ext/push_back.qbk b/doc/reference/algorithm_ext/push_back.qbk
new file mode 100644
index 0000000..ec46d0b
--- /dev/null
+++ b/doc/reference/algorithm_ext/push_back.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:push_back push_back]
+
+[heading Prototype]
+
+``
+template<
+ class Container,
+ class SinglePassRange
+ >
+Container& push_back(Container& target,
+ const SinglePassRange& from);
+``
+
+[heading Description]
+
+`push_back` all of the elements in the range `from` to the back of the container `target`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/push_back.hpp`
+
+[heading Requirements]
+
+# `SinglePassRange` is a model of the __single_pass_range__ Concept.
+# `Container` supports insert at `end()`.
+# `SinglePassRange`'s value type is convertible to `Container`'s value type.
+
+[heading Complexity]
+
+Linear. `distance(from)` assignments are performed.
+
+[endsect]
diff --git a/doc/reference/algorithm_ext/push_front.qbk b/doc/reference/algorithm_ext/push_front.qbk
new file mode 100644
index 0000000..d9ca4fe
--- /dev/null
+++ b/doc/reference/algorithm_ext/push_front.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:push_front push_front]
+
+[heading Prototype]
+
+``
+template<
+ class Container,
+ class SinglePassRange
+ >
+Container& push_front(Container& target,
+ const SinglePassRange& from);
+``
+
+[heading Description]
+
+`push_front` all of the elements in the range `from` to the front of the container `target`.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/push_front.hpp`
+
+[heading Requirements]
+
+# `SinglePassRange` is a model of the __single_pass_range__ Concept.
+# `Container` supports insert at `begin()`.
+# `SinglePassRange`'s value type is convertible to `Container`'s value type.
+
+[heading Complexity]
+
+Linear. `distance(from)` assignments are performed.
+
+[endsect]
diff --git a/doc/reference/algorithm_ext/remove_erase.qbk b/doc/reference/algorithm_ext/remove_erase.qbk
new file mode 100644
index 0000000..eecc97b
--- /dev/null
+++ b/doc/reference/algorithm_ext/remove_erase.qbk
@@ -0,0 +1,33 @@
+[/
+ Copyright 2010 Neil Groves
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+/]
+[section:remove_erase remove_erase]
+
+[heading Prototype]
+
+``
+template<class Container, class Value>
+Container& remove_erase(Container& target,
+ const Value& value);
+``
+
+[heading Description]
+
+`remove_erase` actually eliminates the elements equal to `value` from the container. This
+is in contrast to the `remove` algorithm which merely rearranges elements.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/erase.hpp`
+
+[heading Requirements]
+
+# `Container` supports erase of an iterator range.
+
+[heading Complexity]
+
+Linear. Proportional to `distance(target)`s.
+
+[endsect]
diff --git a/doc/reference/algorithm_ext/remove_erase_if.qbk b/doc/reference/algorithm_ext/remove_erase_if.qbk
new file mode 100644
index 0000000..5eab446
--- /dev/null
+++ b/doc/reference/algorithm_ext/remove_erase_if.qbk
@@ -0,0 +1,34 @@
+[/
+ 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_erase_if remove_erase_if]
+
+[heading Prototype]
+
+``
+template<class Container, class Pred>
+Container& remove_erase_if(Container& target,
+ Pred pred);
+``
+
+[heading Description]
+
+`remove_erase_if` removes the elements `x` that satisfy `pred(x)` from the container.
+This is in contrast to the `erase` algorithm which merely rearranges elements.
+
+[heading Definition]
+
+Defined in the header file `boost/range/algorithm_ext/erase.hpp`
+
+[heading Requirements]
+
+# `Container` supports erase of an iterator range.
+# `Pred` is a model of the `Predicate` Concept.
+
+[heading Complexity]
+
+Linear. Proportional to `distance(target)`s.
+
+[endsect]