Imported from /home/lorry/working-area/delta_boost-tarball/boost_1_54_0.tar.bz2.boost_1_54_0baserock/morph

3 files changed, 350 insertions, 0 deletions

diff --git a/libs/algorithm/minmax/test/Jamfile.v2 b/libs/algorithm/minmax/test/Jamfile.v2
new file mode 100644
index 000000000..fcfba8ae1
--- /dev/null
+++ b/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/libs/algorithm/minmax/test/minmax_element_test.cpp b/libs/algorithm/minmax/test/minmax_element_test.cpp
new file mode 100644
index 000000000..b8c02f549
--- /dev/null
+++ b/libs/algorithm/minmax/test/minmax_element_test.cpp
@@ -0,0 +1,240 @@
+//  (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>
+
+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
+  std::random_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/libs/algorithm/minmax/test/minmax_test.cpp b/libs/algorithm/minmax/test/minmax_test.cpp
new file mode 100644
index 000000000..151b09684
--- /dev/null
+++ b/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 ");
+}