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