random.tcc (discrete_distribution<>::param_type:: param_type(size_t, double, double, _Func), [...]): Tidy.

2009-06-19  Paolo Carlini  <paolo.carlini@oracle.com>

	* include/bits/random.tcc (discrete_distribution<>::param_type::
      	param_type(size_t, double, double, _Func),
	discrete_distribution<>::operator()(_UniformRandomNumberGenerator&,
	const param_type&)): Tidy.
	(piecewise_constant_distribution<>::param_type::_M_initialize):
	Use reserve, fix.
	(piecewise_constant_distribution<>::param_type::
	param_type(initializer_list<>, _Func),
	piecewise_constant_distribution<>::param_type::
	param_type(size_t, _RealType, _RealType, _Func),
       	piecewise_linear_distribution<>::param_type::
	param_type(initializer_list<>, _Func),
       	piecewise_linear_distribution<>::param_type::
	param_type(size_t, _RealType, _RealType, _Func)): Use reserve, tidy.
	(piecewise_constant_distribution<>::param_type::
	param_type(_InputIteratorB, _InputIteratorB, _InputIteratorW),
	piecewise_constant_distribution<>::
	operator()(_UniformRandomNumberGenerator&, const param_type&),
      	piecewise_linear_distribution<>::
	operator()(_UniformRandomNumberGenerator&, const param_type&)): Fix.
	(operator>>(std::basic_istream<>&,
	piecewise_constant_distribution<>&),
	operator>>(std::basic_istream<>&, piecewise_linear_distribution<>&)):
	Use reserve.
	* include/bits/random.h: Minor cosmetic changes.

From-SVN: r148719

3 files changed, 133 insertions, 98 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 29747b1..ded7f3e 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,31 @@
+2009-06-19  Paolo Carlini  <paolo.carlini@oracle.com>
+
+	* include/bits/random.tcc (discrete_distribution<>::param_type::
+      	param_type(size_t, double, double, _Func),
+	discrete_distribution<>::operator()(_UniformRandomNumberGenerator&,
+	const param_type&)): Tidy.
+	(piecewise_constant_distribution<>::param_type::_M_initialize):
+	Use reserve, fix.
+	(piecewise_constant_distribution<>::param_type::
+	param_type(initializer_list<>, _Func),
+	piecewise_constant_distribution<>::param_type::
+	param_type(size_t, _RealType, _RealType, _Func),
+       	piecewise_linear_distribution<>::param_type::
+	param_type(initializer_list<>, _Func),
+       	piecewise_linear_distribution<>::param_type::
+	param_type(size_t, _RealType, _RealType, _Func)): Use reserve, tidy.
+	(piecewise_constant_distribution<>::param_type::
+	param_type(_InputIteratorB, _InputIteratorB, _InputIteratorW),
+	piecewise_constant_distribution<>::
+	operator()(_UniformRandomNumberGenerator&, const param_type&),
+      	piecewise_linear_distribution<>::
+	operator()(_UniformRandomNumberGenerator&, const param_type&)): Fix.
+	(operator>>(std::basic_istream<>&,
+	piecewise_constant_distribution<>&),
+	operator>>(std::basic_istream<>&, piecewise_linear_distribution<>&)):
+	Use reserve.
+	* include/bits/random.h: Minor cosmetic changes.
+
 2009-06-17  Benjamin Kosnik  <bkoz@redhat.com>
 
 	* testsuite/23_containers/list/check_construct_destroy.h: New.
diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h
index e8edbf0..ec3dd13 100644
--- a/libstdc++-v3/include/bits/random.h
+++ b/libstdc++-v3/include/bits/random.h
@@ -4108,8 +4108,8 @@ namespace std
 	: _M_param(__wbegin, __wend)
 	{ }
 
-      discrete_distribution(initializer_list<double> __wil)
-      : _M_param(__wil)
+      discrete_distribution(initializer_list<double> __wl)
+      : _M_param(__wl)
       { }
 
       template<typename _Func>
@@ -4240,7 +4240,7 @@ namespace std
 		     _InputIteratorW __wbegin);
 
 	template<typename _Func>
-	  param_type(initializer_list<_RealType> __bil, _Func __fw);
+	  param_type(initializer_list<_RealType> __bi, _Func __fw);
 
 	template<typename _Func>
 	  param_type(size_t __nw, _RealType __xmin, _RealType __xmax,
@@ -4276,9 +4276,9 @@ namespace std
 	{ }
 
       template<typename _Func>
-	piecewise_constant_distribution(initializer_list<_RealType> __bil,
+	piecewise_constant_distribution(initializer_list<_RealType> __bl,
 					_Func __fw)
-	: _M_param(__bil, __fw)
+	: _M_param(__bl, __fw)
 	{ }
 
       template<typename _Func>
@@ -4408,7 +4408,9 @@ namespace std
 	typedef piecewise_linear_distribution<_RealType> distribution_type;
 	friend class piecewise_linear_distribution<_RealType>;
 
-	param_type();
+	param_type()
+	: _M_int(), _M_den(), _M_cp(), _M_m()
+	{ _M_initialize(); }
 
 	template<typename _InputIteratorB, typename _InputIteratorW>
 	  param_type(_InputIteratorB __bfirst,
@@ -4416,7 +4418,7 @@ namespace std
 		     _InputIteratorW __wbegin);
 
 	template<typename _Func>
-	  param_type(initializer_list<_RealType> __bil, _Func __fw);
+	  param_type(initializer_list<_RealType> __bl, _Func __fw);
 
 	template<typename _Func>
 	  param_type(size_t __nw, _RealType __xmin, _RealType __xmax,
@@ -4453,9 +4455,9 @@ namespace std
 	{ }
 
       template<typename _Func>
-	piecewise_linear_distribution(initializer_list<_RealType> __bil,
+	piecewise_linear_distribution(initializer_list<_RealType> __bl,
 				      _Func __fw)
-	: _M_param(__bil, __fw)
+	: _M_param(__bl, __fw)
 	{ }
 
       template<typename _Func>
diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index eb2ce4a..846b6b0 100644
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -1985,30 +1985,31 @@ namespace std
 	  return;
 	}
 
-      double __sum = std::accumulate(_M_prob.begin(), _M_prob.end(), 0.0);
-      //  Now normalize the densities.
+      const double __sum = std::accumulate(_M_prob.begin(),
+					   _M_prob.end(), 0.0);
+      // Now normalize the probabilites.
       std::transform(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
 		     std::bind2nd(std::divides<double>(), __sum));
-      //  Accumulate partial sums.
+      // Accumulate partial sums.
+      _M_cp.reserve(_M_prob.size());
       std::partial_sum(_M_prob.begin(), _M_prob.end(),
 		       std::back_inserter(_M_cp));
-      //  Make sure the last cumulative probablility is one.
+      // Make sure the last cumulative probability is one.
       _M_cp[_M_cp.size() - 1] = 1.0;
     }
 
   template<typename _IntType>
     template<typename _Func>
       discrete_distribution<_IntType>::param_type::
-      param_type(size_t __nw, double __xmin, double __xmax,
-		 _Func __fw)
+      param_type(size_t __nw, double __xmin, double __xmax, _Func __fw)
       : _M_prob(), _M_cp()
       {
-	for (size_t __i = 0; __i < __nw; ++__i)
-	  {
-	    const double __x = ((__nw - __i - 0.5) * __xmin
-				     + (__i + 0.5) * __xmax) / __nw;
-	    _M_prob.push_back(__fw(__x));
-	  }
+	const size_t __n = __nw == 0 ? 1 : __nw;
+	const double __delta = (__xmax - __xmin) / __n;
+
+	_M_prob.reserve(__n);
+	for (size_t __k = 0; __k < __nw; ++__k)
+	  _M_prob.push_back(__fw(__xmin + __k * __delta + 0.5 * __delta));
 
 	_M_initialize();
       }
@@ -2026,11 +2027,8 @@ namespace std
 	const double __p = __aurng();
 	auto __pos = std::lower_bound(__param._M_cp.begin(),
 				      __param._M_cp.end(), __p);
-	if (__pos == __param._M_cp.end())
-	  return 0;
-	const size_t __i = __pos - __param._M_cp.begin();
 
-	return __i;
+	return __pos - __param._M_cp.begin();
       }
 
   template<typename _IntType, typename _CharT, typename _Traits>
@@ -2075,6 +2073,7 @@ namespace std
       __is >> __n;
 
       std::vector<double> __prob_vec;
+      __prob_vec.reserve(__n);
       for (; __n != 0; --__n)
 	{
 	  double __prob;
@@ -2098,6 +2097,7 @@ namespace std
       if (_M_int.size() < 2)
 	{
 	  _M_int.clear();
+	  _M_int.reserve(2);
 	  _M_int.push_back(_RealType(0));
 	  _M_int.push_back(_RealType(1));
 
@@ -2107,21 +2107,21 @@ namespace std
 	  return;
 	}
 
-      double __sum = 0.0;
-      for (size_t __i = 0; __i < _M_den.size(); ++__i)
-	{
-	  __sum += _M_den[__i] * (_M_int[__i + 1] - _M_int[__i]);
-	  _M_cp.push_back(__sum);
-	}
+      const double __sum = std::accumulate(_M_den.begin(),
+					   _M_den.end(), 0.0);
 
-      //  Now normalize the densities...
       std::transform(_M_den.begin(), _M_den.end(), _M_den.begin(),
 		     std::bind2nd(std::divides<double>(), __sum));
-      //  ... and partial sums.
-      std::transform(_M_cp.begin(), _M_cp.end(), _M_cp.begin(),
-		     std::bind2nd(std::divides<double>(), __sum));
-      //  Make sure the last cumulative probablility is one.
+
+      _M_cp.reserve(_M_den.size());
+      std::partial_sum(_M_den.begin(), _M_den.end(),
+		       std::back_inserter(_M_cp));
+
+      // Make sure the last cumulative probability is one.
       _M_cp[_M_cp.size() - 1] = 1.0;
+
+      for (size_t __k = 0; __k < _M_den.size(); ++__k)
+	_M_den[__k] /= _M_int[__k + 1] - _M_int[__k];
     }
 
   template<typename _RealType>
@@ -2132,17 +2132,19 @@ namespace std
 		 _InputIteratorW __wbegin)
       : _M_int(), _M_den(), _M_cp()
       {
-	do
+	if (__bbegin != __bend)
 	  {
-	    _M_int.push_back(*__bbegin);
-	    ++__bbegin;
-	    if (__bbegin != __bend)
+	    for (;;)
 	      {
+		_M_int.push_back(*__bbegin);
+		++__bbegin;
+		if (__bbegin == __bend)
+		  break;
+
 		_M_den.push_back(*__wbegin);
 		++__wbegin;
 	      }
 	  }
-	while (__bbegin != __bend);
 
 	_M_initialize();
       }
@@ -2150,17 +2152,16 @@ namespace std
   template<typename _RealType>
     template<typename _Func>
       piecewise_constant_distribution<_RealType>::param_type::
-      param_type(initializer_list<_RealType> __bil, _Func __fw)
+      param_type(initializer_list<_RealType> __bl, _Func __fw)
       : _M_int(), _M_den(), _M_cp()
       {
-	for (auto __biter = __bil.begin(); __biter != __bil.end(); ++__biter)
+	_M_int.reserve(__bl.size());
+	for (auto __biter = __bl.begin(); __biter != __bl.end(); ++__biter)
 	  _M_int.push_back(*__biter);
 
-	for (size_t __i = 0; __i < _M_int.size() - 1; ++__i)
-	  {
-	    _RealType __x = 0.5 * (_M_int[__i] + _M_int[__i + 1]);
-	    _M_den.push_back(__fw(__x));
-	  }
+	_M_den.reserve(_M_int.size() - 1);
+	for (size_t __k = 0; __k < _M_int.size() - 1; ++__k)
+	  _M_den.push_back(__fw(0.5 * (_M_int[__k + 1] + _M_int[__k])));
 
 	_M_initialize();
       }
@@ -2171,18 +2172,16 @@ namespace std
       param_type(size_t __nw, _RealType __xmin, _RealType __xmax, _Func __fw)
       : _M_int(), _M_den(), _M_cp()
       {
-	for (size_t __i = 0; __i <= __nw; ++__i)
-	  {
-	    const _RealType __x = ((__nw - __i) * __xmin
-					  + __i * __xmax) / __nw;
-	    _M_int.push_back(__x);
-	  }
-	for (size_t __i = 0; __i < __nw; ++__i)
-	  {
-	    const _RealType __x = ((__nw - __i - 0.5) * __xmin
-					+ (__i + 0.5) * __xmax) / __nw;
-	    _M_den.push_back(__fw(__x));
-	  }
+	const size_t __n = __nw == 0 ? 1 : __nw;
+	const _RealType __delta = (__xmax - __xmin) / __n;
+
+	_M_int.reserve(__n + 1);
+	for (size_t __k = 0; __k <= __nw; ++__k)
+	  _M_int.push_back(__xmin + __k * __delta);
+
+	_M_den.reserve(__n);
+	for (size_t __k = 0; __k < __nw; ++__k)
+	  _M_den.push_back(__fw(_M_int[__k] + 0.5 * __delta));
 
 	_M_initialize();
       }
@@ -2202,8 +2201,9 @@ namespace std
 				      __param._M_cp.end(), __p);
 	const size_t __i = __pos - __param._M_cp.begin();
 
-	return __param._M_int[__i]
-	     + (__p - __param._M_cp[__i]) / __param._M_den[__i];
+	const double __pref = __i > 0 ? __param._M_cp[__i - 1] : 0.0;
+
+	return __param._M_int[__i] + (__p - __pref) / __param._M_den[__i];
       }
 
   template<typename _RealType, typename _CharT, typename _Traits>
@@ -2253,6 +2253,7 @@ namespace std
       __is >> __n;
 
       std::vector<_RealType> __int_vec;
+      __int_vec.reserve(__n + 1);
       for (size_t __i = 0; __i <= __n; ++__i)
 	{
 	  _RealType __int;
@@ -2261,6 +2262,7 @@ namespace std
 	}
 
       std::vector<double> __den_vec;
+      __den_vec.reserve(__n);
       for (size_t __i = 0; __i < __n; ++__i)
 	{
 	  double __den;
@@ -2284,10 +2286,12 @@ namespace std
       if (_M_int.size() < 2)
 	{
 	  _M_int.clear();
+	  _M_int.reserve(2);
 	  _M_int.push_back(_RealType(0));
 	  _M_int.push_back(_RealType(1));
 
 	  _M_den.clear();
+	  _M_den.reserve(2);
 	  _M_den.push_back(1.0);
 	  _M_den.push_back(1.0);
 
@@ -2295,17 +2299,19 @@ namespace std
 	}
 
       double __sum = 0.0;
-      for (size_t __i = 0; __i < _M_int.size() - 1; ++__i)
+      _M_cp.reserve(_M_int.size() - 1);
+      _M_m.reserve(_M_int.size() - 1);
+      for (size_t __k = 0; __k < _M_int.size() - 1; ++__k)
 	{
-	  const _RealType __delta = _M_int[__i + 1] - _M_int[__i];
-	  __sum += 0.5 * (_M_den[__i + 1] + _M_den[__i]) * __delta;
+	  const _RealType __delta = _M_int[__k + 1] - _M_int[__k];
+	  __sum += 0.5 * (_M_den[__k + 1] + _M_den[__k]) * __delta;
 	  _M_cp.push_back(__sum);
-	  _M_m.push_back((_M_den[__i + 1] - _M_den[__i]) / __delta);
+	  _M_m.push_back((_M_den[__k + 1] - _M_den[__k]) / __delta);
 	}
 
       //  Now normalize the densities...
       std::transform(_M_den.begin(), _M_den.end(), _M_den.begin(),
-		     std::bind2nd(std::divides<double>(),__sum));
+		     std::bind2nd(std::divides<double>(), __sum));
       //  ... and partial sums... 
       std::transform(_M_cp.begin(), _M_cp.end(), _M_cp.begin(),
 		     std::bind2nd(std::divides<double>(), __sum));
@@ -2314,13 +2320,7 @@ namespace std
 		     std::bind2nd(std::divides<double>(), __sum));
       //  Make sure the last cumulative probablility is one.
       _M_cp[_M_cp.size() - 1] = 1.0;
-    }
-
-  template<typename _RealType>
-    piecewise_linear_distribution<_RealType>::param_type::
-    param_type()
-    : _M_int(), _M_den(), _M_cp(), _M_m()
-    { _M_initialize(); }
+     }
 
   template<typename _RealType>
     template<typename _InputIteratorB, typename _InputIteratorW>
@@ -2342,10 +2342,12 @@ namespace std
   template<typename _RealType>
     template<typename _Func>
       piecewise_linear_distribution<_RealType>::param_type::
-      param_type(initializer_list<_RealType> __bil, _Func __fw)
+      param_type(initializer_list<_RealType> __bl, _Func __fw)
       : _M_int(), _M_den(), _M_cp(), _M_m()
       {
-	for (auto __biter = __bil.begin(); __biter != __bil.end(); ++__biter)
+	_M_int.reserve(__bl.size());
+	_M_den.reserve(__bl.size());
+	for (auto __biter = __bl.begin(); __biter != __bl.end(); ++__biter)
 	  {
 	    _M_int.push_back(*__biter);
 	    _M_den.push_back(__fw(*__biter));
@@ -2357,16 +2359,18 @@ namespace std
   template<typename _RealType>
     template<typename _Func>
       piecewise_linear_distribution<_RealType>::param_type::
-      param_type(size_t __nw, _RealType __xmin, _RealType __xmax,
-		 _Func __fw)
+      param_type(size_t __nw, _RealType __xmin, _RealType __xmax, _Func __fw)
       : _M_int(), _M_den(), _M_cp(), _M_m()
       {
-	for (size_t __i = 0; __i <= __nw; ++__i)
+	const size_t __n = __nw == 0 ? 1 : __nw;
+	const _RealType __delta = (__xmax - __xmin) / __n;
+
+	_M_int.reserve(__n + 1);
+	_M_den.reserve(__n + 1);
+	for (size_t __k = 0; __k <= __nw; ++__k)
 	  {
-	    const _RealType __x = ((__nw - __i) * __xmin
-					  + __i * __xmax) / __nw;
-	    _M_int.push_back(__x);
-	    _M_den.push_back(__fw(__x));
+	    _M_int.push_back(__xmin + __k * __delta);
+	    _M_den.push_back(__fw(_M_int[__k] + __delta));
 	  }
 
 	_M_initialize();
@@ -2379,7 +2383,6 @@ namespace std
       operator()(_UniformRandomNumberGenerator& __urng,
 		 const param_type& __param)
       {
-	result_type __x;
 	__detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
 	  __aurng(__urng);
 
@@ -2387,23 +2390,23 @@ namespace std
 	auto __pos = std::lower_bound(__param._M_cp.begin(),
 				      __param._M_cp.end(), __p);
 	const size_t __i = __pos - __param._M_cp.begin();
+
+	const double __pref = __i > 0 ? __param._M_cp[__i - 1] : 0.0;
+
 	const double __a = 0.5 * __param._M_m[__i];
 	const double __b = __param._M_den[__i];
-	const double __c = __param._M_cp[__i];
-	const double __q = -0.5 * (__b
-#if _GLIBCXX_USE_C99_MATH_TR1
-			 + std::copysign(std::sqrt(__b * __b
-						 - 4.0 * __a * __c), __b));
-#else
-			 + (__b < 0.0 ? -1.0 : 1.0)
-			 * std::sqrt(__b * __b - 4.0 * __a * __c));
-#endif
-	const double __x0 = __param._M_int[__i];
-	const double __x1 = __q / __a;
-	const double __x2 = __c / __q;
-	__x = std::max(__x0 + __x1, __x0 + __x2);
+	const double __cm = __p - __pref;
+
+	_RealType __x = __param._M_int[__i];
+	if (__a == 0)
+	  __x += __cm / __b;
+	else
+	  {
+	    const double __d = __b * __b + 4.0 * __a * __cm;
+	    __x += 0.5 * (std::sqrt(__d) - __b) / __a;
+          }
 
-	return __x;
+        return __x;
       }
 
   template<typename _RealType, typename _CharT, typename _Traits>
@@ -2453,6 +2456,7 @@ namespace std
       __is >> __n;
 
       std::vector<_RealType> __int_vec;
+      __int_vec.reserve(__n + 1);
       for (size_t __i = 0; __i <= __n; ++__i)
 	{
 	  _RealType __int;
@@ -2461,6 +2465,7 @@ namespace std
 	}
 
       std::vector<double> __den_vec;
+      __den_vec.reserve(__n + 1);
       for (size_t __i = 0; __i <= __n; ++__i)
 	{
 	  double __den;