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
#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>::_M_type>::
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>::_M_type>::
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>::_M_type>::
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>::_M_type)
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>::_M_type)
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>::_M_type)
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>::_M_type>::
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 template<typename _Tp>
00432 inline
void
00433 __valarray_fill (_Array<_Tp> __a, size_t __n, const _Tp& __t)
00434 { std::__valarray_fill(__a._M_data, __n, __t); }
00435
00436
template<
typename _Tp>
00437
inline void
00438 __valarray_fill(_Array<_Tp> __a, size_t __n, size_t __s,
const _Tp& __t)
00439 { std::__valarray_fill(__a._M_data, __n, __s, __t); }
00440
00441
template<
typename _Tp>
00442
inline void
00443 __valarray_fill(_Array<_Tp> __a, _Array<size_t> __i,
00444 size_t __n,
const _Tp& __t)
00445 { std::__valarray_fill(__a._M_data, __i._M_data, __n, __t); }
00446
00447
00448
template<
typename _Tp>
00449
inline void
00450 __valarray_copy(_Array<_Tp> __a, size_t __n, _Array<_Tp> __b)
00451 { std::__valarray_copy(__a._M_data, __n, __b._M_data); }
00452
00453
00454
template<
typename _Tp>
00455
inline void
00456 __valarray_copy(_Array<_Tp> __a, size_t __n, size_t __s, _Array<_Tp> __b)
00457 { std::__valarray_copy(__a._M_data, __n, __s, __b._M_data); }
00458
00459
00460
template<
typename _Tp>
00461
inline void
00462 __valarray_copy(_Array<_Tp> __a, _Array<_Tp> __b, size_t __n, size_t __s)
00463 { __valarray_copy(__a._M_data, __b._M_data, __n, __s); }
00464
00465
00466
00467
template<
typename _Tp>
00468
inline void
00469 __valarray_copy(_Array<_Tp> __a, size_t __n, size_t __s1,
00470 _Array<_Tp> __b, size_t __s2)
00471 { std::__valarray_copy(__a._M_data, __n, __s1, __b._M_data, __s2); }
00472
00473
00474
template<
typename _Tp>
00475
inline void
00476 __valarray_copy(_Array<_Tp> __a, _Array<size_t> __i,
00477 _Array<_Tp> __b, size_t __n)
00478 { std::__valarray_copy(__a._M_data, __i._M_data, __b._M_data, __n); }
00479
00480
00481
template<
typename _Tp>
00482
inline void
00483 __valarray_copy(_Array<_Tp> __a, size_t __n, _Array<_Tp> __b,
00484 _Array<size_t> __i)
00485 { std::__valarray_copy(__a._M_data, __n, __b._M_data, __i._M_data); }
00486
00487
00488
00489
template<
typename _Tp>
00490
inline void
00491 __valarray_copy(_Array<_Tp> __src, size_t __n, _Array<size_t> __i,
00492 _Array<_Tp> __dst, _Array<size_t> __j)
00493 {
00494 std::__valarray_copy(__src._M_data, __n, __i._M_data,
00495 __dst._M_data, __j._M_data);
00496 }
00497
00498
template<
typename _Tp>
00499
inline
00500 _Array<_Tp>::_Array(size_t __n)
00501 : _M_data(__valarray_get_storage<_Tp>(__n))
00502 { std::__valarray_default_construct(_M_data, _M_data + __n); }
00503
00504
template<
typename _Tp>
00505
inline
00506 _Array<_Tp>::_Array(_Tp*
const __restrict__ __p)
00507 : _M_data (__p) {}
00508
00509
template<
typename _Tp>
00510
inline
00511 _Array<_Tp>::_Array(
const valarray<_Tp>& __v)
00512 : _M_data (__v._M_data) {}
00513
00514
template<
typename _Tp>
00515
inline
00516 _Array<_Tp>::_Array(
const _Tp* __restrict__ __b, size_t __s)
00517 : _M_data(__valarray_get_storage<_Tp>(__s))
00518 { std::__valarray_copy_construct(__b, __s, _M_data); }
00519
00520
template<
typename _Tp>
00521
inline _Tp*
00522 _Array<_Tp>::begin ()
const
00523
{
return _M_data; }
00524
00525
#define _DEFINE_ARRAY_FUNCTION(_Op, _Name) \
00526
template<typename _Tp> \
00527
inline void \
00528
_Array_augmented_##_Name(_Array<_Tp> __a, size_t __n, const _Tp& __t) \
00529
{ \
00530
for (_Tp* __p = __a._M_data; __p < __a._M_data + __n; ++__p) \
00531
*__p _Op##= __t; \
00532
} \
00533
\
00534
template<typename _Tp> \
00535
inline void \
00536
_Array_augmented_##_Name(_Array<_Tp> __a, size_t __n, _Array<_Tp> __b) \
00537
{ \
00538
_Tp* __p = __a._M_data; \
00539
for (_Tp* __q = __b._M_data; __q < __b._M_data + __n; ++__p, ++__q) \
00540
*__p _Op##= *__q; \
00541
} \
00542
\
00543
template<typename _Tp, class _Dom> \
00544
void \
00545
_Array_augmented_##_Name(_Array<_Tp> __a, \
00546
const _Expr<_Dom, _Tp>& __e, size_t __n) \
00547
{ \
00548
_Tp* __p(__a._M_data); \
00549
for (size_t __i = 0; __i < __n; ++__i, ++__p) \
00550
*__p _Op##= __e[__i]; \
00551
} \
00552
\
00553
template<typename _Tp> \
00554
inline void \
00555
_Array_augmented_##_Name(_Array<_Tp> __a, size_t __n, size_t __s, \
00556
_Array<_Tp> __b) \
00557
{ \
00558
_Tp* __q(__b._M_data); \
00559
for (_Tp* __p = __a._M_data; __p < __a._M_data + __s * __n; \
00560
__p += __s, ++__q) \
00561
*__p _Op##= *__q; \
00562
} \
00563
\
00564
template<typename _Tp> \
00565
inline void \
00566
_Array_augmented_##_Name(_Array<_Tp> __a, _Array<_Tp> __b, \
00567
size_t __n, size_t __s) \
00568
{ \
00569
_Tp* __q(__b._M_data); \
00570
for (_Tp* __p = __a._M_data; __p < __a._M_data + __n; \
00571
++__p, __q += __s) \
00572
*__p _Op##= *__q; \
00573
} \
00574
\
00575
template<typename _Tp, class _Dom> \
00576
void \
00577
_Array_augmented_##_Name(_Array<_Tp> __a, size_t __s, \
00578
const _Expr<_Dom, _Tp>& __e, size_t __n) \
00579
{ \
00580
_Tp* __p(__a._M_data); \
00581
for (size_t __i = 0; __i < __n; ++__i, __p += __s) \
00582
*__p _Op##= __e[__i]; \
00583
} \
00584
\
00585
template<typename _Tp> \
00586
inline void \
00587
_Array_augmented_##_Name(_Array<_Tp> __a, _Array<size_t> __i, \
00588
_Array<_Tp> __b, size_t __n) \
00589
{ \
00590
_Tp* __q(__b._M_data); \
00591
for (size_t* __j = __i._M_data; __j < __i._M_data + __n; \
00592
++__j, ++__q) \
00593
__a._M_data[*__j] _Op##= *__q; \
00594
} \
00595
\
00596
template<typename _Tp> \
00597
inline void \
00598
_Array_augmented_##_Name(_Array<_Tp> __a, size_t __n, \
00599
_Array<_Tp> __b, _Array<size_t> __i) \
00600
{ \
00601
_Tp* __p(__a._M_data); \
00602
for (size_t* __j = __i._M_data; __j<__i._M_data + __n; \
00603
++__j, ++__p) \
00604
*__p _Op##= __b._M_data[*__j]; \
00605
} \
00606
\
00607
template<typename _Tp, class _Dom> \
00608
void \
00609
_Array_augmented_##_Name(_Array<_Tp> __a, _Array<size_t> __i, \
00610
const _Expr<_Dom, _Tp>& __e, size_t __n) \
00611
{ \
00612
size_t* __j(__i._M_data); \
00613
for (size_t __k = 0; __k<__n; ++__k, ++__j) \
00614
__a._M_data[*__j] _Op##= __e[__k]; \
00615
} \
00616
\
00617
template<typename _Tp> \
00618
void \
00619
_Array_augmented_##_Name(_Array<_Tp> __a, _Array<bool> __m, \
00620
_Array<_Tp> __b, size_t __n) \
00621
{ \
00622
bool* __ok(__m._M_data); \
00623
_Tp* __p(__a._M_data); \
00624
for (_Tp* __q = __b._M_data; __q < __b._M_data + __n; \
00625
++__q, ++__ok, ++__p) \
00626
{ \
00627
while (! *__ok) \
00628
{ \
00629
++__ok; \
00630
++__p; \
00631
} \
00632
*__p _Op##= *__q; \
00633
} \
00634
} \
00635
\
00636
template<typename _Tp> \
00637
void \
00638
_Array_augmented_##_Name(_Array<_Tp> __a, size_t __n, \
00639
_Array<_Tp> __b, _Array<bool> __m) \
00640
{ \
00641
bool* __ok(__m._M_data); \
00642
_Tp* __q(__b._M_data); \
00643
for (_Tp* __p = __a._M_data; __p < __a._M_data + __n; \
00644
++__p, ++__ok, ++__q) \
00645
{ \
00646
while (! *__ok) \
00647
{ \
00648
++__ok; \
00649
++__q; \
00650
} \
00651
*__p _Op##= *__q; \
00652
} \
00653
} \
00654
\
00655
template<typename _Tp, class _Dom> \
00656
void \
00657
_Array_augmented_##_Name(_Array<_Tp> __a, _Array<bool> __m, \
00658
const _Expr<_Dom, _Tp>& __e, size_t __n) \
00659
{ \
00660
bool* __ok(__m._M_data); \
00661
_Tp* __p(__a._M_data); \
00662
for (size_t __i = 0; __i < __n; ++__i, ++__ok, ++__p) \
00663
{ \
00664
while (! *__ok) \
00665
{ \
00666
++__ok; \
00667
++__p; \
00668
} \
00669
*__p _Op##= __e[__i]; \
00670
} \
00671
}
00672
00673 _DEFINE_ARRAY_FUNCTION(+, __plus)
00674 _DEFINE_ARRAY_FUNCTION(-, __minus)
00675 _DEFINE_ARRAY_FUNCTION(*, __multiplies)
00676 _DEFINE_ARRAY_FUNCTION(/, __divides)
00677 _DEFINE_ARRAY_FUNCTION(%, __modulus)
00678 _DEFINE_ARRAY_FUNCTION(^, __bitwise_xor)
00679 _DEFINE_ARRAY_FUNCTION(|, __bitwise_or)
00680 _DEFINE_ARRAY_FUNCTION(&, __bitwise_and)
00681 _DEFINE_ARRAY_FUNCTION(<<, __shift_left)
00682 _DEFINE_ARRAY_FUNCTION(>>, __shift_right)
00683
00684 #undef _DEFINE_VALARRAY_FUNCTION
00685 }
00686
00687 #ifndef _GLIBCXX_EXPORT_TEMPLATE
00688 # include <bits/valarray_array.tcc>
00689 #endif
00690
00691 #endif