00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
#ifndef _EXT_FUNCTIONAL
00063
#define _EXT_FUNCTIONAL 1
00064
00065
#pragma GCC system_header
00066
00067
#include <functional>
00068
00069
namespace __gnu_cxx
00070 {
00071
using std::unary_function;
00072
using std::binary_function;
00073
using std::mem_fun1_t;
00074
using std::const_mem_fun1_t;
00075
using std::mem_fun1_ref_t;
00076
using std::const_mem_fun1_ref_t;
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088 template <
class _Tp>
inline _Tp
identity_element(
std::plus<_Tp>) {
00089
return _Tp(0);
00090 }
00091
00092 template <
class _Tp>
inline _Tp
identity_element(
std::multiplies<_Tp>) {
00093
return _Tp(1);
00094 }
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
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
public:
00133
unary_compose(
const _Operation1& __x,
const _Operation2& __y)
00134 : _M_fn1(__x), _M_fn2(__y) {}
00135
typename _Operation1::result_type
00136 operator()(
const typename _Operation2::argument_type& __x)
const {
00137
return _M_fn1(_M_fn2(__x));
00138 }
00139 };
00140
00141
00142
template <
class _Operation1,
class _Operation2>
00143
inline unary_compose<_Operation1,_Operation2>
00144 compose1(
const _Operation1& __fn1,
const _Operation2& __fn2)
00145 {
00146
return unary_compose<_Operation1,_Operation2>(__fn1, __fn2);
00147 }
00148
00149
00150
template <
class _Operation1,
class _Operation2,
class _Operation3>
00151 class binary_compose
00152 :
public unary_function<typename _Operation2::argument_type,
00153 typename _Operation1::result_type> {
00154
protected:
00155 _Operation1 _M_fn1;
00156 _Operation2 _M_fn2;
00157 _Operation3 _M_fn3;
00158
public:
00159
binary_compose(
const _Operation1& __x,
const _Operation2& __y,
00160
const _Operation3& __z)
00161 : _M_fn1(__x), _M_fn2(__y), _M_fn3(__z) { }
00162
typename _Operation1::result_type
00163 operator()(
const typename _Operation2::argument_type& __x)
const {
00164
return _M_fn1(_M_fn2(__x), _M_fn3(__x));
00165 }
00166 };
00167
00168
00169
template <
class _Operation1,
class _Operation2,
class _Operation3>
00170
inline binary_compose<_Operation1, _Operation2, _Operation3>
00171 compose2(
const _Operation1& __fn1,
const _Operation2& __fn2,
00172
const _Operation3& __fn3)
00173 {
00174
return binary_compose<_Operation1,_Operation2,_Operation3>
00175 (__fn1, __fn2, __fn3);
00176 }
00177
00178
00179
00180
00181
00182
00183
00184
00185
template <
class _Tp>
struct identity :
public std::_Identity<_Tp> {};
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198 template <
class _Pair>
struct select1st :
public std::_Select1st<_Pair> {};
00199
00200 template <
class _Pair>
struct select2nd :
public std::_Select2nd<_Pair> {};
00201
00202
00203
00204
template <
class _Arg1,
class _Arg2>
00205
struct _Project1st :
public binary_function<_Arg1, _Arg2, _Arg1> {
00206 _Arg1 operator()(
const _Arg1& __x,
const _Arg2&)
const {
return __x; }
00207 };
00208
00209
template <
class _Arg1,
class _Arg2>
00210
struct _Project2nd :
public binary_function<_Arg1, _Arg2, _Arg2> {
00211 _Arg2 operator()(
const _Arg1&,
const _Arg2& __y)
const {
return __y; }
00212 };
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
template <
class _Arg1,
class _Arg2>
00224 struct project1st :
public _Project1st<_Arg1, _Arg2> {};
00225
00226
00227
template <
class _Arg1,
class _Arg2>
00228 struct project2nd :
public _Project2nd<_Arg1, _Arg2> {};
00229
00230
00231
00232
template <
class _Result>
00233
struct _Constant_void_fun {
00234
typedef _Result result_type;
00235 result_type _M_val;
00236
00237 _Constant_void_fun(
const result_type& __v) : _M_val(__v) {}
00238
const result_type& operator()()
const {
return _M_val; }
00239 };
00240
00241
template <
class _Result,
class _Argument>
00242
struct _Constant_unary_fun {
00243
typedef _Argument argument_type;
00244
typedef _Result result_type;
00245 result_type _M_val;
00246
00247 _Constant_unary_fun(
const result_type& __v) : _M_val(__v) {}
00248
const result_type& operator()(
const _Argument&)
const {
return _M_val; }
00249 };
00250
00251
template <
class _Result,
class _Arg1,
class _Arg2>
00252
struct _Constant_binary_fun {
00253
typedef _Arg1 first_argument_type;
00254
typedef _Arg2 second_argument_type;
00255
typedef _Result result_type;
00256 _Result _M_val;
00257
00258 _Constant_binary_fun(
const _Result& __v) : _M_val(__v) {}
00259
const result_type& operator()(
const _Arg1&,
const _Arg2&)
const {
00260
return _M_val;
00261 }
00262 };
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279
template <
class _Result>
00280 struct constant_void_fun :
public _Constant_void_fun<_Result> {
00281
constant_void_fun(
const _Result& __v) : _Constant_void_fun<_Result>(__v) {}
00282 };
00283
00284
00285
template <
class _Result,
00286
class _Argument = _Result>
00287 struct constant_unary_fun :
public _Constant_unary_fun<_Result, _Argument>
00288 {
00289
constant_unary_fun(
const _Result& __v)
00290 : _Constant_unary_fun<_Result, _Argument>(__v) {}
00291 };
00292
00293
00294
template <
class _Result,
00295
class _Arg1 = _Result,
00296
class _Arg2 = _Arg1>
00297 struct constant_binary_fun
00298 :
public _Constant_binary_fun<_Result, _Arg1, _Arg2>
00299 {
00300
constant_binary_fun(
const _Result& __v)
00301 : _Constant_binary_fun<_Result, _Arg1, _Arg2>(__v) {}
00302 };
00303
00304
00305
template <
class _Result>
00306 inline constant_void_fun<_Result>
constant0(
const _Result& __val)
00307 {
00308
return constant_void_fun<_Result>(__val);
00309 }
00310
00311
00312
template <
class _Result>
00313 inline constant_unary_fun<_Result,_Result>
constant1(
const _Result& __val)
00314 {
00315
return constant_unary_fun<_Result,_Result>(__val);
00316 }
00317
00318
00319
template <
class _Result>
00320
inline constant_binary_fun<_Result,_Result,_Result>
00321 constant2(
const _Result& __val)
00322 {
00323
return constant_binary_fun<_Result,_Result,_Result>(__val);
00324 }
00325
00326
00327
00328
00329
00330
00331
00332
00333 class subtractive_rng :
public unary_function<unsigned int, unsigned int> {
00334
private:
00335
unsigned int _M_table[55];
00336 size_t _M_index1;
00337 size_t _M_index2;
00338
public:
00339
00340 unsigned int operator()(
unsigned int __limit) {
00341 _M_index1 = (_M_index1 + 1) % 55;
00342 _M_index2 = (_M_index2 + 1) % 55;
00343 _M_table[_M_index1] = _M_table[_M_index1] - _M_table[_M_index2];
00344
return _M_table[_M_index1] % __limit;
00345 }
00346
00347
void _M_initialize(
unsigned int __seed)
00348 {
00349
unsigned int __k = 1;
00350 _M_table[54] = __seed;
00351 size_t __i;
00352
for (__i = 0; __i < 54; __i++) {
00353 size_t __ii = (21 * (__i + 1) % 55) - 1;
00354 _M_table[__ii] = __k;
00355 __k = __seed - __k;
00356 __seed = _M_table[__ii];
00357 }
00358
for (
int __loop = 0; __loop < 4; __loop++) {
00359
for (__i = 0; __i < 55; __i++)
00360 _M_table[__i] = _M_table[__i] - _M_table[(1 + __i + 30) % 55];
00361 }
00362 _M_index1 = 0;
00363 _M_index2 = 31;
00364 }
00365
00366
00367 subtractive_rng(
unsigned int __seed) { _M_initialize(__seed); }
00368
00369 subtractive_rng() { _M_initialize(161803398u); }
00370 };
00371
00372
00373
00374
00375
00376
template <
class _Ret,
class _Tp,
class _Arg>
00377
inline mem_fun1_t<_Ret,_Tp,_Arg> mem_fun1(_Ret (_Tp::*__f)(_Arg))
00378 {
return mem_fun1_t<_Ret,_Tp,_Arg>(__f); }
00379
00380
template <
class _Ret,
class _Tp,
class _Arg>
00381
inline const_mem_fun1_t<_Ret,_Tp,_Arg> mem_fun1(_Ret (_Tp::*__f)(_Arg)
const)
00382 {
return const_mem_fun1_t<_Ret,_Tp,_Arg>(__f); }
00383
00384
template <
class _Ret,
class _Tp,
class _Arg>
00385
inline mem_fun1_ref_t<_Ret,_Tp,_Arg> mem_fun1_ref(_Ret (_Tp::*__f)(_Arg))
00386 {
return mem_fun1_ref_t<_Ret,_Tp,_Arg>(__f); }
00387
00388
template <
class _Ret,
class _Tp,
class _Arg>
00389
inline const_mem_fun1_ref_t<_Ret,_Tp,_Arg>
00390 mem_fun1_ref(_Ret (_Tp::*__f)(_Arg)
const)
00391 {
return const_mem_fun1_ref_t<_Ret,_Tp,_Arg>(__f); }
00392 }
00393
00394
#endif
00395