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 #ifndef _CPP_BITS_ARRAY_H
00038 #define _CPP_BITS_ARRAY_H 1
00039
00040 #pragma GCC system_header
00041
00042 #include <bits/c++config.h>
00043 #include <bits/cpp_type_traits.h>
00044 #include <cstdlib>
00045 #include <cstring>
00046 #include <new>
00047
00048 namespace std
00049 {
00050
00051
00052
00053
00054
00055 inline void*
00056 __valarray_get_memory(size_t __n)
00057 { return operator new(__n); }
00058
00059 template<typename _Tp>
00060 inline _Tp*__restrict__
00061 __valarray_get_storage(size_t __n)
00062 {
00063 return static_cast<_Tp*__restrict__>
00064 (__valarray_get_memory(__n * sizeof(_Tp)));
00065 }
00066
00067
00068 inline void
00069 __valarray_release_memory(void* __p)
00070 { operator delete(__p); }
00071
00072
00073
00074 template<typename _Tp, bool>
00075 struct _Array_default_ctor
00076 {
00077
00078
00079 inline static void
00080 _S_do_it(_Tp* __restrict__ __b, _Tp* __restrict__ __e)
00081 { while (__b != __e) new(__b++) _Tp(); }
00082 };
00083
00084 template<typename _Tp>
00085 struct _Array_default_ctor<_Tp, true>
00086 {
00087
00088 inline static void
00089 _S_do_it(_Tp* __restrict__ __b, _Tp* __restrict__ __e)
00090 { memset(__b, 0, (__e - __b)*sizeof(_Tp)); }
00091 };
00092
00093 template<typename _Tp>
00094 inline void
00095 __valarray_default_construct(_Tp* __restrict__ __b, _Tp* __restrict__ __e)
00096 {
00097 _Array_default_ctor<_Tp, __is_fundamental<_Tp>::_M_type>::
00098 _S_do_it(__b, __e);
00099 }
00100
00101
00102
00103
00104 template<typename _Tp, bool>
00105 struct _Array_init_ctor
00106 {
00107
00108
00109 inline static void
00110 _S_do_it(_Tp* __restrict__ __b, _Tp* __restrict__ __e, const _Tp __t)
00111 { while (__b != __e) new(__b++) _Tp(__t); }
00112 };
00113
00114 template<typename _Tp>
00115 struct _Array_init_ctor<_Tp, true>
00116 {
00117 inline static void
00118 _S_do_it(_Tp* __restrict__ __b, _Tp* __restrict__ __e, const _Tp __t)
00119 { while (__b != __e) *__b++ = __t; }
00120 };
00121
00122 template<typename _Tp>
00123 inline void
00124 __valarray_fill_construct(_Tp* __restrict__ __b, _Tp* __restrict__ __e,
00125 const _Tp __t)
00126 {
00127 _Array_init_ctor<_Tp, __is_fundamental<_Tp>::_M_type>::
00128 _S_do_it(__b, __e, __t);
00129 }
00130
00131
00132
00133
00134
00135 template<typename _Tp, bool>
00136 struct _Array_copy_ctor
00137 {
00138
00139
00140 inline static void
00141 _S_do_it(const _Tp* __restrict__ __b, const _Tp* __restrict__ __e,
00142 _Tp* __restrict__ __o)
00143 { while (__b != __e) new(__o++) _Tp(*__b++); }
00144 };
00145
00146 template<typename _Tp>
00147 struct _Array_copy_ctor<_Tp, true>
00148 {
00149 inline static void
00150 _S_do_it(const _Tp* __restrict__ __b, const _Tp* __restrict__ __e,
00151 _Tp* __restrict__ __o)
00152 { memcpy(__o, __b, (__e - __b)*sizeof(_Tp)); }
00153 };
00154
00155 template<typename _Tp>
00156 inline void
00157 __valarray_copy_construct(const _Tp* __restrict__ __b,
00158 const _Tp* __restrict__ __e,
00159 _Tp* __restrict__ __o)
00160 {
00161 _Array_copy_ctor<_Tp, __is_fundamental<_Tp>::_M_type>::
00162 _S_do_it(__b, __e, __o);
00163 }
00164
00165
00166 template<typename _Tp>
00167 inline void
00168 __valarray_copy_construct (const _Tp* __restrict__ __a, size_t __n,
00169 size_t __s, _Tp* __restrict__ __o)
00170 {
00171 if (__is_fundamental<_Tp>::_M_type)
00172 while (__n--) { *__o++ = *__a; __a += __s; }
00173 else
00174 while (__n--) { new(__o++) _Tp(*__a); __a += __s; }
00175 }
00176
00177
00178 template<typename _Tp>
00179 inline void
00180 __valarray_copy_construct (const _Tp* __restrict__ __a,
00181 const size_t* __restrict__ __i,
00182 _Tp* __restrict__ __o, size_t __n)
00183 {
00184 if (__is_fundamental<_Tp>::_M_type)
00185 while (__n--) *__o++ = __a[*__i++];
00186 else
00187 while (__n--) new (__o++) _Tp(__a[*__i++]);
00188 }
00189
00190
00191 template<typename _Tp>
00192 inline void
00193 __valarray_destroy_elements(_Tp* __restrict__ __b, _Tp* __restrict__ __e)
00194 {
00195 if (!__is_fundamental<_Tp>::_M_type)
00196 while (__b != __e) { __b->~_Tp(); ++__b; }
00197 }
00198
00199
00200 template<typename _Tp>
00201 inline void
00202 __valarray_fill (_Tp* __restrict__ __a, size_t __n, const _Tp& __t)
00203 { while (__n--) *__a++ = __t; }
00204
00205
00206 template<typename _Tp>
00207 inline void
00208 __valarray_fill (_Tp* __restrict__ __a, size_t __n,
00209 size_t __s, const _Tp& __t)
00210 { for (size_t __i=0; __i<__n; ++__i, __a+=__s) *__a = __t; }
00211
00212
00213 template<typename _Tp>
00214 inline void
00215 __valarray_fill(_Tp* __restrict__ __a, const size_t* __restrict__ __i,
00216 size_t __n, const _Tp& __t)
00217 { for (size_t __j=0; __j<__n; ++__j, ++__i) __a[*__i] = __t; }
00218
00219
00220
00221 template<typename _Tp, bool>
00222 struct _Array_copier
00223 {
00224 inline static void
00225 _S_do_it(const _Tp* __restrict__ __a, size_t __n, _Tp* __restrict__ __b)
00226 { while (__n--) *__b++ = *__a++; }
00227 };
00228
00229 template<typename _Tp>
00230 struct _Array_copier<_Tp, true>
00231 {
00232 inline static void
00233 _S_do_it(const _Tp* __restrict__ __a, size_t __n, _Tp* __restrict__ __b)
00234 { memcpy (__b, __a, __n * sizeof (_Tp)); }
00235 };
00236
00237
00238 template<typename _Tp>
00239 inline void
00240 __valarray_copy(const _Tp* __restrict__ __a, size_t __n,
00241 _Tp* __restrict__ __b)
00242 {
00243 _Array_copier<_Tp, __is_fundamental<_Tp>::_M_type>::
00244 _S_do_it(__a, __n, __b);
00245 }
00246
00247
00248 template<typename _Tp>
00249 inline void
00250 __valarray_copy(const _Tp* __restrict__ __a, size_t __n, size_t __s,
00251 _Tp* __restrict__ __b)
00252 { for (size_t __i=0; __i<__n; ++__i, ++__b, __a += __s) *__b = *__a; }
00253
00254
00255 template<typename _Tp>
00256 inline void
00257 __valarray_copy(const _Tp* __restrict__ __a, _Tp* __restrict__ __b,
00258 size_t __n, size_t __s)
00259 { for (size_t __i=0; __i<__n; ++__i, ++__a, __b+=__s) *__b = *__a; }
00260
00261
00262
00263 template<typename _Tp>
00264 inline void
00265 __valarray_copy(const _Tp* __restrict__ __src, size_t __n, size_t __s1,
00266 _Tp* __restrict__ __dst, size_t __s2)
00267 {
00268 for (size_t __i = 0; __i < __n; ++__i)
00269 __dst[__i * __s2] = __src [ __i * __s1];
00270 }
00271
00272
00273
00274 template<typename _Tp>
00275 inline void
00276 __valarray_copy (const _Tp* __restrict__ __a,
00277 const size_t* __restrict__ __i,
00278 _Tp* __restrict__ __b, size_t __n)
00279 { for (size_t __j=0; __j<__n; ++__j, ++__b, ++__i) *__b = __a[*__i]; }
00280
00281
00282 template<typename _Tp>
00283 inline void
00284 __valarray_copy (const _Tp* __restrict__ __a, size_t __n,
00285 _Tp* __restrict__ __b, const size_t* __restrict__ __i)
00286 { for (size_t __j=0; __j<__n; ++__j, ++__a, ++__i) __b[*__i] = *__a; }
00287
00288
00289
00290 template<typename _Tp>
00291 inline void
00292 __valarray_copy(const _Tp* __restrict__ __src, size_t __n,
00293 const size_t* __restrict__ __i,
00294 _Tp* __restrict__ __dst, const size_t* __restrict__ __j)
00295 {
00296 for (size_t __k = 0; __k < __n; ++__k)
00297 __dst[*__j++] = __src[*__i++];
00298 }
00299
00300
00301
00302
00303
00304
00305
00306
00307 template<typename _Tp>
00308 inline _Tp
00309 __valarray_sum(const _Tp* __restrict__ __f, const _Tp* __restrict__ __l)
00310 {
00311 _Tp __r = _Tp();
00312 while (__f != __l) __r += *__f++;
00313 return __r;
00314 }
00315
00316
00317 template<typename _Tp>
00318 inline _Tp
00319 __valarray_product(const _Tp* __restrict__ __f,
00320 const _Tp* __restrict__ __l)
00321 {
00322 _Tp __r = _Tp(1);
00323 while (__f != __l) __r = __r * *__f++;
00324 return __r;
00325 }
00326
00327
00328 template<typename _Ta>
00329 inline typename _Ta::value_type
00330 __valarray_min(const _Ta& __a)
00331 {
00332 size_t __s = __a.size();
00333 typedef typename _Ta::value_type _Value_type;
00334 _Value_type __r = __s == 0 ? _Value_type() : __a[0];
00335 for (size_t __i = 1; __i < __s; ++__i)
00336 {
00337 _Value_type __t = __a[__i];
00338 if (__t < __r)
00339 __r = __t;
00340 }
00341 return __r;
00342 }
00343
00344 template<typename _Ta>
00345 inline typename _Ta::value_type
00346 __valarray_max(const _Ta& __a)
00347 {
00348 size_t __s = __a.size();
00349 typedef typename _Ta::value_type _Value_type;
00350 _Value_type __r = __s == 0 ? _Value_type() : __a[0];
00351 for (size_t __i = 1; __i < __s; ++__i)
00352 {
00353 _Value_type __t = __a[__i];
00354 if (__t > __r)
00355 __r = __t;
00356 }
00357 return __r;
00358 }
00359
00360
00361
00362
00363
00364
00365
00366 template<typename _Tp>
00367 struct _Array
00368 {
00369 explicit _Array (size_t);
00370 explicit _Array (_Tp* const __restrict__);
00371 explicit _Array (const valarray<_Tp>&);
00372 _Array (const _Tp* __restrict__, size_t);
00373
00374 _Tp* begin () const;
00375
00376 _Tp* const __restrict__ _M_data;
00377 };
00378
00379 template<typename _Tp>
00380 inline void
00381 __valarray_fill (_Array<_Tp> __a, size_t __n, const _Tp& __t)
00382 { __valarray_fill (__a._M_data, __n, __t); }
00383
00384 template<typename _Tp>
00385 inline void
00386 __valarray_fill (_Array<_Tp> __a, size_t __n, size_t __s, const _Tp& __t)
00387 { __valarray_fill (__a._M_data, __n, __s, __t); }
00388
00389 template<typename _Tp>
00390 inline void
00391 __valarray_fill (_Array<_Tp> __a, _Array<size_t> __i,
00392 size_t __n, const _Tp& __t)
00393 { __valarray_fill (__a._M_data, __i._M_data, __n, __t); }
00394
00395
00396 template<typename _Tp>
00397 inline void
00398 __valarray_copy(_Array<_Tp> __a, size_t __n, _Array<_Tp> __b)
00399 { __valarray_copy(__a._M_data, __n, __b._M_data); }
00400
00401
00402 template<typename _Tp>
00403 inline void
00404 __valarray_copy(_Array<_Tp> __a, size_t __n, size_t __s, _Array<_Tp> __b)
00405 { __valarray_copy(__a._M_data, __n, __s, __b._M_data); }
00406
00407
00408 template<typename _Tp>
00409 inline void
00410 __valarray_copy(_Array<_Tp> __a, _Array<_Tp> __b, size_t __n, size_t __s)
00411 { __valarray_copy(__a._M_data, __b._M_data, __n, __s); }
00412
00413
00414
00415 template<typename _Tp>
00416 inline void
00417 __valarray_copy(_Array<_Tp> __a, size_t __n, size_t __s1,
00418 _Array<_Tp> __b, size_t __s2)
00419 { __valarray_copy(__a._M_data, __n, __s1, __b._M_data, __s2); }
00420
00421
00422
00423 template<typename _Tp>
00424 inline void
00425 __valarray_copy(_Array<_Tp> __a, _Array<size_t> __i,
00426 _Array<_Tp> __b, size_t __n)
00427 { __valarray_copy(__a._M_data, __i._M_data, __b._M_data, __n); }
00428
00429
00430 template<typename _Tp>
00431 inline void
00432 __valarray_copy(_Array<_Tp> __a, size_t __n, _Array<_Tp> __b,
00433 _Array<size_t> __i)
00434 { __valarray_copy(__a._M_data, __n, __b._M_data, __i._M_data); }
00435
00436
00437
00438 template<typename _Tp>
00439 inline void
00440 __valarray_copy(_Array<_Tp> __src, size_t __n, _Array<size_t> __i,
00441 _Array<_Tp> __dst, _Array<size_t> __j)
00442 {
00443 __valarray_copy(__src._M_data, __n, __i._M_data,
00444 __dst._M_data, __j._M_data);
00445 }
00446
00447 template<typename _Tp>
00448 inline
00449 _Array<_Tp>::_Array (size_t __n)
00450 : _M_data(__valarray_get_storage<_Tp>(__n))
00451 { __valarray_default_construct(_M_data, _M_data + __n); }
00452
00453 template<typename _Tp>
00454 inline
00455 _Array<_Tp>::_Array (_Tp* const __restrict__ __p) : _M_data (__p) {}
00456
00457 template<typename _Tp>
00458 inline _Array<_Tp>::_Array (const valarray<_Tp>& __v)
00459 : _M_data (__v._M_data) {}
00460
00461 template<typename _Tp>
00462 inline
00463 _Array<_Tp>::_Array (const _Tp* __restrict__ __b, size_t __s)
00464 : _M_data(__valarray_get_storage<_Tp>(__s))
00465 { __valarray_copy_construct(__b, __s, _M_data); }
00466
00467 template<typename _Tp>
00468 inline _Tp*
00469 _Array<_Tp>::begin () const
00470 { return _M_data; }
00471
00472 #define _DEFINE_ARRAY_FUNCTION(_Op, _Name) \
00473 template<typename _Tp> \
00474 inline void \
00475 _Array_augmented_##_Name (_Array<_Tp> __a, size_t __n, const _Tp& __t) \
00476 { \
00477 for (_Tp* __p=__a._M_data; __p<__a._M_data+__n; ++__p) \
00478 *__p _Op##= __t; \
00479 } \
00480 \
00481 template<typename _Tp> \
00482 inline void \
00483 _Array_augmented_##_Name (_Array<_Tp> __a, size_t __n, _Array<_Tp> __b) \
00484 { \
00485 _Tp* __p = __a._M_data; \
00486 for (_Tp* __q=__b._M_data; __q<__b._M_data+__n; ++__p, ++__q) \
00487 *__p _Op##= *__q; \
00488 } \
00489 \
00490 template<typename _Tp, class _Dom> \
00491 void \
00492 _Array_augmented_##_Name (_Array<_Tp> __a, \
00493 const _Expr<_Dom,_Tp>& __e, size_t __n) \
00494 { \
00495 _Tp* __p (__a._M_data); \
00496 for (size_t __i=0; __i<__n; ++__i, ++__p) *__p _Op##= __e[__i]; \
00497 } \
00498 \
00499 template<typename _Tp> \
00500 inline void \
00501 _Array_augmented_##_Name (_Array<_Tp> __a, size_t __n, size_t __s, \
00502 _Array<_Tp> __b) \
00503 { \
00504 _Tp* __q (__b._M_data); \
00505 for (_Tp* __p=__a._M_data; __p<__a._M_data+__s*__n; __p+=__s, ++__q) \
00506 *__p _Op##= *__q; \
00507 } \
00508 \
00509 template<typename _Tp> \
00510 inline void \
00511 _Array_augmented_##_Name (_Array<_Tp> __a, _Array<_Tp> __b, \
00512 size_t __n, size_t __s) \
00513 { \
00514 _Tp* __q (__b._M_data); \
00515 for (_Tp* __p=__a._M_data; __p<__a._M_data+__n; ++__p, __q+=__s) \
00516 *__p _Op##= *__q; \
00517 } \
00518 \
00519 template<typename _Tp, class _Dom> \
00520 void \
00521 _Array_augmented_##_Name (_Array<_Tp> __a, size_t __s, \
00522 const _Expr<_Dom,_Tp>& __e, size_t __n) \
00523 { \
00524 _Tp* __p (__a._M_data); \
00525 for (size_t __i=0; __i<__n; ++__i, __p+=__s) *__p _Op##= __e[__i]; \
00526 } \
00527 \
00528 template<typename _Tp> \
00529 inline void \
00530 _Array_augmented_##_Name (_Array<_Tp> __a, _Array<size_t> __i, \
00531 _Array<_Tp> __b, size_t __n) \
00532 { \
00533 _Tp* __q (__b._M_data); \
00534 for (size_t* __j=__i._M_data; __j<__i._M_data+__n; ++__j, ++__q) \
00535 __a._M_data[*__j] _Op##= *__q; \
00536 } \
00537 \
00538 template<typename _Tp> \
00539 inline void \
00540 _Array_augmented_##_Name (_Array<_Tp> __a, size_t __n, \
00541 _Array<_Tp> __b, _Array<size_t> __i) \
00542 { \
00543 _Tp* __p (__a._M_data); \
00544 for (size_t* __j=__i._M_data; __j<__i._M_data+__n; ++__j, ++__p) \
00545 *__p _Op##= __b._M_data[*__j]; \
00546 } \
00547 \
00548 template<typename _Tp, class _Dom> \
00549 void \
00550 _Array_augmented_##_Name (_Array<_Tp> __a, _Array<size_t> __i, \
00551 const _Expr<_Dom, _Tp>& __e, size_t __n) \
00552 { \
00553 size_t* __j (__i._M_data); \
00554 for (size_t __k=0; __k<__n; ++__k, ++__j) \
00555 __a._M_data[*__j] _Op##= __e[__k]; \
00556 } \
00557 \
00558 template<typename _Tp> \
00559 void \
00560 _Array_augmented_##_Name (_Array<_Tp> __a, _Array<bool> __m, \
00561 _Array<_Tp> __b, size_t __n) \
00562 { \
00563 bool* ok (__m._M_data); \
00564 _Tp* __p (__a._M_data); \
00565 for (_Tp* __q=__b._M_data; __q<__b._M_data+__n; ++__q, ++ok, ++__p) { \
00566 while (! *ok) { \
00567 ++ok; \
00568 ++__p; \
00569 } \
00570 *__p _Op##= *__q; \
00571 } \
00572 } \
00573 \
00574 template<typename _Tp> \
00575 void \
00576 _Array_augmented_##_Name (_Array<_Tp> __a, size_t __n, \
00577 _Array<_Tp> __b, _Array<bool> __m) \
00578 { \
00579 bool* ok (__m._M_data); \
00580 _Tp* __q (__b._M_data); \
00581 for (_Tp* __p=__a._M_data; __p<__a._M_data+__n; ++__p, ++ok, ++__q) { \
00582 while (! *ok) { \
00583 ++ok; \
00584 ++__q; \
00585 } \
00586 *__p _Op##= *__q; \
00587 } \
00588 } \
00589 \
00590 template<typename _Tp, class _Dom> \
00591 void \
00592 _Array_augmented_##_Name (_Array<_Tp> __a, _Array<bool> __m, \
00593 const _Expr<_Dom, _Tp>& __e, size_t __n) \
00594 { \
00595 bool* ok(__m._M_data); \
00596 _Tp* __p (__a._M_data); \
00597 for (size_t __i=0; __i<__n; ++__i, ++ok, ++__p) { \
00598 while (! *ok) { \
00599 ++ok; \
00600 ++__p; \
00601 } \
00602 *__p _Op##= __e[__i]; \
00603 } \
00604 }
00605
00606 _DEFINE_ARRAY_FUNCTION(+, __plus)
00607 _DEFINE_ARRAY_FUNCTION(-, __minus)
00608 _DEFINE_ARRAY_FUNCTION(*, __multiplies)
00609 _DEFINE_ARRAY_FUNCTION(/, __divides)
00610 _DEFINE_ARRAY_FUNCTION(%, __modulus)
00611 _DEFINE_ARRAY_FUNCTION(^, __bitwise_xor)
00612 _DEFINE_ARRAY_FUNCTION(|, __bitwise_or)
00613 _DEFINE_ARRAY_FUNCTION(&, __bitwise_and)
00614 _DEFINE_ARRAY_FUNCTION(<<, __shift_left)
00615 _DEFINE_ARRAY_FUNCTION(>>, __shift_right)
00616
00617 #undef _DEFINE_VALARRAY_FUNCTION
00618
00619 }
00620
00621 #ifdef _GLIBCPP_NO_TEMPLATE_EXPORT
00622 # define export
00623 # include <bits/valarray_array.tcc>
00624 #endif
00625
00626 #endif
00627
00628
00629
00630