NGSolve
5.3
|
00001 #ifndef FILE_NGS_Array 00002 #define FILE_NGS_Array 00003 00004 /**************************************************************************/ 00005 /* File: array.hpp */ 00006 /* Author: Joachim Schoeberl */ 00007 /* Date: 01. Jun. 95 */ 00008 /**************************************************************************/ 00009 00010 #ifdef DEBUG 00011 #define CHECK_RANGE 00012 #endif 00013 00014 #include "tuple.hpp" 00015 00016 namespace ngstd 00017 { 00018 00023 class ArrayRangeException : public Exception 00024 { 00025 public: 00026 ArrayRangeException () : Exception("ArrayRangeException\n") { ; } 00027 }; 00028 00029 00030 00031 /* 00032 Some class which can be treated as array 00033 */ 00034 template <typename T> // , typename TA = T> 00035 class BaseArrayObject 00036 { 00037 public: 00038 INLINE BaseArrayObject() { ; } 00039 00040 INLINE const T & Spec() const { return static_cast<const T&> (*this); } 00041 INLINE int Size() const { return Spec().Size(); } 00042 // INLINE auto operator[] (int i) -> decltype (Spec()[i]) { return Spec()[i]; } 00043 // INLINE auto operator[] (int i) const -> decltype (T::operator[](i)) { return Spec()[i]; } 00044 }; 00045 00046 00047 template <typename T> 00048 inline ostream & operator<< (ostream & ost, const BaseArrayObject<T> & array) 00049 { 00050 for (int i = 0; i < array./* Spec().*/ Size(); i++) 00051 ost << i << ":" << array.Spec()[i] << endl; 00052 return ost; 00053 } 00054 00055 00056 00057 template <typename AO> 00058 class AOWrapperIterator 00059 { 00060 const AO & ao; 00061 int ind; 00062 public: 00063 INLINE AOWrapperIterator (const AO & aao, int ai) 00064 : ao(aao), ind(ai) { ; } 00065 INLINE AOWrapperIterator operator++ (int) 00066 { return AOWrapperIterator(ao, ind++); } 00067 INLINE AOWrapperIterator operator++ () 00068 { return AOWrapperIterator(ao, ++ind); } 00069 INLINE auto operator*() const -> decltype(ao[ind]) { return ao[ind]; } 00070 INLINE auto operator*() -> decltype(ao[ind]) { return ao[ind]; } 00071 // INLINE decltype(ao[ind]) operator*() { return ao[ind]; } 00072 INLINE bool operator != (AOWrapperIterator d2) { return ind != d2.ind; } 00073 }; 00074 00075 00076 00077 template <typename T> 00078 class AOWrapper : public BaseArrayObject<AOWrapper<T>> 00079 { 00080 const T & ar; 00081 public: 00082 INLINE AOWrapper (const T & aar) : ar(aar) { ; } 00083 INLINE operator const T& () const { return ar; } 00084 INLINE int Size() const { return ar.Size(); } 00085 INLINE auto operator[] (int i) -> decltype (ar[i]) { return ar[i]; } 00086 INLINE auto operator[] (int i) const -> decltype (ar[i]) { return ar[i]; } 00087 INLINE AOWrapperIterator<AOWrapper> begin () { return AOWrapperIterator<AOWrapper> (*this, 0); } 00088 INLINE AOWrapperIterator<AOWrapper> end () { return AOWrapperIterator<AOWrapper> (*this, Size()); } 00089 }; 00090 00091 template <typename T> 00092 INLINE AOWrapper<T> ArrayObject (const T & ar) 00093 { 00094 return AOWrapper<T> (ar); 00095 } 00096 00097 00098 00099 00100 00101 00102 00107 template <class T> 00108 class CArray 00109 { 00110 protected: 00112 T * data; 00113 public: 00114 00116 INLINE CArray () { data = 0; } 00117 00119 INLINE CArray (T * adata) 00120 : data(adata) { ; } 00121 00123 INLINE T & operator[] (int i) const 00124 { 00125 return data[i]; 00126 } 00127 00128 INLINE operator T* () const { return data; } 00129 }; 00130 00131 template <class T, class TSIZE = int> class FlatArray; 00132 00133 00134 template <typename TELEM, typename TSIZE> 00135 class ArrayIterator 00136 { 00137 FlatArray<TELEM,TSIZE> ar; 00138 TSIZE ind; 00139 public: 00140 INLINE ArrayIterator (FlatArray<TELEM,TSIZE> aar, TSIZE ai) 00141 : ar(aar), ind(ai) { ; } 00142 INLINE ArrayIterator operator++ (int) 00143 { return ArrayIterator(ar, ind++); } 00144 INLINE ArrayIterator operator++ () 00145 { return ArrayIterator(ar, ++ind); } 00146 INLINE TELEM operator*() const { return ar[ind]; } 00147 INLINE TELEM & operator*() { return ar[ind]; } 00148 INLINE bool operator != (ArrayIterator d2) { return ind != d2.ind; } 00149 }; 00150 00151 00152 00153 template <typename TSIZE> 00154 class ArrayRangeIterator 00155 { 00156 TSIZE ind; 00157 public: 00158 INLINE ArrayRangeIterator (TSIZE ai) : ind(ai) { ; } 00159 INLINE ArrayRangeIterator operator++ (int) { return ind++; } 00160 INLINE ArrayRangeIterator operator++ () { return ++ind; } 00161 INLINE ArrayRangeIterator operator*() const { return ind; } 00162 INLINE TSIZE Index() { return ind; } 00163 INLINE operator TSIZE () const { return ind; } 00164 INLINE bool operator != (ArrayRangeIterator d2) { return ind != d2.ind; } 00165 }; 00166 00168 template <typename T> 00169 class T_Range : public BaseArrayObject <T_Range<T>> 00170 { 00171 T first, next; 00172 public: 00173 INLINE T_Range () { ; } 00174 INLINE T_Range (T f, T n) : first(f), next(n) {;} 00175 INLINE T First() const { return first; } 00176 INLINE T Next() const { return next; } 00177 INLINE T Size() const { return next-first; } 00178 INLINE T operator[] (T i) const { return first+i; } 00179 INLINE bool Contains (T i) const { return ((i >= first) && (i < next)); } 00180 00181 INLINE ArrayRangeIterator<T> begin() const { return first; } 00182 INLINE ArrayRangeIterator<T> end() const { return next; } 00183 00184 T_Range Split (size_t nr, int tot) const 00185 { 00186 T diff = next-first; 00187 return T_Range (first + nr * diff / tot, 00188 first + (nr+1) * diff / tot); 00189 } 00190 // INLINE operator IntRange () const { return IntRange(first,next); } 00191 }; 00192 00193 using IntRange = T_Range<int>; 00194 00195 00196 template <typename T> 00197 inline T_Range<T> OmpSplit (T_Range<T> r) 00198 { 00199 int id = omp_get_thread_num(); 00200 int tot = omp_get_num_threads(); 00201 00202 T f = r.First() + (long(r.Size()) * id) / tot; 00203 T n = r.First() + (r.Size() * (id+1)) / tot; 00204 00205 return T_Range<T> (f, n); 00206 } 00207 00208 template <typename T> 00209 inline auto OmpSplit (const T & data) -> decltype (data.OmpSplit()) 00210 { 00211 return data.OmpSplit(); 00212 } 00213 00214 template <typename T> 00215 INLINE T_Range<T> Range (T a, T b) 00216 { 00217 return T_Range<T>(a,b); 00218 } 00219 00220 00221 template <typename T> 00222 INLINE T_Range<T> Range_impl (T n, std::true_type) 00223 { 00224 return T_Range<T> (0, n); 00225 } 00226 00227 template <typename T> 00228 INLINE auto Range_impl (const T & ao, std::false_type) 00229 -> T_Range<decltype(ao.Size())> 00230 { 00231 return T_Range<decltype(ao.Size())> (0, ao.Size()); 00232 } 00233 00234 template <typename T> 00235 auto Range(const T & x) -> decltype(Range_impl(x, std::is_integral<T>())) { 00236 return Range_impl(x, std::is_integral<T>()); 00237 } 00238 00239 00240 00241 00242 00243 INLINE IntRange operator+ (const IntRange & range, int shift) 00244 { 00245 return IntRange (range.First()+shift, range.Next()+shift); 00246 } 00247 00248 INLINE IntRange operator+ (int shift, const IntRange & range) 00249 { 00250 return IntRange (range.First()+shift, range.Next()+shift); 00251 } 00252 00253 INLINE IntRange operator* (int scale, const IntRange & range) 00254 { 00255 return IntRange (scale*range.First(), scale*range.Next()); 00256 } 00257 00258 INLINE IntRange operator* (const IntRange & range, int scale) 00259 { 00260 return IntRange (scale*range.First(), scale*range.Next()); 00261 } 00262 00263 inline ostream & operator<< (ostream & s, const IntRange & ir) 00264 { 00265 s << "[" << ir.First() << "," << ir.Next() << ")"; 00266 return s; 00267 } 00268 00269 template <typename ... ARGS> 00270 ostream & operator<< (ostream & ost, Tuple<IntRange, ARGS...> tup) 00271 { 00272 ost << tup.Head() << ", " << tup.Tail(); 00273 return ost; 00274 } 00275 00276 00277 00278 template <typename T, typename INDEX_ARRAY> 00279 class IndirectArray : public BaseArrayObject<IndirectArray<T, INDEX_ARRAY> > 00280 { 00281 // const FlatArray<T> & ba; 00282 FlatArray<T> ba; 00283 const INDEX_ARRAY & ia; 00284 00285 public: 00286 INLINE IndirectArray (// const FlatArray<T> & aba, 00287 FlatArray<T> aba, 00288 const INDEX_ARRAY & aia) 00289 : ba(aba), ia(aia) { ; } 00290 00291 INLINE int Size() const { return ia. /* Spec(). */ Size(); } 00292 INLINE T operator[] (int i) const { return ba[ia.Spec()[i]]; } 00293 INLINE T & operator[] (int i) { return ba[ia.Spec()[i]]; } 00294 00295 INLINE IndirectArray operator= (const T & val) 00296 { 00297 // for (int i = 0; i < Size(); i++) 00298 for (int i : Range(Size())) 00299 (*this)[i] = val; 00300 return IndirectArray (ba, ia); 00301 } 00302 00303 template <typename T2> 00304 INLINE IndirectArray operator= (const BaseArrayObject<T2> & a2) 00305 { 00306 // for (int i = 0; i < Size(); i++) 00307 for (int i : Range(Size())) 00308 (*this)[i] = a2.Spec()[i]; 00309 return IndirectArray (ba, ia); 00310 } 00311 00312 }; 00313 00314 00322 template <class T, class TSIZE> 00323 class FlatArray : public BaseArrayObject<FlatArray<T> > 00324 { 00325 protected: 00327 TSIZE size; 00329 T * __restrict data; 00330 public: 00331 00333 INLINE FlatArray () { ; } // size = 0; data = 0; } 00334 00336 template <typename TSIZE2> 00337 INLINE FlatArray (const FlatArray<T,TSIZE2> & a2) 00338 : size(a2.Size()), data(&a2[0]) { ; } 00339 00340 00342 INLINE FlatArray (TSIZE asize, T * adata) 00343 : size(asize), data(adata) { ; } 00344 00346 INLINE FlatArray(TSIZE asize, LocalHeap & lh) 00347 : size(asize), 00348 // data(static_cast<T*> (lh.Alloc(asize*sizeof(T)))) 00349 data (lh.Alloc<T> (asize)) 00350 { ; } 00351 00353 INLINE TSIZE Size() const { return size; } 00354 00355 00357 INLINE const FlatArray & operator= (const T & val) const 00358 { 00359 for (TSIZE i = 0; i < size; i++) 00360 data[i] = val; 00361 return *this; 00362 } 00363 00365 INLINE const FlatArray & operator= (const FlatArray & a2) const 00366 { 00367 for (TSIZE i = 0; i < size; i++) data[i] = a2[i]; 00368 return *this; 00369 } 00370 00371 template <typename T2> 00372 INLINE const FlatArray & operator= (const BaseArrayObject<T2> & a2) const 00373 { 00374 T * hdata = data; 00375 for (int i = 0; i < size; i++) hdata[i] = a2.Spec()[i]; 00376 return *this; 00377 } 00378 00379 INLINE const FlatArray & operator= (const std::function<T(int)> & func) const 00380 { 00381 for (TSIZE i = 0; i < size; i++) 00382 data[i] = func(i); 00383 return *this; 00384 } 00385 00387 INLINE const FlatArray & Assign (const FlatArray & a2) 00388 { 00389 size = a2.size; 00390 data = a2.data; 00391 return *this; 00392 } 00393 00395 INLINE const FlatArray & Assign (TSIZE asize, LocalHeap & lh) 00396 { 00397 size = asize; 00398 data = lh.Alloc<T> (asize); 00399 return *this; 00400 } 00401 00402 00404 INLINE T & operator[] (TSIZE i) const 00405 { 00406 00407 #ifdef CHECK_RANGE 00408 if (i < 0 || i >= size) 00409 throw RangeException ("FlatArray::operator[]", i, 0, size-1); 00410 #endif 00411 00412 return data[i]; 00413 } 00414 00415 INLINE T_Range<TSIZE> Range () const 00416 { 00417 return T_Range<TSIZE> (0, Size()); 00418 } 00419 00420 INLINE const CArray<T> Addr (int pos) 00421 { return CArray<T> (data+pos); } 00422 00423 // const CArray<T> operator+ (int pos) 00424 // { return CArray<T> (data+pos); } 00425 INLINE T * operator+ (int pos) { return data+pos; } 00426 00427 00429 T & Last () const 00430 { 00431 #ifdef CHECK_RANGE 00432 if (!size) 00433 throw Exception ("Array should not be empty"); 00434 #endif 00435 00436 return data[size-1]; 00437 } 00438 00440 INLINE const FlatArray<T> Part (int pos) 00441 { 00442 return FlatArray<T> (size-pos, data+pos); 00443 } 00444 00446 INLINE const FlatArray<T> Part (int pos, int subsize) 00447 { 00448 return FlatArray<T> (subsize, data+pos); 00449 } 00450 00452 INLINE /* const */ FlatArray<T> Range (TSIZE start, TSIZE end) const 00453 { 00454 return FlatArray<T> (end-start, data+start); 00455 } 00456 00458 INLINE /* const */ FlatArray<T,TSIZE> Range (T_Range<TSIZE> range) const 00459 { 00460 return FlatArray<T> (range.Size(), data+range.First()); 00461 } 00462 00464 INLINE const FlatArray<T> operator[] (const IntRange range) const 00465 { 00466 return FlatArray<T> (range.Size(), data+range.First()); 00467 } 00468 00469 template <typename TI1> 00470 IndirectArray<T, BaseArrayObject<TI1> > 00471 operator[] (const BaseArrayObject<TI1> & ind_array) const 00472 { 00473 return IndirectArray<T, BaseArrayObject<TI1> > (*this, ind_array); 00474 } 00475 00477 INLINE int Pos(const T & elem) const 00478 { 00479 int pos = -1; 00480 for(int i=0; pos==-1 && i < size; i++) 00481 if(elem == (*this)[i]) pos = i; 00482 return pos; 00483 } 00484 00486 INLINE bool Contains(const T & elem) const 00487 { 00488 return ( Pos(elem) >= 0 ); 00489 } 00490 00491 ArrayIterator<T, TSIZE> begin() const 00492 { return ArrayIterator<T,TSIZE> (*this, 0); } 00493 ArrayIterator<T, TSIZE> end() const 00494 { return ArrayIterator<T,TSIZE> (*this, size); } 00495 00496 FlatArray<T,TSIZE> OmpSplit() const 00497 { 00498 return Range(ngstd::OmpSplit(Range())); 00499 } 00500 }; 00501 00502 00503 00505 template <class T> 00506 inline ostream & operator<< (ostream & s, const FlatArray<T> & a) 00507 { 00508 for (int i = 0; i < a.Size(); i++) 00509 s << i << ": " << a[i] << "\n"; 00510 return s; 00511 } 00512 00514 template <class T1, class T2> 00515 inline bool operator== (const FlatArray<T1> & a1, 00516 const FlatArray<T2> & a2) 00517 { 00518 if (a1.Size () != a2.Size()) return 0; 00519 for (int i = 0; i < a1.Size(); i++) 00520 if (a1[i] != a2[i]) return 0; 00521 return 1; 00522 } 00523 00524 00525 00526 00535 template <class T, class TSIZE = int> 00536 class Array : public FlatArray<T,TSIZE> 00537 { 00538 protected: 00540 TSIZE allocsize; 00542 T * mem_to_delete; 00543 00544 using FlatArray<T,TSIZE>::size; 00545 using FlatArray<T,TSIZE>::data; 00546 00547 public: 00549 INLINE explicit Array() 00550 : FlatArray<T,TSIZE> (0, nullptr) 00551 { 00552 allocsize = 0; 00553 mem_to_delete = nullptr; 00554 } 00555 00556 INLINE explicit Array(TSIZE asize) 00557 : FlatArray<T,TSIZE> (asize, new T[asize]) 00558 { 00559 allocsize = asize; 00560 mem_to_delete = data; 00561 } 00562 00563 00565 INLINE Array(TSIZE asize, T* adata) 00566 : FlatArray<T,TSIZE> (asize, adata) 00567 { 00568 allocsize = asize; 00569 mem_to_delete = nullptr; 00570 } 00571 00573 INLINE Array(TSIZE asize, LocalHeap & lh) 00574 : FlatArray<T,TSIZE> (asize, lh) 00575 { 00576 allocsize = asize; 00577 mem_to_delete = nullptr; 00578 } 00579 00580 INLINE Array (Array && a2) 00581 { 00582 allocsize = 0; 00583 mem_to_delete = nullptr; 00584 size = 0; 00585 data = nullptr; 00586 00587 ngstd::Swap (size, a2.size); 00588 ngstd::Swap (data, a2.data); 00589 ngstd::Swap (allocsize, a2.allocsize); 00590 ngstd::Swap (mem_to_delete, a2.mem_to_delete); 00591 } 00592 00594 INLINE explicit Array (const Array & a2) 00595 : FlatArray<T,TSIZE> (a2.Size(), a2.Size() ? new T[a2.Size()] : nullptr) 00596 { 00597 allocsize = size; 00598 mem_to_delete = data; 00599 for (TSIZE i = 0; i < size; i++) 00600 (*this)[i] = a2[i]; 00601 } 00602 00603 00604 template <typename TA> 00605 explicit Array (const BaseArrayObject<TA> & a2) 00606 : FlatArray<T,TSIZE> (a2.Size(), 00607 a2.Size() ? new T[a2.Size()] : nullptr) 00608 { 00609 allocsize = size; 00610 mem_to_delete = data; 00611 for (TSIZE i = 0; i < size; i++) 00612 (*this)[i] = a2.Spec()[i]; 00613 } 00614 00615 Array (std::initializer_list<T> list) 00616 : FlatArray<T,TSIZE> (list.size(), 00617 list.size() ? new T[list.size()] : NULL) 00618 { 00619 allocsize = size; 00620 mem_to_delete = data; 00621 TSIZE cnt = 0; 00622 for (auto i = list.begin(); i < list.end(); i++, cnt++) 00623 data[cnt] = *i; 00624 } 00625 00627 explicit Array (const Array<T> & a2, const Array<T> & a3) 00628 : FlatArray<T,TSIZE> (a2.Size()+a3.Size(), 00629 a2.Size()+a3.Size() ? new T[a2.Size()+a3.Size()] : 0) 00630 { 00631 allocsize = size; 00632 mem_to_delete = data; 00633 for(TSIZE i = 0; i < a2.Size(); i++) 00634 (*this)[i] = a2[i]; 00635 for (TSIZE i = a2.Size(), j=0; i < size; i++,j++) 00636 (*this)[i] = a3[j]; 00637 } 00638 00640 INLINE ~Array() 00641 { 00642 delete [] mem_to_delete; 00643 } 00644 00646 INLINE void NothingToDelete () 00647 { 00648 mem_to_delete = nullptr; 00649 } 00650 00652 INLINE void SetSize(TSIZE nsize) 00653 { 00654 if (nsize > allocsize) ReSize (nsize); 00655 size = nsize; 00656 } 00657 00659 INLINE void SetSize0() 00660 { 00661 size = 0; 00662 } 00663 00665 INLINE void SetAllocSize (TSIZE nallocsize) 00666 { 00667 if (nallocsize > allocsize) 00668 ReSize (nallocsize); 00669 } 00670 00672 INLINE TSIZE AllocSize () const 00673 { 00674 return allocsize; 00675 } 00676 00677 00679 INLINE const Array & Assign (TSIZE asize, LocalHeap & lh) 00680 { 00681 delete [] mem_to_delete; 00682 size = allocsize = asize; 00683 data = lh.Alloc<T> (asize); 00684 mem_to_delete = nullptr; 00685 return *this; 00686 } 00687 00689 INLINE TSIZE Append (const T & el) 00690 { 00691 if (size == allocsize) 00692 ReSize (size+1); 00693 data[size] = el; 00694 size++; 00695 return size; 00696 } 00697 00698 INLINE Array<T> & operator += (const T & el) 00699 { 00700 Append (el); 00701 return *this; 00702 } 00703 00704 00706 // int Append (const Array<T> & source) 00707 INLINE TSIZE Append (FlatArray<T> source) 00708 { 00709 if(size + source.Size() >= allocsize) 00710 ReSize (size + source.Size() + 1); 00711 00712 TSIZE i,j; 00713 for(i = size, j=0; j<source.Size(); i++, j++) 00714 data[i] = source[j]; 00715 00716 size += source.Size(); 00717 return size; 00718 } 00719 00720 00721 00723 INLINE void DeleteElement (int i) 00724 { 00725 #ifdef CHECK_RANGE 00726 // RangeCheck (i); 00727 #endif 00728 00729 data[i] = data[size-1]; 00730 size--; 00731 } 00732 00733 00735 INLINE void RemoveElement (TSIZE i) 00736 { 00737 for(TSIZE j = i; j < this->size-1; j++) 00738 this->data[i] = this->data[i+1]; 00739 this->size--; 00740 } 00741 00742 00744 INLINE void DeleteLast () 00745 { 00746 #ifdef CHECK_RANGE 00747 // CheckNonEmpty(); 00748 #endif 00749 00750 size--; 00751 } 00752 00754 INLINE void DeleteAll () 00755 { 00756 delete [] mem_to_delete; 00757 mem_to_delete = NULL; 00758 data = 0; 00759 size = allocsize = 0; 00760 } 00761 00763 INLINE Array & operator= (const T & val) 00764 { 00765 FlatArray<T,TSIZE>::operator= (val); 00766 return *this; 00767 } 00768 00770 INLINE Array & operator= (const Array & a2) 00771 { 00772 SetSize (a2.Size()); 00773 for (TSIZE i = 0; i < size; i++) 00774 (*this)[i] = a2[i]; 00775 return *this; 00776 } 00777 00779 INLINE Array & operator= (Array && a2) 00780 { 00781 allocsize = 0; 00782 mem_to_delete = nullptr; 00783 size = 0; 00784 data = nullptr; 00785 00786 ngstd::Swap (size, a2.size); 00787 ngstd::Swap (data, a2.data); 00788 ngstd::Swap (allocsize, a2.allocsize); 00789 ngstd::Swap (mem_to_delete, a2.mem_to_delete); 00790 00791 return *this; 00792 /* 00793 SetSize (a2.Size()); 00794 for (TSIZE i = 0; i < size; i++) 00795 (*this)[i] = a2[i]; 00796 return *this; 00797 */ 00798 } 00799 00800 00802 INLINE Array & operator= (const FlatArray<T,TSIZE> & a2) 00803 { 00804 SetSize (a2.Size()); 00805 for (TSIZE i = 0; i < size; i++) 00806 (*this)[i] = a2[i]; 00807 return *this; 00808 } 00809 00810 /* 00812 Array & operator= (const IntRange & range) 00813 { 00814 SetSize (range.Size()); 00815 for (int i = 0; i < size; i++) 00816 (*this)[i] = range.First()+i; 00817 return *this; 00818 } 00819 */ 00820 template <typename T2> 00821 Array & operator= (const BaseArrayObject<T2> & a2) 00822 { 00823 SetSize (a2.Spec().Size()); 00824 for (TSIZE i = 0; i < size; i++) 00825 (*this)[i] = a2.Spec()[i]; 00826 return *this; 00827 } 00828 00829 template <typename ...ARGS> 00830 Array & operator= (Tuple<ARGS...> tup) 00831 { 00832 SetSize (ArraySize (tup)); 00833 StoreToArray (*this, tup); 00834 return *this; 00835 } 00836 00837 00838 INLINE void Swap (Array & b) 00839 { 00840 ngstd::Swap (size, b.size); 00841 ngstd::Swap (data, b.data); 00842 ngstd::Swap (allocsize, b.allocsize); 00843 // ngstd::Swap (ownmem, b.ownmem); 00844 ngstd::Swap (mem_to_delete, b.mem_to_delete); 00845 } 00846 00847 private: 00848 00850 INLINE void ReSize (TSIZE minsize); 00851 /* 00852 { 00853 TSIZE nsize = 2 * allocsize; 00854 if (nsize < minsize) nsize = minsize; 00855 00856 if (data) 00857 { 00858 T * p = new T[nsize]; 00859 00860 TSIZE mins = (nsize < size) ? nsize : size; 00861 memcpy (p, data, mins * sizeof(T)); 00862 00863 if (ownmem) delete [] data; 00864 ownmem = 1; 00865 data = p; 00866 } 00867 else 00868 { 00869 data = new T[nsize]; 00870 ownmem = 1; 00871 } 00872 00873 allocsize = nsize; 00874 } 00875 */ 00876 }; 00877 00879 template <class T, class TSIZE> 00880 INLINE void Array<T,TSIZE> :: ReSize (TSIZE minsize) 00881 { 00882 TSIZE nsize = 2 * allocsize; 00883 if (nsize < minsize) nsize = minsize; 00884 00885 T * hdata = data; 00886 data = new T[nsize]; 00887 00888 if (hdata) 00889 { 00890 TSIZE mins = (nsize < size) ? nsize : size; 00891 for (TSIZE i = 0; i < mins; i++) data[i] = hdata[i]; 00892 delete [] mem_to_delete; 00893 } 00894 00895 mem_to_delete = data; 00896 allocsize = nsize; 00897 } 00898 00899 //extern template class Array<int,int>; 00900 00901 00908 template <class T, int S> 00909 class ArrayMem : public Array<T> 00910 { 00911 T mem[S]; 00912 00913 using Array<T>::size; 00914 using Array<T>::allocsize; 00915 using Array<T>::data; 00916 using Array<T>::mem_to_delete; 00917 // using Array<T>::ownmem; 00918 00919 public: 00921 explicit ArrayMem(int asize = 0) 00922 : Array<T> (S, mem) 00923 { 00924 size = asize; 00925 if (asize > S) 00926 { 00927 data = new T[asize]; 00928 allocsize = size; 00929 // ownmem = 1; 00930 mem_to_delete = data; 00931 } 00932 } 00933 00935 explicit ArrayMem(const Array<T> & a2) 00936 : Array<T> (S, (T*)mem) 00937 { 00938 Array<T>::operator= (a2); 00939 } 00940 00942 explicit ArrayMem(const ArrayMem & a2) 00943 : Array<T> (S, (T*)mem) 00944 { 00945 Array<T>::operator= (a2); 00946 } 00947 00948 00949 ArrayMem & operator= (const T & val) 00950 { 00951 FlatArray<T>::operator= (val); 00952 return *this; 00953 } 00954 00956 ArrayMem & operator= (const FlatArray<T> & a2) 00957 { 00958 this->SetSize (a2.Size()); 00959 for (int i = 0; i < size; i++) 00960 (*this)[i] = a2[i]; 00961 return *this; 00962 } 00963 00964 00965 template <typename T2> 00966 ArrayMem & operator= (const BaseArrayObject<T2> & a2) 00967 { 00968 this->SetSize (a2.Spec().Size()); 00969 for (int i = 0; i < size; i++) 00970 (*this)[i] = a2.Spec()[i]; 00971 return *this; 00972 } 00973 00974 }; 00975 00976 00977 00978 00979 00980 template <typename ... ARGS> 00981 int ArraySize (Tuple<ARGS...> tup) 00982 { return 0;} 00983 00984 template <typename ... ARGS> 00985 int ArraySize (Tuple<int,ARGS...> tup) 00986 { return 1+ArraySize(tup.Tail()); } 00987 00988 template <typename ... ARGS> 00989 int ArraySize (Tuple<IntRange,ARGS...> tup) 00990 { return tup.Head().Size()+ArraySize(tup.Tail()); } 00991 00992 00993 template <typename ... ARGS> 00994 void StoreToArray (FlatArray<int> a, Tuple<ARGS...> tup) { ; } 00995 00996 template <typename ... ARGS> 00997 void StoreToArray (FlatArray<int> a, Tuple<int,ARGS...> tup) 00998 { 00999 a[0] = tup.Head(); 01000 StoreToArray (a.Range(1, a.Size()), tup.Tail()); 01001 } 01002 01003 template <typename ... ARGS> 01004 void StoreToArray (FlatArray<int> a, Tuple<IntRange,ARGS...> tup) 01005 { 01006 IntRange r = tup.Head(); 01007 a.Range(0,r.Size()) = r; 01008 StoreToArray (a.Range(r.Size(), a.Size()), tup.Tail()); 01009 } 01010 01011 /* 01012 template <typename T> template <typename ...ARGS> 01013 INLINE Array<T> & Array<T> :: operator= (Tuple<ARGS...> tup) 01014 { 01015 SetSize (ArraySize (tup)); 01016 StoreToArray (*this, tup); 01017 } 01018 */ 01019 01020 /* 01022 inline Array<int> & operator+= (Array<int> & array, const IntRange & range) 01023 { 01024 int oldsize = array.Size(); 01025 int s = range.Next() - range.First(); 01026 01027 array.SetSize (oldsize+s); 01028 01029 for (int i = 0; i < s; i++) 01030 array[oldsize+i] = range.First()+i; 01031 01032 return array; 01033 } 01034 */ 01035 01036 01037 template <typename T2> 01038 inline Array<int> & operator+= (Array<int> & array, const BaseArrayObject<T2> & a2) 01039 { 01040 int oldsize = array.Size(); 01041 int s = a2.Spec().Size(); 01042 01043 array.SetSize (oldsize+s); 01044 01045 for (int i = 0; i < s; i++) 01046 array[oldsize+i] = a2.Spec()[i]; 01047 01048 return array; 01049 } 01050 01051 01052 01053 01055 template <class T> 01056 inline void BubbleSort (const FlatArray<T> & data) 01057 { 01058 T hv; 01059 for (int i = 0; i < data.Size(); i++) 01060 for (int j = i+1; j < data.Size(); j++) 01061 if (data[i] > data[j]) 01062 { 01063 hv = data[i]; 01064 data[i] = data[j]; 01065 data[j] = hv; 01066 } 01067 } 01068 01070 template <class T, class S> 01071 inline void BubbleSort (FlatArray<T> & data, FlatArray<S> & slave) 01072 { 01073 for (int i = 0; i < data.Size(); i++) 01074 for (int j = i+1; j < data.Size(); j++) 01075 if (data[i] > data[j]) 01076 { 01077 T hv = data[i]; 01078 data[i] = data[j]; 01079 data[j] = hv; 01080 01081 S hvs = slave[i]; 01082 slave[i] = slave[j]; 01083 slave[j] = hvs; 01084 } 01085 } 01086 01087 01088 01089 01090 template <class T, typename TLESS> 01091 void QuickSort (FlatArray<T> data, TLESS less) 01092 { 01093 if (data.Size() <= 1) return; 01094 01095 int i = 0; 01096 int j = data.Size()-1; 01097 01098 T midval = data[ (i+j)/2 ]; 01099 01100 do 01101 { 01102 while (less (data[i], midval)) i++; 01103 while (less (midval, data[j])) j--; 01104 01105 if (i <= j) 01106 { 01107 Swap (data[i], data[j]); 01108 i++; j--; 01109 } 01110 } 01111 while (i <= j); 01112 01113 QuickSort (data.Range (0, j+1), less); 01114 QuickSort (data.Range (i, data.Size()), less); 01115 } 01116 01117 template <typename T> 01118 INLINE bool DefaultLess (const T & a, const T & b) 01119 { 01120 return a < b; 01121 } 01122 01123 template <typename T> 01124 class DefaultLessCl 01125 { 01126 public: 01127 bool operator() (const T & a, const T & b) const 01128 { 01129 return a < b; 01130 } 01131 }; 01132 01133 01134 01135 template <class T> 01136 INLINE void QuickSort (FlatArray<T> data) 01137 { 01138 QuickSort (data, DefaultLessCl<T>()); 01139 } 01140 01141 01142 01143 template <class T, typename TLESS> 01144 void QuickSortI (FlatArray<T> data, FlatArray<int> index, TLESS less) 01145 { 01146 if (index.Size() <= 1) return; 01147 01148 int i = 0; 01149 int j = index.Size()-1; 01150 01151 int midval = index[ (i+j)/2 ]; 01152 01153 do 01154 { 01155 while (less (data[index[i]],data[midval]) ) i++; 01156 while (less (data[midval], data[index[j]])) j--; 01157 01158 if (i <= j) 01159 { 01160 Swap (index[i], index[j]); 01161 i++; j--; 01162 } 01163 } 01164 while (i <= j); 01165 01166 QuickSortI (data, index.Range (0, j+1), less); 01167 QuickSortI (data, index.Range (i, index.Size()), less); 01168 } 01169 01170 01171 template <class T> 01172 INLINE void QuickSortI (FlatArray<T> data, FlatArray<int> index) 01173 { 01174 QuickSortI (data, index, DefaultLessCl<T>()); 01175 } 01176 01177 01178 01179 01180 01181 template <typename T> 01182 INLINE T xxxRemoveRef (const T & x) 01183 { 01184 return x; 01185 } 01186 01187 template <class TA1, class TA2> 01188 class SumArray : public BaseArrayObject<SumArray<TA1,TA2>> 01189 { 01190 const TA1 & a1; 01191 const TA2 & a2; 01192 public: 01193 SumArray (const TA1 & aa1, const TA2 & aa2) : a1(aa1), a2(aa2) { ; } 01194 int Size() const { return a1.Size()+a2.Size(); } 01195 auto operator[] (int i) const -> decltype (xxxRemoveRef (a1[0])) 01196 { 01197 return (i < a1.Size()) ? a1[i] : a2[i-a1.Size()]; 01198 } 01199 }; 01200 01201 template <class TA1, class TA2> 01202 SumArray<TA1,TA2> operator+ (const BaseArrayObject<TA1> & a1, 01203 const BaseArrayObject<TA2> & a2) 01204 { 01205 return SumArray<TA1,TA2> (a1.Spec(), a2.Spec()); 01206 } 01207 01208 01209 01210 01211 01212 template <typename T, typename TSIZE> 01213 Archive & operator & (Archive & archive, Array<T,TSIZE> & a) 01214 { 01215 if (archive.Output()) 01216 archive << a.Size(); 01217 else 01218 { 01219 TSIZE size; 01220 archive & size; 01221 a.SetSize (size); 01222 } 01223 01224 /* 01225 for (auto & ai : a) 01226 archive & ai; 01227 */ 01228 archive.Do (&a[0], a.Size()); 01229 return archive; 01230 } 01231 } 01232 01233 01234 #endif 01235