Adding upstream version 16.2.11+ds.upstream/16.2.11+dsupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

9 files changed, 1378 insertions, 0 deletions

diff --git a/src/boost/libs/algorithm/minmax/example/Jamfile b/src/boost/libs/algorithm/minmax/example/Jamfile
new file mode 100644
index 000000000..d8650e042
--- /dev/null
+++ b/src/boost/libs/algorithm/minmax/example/Jamfile
@@ -0,0 +1,12 @@
+#  Boost.Minmax Library Example Jamfile
+#
+#  Copyright (C) 2002--2004, Herve Bronnimann
+#
+# Use, modification, and distribution is subject to the Boost Software
+# License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+# http://www.boost.org/LICENSE_1_0.txt)
+#
+
+exe minmax_ex : minmax_ex.cpp ;
+exe minmax_timer : minmax_timer.cpp ;
+
diff --git a/src/boost/libs/algorithm/minmax/example/minmax_ex.cpp b/src/boost/libs/algorithm/minmax/example/minmax_ex.cpp
new file mode 100644
index 000000000..d77820b39
--- /dev/null
+++ b/src/boost/libs/algorithm/minmax/example/minmax_ex.cpp
@@ -0,0 +1,37 @@
+//  (C) Copyright Herve Bronnimann 2004.
+//  Use, modification and distribution are subject to the
+//  Boost Software License, Version 1.0. (See accompanying file
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <list>
+#include <algorithm>
+#include <cstdlib>
+#include <cassert>
+#include <iostream>
+#include <iterator>
+
+#include <boost/algorithm/minmax.hpp>
+#include <boost/algorithm/minmax_element.hpp>
+
+int main()
+{
+  using namespace std;
+
+  // Demonstrating minmax()
+  boost::tuple<int const&, int const&> result1 = boost::minmax(1, 0);
+  assert( result1.get<0>() == 0 );
+  assert( result1.get<1>() == 1 );
+
+
+  // Demonstrating minmax_element()
+  list<int> L;
+  typedef list<int>::const_iterator iterator;
+  generate_n(front_inserter(L), 1000, rand);
+  pair< iterator, iterator > result2 = boost::minmax_element(L.begin(), L.end());
+
+  cout << "The smallest element is " << *(result2.first) << endl;
+  cout << "The largest element is  " << *(result2.second) << endl;
+
+  assert( result2.first  == std::min_element(L.begin(), L.end()) );
+  assert( result2.second == std::max_element(L.begin(), L.end()) );
+}
diff --git a/src/boost/libs/algorithm/minmax/example/minmax_timer.cpp b/src/boost/libs/algorithm/minmax/example/minmax_timer.cpp
new file mode 100644
index 000000000..0ab51a8a4
--- /dev/null
+++ b/src/boost/libs/algorithm/minmax/example/minmax_timer.cpp
@@ -0,0 +1,212 @@
+//  (C) Copyright Herve Bronnimann 2004.
+//  Use, modification and distribution are subject to the
+//  Boost Software License, Version 1.0. (See accompanying file
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <utility>
+#include <functional>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <vector>
+#include <list>
+#include <set>
+#include <iostream>
+// What's the proper BOOST_ flag for <iomanip.h> vs <ios>
+#include <iomanip>
+
+#include <boost/timer.hpp>
+#include <boost/algorithm/minmax.hpp>
+
+template <class T1, class T2>
+void tie(std::pair<T1, T2> p, T1& min, T2& max)
+{
+  min = p.first; max = p.second;
+}
+
+template <class Value>
+struct less_count : std::less<Value> {
+  less_count(less_count<Value> const& lc) : _M_counter(lc._M_counter) {}
+  less_count(int& counter) : _M_counter(counter) {}
+  bool operator()(Value const& a, Value const& b) const {
+    ++_M_counter;
+    return std::less<Value>::operator()(a,b);
+  }
+  void reset() {
+    _M_counter = 0;
+  }
+private:
+  int& _M_counter;
+};
+
+inline int opt_min_count(int n) {
+  return (n==0) ? 0 : n-1;
+}
+inline int opt_minmax_count(int n) {
+  if (n < 2) return 0;
+  if (n == 2) return 1;
+  return (n%2 == 0) ? 3*(n/2)-1 : 3*(n/2)+1;
+}
+inline int opt_boost_minmax_count(int n) {
+  if (n < 2) return 0;
+  if (n == 2) return 1;
+  return (n%2 == 0) ? 3*(n/2)-2 : 3*(n/2);
+}
+
+int repeats = 10;
+
+#define TIMER( n, cmd , cmdname ) \
+  t.restart(); \
+  for (int i=0; i<repeats; ++i) { cmd ; } \
+  std::cout << "    " << std::setprecision(4) \
+            << (double)n*repeats/t.elapsed()/1.0E6 \
+            << "M items/sec  " << cmdname << "\n"
+
+#define CTIMER( n, cmd , cmdname, count, opt ) \
+  t.restart(); lc.reset(); \
+  for (int i=0; i<repeats; ++i) { cmd ; } \
+  std::cout << "    " << std::setprecision(4) \
+            << (double)n*repeats/t.elapsed()/1.0E6 \
+            << "M items/sec  " << cmdname \
+            << " ("<< (count)/repeats << " vs " << opt << ")\n"
+
+template <class CIterator>
+void test_minmax_element(CIterator first, CIterator last, int n, char* name)
+{
+  typedef typename std::iterator_traits<CIterator>::value_type vtype;
+  boost::timer t;
+
+  std::cout << "  ON " << name << " WITH OPERATOR<()\n";
+  TIMER( n, std::min_element(first, last),
+    "std::min_element" << name << "");
+  TIMER( n, std::max_element(first, last),
+    "std::max_element" << name << "");
+  TIMER( n, boost::first_min_element(first, last),
+    "boost::first_min_element" << name << "");
+  TIMER( n, boost::last_min_element(first, last),
+    "boost::last_min_element" << name << " ");
+  TIMER( n, boost::first_max_element(first, last),
+    "boost::first_max_element" << name << "");
+  TIMER( n, boost::last_max_element(first, last),
+    "boost::last_max_element" << name << " ");
+  TIMER( n, boost::minmax_element(first, last),
+    "boost::minmax_element" << name << "    ");
+  TIMER( n, boost::first_min_last_max_element(first, last),
+    "boost::first_min_last_max_element" << name << "");
+  TIMER( n, boost::last_min_first_max_element(first, last),
+    "boost::last_min_first_max_element" << name << "");
+  TIMER( n, boost::last_min_last_max_element(first, last),
+    "boost::last_min_last_max_element" << name << " ");
+
+  #define pred std::bind2nd( std::greater<vtype>(), vtype(10) )
+  TIMER( n, boost::min_element_if(first, last, pred),
+    "boost::min_element_if" << name << "");
+  TIMER( n, boost::max_element_if(first, last, pred),
+    "boost::max_element_if" << name << "");
+  TIMER( n, std::min_element(boost::make_filter_iterator(first, last, pred),
+                             boost::make_filter_iterator(last, last, pred)),
+    "std::min_element_with_filter_iterator" << name << "");
+  TIMER( n, std::max_element(boost::make_filter_iterator(first, last, pred),
+                             boost::make_filter_iterator(last, last, pred)),
+    "std::max_element_if_with_filter_iterator" << name << "");
+  #undef pred
+
+  int counter = 0;
+  less_count<vtype> lc(counter);
+  std::cout << "  ON " << name << " WITH LESS<> AND COUNTING COMPARISONS\n";
+  CTIMER( n, std::min_element(first, last, lc),
+    "std::min_element" << name << "        ",
+    counter, opt_min_count(n) );
+  CTIMER( n, std::max_element(first, last, lc),
+    "std::max_element" << name << "        ",
+    counter, opt_min_count(n) );
+  CTIMER( n, boost::first_min_element(first, last, lc),
+    "boost::first_min_element" << name << "",
+    counter, opt_min_count(n) );
+  CTIMER( n, boost::last_min_element(first, last, lc),
+    "boost::last_max_element" << name << " ",
+    counter, opt_min_count(n) );
+  CTIMER( n, boost::first_max_element(first, last, lc),
+    "boost::first_min_element" << name << "",
+    counter, opt_min_count(n) );
+  CTIMER( n, boost::last_max_element(first, last, lc),
+    "boost::last_max_element" << name << " ",
+    counter, opt_min_count(n) );
+  CTIMER( n, boost::minmax_element(first, last, lc),
+    "boost::minmax_element" << name << "   ",
+    counter, opt_minmax_count(n) );
+  CTIMER( n, boost::first_min_last_max_element(first, last, lc),
+    "boost::first_min_last_max_element" << name << "",
+    counter, opt_boost_minmax_count(n) );
+  CTIMER( n, boost::last_min_first_max_element(first, last, lc),
+    "boost::last_min_first_max_element" << name << "",
+    counter, opt_boost_minmax_count(n) );
+  CTIMER( n, boost::last_min_last_max_element(first, last, lc),
+    "boost::last_min_last_max_element" << name << " ",
+    counter, opt_minmax_count(n) );
+}
+
+template <class Container, class Iterator, class Value>
+void test_container(Iterator first, Iterator last, int n, char* name)
+{
+  Container c(first, last);
+  typename Container::iterator fit(c.begin()), lit(c.end());
+  test_minmax_element(fit, lit, n, name);
+}
+
+template <class Iterator>
+void test_range(Iterator first, Iterator last, int n)
+{
+  typedef typename std::iterator_traits<Iterator>::value_type Value;
+  // Test various containers with these values
+  test_container< std::vector<Value>, Iterator, Value >(first, last, n, "<vector>");
+#ifndef ONLY_VECTOR
+  test_container< std::list<Value>,   Iterator, Value >(first, last, n, "<list>  ");
+  test_container< std::multiset<Value>,    Iterator, Value >(first, last, n, "<set>   ");
+#endif
+}
+
+template <class Value>
+void test(int n)
+{
+  // Populate test vector with identical values
+  std::cout << "IDENTICAL VALUES...   \n";
+  std::vector<Value> test_vector(n, Value(1));
+  typename std::vector<Value>::iterator first( test_vector.begin() );
+  typename std::vector<Value>::iterator last( test_vector.end() );
+  test_range(first, last, n);
+
+  // Populate test vector with two values
+  std::cout << "TWO DISTINCT VALUES...\n";
+  typename std::vector<Value>::iterator middle( first + n/2 );
+  std::fill(middle, last, Value(2));
+  test_range(first, last, n);
+
+  // Populate test vector with increasing values
+  std::cout << "INCREASING VALUES...  \n";
+  std::fill(first, last, Value(1));
+  std::accumulate(first, last, Value(0));
+  test_range(first, last, n);
+
+  // Populate test vector with decreasing values
+  std::cout << "DECREASING VALUES...  \n";
+  std::reverse(first, last);
+  test_range(first, last, n);
+
+  // Populate test vector with random values
+  std::cout << "RANDOM VALUES...      \n";
+  std::random_shuffle(first, last);
+  test_range(first, last, n);
+}
+
+int
+main(char argc, char** argv)
+{
+  int n = 100;
+  if (argc > 1) n = atoi(argv[1]);
+  if (argc > 2) repeats = atoi(argv[2]);
+
+  test<int>(n);
+
+  return 0;
+}
diff --git a/src/boost/libs/algorithm/minmax/fuzzing/minmax_element.fuzz.cpp b/src/boost/libs/algorithm/minmax/fuzzing/minmax_element.fuzz.cpp
new file mode 100644
index 000000000..63b6a9b74
--- /dev/null
+++ b/src/boost/libs/algorithm/minmax/fuzzing/minmax_element.fuzz.cpp
@@ -0,0 +1,81 @@
+//  (C) Copyright Marshall Clow 2018
+//  Use, modification and distribution are subject to the
+//  Boost Software License, Version 1.0. (See accompanying file
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iterator> // for std::distance
+#include <cassert>  // for assert
+
+#include <boost/algorithm/minmax_element.hpp>
+#include <boost/algorithm/cxx11/none_of.hpp>
+
+//	Fuzzing tests for:
+//
+//		template <class ForwardIterator>
+//		std::pair<ForwardIterator,ForwardIterator>
+//		minmax_element(ForwardIterator first, ForwardIterator last);
+//
+//		template <class ForwardIterator, class BinaryPredicate>
+//		std::pair<ForwardIterator,ForwardIterator>
+//		minmax_element(ForwardIterator first, ForwardIterator last,
+//	               		BinaryPredicate comp);
+
+
+bool greater(uint8_t lhs, uint8_t rhs) { return lhs > rhs; }
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t sz) {
+	typedef std::pair<const uint8_t *, const uint8_t *> result_t;
+	if (sz == 0) return 0; // we need at least one element
+	
+	{
+//	Find the min and max
+	result_t result = boost::minmax_element(data, data + sz);
+
+//	The iterators have to be in the sequence - and not at the end!
+	assert(std::distance(data, result.first)  < sz);
+	assert(std::distance(data, result.second) < sz);
+	
+//	the minimum element can't be bigger than the max element
+	uint8_t min_value = *result.first;
+	uint8_t max_value = *result.second;
+	
+	assert(min_value <= max_value);
+
+//	None of the elements in the sequence can be less than the min, nor greater than the max
+	for (size_t i = 0; i < sz; ++i) {
+		assert(min_value <= data[i]);
+		assert(data[i] <= max_value);
+		}
+
+//	We returned the first min element, and the first max element
+	assert(boost::algorithm::none_of_equal(data, result.first,  min_value));
+	assert(boost::algorithm::none_of_equal(data, result.second, max_value));
+	}
+	
+	{
+//	Find the min and max
+	result_t result = boost::minmax_element(data, data + sz, greater);
+
+//	The iterators have to be in the sequence - and not at the end!
+	assert(std::distance(data, result.first)  < sz);
+	assert(std::distance(data, result.second) < sz);
+
+//	the minimum element can't be bigger than the max element
+	uint8_t min_value = *result.first;
+	uint8_t max_value = *result.second;
+	
+	assert (!greater(max_value, min_value));
+
+//	None of the elements in the sequence can be less than the min, nor greater than the max
+	for (size_t i = 0; i < sz; ++i) {
+		assert(!greater(data[i], min_value));
+		assert(!greater(max_value, data[i]));
+		}
+
+//	We returned the first min element, and the first max element
+	assert(boost::algorithm::none_of_equal(data, result.first,  min_value));
+	assert(boost::algorithm::none_of_equal(data, result.second, max_value));
+	}
+
+  return 0;
+}
diff --git a/src/boost/libs/algorithm/minmax/fuzzing/minmax_element_variants.fuzz.cpp b/src/boost/libs/algorithm/minmax/fuzzing/minmax_element_variants.fuzz.cpp
new file mode 100644
index 000000000..ba517e22f
--- /dev/null
+++ b/src/boost/libs/algorithm/minmax/fuzzing/minmax_element_variants.fuzz.cpp
@@ -0,0 +1,141 @@
+//  (C) Copyright Marshall Clow 2018
+//  Use, modification and distribution are subject to the
+//  Boost Software License, Version 1.0. (See accompanying file
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iterator> // for std::distance
+#include <cassert>  // for assert
+
+#include <boost/algorithm/minmax_element.hpp>
+#include <boost/algorithm/cxx11/none_of.hpp>
+
+//	Fuzzing tests for:
+//
+//		template <class ForwardIterator>
+//		std::pair<ForwardIterator,ForwardIterator>
+//		first_min_first_max_element(ForwardIterator first, ForwardIterator last);
+//
+//		template <class ForwardIterator, class BinaryPredicate>
+//		std::pair<ForwardIterator,ForwardIterator>
+//		first_min_first_max_element(ForwardIterator first, ForwardIterator last,
+//	               		BinaryPredicate comp);
+//
+//	identical signatures for:
+//		first_min_last_max_element
+//		last_min_first_max_element
+//		last_min_last_max_element
+
+bool greater(uint8_t lhs, uint8_t rhs) { return lhs > rhs; }
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t sz) {
+	typedef std::pair<const uint8_t *, const uint8_t *> result_t;
+	const uint8_t * const dend = data + sz;
+	if (sz == 0) return 0; // we need at least one element
+	
+	{
+//	Find the min and max
+	result_t resultff = boost::first_min_first_max_element(data, dend);
+	result_t resultfl = boost::first_min_last_max_element (data, dend);
+	result_t resultlf = boost::last_min_first_max_element (data, dend);
+	result_t resultll = boost::last_min_last_max_element  (data, dend);
+
+//	The iterators have to be in the sequence - and not at the end!
+	assert(std::distance(data, resultff.first)  < sz);
+	assert(std::distance(data, resultff.second) < sz);
+	assert(std::distance(data, resultfl.first)  < sz);
+	assert(std::distance(data, resultfl.second) < sz);
+	assert(std::distance(data, resultlf.first)  < sz);
+	assert(std::distance(data, resultlf.second) < sz);
+	assert(std::distance(data, resultll.first)  < sz);
+	assert(std::distance(data, resultll.second) < sz);
+	
+//	the minimum element can't be bigger than the max element
+
+//	Did we find the same min value and max value?
+	uint8_t min_value = *resultff.first;
+	uint8_t max_value = *resultff.second;
+	assert(min_value <= max_value);
+
+//	Each variant should have found the same min/max values
+	assert(*resultff.first  == min_value);
+	assert(*resultfl.first  == min_value);
+	assert(*resultlf.first  == min_value);
+	assert(*resultll.first  == min_value);
+
+	assert(*resultff.second == max_value);
+	assert(*resultfl.second == max_value);
+	assert(*resultlf.second == max_value);
+	assert(*resultll.second == max_value);
+
+//	None of the elements in the sequence can be less than the min, nor greater than the max
+	for (size_t i = 0; i < sz; ++i) {
+		assert(min_value <= data[i]);
+		assert(data[i] <= max_value);
+		}
+
+//	Make sure we returned the "right" first and last element
+	assert(boost::algorithm::none_of_equal(data, resultff.first,     min_value));
+	assert(boost::algorithm::none_of_equal(data, resultfl.first,     min_value));
+	assert(boost::algorithm::none_of_equal(resultlf.first + 1, dend, min_value));
+	assert(boost::algorithm::none_of_equal(resultll.first + 1, dend, min_value));
+
+	assert(boost::algorithm::none_of_equal(data, resultff.second,     max_value));
+	assert(boost::algorithm::none_of_equal(resultfl.second + 1, dend, max_value));
+	assert(boost::algorithm::none_of_equal(data, resultlf.second,     max_value));
+	assert(boost::algorithm::none_of_equal(resultll.second + 1, dend, max_value));
+	}
+	
+	{
+//	Find the min and max
+	result_t resultff = boost::first_min_first_max_element(data, dend, greater);
+	result_t resultfl = boost::first_min_last_max_element (data, dend, greater);
+	result_t resultlf = boost::last_min_first_max_element (data, dend, greater);
+	result_t resultll = boost::last_min_last_max_element  (data, dend, greater);
+
+//	The iterators have to be in the sequence - and not at the end!
+	assert(std::distance(data, resultff.first)  < sz);
+	assert(std::distance(data, resultff.second) < sz);
+	assert(std::distance(data, resultfl.first)  < sz);
+	assert(std::distance(data, resultfl.second) < sz);
+	assert(std::distance(data, resultlf.first)  < sz);
+	assert(std::distance(data, resultlf.second) < sz);
+	assert(std::distance(data, resultll.first)  < sz);
+	assert(std::distance(data, resultll.second) < sz);
+
+//	the minimum element can't be bigger than the max element
+	uint8_t min_value = *resultff.first;
+	uint8_t max_value = *resultff.second;
+	
+	assert (!greater(max_value, min_value));
+
+//	Each variant should have found the same min/max values
+	assert(*resultff.first  == min_value);
+	assert(*resultfl.first  == min_value);
+	assert(*resultlf.first  == min_value);
+	assert(*resultll.first  == min_value);
+
+	assert(*resultff.second == max_value);
+	assert(*resultfl.second == max_value);
+	assert(*resultlf.second == max_value);
+	assert(*resultll.second == max_value);
+
+//	None of the elements in the sequence can be less than the min, nor greater than the max
+	for (size_t i = 0; i < sz; ++i) {
+		assert(!greater(data[i], min_value));
+		assert(!greater(max_value, data[i]));
+		}
+
+//	We returned the first min element, and the first max element
+	assert(boost::algorithm::none_of_equal(data, resultff.first,     min_value));
+	assert(boost::algorithm::none_of_equal(data, resultfl.first,     min_value));
+	assert(boost::algorithm::none_of_equal(resultlf.first + 1, dend, min_value));
+	assert(boost::algorithm::none_of_equal(resultll.first + 1, dend, min_value));
+
+	assert(boost::algorithm::none_of_equal(data, resultff.second,     max_value));
+	assert(boost::algorithm::none_of_equal(resultfl.second + 1, dend, max_value));
+	assert(boost::algorithm::none_of_equal(data, resultlf.second,     max_value));
+	assert(boost::algorithm::none_of_equal(resultll.second + 1, dend, max_value));
+	}
+
+  return 0;
+}
diff --git a/src/boost/libs/algorithm/minmax/index.html b/src/boost/libs/algorithm/minmax/index.html
new file mode 100644
index 000000000..f58bfe659
--- /dev/null
+++ b/src/boost/libs/algorithm/minmax/index.html
@@ -0,0 +1,532 @@
+<!DOCTYPE html public "-//w3c//dtd html 4.0 transitional//en">
+<HTML>
+<HEAD>
+   <LINK REL="stylesheet" TYPE="text/css" HREF="../../../boost.css">
+   <META http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
+   <META name="GENERATOR" content="Mozilla/4.77 [en] (X11; U; Linux 2.2.19 i686) [Netscape]">
+   <META name="Author" content="Herve Bronnimann">
+   <META name="Description" content="Small library to propose minmax_element algorithm.">
+   <title>Boost Minmax library</title>
+</HEAD>
+<body text="#000000" bgcolor="#FFFFFF" link="#0000EE" vlink="#551A8B" alink="#FF0000">
+
+<h2><img src="../../../boost.png" WIDTH="276" HEIGHT="86">Header &lt;<A
+HREF="../../../boost/algorithm/minmax.hpp">boost/algorithm/minmax.hpp</A>&gt; </H2>
+
+<quote>
+<b>
+<a href="#minmax_element">Motivation</a><br>
+<a href="#synopsis">Synopsis</a><br>
+<a href="#description">Function templates description</a><br>
+<a href="#definition">Definition</a><br>
+<a href="#reqs">Requirements on types</a><br>
+<a href="#precond">Preconditions</a><br>
+<a href="#postcond">Postconditions</a><br>
+<a href="#complexity">Complexity</a><br>
+<a href="#example">Example</a><br>
+<a href="#notes">Notes</a><br>
+<a href="#rationale">Rationale</a><br>
+<a href="#perf">Note about performance</a><br>
+<a href="#acks">Acknowledgements</a>
+</b>
+</quote>
+
+
+<a name="minmax_element">
+<h3>
+Motivation</h3>
+
+<p>The minmax library is composed of two headers, <a
+href="../../../boost/algorithm/minmax.hpp">&lt;boost/algorithm/minmax.hpp></a>
+and <a
+href="../../../boost/algorithm/minmax_element.hpp">&lt;boost/algorithm/minmax_element.hpp></a>.
+(See <a href="#two_headers">rationale</a>.)
+The problem solved by this library is that simultaneous min and max
+computation requires
+only one comparison, but using <tt>std::min</tt> and <tt>std::max</tt>
+forces two comparisons. Worse, to compute the minimum and
+maximum elements of a range of <tt>n</tt> elements requires only
+<tt>3n/2+1</tt> comparisons, instead of the <tt>2n</tt> (in two passes)
+forced by <tt>std::min_element</tt> and <tt>std::max_element</tt>.
+I always thought it is a waste to have to call two functions to compute the
+extent of a range, performing two passes over the input, when one should
+be enough. The present library solves both problems.</p>
+
+<p>The first file implements the function templates
+<tt>minmax</tt>
+as straightforward extensions of the C++
+standard. As it returns a pair of <tt>const&amp;</tt>, we must use the <a
+href="../../tuple/index.html">Boost.tuple</a> library to construct such
+pairs. (Please note: the intent is not to fix the known defaults of
+<tt>std::min</tt>
+and <tt>std::max</tt>, but to add one more algorithms that combines both; see the
+<a href="#no-fix">rationale</a>.)</p>
+
+<p>The second file implements the function templates
+<tt>minmax_element</tt>. In a
+second part, it also proposes variants that can usually not be computed by
+the minmax algorithm, and which are more flexible in case some elements are equal.
+Those variants could have been also provided with policy-based design,
+but I ruled against that (see <a href="#no-policy">rationale</a>).
+</p>
+
+<p>If you are interested about
+<a href="doc/minmax_benchs.html">performance</a>,
+you will see that <tt>minmax_element</tt> is just slightly less efficient
+than a single <tt>min_element</tt> or <tt>max_element</tt>, and thus
+twice as efficient as two separate calls to <tt>min_element</tt> and
+<tt>max_element</tt>. From a
+theoretical standpoint,
+all the <tt>minmax_element</tt> functions perform at most
+<tt>3n/2+1</tt>
+comparisons and exactly n increments of the
+<tt>ForwardIterator</tt>.</p>
+</a>
+
+<a name="synopsis">
+<h3>
+Synopsis of <tt>&lt;boost/algorithm/minmax.hpp></tt></h3>
+
+<pre>#include &lt;boost/tuple/tuple.hpp>
+
+namespace boost {
+
+  template &lt;class T>
+  tuple&lt;T const&amp;, T const&amp;>
+  minmax(const T&amp; a, const T&amp; b);
+
+  template &lt;class T, class <a href="https://www.boost.org/sgi/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  tuple&lt;T const&amp;, T const&amp;>
+  minmax(const T&amp; a, const T&amp; b, BinaryPredicate comp);
+
+}
+</pre>
+
+<h3>
+Synopsis of <tt>&lt;boost/algorithm/minmax_element.hpp></tt></h3>
+
+<pre>#include &lt;utility> // for std::pair
+
+namespace boost {
+
+  template &lt;class <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">ForwardIterator</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  minmax_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="https://www.boost.org/sgi/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  minmax_element(ForwardIterator first, ForwardIterator last,
+                 BinaryPredicate comp);
+
+}
+</pre>
+
+In addition, there are a bunch of extensions which specify
+which element(s) you want to pick in case of equal elements. They are:
+<ul>
+<li><tt>first_min_element</tt> and <tt>last_min_element</tt></li>
+<li><tt>first_max_element</tt> and <tt>last_max_element</tt></li>
+<li><tt>first_min_first_max_element</tt>,
+<tt>first_min_last_max_element</tt>,
+<tt>last_min_first_max_element</tt>, and
+<tt>last_min_last_max_element</tt></li>
+</ul>
+I won't bore you with the complete synopsis, they have exactly the same
+declaration as their corresponding <tt>_element</tt> function. Still,
+you can find the complete synopsis <a href="doc/minmax_synopsis.html">here</a>.
+</a>
+
+<a name="description">
+<h3>
+Function templates description</h3>
+The <tt>minmax</tt> algorithm returns a pair <tt>p</tt> containing either
+<i>(a,b)</i>
+or <i>(b,a)</i>, such that <tt>p.first&lt;p.second</tt> in the first version,
+or <tt>comp(p.first,p.second)</tt> in the second version. If the elements
+are equivalent, the pair <i>(a,b) </i>is returned. <a href="#Note1">[1]</a>
+<p>The <tt>minmax_element </tt>is semantically equivalent to <tt>first_min_first_max_element</tt>.
+<p><tt>First_min_element</tt> and <tt>first_max_element</tt> find the smallest
+and largest elements in the range <tt>[first, last)</tt>. If there are
+several instance of these elements, the first one is returned. They are
+identical to
+<tt>std::min_element</tt> and <tt>std::max_element</tt>and
+are only included in this library for symmetry.
+<p><tt>Last_min_element</tt> and <tt>last_max_element</tt> find the smallest
+and largest elements in the range <tt>[first, last)</tt>. They are almost
+identical to
+<tt>std::min_element</tt> and <tt>std::max_element</tt>, except
+that they return the last instance of the largest element (and not the
+first, as <tt>first_min_element</tt> and <tt>last_max_element</tt> would).
+<p>The family of algorithms comprising <tt>first_min_first_max_element</tt>,
+<tt>first_min_last_max_element</tt>,
+<tt>last_min_first_max_element</tt>,
+and <tt>last_min_last_max_element</tt> can be described generically as
+follows (using <i><tt>which</tt></i> and
+<i><tt>what</tt></i> for <tt>first</tt>
+or <tt>last</tt>): <tt><i>which</i>_min_<i>what</i>_max_element</tt> finds
+the (first or last, according to <i><tt>which</tt></i>) smallest element
+and the (first or last, according to <i><tt>what</tt></i>) largest element
+in the range
+<tt>[first, last)</tt>. The first version is semantically
+equivalent to:
+<pre><tt>  std::make_pair(boost::<i>which</i>_min_element(first,last),
+                 boost::<i>what</i>_max_element(first,last))</tt>,</pre>
+and the second version to:
+<pre><tt>  std::make_pair(boost::<i>which</i>_min_element(first,last,comp),
+                 boost::<i>what</i>_max_element(first,last,comp))</tt>.</pre>
+
+<p><br><b><i>Note</i></b>: the <tt>first_min_last_max_element</tt> can also be described
+as finding the first and last elements in the range if it were stably sorted.
+</a>
+
+<a name="definition">
+<h3>
+Definition</h3>
+Defined in <a href="../../../boost/algorithm/minmax.hpp">minmax.hpp</a>
+and
+in <a href="../../../boost/algorithm/minmax_element.hpp">minmax_element.hpp</a>.
+</a>
+
+<a name="reqs">
+<h3>
+Requirements on types</h3>
+For minmax, <tt>T</tt> must be a model of <a href="https://www.boost.org/sgi/stl/LessThanComparable.html">LessThan
+Comparable</a>.
+<p>For all the other function templates, versions with two template parameters:
+<ul>
+<li>
+<tt>ForwardIterator</tt> is a model of <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">Forward
+Iterator</a>.</li>
+
+<li>
+<tt>ForwardIterator</tt>'s value type is <a href="https://www.boost.org/sgi/stl/LessThanComparable.html">LessThan
+Comparable</a>.</li>
+</ul>
+For the versions with three template parameters:
+<ul>
+<li>
+<tt>ForwardIterator</tt> is a model of <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">Forward
+Iterator</a>.</li>
+
+<li>
+<tt>BinaryPredicate</tt> is a model of <a href="https://www.boost.org/sgi/stl/BinaryPredicate.html">Binary
+Predicate</a>.</li>
+
+<li>
+<tt>ForwardIterator</tt>'s value type is convertible to <tt>BinaryPredicate</tt>'s
+first argument type and second argument type.</li>
+</ul>
+</a>
+
+<a name="precond">
+<h3>
+Preconditions</h3>
+
+<ul>
+<li>
+<tt>[first, last)</tt> is a valid range.</li>
+</ul>
+</a>
+
+<a name="postcond">
+<h3>
+Postconditions</h3>
+In addition to the semantic description above. for <tt>minmax_element</tt>
+and all the <tt><i>which</i>_min_<i>what</i>_max_element</tt>
+variants, the return value is
+<tt>last</tt> or <tt>std::make_pair(last,last)</tt>
+if and only if <tt>[first, last)</tt> is an empty range. Otherwise, the
+return value or both members of the resulting pair are iterators in the
+range
+<tt>[first, last)</tt>.
+</a>
+
+<a name="complexity">
+<h3>
+Complexity</h3>
+Minmax performs a single comparison and is otherwise of constant complexity.
+The use of <tt>boost::tuple&lt;T const&amp;></tt> prevents copy
+constructors in case the arguments are passed by reference.
+<p>The complexity of all the other algorithms is linear. They all perform
+exactly n increment operations, and zero comparisons if <tt>[first,last)</tt>
+is empty, otherwise :
+<ul>
+<li>
+all the <tt>min_element</tt> and <tt>max_element</tt> variants perform
+exactly<tt>(n-1)</tt> comparisons,</li>
+
+<li>
+<tt>minmax_element</tt> , <tt>first_min_first_max_element</tt>, and <tt>last_min_last_max_element</tt>
+perform at most <tt>3(n/2)-1</tt> comparisons if <tt>n</tt> is even and
+non-zero, and at most <tt>3(n/2)+1</tt> if <tt>n</tt> is odd,
+<a href="#Note2">[2]</a></li>
+
+<li>
+<tt>first_min_last_max_element</tt>, and <tt>last_min_first_max_element</tt>
+perform exactly <tt>3n/2-2</tt> comparisons if n is even and non-zero,
+and at most <tt>3(n/2)</tt> if <tt>n</tt> is odd,
+<a href="#Note1">[3]</a></li>
+</ul>
+where <tt>n</tt> is the number of elements in <tt>[first,last)</tt>.
+</a>
+
+<a name="example">
+<h3>
+Example</h3>
+This example is included in the distribution in the examples section of
+the library under
+<a href="example/minmax_ex.cpp">minmax_ex.cpp</a>.
+
+<pre>int main()
+{
+  using namespace std;
+  boost::tuple&lt;int const&amp;, int const&amp;> result1 = boost::minmax(1, 0);
+
+  assert( result1.get<0>() == 0 );
+  assert( result1.get<1>() == 1 );
+
+  <a href="https://www.boost.org/sgi/stl/List.html">list</a>&lt;int> L;
+  <a href="https://www.boost.org/sgi/stl/generate_n.html">generate_n</a>(<a href="https://www.boost.org/sgi/stl/front_insert_iterator.html">front_inserter</a>(L), 1000, rand);
+
+  typedef list&lt;int>::const_iterator iterator;
+  pair&lt; iterator, iterator > result2 = boost::minmax_element(L.begin(), L.end());
+  cout &lt;&lt; "The smallest element is " &lt;&lt; *(result2.first) &lt;&lt; endl;
+  cout &lt;&lt; "The largest element is  " &lt;&lt; *(result2.second) &lt;&lt; endl;
+
+  assert( result2.first  == std::min_element(L.begin(), L.end());
+  assert( result2.second == std::max_element(L.begin(), L.end());
+}</pre>
+</a>
+
+<a name="notes">
+<h3>
+Notes</h3>
+<a NAME="Note1"></a><a href="#Note1">[1]</a> We do not support
+idioms such as <tt><a href="../../tuple/doc/tuple_users_guide.html#tiers">tie</a>(a,b)=minmax(a,b)</tt>
+to order two elements <tt>a</tt>, <tt>b</tt>, although this would have
+the desired effect if we returned a reference instead of a constant
+reference. The reason is that two unnecessary assignments are
+performed if a and b are in order. It is better to stick to <tt>if (b&lt;a)
+swap(a,b)</tt> to achieve that effect.
+<p><a NAME="Note2"></a><a href="#Note2">[2]</a> These algorithms always
+perform at least <tt>3n/2-2</tt> comparisons, which is a lower bound on
+the number of comparisons in any case (Cormen, Leiserson, Rivest: "Introduction
+to Algorithms", section 9.1, Exercise 9.1-). The algorithms essentially compare
+the elements in pairs, performing 1 comparison for the first two elements,
+then 3 comparisons for each remaining pair of elements (one to order the
+elements and one for updating each the minimum and and the maximum). When
+the number of elements is odd, the last one needs to be compared to the
+current minimum and also to the current maximum. In addition, for <tt>minmax</tt>,
+in cases where equality of the two members in the pair could occur, and
+the update stores the second, we save the first to check at the end if
+the update should have stored the first (in case of equality). It's hard
+to predict if the last comparison is performed or not, hence the at most
+in both cases.
+<p><a NAME="Note3"></a><a href="#Note3">[3]</a> These algorithms always
+perform at least <tt>3n/2-2</tt> comparisons, which is a lower bound on
+the number of comparisons in any case. The method is the same as in note
+<a href="#Note2">[2]</a>
+above, and like above, when the number of elements is odd, the last one
+needs to be compared to the current minimum and also to the current maximum.
+We can avoid the latter comparison if the former is successful, hence the
+<i>at
+most</i> instead of <i>exactly</i> in the odd case.
+</a>
+
+<a name="rationale">
+<h3>
+<b>Rationale:</b></h3>
+
+<a name="two_headers">
+<h4><b>Why not a single header <tt>&lt;boost/algorithm/minmax.hpp></tt>?</b></h4>
+<p>This was the design originally proposed and approved in the formal
+review. As the need for Boost.tuple became clear (due to the limitations
+of <tt>std::pair</tt>), it became also annoying to require another
+library for <tt>minmax_element</tt> which does not need it. Hence the
+separation into two header files.</p>
+
+<a name="no-fix">
+<h4><b>Your minmax suffers from the same problems as std::min and
+std::max.</b></h4>
+<p>I am aware of the problems with std::min and
+std::max, and all the debate that has been going on (please consult
+<a href="#Alexandrescu">Alexandrescu's paper</a> and the links therein). But I don't see the purpose of this
+library as fixing something that is part of the C++ standard. I humbly
+think it's beyond the scope of this library. Rather, I am
+following the way of the standard in simply providing one more function
+of the same family. If someone else wants to fix std::min, their fix
+would probably apply to boost::minmax as well.</p>
+</a>
+
+<h4><b>Why no <tt>min/max_element_if</tt>?</b></h4>
+<p>In a first version of the library, I proposed <tt>_if</tt> versions of
+all the algorithms (well, not all, because that would be too much).
+However, there is simply no reason to do so, and all the versions I had
+were just as fast implemented using the excellent
+<tt>&lt;boost/iterator_adaptors.hpp></tt> library. Namely, a call to
+<tt>min_element_if(first, last, pred)</tt> would be just as well
+implemented by:
+<pre>
+     // equivalent to min_element_if(first, last, pred)
+     min_element(boost::make_filter_iterator(first, last, pred),
+                 boost::make_filter_iterator(last, last, pred));
+</pre>
+Arguably, the <tt>min_element_if</tt> version is somewhat shorter, but
+the overhead of iterator adaptors is not large, and they get rid of a
+lot of code (think of all the combinations between first/last and
+doubling them with _if variants!).</p>
+
+<h4><b>Discussion: about std::max_element</b></h4>
+<p>This rationale is somewhat historical, but explains why there are all
+these <tt>first/last_min/max_element</tt> functions.</p>
+<p>The C++ standard mandates that <tt>std::min_element</tt> and <tt>std::max_element</tt>
+return the first instance of the smallest and largest elements (as opposed
+to, say, the last). This arbitrary choice has some consistency: In the
+case of v of type vector&lt;int>, for instance, it is true that <tt>std::min_element(v.begin(),v.end(),std::less&lt;int>())
+== std::max_element(v.begin(),v.end(),std::greater&lt;int>())</tt>.
+<p>There is of course nothing wrong with this: it's simply a matter of
+choice. Yet another way to specify min_element and max_element is to define
+them as the first and the last elements if the range was stably sorted.
+(The <i>stable</i> sort is necessary to disambiguate between iterators
+that have the same value.) In that case, min should return the first instance
+and max should return the last. Then, both functions are related by
+<tt>reverse_iterator(std::first_min_element(v.begin(),v.end(),std::less&lt;int>()))
+==
+std::last_max_element(v.rbegin(),v.rend(),std::greater&lt;int>())</tt>.
+This definition is subtly different from the previous one.</p>
+<p>The definition problem surfaces when one tries to design a minmax_element,
+using the procedure proposed in (Cormen, Leiserson, Rivest: "Introduction
+to Algorithms", section 9.1). It <i>should</i> be possible to derive an
+algorithm using only <tt>3n/2</tt> comparisons if <tt>[first,last) </tt>has
+<tt>n</tt>
+elements, but if one tries to write a function called <tt>first_min_first_max_element()</tt>
+which returns both <tt>std::min_element</tt> and <tt>std::max_element</tt>
+in a pair, the trivial implementation does not work. The problem, rather
+subtly, is about equal elements: I had to think for a while to find a
+way to perform only three
+comparisons per pair and return the first min and first max elements.
+For a long time, it seemed any
+attempts at doing so would consume four comparisons per pair in the worst
+case. This implementation achieves three.</p>
+<p>It is not possible (or even desirable) to change the meaning of
+<tt>max_element</tt>,
+but it is still beneficial to provide a function called <tt>minmax_element</tt>,
+which returns a pair of <tt>min_element</tt> and <tt>max_element</tt>.
+Although it is easy enough to call <tt>min_element</tt> and <tt>max_element</tt>,
+this performs
+<tt>2(n-1)</tt> comparisons, and necessitates <b>two</b>
+passes over the input. In contrast,
+<tt>minmax_element</tt> will perform
+the fewer comparisons and perform a <b>single</b> pass over the input.
+The savings can be significant when the iterator type is not a raw pointer,
+or even is just a model of the InputIterator concept (although in that
+case the interface would have to be
+changed, as the return type could not be copied, so one could e.g.
+return a value).</p>
+<p>In order to benefit from all the variants of the algorithm, I propose
+to introduce both <tt>first_min_element</tt> and <tt>last_min_element</tt>,
+and their counterparts <tt>first_max_element</tt> and <tt>last_max_element</tt>.
+Then I also propose all the variants algorithms: <tt>first_min_last_max_element</tt>
+and <tt>last_min_first_max_element</tt>, which perform only at most <tt>3n/2</tt>
+comparisons, and only a single pass on the input. In fact, it can be proven
+that computing minmax requires at least <tt>3(n/2)-2</tt> comparisons in
+any instance of the problem (Cormen, Leiserson, Rivest, 2nd edition, section
+9.1). The implementation I give does not perform unnecessary comparisons
+(whose result could have been computed by transitivity from previous
+comparisons).</p>
+<p>It appears that <tt>first_min_last_max_element</tt> may be just a tad
+slower than
+<tt>first_min_element</tt> alone, still much less than <tt>first_min_element</tt>
+and
+<tt>last_max_element</tt> called separately.  <a href="#Note2">[2]</a>
+
+<h4><b>Why algorithms and not accumulators?</b></h4>
+<p>The minmax algorithms are useful in computing the extent of a range.
+In computer graphics, we need a bounding box of a set of objects.
+In that case the need for a single pass is even more stringent
+as all three directions must be done at once. Food for thoughts: there
+is matter for a nice generic programming library with stackable <tt>update_min</tt>
+and <tt>update_max</tt> function objects which store a reference to the
+<tt>min_result</tt>and
+<tt>max_result</tt> variables, in conjunction with the <tt>for_each</tt>
+algorithm).</p>
+<p>I believe many standard sequential algorithms could be reformulated
+with accumulators (and many others, such as in statistics, expectation /
+variance / etc.). It seems that there is room for another library, but I
+do not see it competing with minmax, rather extending several algorithms
+(including minmax) to the accumulator framework. However, I felt it is
+beyond the scope of this library to provide such accumulators.</p>
+
+<a NAME="no-policy">
+<h4><b>This first/last is a perfect application for a policy-based
+design.</b></h4>
+<p>True, and I could have gone that way, with the default policy for
+<tt>min_element</tt> and <tt>max_element</tt> to pick the first
+occurence of the result. This would have thinned the number of
+combinations of the minmax_element variants. But it would also have
+meant to change the interface of <tt>boost::minmax_element</tt>.
+One of the goals of the <tt>minmax_element</tt> algorithm is its
+eventual addition to the C++ standard, in connection with
+<tt>std::min_element</tt> and <tt>std::max_element</tt>
+(and I feel that it would be quite natural
+given the shortness of the implementation, and the not quite trivial
+detail which is needed to get it right). So changing the interface by
+adding policies would have meant unfortunately to depart from the
+standard and created an obstacle towards that goal. Besides, the code
+remains rather readable and simple without policies. So I am quite happy
+to keep it like this.
+</p></a>
+</a>
+
+<a name="perf">
+<a href="doc/minmax_benchs.html"><h3><b>About performance</b></h3></a>
+</a>
+
+<a name="acks">
+<h3>
+Acknowledgements</h3>
+
+<a name="Alexandrescu">
+<a href="http://www.drdobbs.com/generic-min-and-max-redivivus/184403774">Generic: Min and Max Redivivus, by Andrei Alexandrescu</a>
+Dr. Dobbs, April 2001
+
+<p>My students in CS903 (Polytechnic Univ., <a href="http://photon.poly.edu/~hbr/cs903/">http://photon.poly.edu/~hbr/cs903/</a>)
+who had <tt>minmax_element</tt> as an assignment helped clarify the issues,
+and also come up with the optimum number of comparisons for <tt>first_min_last_max_element</tt>.
+The identification of the issue surrounding <tt>max_element</tt> is solely
+my own.
+<p>One <tt>minmax_element</tt> implementation, which performs <tt>3(n/2)+O(log
+n)</tt> comparisons on the average when the elements are <tt>random_shuffle</tt>d,
+was suggested by my student Marc Glisse. The current one, which performs
+<tt>3(n/2)+1</tt>
+comparisons in the worst case, was suggested by John Iacono.<p>
+<p>Finally, Matthew Wilson and Jeremy Siek contributed pre-review
+comments, while Gennadiy Rozental, John Maddock, Craig Henderson, Gary
+Powell participated in the review of the library, managed by Thomas
+Witt. In particular, Gennadiy suggested a factorization of the code;
+while I haven't followed it all the way, his suggestions do make the
+code more readable and still work with older compilers. 
+Late after the review, as I finally scrounged to add the library for a
+release, Eric Niebler noted the bad behavior of <tt>std::pair</tt> for
+<tt>minmax</tt> and suggested to use Boost.tuple instead. 
+All my thanks for the excellent advice and reviews from all.
+<h3>
+See also</h3>
+<tt><a href="https://www.boost.org/sgi/stl/min.html">min</a></tt>, <tt><a href="https://www.boost.org/sgi/stl/max.html">max</a></tt>,
+<tt><a href="https://www.boost.org/sgi/stl/min_element.html">min_element</a></tt>,
+<tt><a href="https://www.boost.org/sgi/stl/max_element.html">max_element</a></tt>,
+<tt><a href="https://www.boost.org/sgi/stl/LessThanComparable.html">LessThan
+Comparable</a></tt>,
+<tt><a href="https://www.boost.org/sgi/stl/sort.html">sort</a></tt>,
+<tt><a href="https://www.boost.org/sgi/stl/nth_element.html">nth_element</a></tt>
+.
+<hr SIZE="6">
+<br>Last modified 2012-12-10
+<p><font face="Arial,Helvetica"><font size=-1>&copy; Copyright Herv&eacute;
+Br&ouml;nnimann, Polytechnic University, 2002--2004. 
+Use, modification, and distribution is subject to the Boost Software
+License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">License_1_0.txt</a> or copy at
+<a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)
+</font></font>
+</body>
+</html>
diff --git a/src/boost/libs/algorithm/minmax/test/Jamfile.v2 b/src/boost/libs/algorithm/minmax/test/Jamfile.v2
new file mode 100644
index 000000000..384b35929
--- /dev/null
+++ b/src/boost/libs/algorithm/minmax/test/Jamfile.v2
@@ -0,0 +1,25 @@
+#  Boost.Minmax Library test Jamfile
+#
+#  Copyright (C) 2002--2004, Herve Bronnimann
+#
+# Use, modification, and distribution is subject to the Boost Software
+# License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+# http://www.boost.org/LICENSE_1_0.txt)
+#
+
+import testing ;
+
+alias unit_test_framework
+    : # sources
+        /boost//unit_test_framework
+    ;        
+
+{
+  test-suite algorithm/minmax
+   : [ run minmax_element_test.cpp unit_test_framework
+       : : : : minmax_element ]
+     [ run minmax_test.cpp unit_test_framework
+       : : : : minmax ]      
+   ;
+}
+
diff --git a/src/boost/libs/algorithm/minmax/test/minmax_element_test.cpp b/src/boost/libs/algorithm/minmax/test/minmax_element_test.cpp
new file mode 100644
index 000000000..11cf2c4cd
--- /dev/null
+++ b/src/boost/libs/algorithm/minmax/test/minmax_element_test.cpp
@@ -0,0 +1,253 @@
+//  (C) Copyright Herve Bronnimann 2004.
+//  Use, modification and distribution are subject to the
+//  Boost Software License, Version 1.0. (See accompanying file
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <utility>
+#include <functional>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <vector>
+#include <list>
+#include <set>
+#include <cstdlib>
+
+#include <boost/config.hpp> /* prevents some nasty warns in MSVC */
+#include <boost/algorithm/minmax_element.hpp>
+#include <boost/iterator/reverse_iterator.hpp>
+
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#if (__cplusplus >= 201103L) || defined(BOOST_NO_CXX98_RANDOM_SHUFFLE)
+#include <random>
+
+std::default_random_engine gen;
+template<typename RandomIt>
+void do_shuffle(RandomIt first, RandomIt last)
+{ std::shuffle(first, last, gen); }
+#else
+template<typename RandomIt>
+void do_shuffle(RandomIt first, RandomIt last)
+{ std::random_shuffle(first, last); }
+#endif
+
+class custom {
+  int m_x;
+  friend bool operator<(custom const& x, custom const& y);
+public:
+  explicit custom(int x = 0) : m_x(x) {}
+  custom(custom const& y) : m_x(y.m_x) {}
+  custom operator+(custom const& y) const { return custom(m_x+y.m_x); }
+  custom& operator+=(custom const& y) { m_x += y.m_x; return *this; }
+};
+
+bool operator< (custom const& x, custom const& y)
+{
+  return x.m_x < y.m_x;
+}
+
+BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(custom)
+
+namespace std {
+
+template <>
+struct iterator_traits<int*> {
+  typedef random_access_iterator_tag  iterator_category;
+  typedef int                          value_type;
+  typedef ptrdiff_t                    difference_type;
+  typedef value_type*                  pointer;
+  typedef value_type&                  reference;
+};
+
+template <>
+struct iterator_traits<custom*> {
+  typedef random_access_iterator_tag  iterator_category;
+  typedef custom                       value_type;
+  typedef ptrdiff_t                    difference_type;
+  typedef value_type*                  pointer;
+  typedef value_type&                  reference;
+};
+
+}
+
+template <class T1, class T2, class T3, class T4>
+void tie(std::pair<T1, T2> p, T3& first, T4& second)
+{
+  first = T3(p.first); second = T4(p.second);
+}
+
+template <class Value>
+struct less_count : std::less<Value> {
+    typedef std::less<Value> Base;
+  less_count(less_count<Value> const& lc) : m_counter(lc.m_counter) {}
+  less_count(int& counter) : m_counter(counter) {}
+  bool operator()(Value const& a, Value const& b) const {
+    ++m_counter;
+    return Base::operator()(a,b);
+  }
+  void reset() {
+    m_counter = 0;
+  }
+private:
+  int& m_counter;
+};
+
+inline int opt_min_count(int n) {
+  return (n==0) ? 0 : n-1;
+}
+inline int opt_minmax_count(int n) {
+  if (n < 2) return 0;
+  if (n == 2) return 2;
+  return (n%2 == 0) ? 3*(n/2)-1 : 3*(n/2)+1;
+}
+inline int opt_boost_minmax_count(int n) {
+  if (n < 2) return 0;
+  if (n == 2) return 1;
+  return (n%2 == 0) ? 3*(n/2)-2 : 3*(n/2);
+}
+
+#define CHECK_EQUAL_ITERATORS( left, right, first ) \
+BOOST_CHECK_EQUAL( std::distance( first, left ), std::distance( first, right ) )
+
+template <class CIterator>
+void test_minmax(CIterator first, CIterator last, int n)
+{
+  using namespace boost;
+
+  typedef typename std::iterator_traits<CIterator>::value_type Value;
+  typedef boost::reverse_iterator<CIterator> RCIterator;
+  // assume that CIterator is BidirectionalIter
+  CIterator min, max;
+  RCIterator rfirst(last), rlast(first), rmin, rmax;
+  int counter = 0;
+  less_count<Value> lc(counter);
+
+  // standard extensions
+  // first version, operator<
+  tie( boost::minmax_element(first, last), min, max );
+
+  CHECK_EQUAL_ITERATORS( min, std::min_element(first, last), first );
+  CHECK_EQUAL_ITERATORS( max, std::max_element(first, last), first );
+
+  // second version, comp function object (keeps a counter!)
+  lc.reset();
+  tie( boost::minmax_element(first, last, lc), min, max );
+  BOOST_CHECK( counter <= opt_minmax_count(n) );
+  CHECK_EQUAL_ITERATORS( min, std::min_element(first, last, lc), first );
+  CHECK_EQUAL_ITERATORS( max, std::max_element(first, last, lc), first );
+
+  // boost extensions
+  // first version, operator<
+  CHECK_EQUAL_ITERATORS( boost::first_min_element(first, last), std::min_element(first, last), first );
+  rmin = RCIterator(boost::last_min_element(first, last));
+  rmin = (rmin == rfirst) ? rlast : --rmin;
+  CHECK_EQUAL_ITERATORS( rmin, std::min_element(rfirst, rlast), rfirst );
+  CHECK_EQUAL_ITERATORS( boost::first_max_element(first, last), std::max_element(first, last), first );
+  rmax = RCIterator(boost::last_max_element(first, last));
+  rmax = (rmax == rfirst) ? rlast : --rmax;
+  CHECK_EQUAL_ITERATORS( rmax, std::max_element(rfirst, rlast), rfirst );
+  tie( boost::first_min_last_max_element(first, last), min, max );
+  CHECK_EQUAL_ITERATORS( min, boost::first_min_element(first, last), first );
+  CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last), first );
+  tie( boost::last_min_first_max_element(first, last), min, max );
+  CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last), first );
+  CHECK_EQUAL_ITERATORS( max, boost::first_max_element(first, last), first );
+  tie( boost::last_min_last_max_element(first, last), min, max );
+  CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last), first );
+  CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last), first );
+
+  // second version, comp function object (keeps a counter!)
+  lc.reset();
+  min = boost::first_min_element(first, last, lc);
+  BOOST_CHECK( counter <= opt_min_count(n) );
+  CHECK_EQUAL_ITERATORS( min, std::min_element(first, last, lc), first );
+  lc.reset();
+  rmin = RCIterator(boost::last_min_element(first, last, lc));
+  rmin = (rmin == rfirst) ? rlast : --rmin;
+  BOOST_CHECK( counter <= opt_min_count(n) );
+  CHECK_EQUAL_ITERATORS( rmin, std::min_element(rfirst, rlast, lc), rfirst );
+  lc.reset();
+  max =  boost::first_max_element(first, last, lc);
+  BOOST_CHECK( counter <= opt_min_count(n) );
+  CHECK_EQUAL_ITERATORS( max, std::max_element(first, last, lc), first );
+  lc.reset();
+  rmax = RCIterator(boost::last_max_element(first, last, lc));
+  rmax = (rmax == rfirst) ? rlast : --rmax;
+  BOOST_CHECK( counter <= opt_min_count(n) );
+  CHECK_EQUAL_ITERATORS( rmax, std::max_element(rfirst, rlast, lc), rfirst );
+  lc.reset();
+  tie( boost::first_min_last_max_element(first, last, lc), min, max );
+  BOOST_CHECK( counter <= opt_boost_minmax_count(n) );
+  CHECK_EQUAL_ITERATORS( min, boost::first_min_element(first, last, lc), first );
+  CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last, lc), first );
+  lc.reset();
+  tie( boost::last_min_first_max_element(first, last, lc), min, max );
+  BOOST_CHECK( counter <= opt_boost_minmax_count(n) );
+  BOOST_CHECK( min == boost::last_min_element(first, last, lc) );
+  CHECK_EQUAL_ITERATORS( max, boost::first_max_element(first, last, lc), first );
+  lc.reset();
+  tie( boost::last_min_last_max_element(first, last, lc), min, max );
+  BOOST_CHECK( counter <= opt_minmax_count(n) );
+  CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last, lc), first );
+  CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last, lc), first );
+}
+
+template <class Container, class Iterator, class Value>
+void test_container(Iterator first, Iterator last, int n,
+                    Container* /* dummy */ = 0
+                    BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Value) )
+{
+  Container c(first, last);
+  test_minmax(c.begin(), c.end(), n);
+}
+
+template <class Iterator>
+void test_range(Iterator first, Iterator last, int n)
+{
+  typedef typename std::iterator_traits<Iterator>::value_type Value;
+  // Test various containers with these values
+  test_container< std::vector<Value>, Iterator, Value >(first, last, n);
+  test_container< std::list<Value>,   Iterator, Value >(first, last, n);
+  test_container< std::set<Value>,    Iterator, Value >(first, last, n);
+}
+
+template <class Value>
+void test(int n BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Value))
+{
+  // Populate test vector with identical values
+  std::vector<Value> test_vector(n, Value(1));
+  typename std::vector<Value>::iterator first( test_vector.begin() );
+  typename std::vector<Value>::iterator last( test_vector.end() );
+  test_range(first, last, n);
+
+  // Populate test vector with two values
+  typename std::vector<Value>::iterator middle( first + n/2 );
+  std::fill(middle, last, Value(2));
+  test_range(first, last, n);
+
+  // Populate test vector with increasing values
+  std::accumulate(first, last, Value(0));
+  test_range(first, last, n);
+
+  // Populate test vector with decreasing values
+  std::reverse(first, last);
+  test_range(first, last, n);
+
+  // Populate test vector with random values
+  do_shuffle(first, last);
+  test_range(first, last, n);
+}
+
+BOOST_AUTO_TEST_CASE( test_main )
+{
+#ifndef BOOST_NO_STDC_NAMESPACE
+  using std::atoi;
+#endif
+
+  int n = 100;
+
+  test<int>(n);
+  test<custom>(n);
+}
diff --git a/src/boost/libs/algorithm/minmax/test/minmax_test.cpp b/src/boost/libs/algorithm/minmax/test/minmax_test.cpp
new file mode 100644
index 000000000..151b09684
--- /dev/null
+++ b/src/boost/libs/algorithm/minmax/test/minmax_test.cpp
@@ -0,0 +1,85 @@
+//  (C) Copyright Herve Bronnimann 2004.
+//  Use, modification and distribution are subject to the
+//  Boost Software License, Version 1.0. (See accompanying file
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <utility>
+#include <functional>
+
+#include <boost/config.hpp>
+#include <boost/algorithm/minmax.hpp>
+
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+class custom {
+  int m_x;
+  friend std::ostream& operator<<(std::ostream& str, custom const& x);
+public:
+  explicit custom(int x = 0) : m_x(x) {}
+  custom(custom const& y) : m_x(y.m_x) {}
+  bool operator==(custom const& y) const { return m_x == y.m_x; }
+  bool operator<(custom const& y) const { return m_x < y.m_x; }
+  custom operator+(custom const& y) const { return custom(m_x+y.m_x); }
+  custom& operator+=(custom const& y) { m_x += y.m_x; return *this; }
+};
+
+std::ostream&
+operator<<(std::ostream& str, custom const& x)
+{
+  return  str << x.m_x;
+}
+
+template <class Value>
+struct less_count : std::less<Value> {
+  typedef std::less<Value> Base;
+  less_count(less_count<Value> const& lc) : m_counter(lc.m_counter) {}
+  less_count(int& counter) : m_counter(counter) {}
+  bool operator()(Value const& a, Value const& b) const {
+    ++m_counter;
+    return Base::operator()(a,b);
+  }
+  void reset() {
+    m_counter = 0;
+  }
+private:
+  int& m_counter;
+};
+
+using namespace boost;
+
+template <class Value>
+void test(BOOST_EXPLICIT_TEMPLATE_TYPE(Value))
+{
+  Value zero(0), one(1);
+  int counter = 0;
+  less_count<Value> lc(counter);
+
+  // Test functionality
+  tuple<Value const&, Value const&> result1 = boost::minmax(zero, one);
+  BOOST_CHECK_EQUAL( get<0>(result1), zero );
+  BOOST_CHECK_EQUAL( get<1>(result1), one );
+
+  tuple<Value const&, Value const&> result2 = boost::minmax(one, zero);
+  BOOST_CHECK_EQUAL( get<0>(result2), zero );
+  BOOST_CHECK_EQUAL( get<1>(result2), one );
+  
+  // Test functionality and number of comparisons
+  lc.reset();
+  tuple<Value const&, Value const&> result3 = boost::minmax(zero, one, lc );
+  BOOST_CHECK_EQUAL( get<0>(result3), zero );
+  BOOST_CHECK_EQUAL( get<1>(result3), one );
+  BOOST_CHECK_EQUAL( counter, 1 );
+
+  lc.reset();
+  tuple<Value const&, Value const&> result4 = boost::minmax(one, zero, lc );
+  BOOST_CHECK_EQUAL( get<0>(result4), zero );
+  BOOST_CHECK_EQUAL( get<1>(result4), one );
+  BOOST_CHECK_EQUAL( counter, 1);
+}
+
+BOOST_AUTO_TEST_CASE( test_main )
+{
+  test<int>(); // ("builtin");
+  test<custom>(); // ("custom ");
+}