functional revision 97403
197403Sobrien// Functional extensions -*- C++ -*- 297403Sobrien 397403Sobrien// Copyright (C) 2002 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 1897403Sobrien// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * 3297403Sobrien * Copyright (c) 1994 3397403Sobrien * Hewlett-Packard Company 3497403Sobrien * 3597403Sobrien * Permission to use, copy, modify, distribute and sell this software 3697403Sobrien * and its documentation for any purpose is hereby granted without fee, 3797403Sobrien * provided that the above copyright notice appear in all copies and 3897403Sobrien * that both that copyright notice and this permission notice appear 3997403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4097403Sobrien * representations about the suitability of this software for any 4197403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4297403Sobrien * 4397403Sobrien * 4497403Sobrien * Copyright (c) 1996 4597403Sobrien * Silicon Graphics Computer Systems, Inc. 4697403Sobrien * 4797403Sobrien * Permission to use, copy, modify, distribute and sell this software 4897403Sobrien * and its documentation for any purpose is hereby granted without fee, 4997403Sobrien * provided that the above copyright notice appear in all copies and 5097403Sobrien * that both that copyright notice and this permission notice appear 5197403Sobrien * in supporting documentation. Silicon Graphics makes no 5297403Sobrien * representations about the suitability of this software for any 5397403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5497403Sobrien */ 5597403Sobrien 5697403Sobrien/** @file ext/functional 5797403Sobrien * This file is a GNU extension to the Standard C++ Library (possibly 5897403Sobrien * containing extensions from the HP/SGI STL subset). You should only 5997403Sobrien * include this header if you are using GCC 3 or later. 6097403Sobrien */ 6197403Sobrien 6297403Sobrien#ifndef _EXT_FUNCTIONAL 6397403Sobrien#define _EXT_FUNCTIONAL 6497403Sobrien 6597403Sobrien#pragma GCC system_header 6697403Sobrien#include <functional> 6797403Sobrien 6897403Sobriennamespace __gnu_cxx 6997403Sobrien{ 7097403Sobrienusing std::unary_function; 7197403Sobrienusing std::binary_function; 7297403Sobrienusing std::mem_fun1_t; 7397403Sobrienusing std::const_mem_fun1_t; 7497403Sobrienusing std::mem_fun1_ref_t; 7597403Sobrienusing std::const_mem_fun1_ref_t; 7697403Sobrien 7797403Sobrien/** The @c identity_element functions are not part of the C++ standard; SGI 7897403Sobrien * provided them as an extension. Its argument is an operation, and its 7997403Sobrien * return value is the identity element for that operation. It is overloaded 8097403Sobrien * for addition and multiplication, and you can overload it for your own 8197403Sobrien * nefarious operations. 8297403Sobrien * 8397403Sobrien * @addtogroup SGIextensions 8497403Sobrien * @{ 8597403Sobrien*/ 8697403Sobrien/// An \link SGIextensions SGI extension \endlink. 8797403Sobrientemplate <class _Tp> inline _Tp identity_element(std::plus<_Tp>) { 8897403Sobrien return _Tp(0); 8997403Sobrien} 9097403Sobrien/// An \link SGIextensions SGI extension \endlink. 9197403Sobrientemplate <class _Tp> inline _Tp identity_element(std::multiplies<_Tp>) { 9297403Sobrien return _Tp(1); 9397403Sobrien} 9497403Sobrien/** @} */ 9597403Sobrien 9697403Sobrien/** As an extension to the binders, SGI provided composition functors and 9797403Sobrien * wrapper functions to aid in their creation. The @c unary_compose 9897403Sobrien * functor is constructed from two functions/functors, @c f and @c g. 9997403Sobrien * Calling @c operator() with a single argument @c x returns @c f(g(x)). 10097403Sobrien * The function @c compose1 takes the two functions and constructs a 10197403Sobrien * @c unary_compose variable for you. 10297403Sobrien * 10397403Sobrien * @c binary_compose is constructed from three functors, @c f, @c g1, 10497403Sobrien * and @c g2. Its @c operator() returns @c f(g1(x),g2(x)). The function 10597403Sobrien * @compose2 takes f, g1, and g2, and constructs the @c binary_compose 10697403Sobrien * instance for you. For example, if @c f returns an int, then 10797403Sobrien * \code 10897403Sobrien * int answer = (compose2(f,g1,g2))(x); 10997403Sobrien * \endcode 11097403Sobrien * is equivalent to 11197403Sobrien * \code 11297403Sobrien * int temp1 = g1(x); 11397403Sobrien * int temp2 = g2(x); 11497403Sobrien * int answer = f(temp1,temp2); 11597403Sobrien * \endcode 11697403Sobrien * But the first form is more compact, and can be passed around as a 11797403Sobrien * functor to other algorithms. 11897403Sobrien * 11997403Sobrien * @addtogroup SGIextensions 12097403Sobrien * @{ 12197403Sobrien*/ 12297403Sobrien/// An \link SGIextensions SGI extension \endlink. 12397403Sobrientemplate <class _Operation1, class _Operation2> 12497403Sobrienclass unary_compose 12597403Sobrien : public unary_function<typename _Operation2::argument_type, 12697403Sobrien typename _Operation1::result_type> 12797403Sobrien{ 12897403Sobrienprotected: 12997403Sobrien _Operation1 _M_fn1; 13097403Sobrien _Operation2 _M_fn2; 13197403Sobrienpublic: 13297403Sobrien unary_compose(const _Operation1& __x, const _Operation2& __y) 13397403Sobrien : _M_fn1(__x), _M_fn2(__y) {} 13497403Sobrien typename _Operation1::result_type 13597403Sobrien operator()(const typename _Operation2::argument_type& __x) const { 13697403Sobrien return _M_fn1(_M_fn2(__x)); 13797403Sobrien } 13897403Sobrien}; 13997403Sobrien 14097403Sobrien/// An \link SGIextensions SGI extension \endlink. 14197403Sobrientemplate <class _Operation1, class _Operation2> 14297403Sobrieninline unary_compose<_Operation1,_Operation2> 14397403Sobriencompose1(const _Operation1& __fn1, const _Operation2& __fn2) 14497403Sobrien{ 14597403Sobrien return unary_compose<_Operation1,_Operation2>(__fn1, __fn2); 14697403Sobrien} 14797403Sobrien 14897403Sobrien/// An \link SGIextensions SGI extension \endlink. 14997403Sobrientemplate <class _Operation1, class _Operation2, class _Operation3> 15097403Sobrienclass binary_compose 15197403Sobrien : public unary_function<typename _Operation2::argument_type, 15297403Sobrien typename _Operation1::result_type> { 15397403Sobrienprotected: 15497403Sobrien _Operation1 _M_fn1; 15597403Sobrien _Operation2 _M_fn2; 15697403Sobrien _Operation3 _M_fn3; 15797403Sobrienpublic: 15897403Sobrien binary_compose(const _Operation1& __x, const _Operation2& __y, 15997403Sobrien const _Operation3& __z) 16097403Sobrien : _M_fn1(__x), _M_fn2(__y), _M_fn3(__z) { } 16197403Sobrien typename _Operation1::result_type 16297403Sobrien operator()(const typename _Operation2::argument_type& __x) const { 16397403Sobrien return _M_fn1(_M_fn2(__x), _M_fn3(__x)); 16497403Sobrien } 16597403Sobrien}; 16697403Sobrien 16797403Sobrien/// An \link SGIextensions SGI extension \endlink. 16897403Sobrientemplate <class _Operation1, class _Operation2, class _Operation3> 16997403Sobrieninline binary_compose<_Operation1, _Operation2, _Operation3> 17097403Sobriencompose2(const _Operation1& __fn1, const _Operation2& __fn2, 17197403Sobrien const _Operation3& __fn3) 17297403Sobrien{ 17397403Sobrien return binary_compose<_Operation1,_Operation2,_Operation3> 17497403Sobrien (__fn1, __fn2, __fn3); 17597403Sobrien} 17697403Sobrien/** @} */ 17797403Sobrien 17897403Sobrien/** As an extension, SGI provided a functor called @c identity. When a 17997403Sobrien * functor is required but no operations are desired, this can be used as a 18097403Sobrien * pass-through. Its @c operator() returns its argument unchanged. 18197403Sobrien * 18297403Sobrien * @addtogroup SGIextensions 18397403Sobrien*/ 18497403Sobrientemplate <class _Tp> struct identity : public std::_Identity<_Tp> {}; 18597403Sobrien 18697403Sobrien/** @c select1st and @c select2nd are extensions provided by SGI. Their 18797403Sobrien * @c operator()s 18897403Sobrien * take a @c std::pair as an argument, and return either the first member 18997403Sobrien * or the second member, respectively. They can be used (especially with 19097403Sobrien * the composition functors) to "strip" data from a sequence before 19197403Sobrien * performing the remainder of an algorithm. 19297403Sobrien * 19397403Sobrien * @addtogroup SGIextensions 19497403Sobrien * @{ 19597403Sobrien*/ 19697403Sobrien/// An \link SGIextensions SGI extension \endlink. 19797403Sobrientemplate <class _Pair> struct select1st : public std::_Select1st<_Pair> {}; 19897403Sobrien/// An \link SGIextensions SGI extension \endlink. 19997403Sobrientemplate <class _Pair> struct select2nd : public std::_Select2nd<_Pair> {}; 20097403Sobrien/** @} */ 20197403Sobrien 20297403Sobrien// extension documented next 20397403Sobrientemplate <class _Arg1, class _Arg2> 20497403Sobrienstruct _Project1st : public binary_function<_Arg1, _Arg2, _Arg1> { 20597403Sobrien _Arg1 operator()(const _Arg1& __x, const _Arg2&) const { return __x; } 20697403Sobrien}; 20797403Sobrien 20897403Sobrientemplate <class _Arg1, class _Arg2> 20997403Sobrienstruct _Project2nd : public binary_function<_Arg1, _Arg2, _Arg2> { 21097403Sobrien _Arg2 operator()(const _Arg1&, const _Arg2& __y) const { return __y; } 21197403Sobrien}; 21297403Sobrien 21397403Sobrien/** The @c operator() of the @c project1st functor takes two arbitrary 21497403Sobrien * arguments and returns the first one, while @c project2nd returns the 21597403Sobrien * second one. They are extensions provided by SGI. 21697403Sobrien * 21797403Sobrien * @addtogroup SGIextensions 21897403Sobrien * @{ 21997403Sobrien*/ 22097403Sobrien 22197403Sobrien/// An \link SGIextensions SGI extension \endlink. 22297403Sobrientemplate <class _Arg1, class _Arg2> 22397403Sobrienstruct project1st : public _Project1st<_Arg1, _Arg2> {}; 22497403Sobrien 22597403Sobrien/// An \link SGIextensions SGI extension \endlink. 22697403Sobrientemplate <class _Arg1, class _Arg2> 22797403Sobrienstruct project2nd : public _Project2nd<_Arg1, _Arg2> {}; 22897403Sobrien/** @} */ 22997403Sobrien 23097403Sobrien// extension documented next 23197403Sobrientemplate <class _Result> 23297403Sobrienstruct _Constant_void_fun { 23397403Sobrien typedef _Result result_type; 23497403Sobrien result_type _M_val; 23597403Sobrien 23697403Sobrien _Constant_void_fun(const result_type& __v) : _M_val(__v) {} 23797403Sobrien const result_type& operator()() const { return _M_val; } 23897403Sobrien}; 23997403Sobrien 24097403Sobrientemplate <class _Result, class _Argument> 24197403Sobrienstruct _Constant_unary_fun { 24297403Sobrien typedef _Argument argument_type; 24397403Sobrien typedef _Result result_type; 24497403Sobrien result_type _M_val; 24597403Sobrien 24697403Sobrien _Constant_unary_fun(const result_type& __v) : _M_val(__v) {} 24797403Sobrien const result_type& operator()(const _Argument&) const { return _M_val; } 24897403Sobrien}; 24997403Sobrien 25097403Sobrientemplate <class _Result, class _Arg1, class _Arg2> 25197403Sobrienstruct _Constant_binary_fun { 25297403Sobrien typedef _Arg1 first_argument_type; 25397403Sobrien typedef _Arg2 second_argument_type; 25497403Sobrien typedef _Result result_type; 25597403Sobrien _Result _M_val; 25697403Sobrien 25797403Sobrien _Constant_binary_fun(const _Result& __v) : _M_val(__v) {} 25897403Sobrien const result_type& operator()(const _Arg1&, const _Arg2&) const { 25997403Sobrien return _M_val; 26097403Sobrien } 26197403Sobrien}; 26297403Sobrien 26397403Sobrien/** These three functors are each constructed from a single arbitrary 26497403Sobrien * variable/value. Later, their @c operator()s completely ignore any 26597403Sobrien * arguments passed, and return the stored value. 26697403Sobrien * - @c constant_void_fun's @c operator() takes no arguments 26797403Sobrien * - @c constant_unary_fun's @c operator() takes one argument (ignored) 26897403Sobrien * - @c constant_binary_fun's @c operator() takes two arguments (ignored) 26997403Sobrien * 27097403Sobrien * The helper creator functions @c constant0, @c constant1, and 27197403Sobrien * @c constant2 each take a "result" argument and construct variables of 27297403Sobrien * the appropriate functor type. 27397403Sobrien * 27497403Sobrien * @addtogroup SGIextensions 27597403Sobrien * @{ 27697403Sobrien*/ 27797403Sobrien/// An \link SGIextensions SGI extension \endlink. 27897403Sobrientemplate <class _Result> 27997403Sobrienstruct constant_void_fun : public _Constant_void_fun<_Result> { 28097403Sobrien constant_void_fun(const _Result& __v) : _Constant_void_fun<_Result>(__v) {} 28197403Sobrien}; 28297403Sobrien 28397403Sobrien/// An \link SGIextensions SGI extension \endlink. 28497403Sobrientemplate <class _Result, 28597403Sobrien class _Argument = _Result> 28697403Sobrienstruct constant_unary_fun : public _Constant_unary_fun<_Result, _Argument> 28797403Sobrien{ 28897403Sobrien constant_unary_fun(const _Result& __v) 28997403Sobrien : _Constant_unary_fun<_Result, _Argument>(__v) {} 29097403Sobrien}; 29197403Sobrien 29297403Sobrien/// An \link SGIextensions SGI extension \endlink. 29397403Sobrientemplate <class _Result, 29497403Sobrien class _Arg1 = _Result, 29597403Sobrien class _Arg2 = _Arg1> 29697403Sobrienstruct constant_binary_fun 29797403Sobrien : public _Constant_binary_fun<_Result, _Arg1, _Arg2> 29897403Sobrien{ 29997403Sobrien constant_binary_fun(const _Result& __v) 30097403Sobrien : _Constant_binary_fun<_Result, _Arg1, _Arg2>(__v) {} 30197403Sobrien}; 30297403Sobrien 30397403Sobrien/// An \link SGIextensions SGI extension \endlink. 30497403Sobrientemplate <class _Result> 30597403Sobrieninline constant_void_fun<_Result> constant0(const _Result& __val) 30697403Sobrien{ 30797403Sobrien return constant_void_fun<_Result>(__val); 30897403Sobrien} 30997403Sobrien 31097403Sobrien/// An \link SGIextensions SGI extension \endlink. 31197403Sobrientemplate <class _Result> 31297403Sobrieninline constant_unary_fun<_Result,_Result> constant1(const _Result& __val) 31397403Sobrien{ 31497403Sobrien return constant_unary_fun<_Result,_Result>(__val); 31597403Sobrien} 31697403Sobrien 31797403Sobrien/// An \link SGIextensions SGI extension \endlink. 31897403Sobrientemplate <class _Result> 31997403Sobrieninline constant_binary_fun<_Result,_Result,_Result> 32097403Sobrienconstant2(const _Result& __val) 32197403Sobrien{ 32297403Sobrien return constant_binary_fun<_Result,_Result,_Result>(__val); 32397403Sobrien} 32497403Sobrien/** @} */ 32597403Sobrien 32697403Sobrien/** The @c subtractive_rng class is documented on 32797403Sobrien * <a href="http://www.sgi.com/tech/stl/">SGI's site</a>. 32897403Sobrien * Note that this code assumes that @c int is 32 bits. 32997403Sobrien * 33097403Sobrien * @ingroup SGIextensions 33197403Sobrien*/ 33297403Sobrienclass subtractive_rng : public unary_function<unsigned int, unsigned int> { 33397403Sobrienprivate: 33497403Sobrien unsigned int _M_table[55]; 33597403Sobrien size_t _M_index1; 33697403Sobrien size_t _M_index2; 33797403Sobrienpublic: 33897403Sobrien /// Returns a number less than the argument. 33997403Sobrien unsigned int operator()(unsigned int __limit) { 34097403Sobrien _M_index1 = (_M_index1 + 1) % 55; 34197403Sobrien _M_index2 = (_M_index2 + 1) % 55; 34297403Sobrien _M_table[_M_index1] = _M_table[_M_index1] - _M_table[_M_index2]; 34397403Sobrien return _M_table[_M_index1] % __limit; 34497403Sobrien } 34597403Sobrien 34697403Sobrien void _M_initialize(unsigned int __seed) 34797403Sobrien { 34897403Sobrien unsigned int __k = 1; 34997403Sobrien _M_table[54] = __seed; 35097403Sobrien size_t __i; 35197403Sobrien for (__i = 0; __i < 54; __i++) { 35297403Sobrien size_t __ii = (21 * (__i + 1) % 55) - 1; 35397403Sobrien _M_table[__ii] = __k; 35497403Sobrien __k = __seed - __k; 35597403Sobrien __seed = _M_table[__ii]; 35697403Sobrien } 35797403Sobrien for (int __loop = 0; __loop < 4; __loop++) { 35897403Sobrien for (__i = 0; __i < 55; __i++) 35997403Sobrien _M_table[__i] = _M_table[__i] - _M_table[(1 + __i + 30) % 55]; 36097403Sobrien } 36197403Sobrien _M_index1 = 0; 36297403Sobrien _M_index2 = 31; 36397403Sobrien } 36497403Sobrien 36597403Sobrien /// Ctor allowing you to initialize the seed. 36697403Sobrien subtractive_rng(unsigned int __seed) { _M_initialize(__seed); } 36797403Sobrien /// Default ctor; initializes its state with some number you don't see. 36897403Sobrien subtractive_rng() { _M_initialize(161803398u); } 36997403Sobrien}; 37097403Sobrien 37197403Sobrien// Mem_fun adaptor helper functions mem_fun1 and mem_fun1_ref, 37297403Sobrien// provided for backward compatibility, they are no longer part of 37397403Sobrien// the C++ standard. 37497403Sobrien 37597403Sobrientemplate <class _Ret, class _Tp, class _Arg> 37697403Sobrieninline mem_fun1_t<_Ret,_Tp,_Arg> mem_fun1(_Ret (_Tp::*__f)(_Arg)) 37797403Sobrien { return mem_fun1_t<_Ret,_Tp,_Arg>(__f); } 37897403Sobrien 37997403Sobrientemplate <class _Ret, class _Tp, class _Arg> 38097403Sobrieninline const_mem_fun1_t<_Ret,_Tp,_Arg> mem_fun1(_Ret (_Tp::*__f)(_Arg) const) 38197403Sobrien { return const_mem_fun1_t<_Ret,_Tp,_Arg>(__f); } 38297403Sobrien 38397403Sobrientemplate <class _Ret, class _Tp, class _Arg> 38497403Sobrieninline mem_fun1_ref_t<_Ret,_Tp,_Arg> mem_fun1_ref(_Ret (_Tp::*__f)(_Arg)) 38597403Sobrien { return mem_fun1_ref_t<_Ret,_Tp,_Arg>(__f); } 38697403Sobrien 38797403Sobrientemplate <class _Ret, class _Tp, class _Arg> 38897403Sobrieninline const_mem_fun1_ref_t<_Ret,_Tp,_Arg> 38997403Sobrienmem_fun1_ref(_Ret (_Tp::*__f)(_Arg) const) 39097403Sobrien { return const_mem_fun1_ref_t<_Ret,_Tp,_Arg>(__f); } 39197403Sobrien 39297403Sobrien} // namespace __gnu_cxx 39397403Sobrien 39497403Sobrien#endif /* _EXT_FUNCTIONAL */ 39597403Sobrien 396