ext/functional

Go to the documentation of this file.
00001 // Functional extensions -*- C++ -*-
00002 
00003 // Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2009
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /*
00027  *
00028  * Copyright (c) 1994
00029  * Hewlett-Packard Company
00030  *
00031  * Permission to use, copy, modify, distribute and sell this software
00032  * and its documentation for any purpose is hereby granted without fee,
00033  * provided that the above copyright notice appear in all copies and
00034  * that both that copyright notice and this permission notice appear
00035  * in supporting documentation.  Hewlett-Packard Company makes no
00036  * representations about the suitability of this software for any
00037  * purpose.  It is provided "as is" without express or implied warranty.
00038  *
00039  *
00040  * Copyright (c) 1996
00041  * Silicon Graphics Computer Systems, Inc.
00042  *
00043  * Permission to use, copy, modify, distribute and sell this software
00044  * and its documentation for any purpose is hereby granted without fee,
00045  * provided that the above copyright notice appear in all copies and
00046  * that both that copyright notice and this permission notice appear
00047  * in supporting documentation.  Silicon Graphics makes no
00048  * representations about the suitability of this software for any
00049  * purpose.  It is provided "as is" without express or implied warranty.
00050  */
00051 
00052 /** @file ext/functional
00053  *  This file is a GNU extension to the Standard C++ Library (possibly
00054  *  containing extensions from the HP/SGI STL subset).
00055  */
00056 
00057 #ifndef _EXT_FUNCTIONAL
00058 #define _EXT_FUNCTIONAL 1
00059 
00060 #pragma GCC system_header
00061 
00062 #include <functional>
00063 #include <cstddef>
00064 
00065 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00066 
00067   using std::size_t;
00068   using std::unary_function;
00069   using std::binary_function;
00070   using std::mem_fun1_t;
00071   using std::const_mem_fun1_t;
00072   using std::mem_fun1_ref_t;
00073   using std::const_mem_fun1_ref_t;
00074 
00075   /** The @c identity_element functions are not part of the C++
00076    *  standard; SGI provided them as an extension.  Its argument is an
00077    *  operation, and its return value is the identity element for that
00078    *  operation.  It is overloaded for addition and multiplication,
00079    *  and you can overload it for your own nefarious operations.
00080    *
00081    *  @addtogroup SGIextensions
00082    *  @{
00083    */
00084   /// An \link SGIextensions SGI extension \endlink.
00085   template <class _Tp>
00086     inline _Tp
00087     identity_element(std::plus<_Tp>)
00088     { return _Tp(0); }
00089 
00090   /// An \link SGIextensions SGI extension \endlink.
00091   template <class _Tp>
00092     inline _Tp
00093     identity_element(std::multiplies<_Tp>)
00094     { return _Tp(1); }
00095   /** @}  */
00096   
00097   /** As an extension to the binders, SGI provided composition functors and
00098    *  wrapper functions to aid in their creation.  The @c unary_compose
00099    *  functor is constructed from two functions/functors, @c f and @c g.
00100    *  Calling @c operator() with a single argument @c x returns @c f(g(x)).
00101    *  The function @c compose1 takes the two functions and constructs a
00102    *  @c unary_compose variable for you.
00103    *
00104    *  @c binary_compose is constructed from three functors, @c f, @c g1,
00105    *  and @c g2.  Its @c operator() returns @c f(g1(x),g2(x)).  The function
00106    *  @compose2 takes f, g1, and g2, and constructs the @c binary_compose
00107    *  instance for you.  For example, if @c f returns an int, then
00108    *  \code
00109    *  int answer = (compose2(f,g1,g2))(x);
00110    *  \endcode
00111    *  is equivalent to
00112    *  \code
00113    *  int temp1 = g1(x);
00114    *  int temp2 = g2(x);
00115    *  int answer = f(temp1,temp2);
00116    *  \endcode
00117    *  But the first form is more compact, and can be passed around as a
00118    *  functor to other algorithms.
00119    *
00120    *  @addtogroup SGIextensions
00121    *  @{
00122    */
00123   /// An \link SGIextensions SGI extension \endlink.
00124   template <class _Operation1, class _Operation2>
00125     class unary_compose
00126     : public unary_function<typename _Operation2::argument_type,
00127                 typename _Operation1::result_type>
00128     {
00129     protected:
00130       _Operation1 _M_fn1;
00131       _Operation2 _M_fn2;
00132 
00133     public:
00134       unary_compose(const _Operation1& __x, const _Operation2& __y)
00135       : _M_fn1(__x), _M_fn2(__y) {}
00136 
00137       typename _Operation1::result_type
00138       operator()(const typename _Operation2::argument_type& __x) const
00139       { return _M_fn1(_M_fn2(__x)); }
00140     };
00141 
00142   /// An \link SGIextensions SGI extension \endlink.
00143   template <class _Operation1, class _Operation2>
00144     inline unary_compose<_Operation1, _Operation2>
00145     compose1(const _Operation1& __fn1, const _Operation2& __fn2)
00146     { return unary_compose<_Operation1,_Operation2>(__fn1, __fn2); }
00147 
00148   /// An \link SGIextensions SGI extension \endlink.
00149   template <class _Operation1, class _Operation2, class _Operation3>
00150     class binary_compose
00151     : public unary_function<typename _Operation2::argument_type,
00152                 typename _Operation1::result_type>
00153     {
00154     protected:
00155       _Operation1 _M_fn1;
00156       _Operation2 _M_fn2;
00157       _Operation3 _M_fn3;
00158       
00159     public:
00160       binary_compose(const _Operation1& __x, const _Operation2& __y,
00161              const _Operation3& __z)
00162       : _M_fn1(__x), _M_fn2(__y), _M_fn3(__z) { }
00163 
00164       typename _Operation1::result_type
00165       operator()(const typename _Operation2::argument_type& __x) const
00166       { return _M_fn1(_M_fn2(__x), _M_fn3(__x)); }
00167     };
00168 
00169   /// An \link SGIextensions SGI extension \endlink.
00170   template <class _Operation1, class _Operation2, class _Operation3>
00171     inline binary_compose<_Operation1, _Operation2, _Operation3>
00172     compose2(const _Operation1& __fn1, const _Operation2& __fn2,
00173          const _Operation3& __fn3)
00174     { return binary_compose<_Operation1, _Operation2, _Operation3>
00175     (__fn1, __fn2, __fn3); }
00176   /** @}  */
00177 
00178   /** As an extension, SGI provided a functor called @c identity.  When a
00179    *  functor is required but no operations are desired, this can be used as a
00180    *  pass-through.  Its @c operator() returns its argument unchanged.
00181    *
00182    *  @addtogroup SGIextensions
00183    */
00184   template <class _Tp>
00185     struct identity : public std::_Identity<_Tp> {};
00186 
00187   /** @c select1st and @c select2nd are extensions provided by SGI.  Their
00188    *  @c operator()s
00189    *  take a @c std::pair as an argument, and return either the first member
00190    *  or the second member, respectively.  They can be used (especially with
00191    *  the composition functors) to "strip" data from a sequence before
00192    *  performing the remainder of an algorithm.
00193    *
00194    *  @addtogroup SGIextensions
00195    *  @{
00196    */
00197   /// An \link SGIextensions SGI extension \endlink.
00198   template <class _Pair>
00199     struct select1st : public std::_Select1st<_Pair> {};
00200 
00201   /// An \link SGIextensions SGI extension \endlink.
00202   template <class _Pair>
00203     struct select2nd : public std::_Select2nd<_Pair> {};
00204   /** @}  */
00205 
00206   // extension documented next
00207   template <class _Arg1, class _Arg2>
00208     struct _Project1st : public binary_function<_Arg1, _Arg2, _Arg1>
00209     {
00210       _Arg1
00211       operator()(const _Arg1& __x, const _Arg2&) const
00212       { return __x; }
00213     };
00214 
00215   template <class _Arg1, class _Arg2>
00216     struct _Project2nd : public binary_function<_Arg1, _Arg2, _Arg2>
00217     {
00218       _Arg2
00219       operator()(const _Arg1&, const _Arg2& __y) const
00220       { return __y; }
00221     };
00222 
00223   /** The @c operator() of the @c project1st functor takes two arbitrary
00224    *  arguments and returns the first one, while @c project2nd returns the
00225    *  second one.  They are extensions provided by SGI.
00226    *
00227    *  @addtogroup SGIextensions
00228    *  @{
00229    */
00230 
00231   /// An \link SGIextensions SGI extension \endlink.
00232   template <class _Arg1, class _Arg2>
00233     struct project1st : public _Project1st<_Arg1, _Arg2> {};
00234 
00235   /// An \link SGIextensions SGI extension \endlink.
00236   template <class _Arg1, class _Arg2>
00237     struct project2nd : public _Project2nd<_Arg1, _Arg2> {};
00238   /** @}  */
00239 
00240   // extension documented next
00241   template <class _Result>
00242     struct _Constant_void_fun
00243     {
00244       typedef _Result result_type;
00245       result_type _M_val;
00246 
00247       _Constant_void_fun(const result_type& __v) : _M_val(__v) {}
00248 
00249       const result_type&
00250       operator()() const
00251       { return _M_val; }
00252     };
00253 
00254   template <class _Result, class _Argument>
00255     struct _Constant_unary_fun
00256     {
00257       typedef _Argument argument_type;
00258       typedef  _Result  result_type;
00259       result_type _M_val;
00260       
00261       _Constant_unary_fun(const result_type& __v) : _M_val(__v) {}
00262 
00263       const result_type&
00264       operator()(const _Argument&) const
00265       { return _M_val; }
00266     };
00267 
00268   template <class _Result, class _Arg1, class _Arg2>
00269     struct _Constant_binary_fun
00270     {
00271       typedef  _Arg1   first_argument_type;
00272       typedef  _Arg2   second_argument_type;
00273       typedef  _Result result_type;
00274       _Result _M_val;
00275 
00276       _Constant_binary_fun(const _Result& __v) : _M_val(__v) {}
00277       
00278       const result_type&
00279       operator()(const _Arg1&, const _Arg2&) const
00280       { return _M_val; }
00281     };
00282 
00283   /** These three functors are each constructed from a single arbitrary
00284    *  variable/value.  Later, their @c operator()s completely ignore any
00285    *  arguments passed, and return the stored value.
00286    *  - @c constant_void_fun's @c operator() takes no arguments
00287    *  - @c constant_unary_fun's @c operator() takes one argument (ignored)
00288    *  - @c constant_binary_fun's @c operator() takes two arguments (ignored)
00289    *
00290    *  The helper creator functions @c constant0, @c constant1, and
00291    *  @c constant2 each take a "result" argument and construct variables of
00292    *  the appropriate functor type.
00293    *
00294    *  @addtogroup SGIextensions
00295    *  @{
00296    */
00297   /// An \link SGIextensions SGI extension \endlink.
00298   template <class _Result>
00299     struct constant_void_fun
00300     : public _Constant_void_fun<_Result>
00301     {
00302       constant_void_fun(const _Result& __v)
00303       : _Constant_void_fun<_Result>(__v) {}
00304     };
00305 
00306   /// An \link SGIextensions SGI extension \endlink.
00307   template <class _Result, class _Argument = _Result>
00308     struct constant_unary_fun : public _Constant_unary_fun<_Result, _Argument>
00309     {
00310       constant_unary_fun(const _Result& __v)
00311       : _Constant_unary_fun<_Result, _Argument>(__v) {}
00312     };
00313 
00314   /// An \link SGIextensions SGI extension \endlink.
00315   template <class _Result, class _Arg1 = _Result, class _Arg2 = _Arg1>
00316     struct constant_binary_fun
00317     : public _Constant_binary_fun<_Result, _Arg1, _Arg2>
00318     {
00319       constant_binary_fun(const _Result& __v)
00320       : _Constant_binary_fun<_Result, _Arg1, _Arg2>(__v) {}
00321     };
00322 
00323   /// An \link SGIextensions SGI extension \endlink.
00324   template <class _Result>
00325     inline constant_void_fun<_Result>
00326     constant0(const _Result& __val)
00327     { return constant_void_fun<_Result>(__val); }
00328 
00329   /// An \link SGIextensions SGI extension \endlink.
00330   template <class _Result>
00331     inline constant_unary_fun<_Result, _Result>
00332     constant1(const _Result& __val)
00333     { return constant_unary_fun<_Result, _Result>(__val); }
00334 
00335   /// An \link SGIextensions SGI extension \endlink.
00336   template <class _Result>
00337     inline constant_binary_fun<_Result,_Result,_Result>
00338     constant2(const _Result& __val)
00339     { return constant_binary_fun<_Result, _Result, _Result>(__val); }
00340   /** @}  */
00341 
00342   /** The @c subtractive_rng class is documented on
00343    *  <a href="http://www.sgi.com/tech/stl/">SGI's site</a>.
00344    *  Note that this code assumes that @c int is 32 bits.
00345    *
00346    *  @ingroup SGIextensions
00347    */
00348   class subtractive_rng
00349   : public unary_function<unsigned int, unsigned int>
00350   {
00351   private:
00352     unsigned int _M_table[55];
00353     size_t _M_index1;
00354     size_t _M_index2;
00355 
00356   public:
00357     /// Returns a number less than the argument.
00358     unsigned int
00359     operator()(unsigned int __limit)
00360     {
00361       _M_index1 = (_M_index1 + 1) % 55;
00362       _M_index2 = (_M_index2 + 1) % 55;
00363       _M_table[_M_index1] = _M_table[_M_index1] - _M_table[_M_index2];
00364       return _M_table[_M_index1] % __limit;
00365     }
00366 
00367     void
00368     _M_initialize(unsigned int __seed)
00369     {
00370       unsigned int __k = 1;
00371       _M_table[54] = __seed;
00372       size_t __i;
00373       for (__i = 0; __i < 54; __i++)
00374     {
00375       size_t __ii = (21 * (__i + 1) % 55) - 1;
00376       _M_table[__ii] = __k;
00377       __k = __seed - __k;
00378       __seed = _M_table[__ii];
00379     }
00380       for (int __loop = 0; __loop < 4; __loop++)
00381     {
00382       for (__i = 0; __i < 55; __i++)
00383             _M_table[__i] = _M_table[__i] - _M_table[(1 + __i + 30) % 55];
00384     }
00385       _M_index1 = 0;
00386       _M_index2 = 31;
00387     }
00388 
00389     /// Ctor allowing you to initialize the seed.
00390     subtractive_rng(unsigned int __seed)
00391     { _M_initialize(__seed); }
00392 
00393     /// Default ctor; initializes its state with some number you don't see.
00394     subtractive_rng()
00395     { _M_initialize(161803398u); }
00396   };
00397 
00398   // Mem_fun adaptor helper functions mem_fun1 and mem_fun1_ref,
00399   // provided for backward compatibility, they are no longer part of
00400   // the C++ standard.
00401   
00402   template <class _Ret, class _Tp, class _Arg>
00403     inline mem_fun1_t<_Ret, _Tp, _Arg>
00404     mem_fun1(_Ret (_Tp::*__f)(_Arg))
00405     { return mem_fun1_t<_Ret, _Tp, _Arg>(__f); }
00406 
00407   template <class _Ret, class _Tp, class _Arg>
00408     inline const_mem_fun1_t<_Ret, _Tp, _Arg>
00409     mem_fun1(_Ret (_Tp::*__f)(_Arg) const)
00410     { return const_mem_fun1_t<_Ret, _Tp, _Arg>(__f); }
00411 
00412   template <class _Ret, class _Tp, class _Arg>
00413     inline mem_fun1_ref_t<_Ret, _Tp, _Arg>
00414     mem_fun1_ref(_Ret (_Tp::*__f)(_Arg))
00415     { return mem_fun1_ref_t<_Ret, _Tp, _Arg>(__f); }
00416 
00417   template <class _Ret, class _Tp, class _Arg>
00418     inline const_mem_fun1_ref_t<_Ret, _Tp, _Arg>
00419     mem_fun1_ref(_Ret (_Tp::*__f)(_Arg) const)
00420     { return const_mem_fun1_ref_t<_Ret, _Tp, _Arg>(__f); }
00421 
00422 _GLIBCXX_END_NAMESPACE
00423 
00424 #endif
00425 

Generated on Thu Jul 23 21:16:06 2009 for libstdc++ by  doxygen 1.5.8