NGSolve
4.9
|
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 00015 namespace ngstd 00016 { 00017 00022 class ArrayRangeException : public Exception 00023 { 00024 public: 00025 ArrayRangeException () : Exception("ArrayRangeException\n") { ; } 00026 }; 00027 00028 00029 00030 00031 00032 /* 00033 Some class which can be treated as array 00034 */ 00035 template <typename T, typename TA = T> 00036 class BaseArrayObject 00037 { 00038 public: 00039 const TA & Spec() const { return static_cast<const T&>(*this).Spec2 (); } 00040 const TA & Spec2() const { return static_cast<const T&> (*this); } 00041 }; 00042 00043 00044 template <typename T, typename TA> 00045 inline ostream & operator<< (ostream & ost, const BaseArrayObject<T,TA> & array) 00046 { 00047 for (int i = 0; i < array.Spec().Size(); i++) 00048 ost << i << ":" << array.Spec()[i] << endl; 00049 return ost; 00050 } 00051 00052 template <typename T> 00053 class AOWrapper : public BaseArrayObject< AOWrapper<T> , T> 00054 { 00055 const T & ar; 00056 public: 00057 AOWrapper (const T & aar) : ar(aar) { ; } 00058 const T & Spec2() const { return ar; } 00059 }; 00060 00061 00062 template <typename T> 00063 inline AOWrapper<T> ArrayObject (const T & ar) 00064 { 00065 return AOWrapper<T> (ar); 00066 } 00067 00068 00069 00070 00071 00072 00073 00078 template <class T> 00079 class CArray 00080 { 00081 protected: 00083 T * data; 00084 public: 00085 00087 CArray () { data = 0; } 00088 00090 CArray (T * adata) 00091 : data(adata) { ; } 00092 00094 T & operator[] (int i) const 00095 { 00096 return data[i]; 00097 } 00098 00099 operator T* () const { return data; } 00100 }; 00101 00102 00103 00104 00105 00106 00108 class IntRange : public BaseArrayObject <IntRange> 00109 { 00110 int first, next; 00111 public: 00112 IntRange (int f, int n) : first(f), next(n) {;} 00113 int First() const { return first; } 00114 int Next() const { return next; } 00115 int Size() const { return next-first; } 00116 int operator[] (int i) const { return first+i; } 00117 bool Contains (int i) const { return ((i >= first) && (i < next)); } 00118 }; 00119 00120 inline IntRange operator+ (const IntRange & range, int shift) 00121 { 00122 return IntRange (range.First()+shift, range.Next()+shift); 00123 } 00124 00125 inline IntRange operator+ (int shift, const IntRange & range) 00126 { 00127 return IntRange (range.First()+shift, range.Next()+shift); 00128 } 00129 00130 inline IntRange operator* (int scale, const IntRange & range) 00131 { 00132 return IntRange (scale*range.First(), scale*range.Next()); 00133 } 00134 00135 inline IntRange operator* (const IntRange & range, int scale) 00136 { 00137 return IntRange (scale*range.First(), scale*range.Next()); 00138 } 00139 00140 inline ostream & operator<< (ostream & s, const IntRange & ir) 00141 { 00142 s << "[" << ir.First() << "," << ir.Next() << ")"; 00143 return s; 00144 } 00145 00146 00147 template <class T, class TSIZE = int> class FlatArray; 00148 00149 template <typename T, typename INDEX_ARRAY> 00150 class IndirectArray : public BaseArrayObject<IndirectArray<T, INDEX_ARRAY> > 00151 { 00152 const FlatArray<T> & ba; 00153 const INDEX_ARRAY & ia; 00154 00155 public: 00156 IndirectArray (const FlatArray<T> & aba, 00157 const INDEX_ARRAY & aia) 00158 : ba(aba), ia(aia) { ; } 00159 00160 int Size() const { return ia.Spec().Size(); } 00161 T operator[] (int i) const { return ba[ia.Spec()[i]]; } 00162 T & operator[] (int i) { return ba[ia.Spec()[i]]; } 00163 00164 IndirectArray operator= (const T & val) 00165 { 00166 for (int i = 0; i < Size(); i++) 00167 (*this)[i] = val; 00168 return IndirectArray (ba, ia); 00169 } 00170 00171 template <typename T2, typename TA> 00172 IndirectArray operator= (const BaseArrayObject<T2,TA> & a2) 00173 { 00174 for (int i = 0; i < Size(); i++) 00175 (*this)[i] = a2.Spec()[i]; 00176 return IndirectArray (ba, ia); 00177 } 00178 00179 }; 00180 00181 00182 00190 template <class T, class TSIZE> 00191 class FlatArray : public BaseArrayObject<FlatArray<T> > 00192 { 00193 protected: 00195 TSIZE size; 00197 T * data; 00198 public: 00199 00201 FlatArray () { ; } // size = 0; data = 0; } 00202 00204 FlatArray (TSIZE asize, T * adata) 00205 : size(asize), data(adata) { ; } 00206 00208 FlatArray(TSIZE asize, LocalHeap & lh) 00209 : size(asize), 00210 // data(static_cast<T*> (lh.Alloc(asize*sizeof(T)))) 00211 data (lh.Alloc<T> (asize)) 00212 { ; } 00213 00215 TSIZE Size() const { return size; } 00216 00217 00219 const FlatArray & operator= (const T & val) const 00220 { 00221 for (TSIZE i = 0; i < size; i++) 00222 data[i] = val; 00223 return *this; 00224 } 00225 00226 /* 00228 const FlatArray & operator= (const FlatArray & a2) 00229 { 00230 size = a2.size; 00231 data = a2.data; 00232 return *this; 00233 } 00234 */ 00235 00237 const FlatArray & operator= (const FlatArray & a2) const 00238 { 00239 for (TSIZE i = 0; i < size; i++) data[i] = a2[i]; 00240 return *this; 00241 } 00242 00243 template <typename T2, typename TA> 00244 const FlatArray & operator= (const BaseArrayObject<T2,TA> & a2) const 00245 { 00246 for (int i = 0; i < size; i++) (*this)[i] = a2.Spec()[i]; 00247 return *this; 00248 } 00249 00250 00252 T & operator[] (TSIZE i) const 00253 { 00254 00255 #ifdef CHECK_RANGE 00256 if (i < 0 || i >= size) 00257 throw RangeException ("FlatArray::operator[]", i, 0, size-1); 00258 #endif 00259 00260 return data[i]; 00261 } 00262 00263 00264 const CArray<T> Addr (int pos) 00265 { 00266 return CArray<T> (data+pos); 00267 } 00268 00269 /* 00270 // icc does not like this version 00271 T * const Addr (int i) const 00272 { 00273 return data+i; 00274 } 00275 */ 00276 00278 T & Last () const 00279 { 00280 #ifdef CHECK_RANGE 00281 if (!size) 00282 throw Exception ("Array should not be empty"); 00283 #endif 00284 00285 return data[size-1]; 00286 } 00287 00289 const FlatArray<T> Part (int pos) 00290 { 00291 return FlatArray<T> (size-pos, data+pos); 00292 } 00293 00295 const FlatArray<T> Part (int pos, int subsize) 00296 { 00297 return FlatArray<T> (subsize, data+pos); 00298 } 00299 00301 const FlatArray<T> Range (int start, int end) const 00302 { 00303 return FlatArray<T> (end-start, data+start); 00304 } 00305 00307 const FlatArray<T> Range (class IntRange range) const 00308 { 00309 return FlatArray<T> (range.Size(), data+range.First()); 00310 } 00311 00313 const FlatArray<T> operator[] (const IntRange range) const 00314 { 00315 return FlatArray<T> (range.Size(), data+range.First()); 00316 } 00317 00318 template <typename TI1, typename TI2> 00319 IndirectArray<T, BaseArrayObject<TI1,TI2> > 00320 operator[] (const BaseArrayObject<TI1,TI2> & ind_array) const 00321 { 00322 return IndirectArray<T, BaseArrayObject<TI1,TI2> > (*this, ind_array); 00323 } 00324 00326 int Pos(const T & elem) const 00327 { 00328 int pos = -1; 00329 for(int i=0; pos==-1 && i < size; i++) 00330 if(elem == (*this)[i]) pos = i; 00331 return pos; 00332 } 00333 00335 bool Contains(const T & elem) const 00336 { 00337 return ( Pos(elem) >= 0 ); 00338 } 00339 00340 }; 00341 00342 00343 00345 template <class T> 00346 ostream & operator<< (ostream & s, const FlatArray<T> & a) 00347 { 00348 for (int i = 0; i < a.Size(); i++) 00349 s << i << ": " << a[i] << "\n"; 00350 return s; 00351 } 00352 00354 template <class T1, class T2> 00355 inline bool operator== (const FlatArray<T1> & a1, 00356 const FlatArray<T2> & a2) 00357 { 00358 if (a1.Size () != a2.Size()) return 0; 00359 for (int i = 0; i < a1.Size(); i++) 00360 if (a1[i] != a2[i]) return 0; 00361 return 1; 00362 } 00363 00364 00365 00366 00375 template <class T, class TSIZE = int> 00376 class Array : public FlatArray<T,TSIZE> 00377 { 00378 protected: 00380 TSIZE allocsize; 00382 bool ownmem; 00383 00384 using FlatArray<T,TSIZE>::size; 00385 using FlatArray<T,TSIZE>::data; 00386 public: 00388 explicit Array() 00389 : FlatArray<T,TSIZE> (0, NULL) 00390 { 00391 allocsize = 0; 00392 ownmem = 1; 00393 } 00394 00395 explicit Array(TSIZE asize) 00396 : FlatArray<T,TSIZE> (asize, new T[asize]) 00397 { 00398 allocsize = asize; 00399 ownmem = 1; 00400 } 00401 00402 00404 Array(TSIZE asize, T* adata) 00405 : FlatArray<T,TSIZE> (asize, adata) 00406 { 00407 allocsize = asize; 00408 ownmem = 0; 00409 } 00410 00412 Array(TSIZE asize, LocalHeap & lh) 00413 : FlatArray<T,TSIZE> (asize, lh) 00414 { 00415 allocsize = asize; 00416 ownmem = 0; 00417 } 00418 00419 00421 explicit Array (const Array<T> & a2) 00422 : FlatArray<T,TSIZE> (a2.Size(), a2.Size() ? new T[a2.Size()] : 0) 00423 { 00424 allocsize = size; 00425 ownmem = 1; 00426 for (int i = 0; i < size; i++) 00427 (*this)[i] = a2[i]; 00428 } 00429 00431 explicit Array (const Array<T> & a2, const Array<T> & a3) 00432 : FlatArray<T,TSIZE> (a2.Size()+a3.Size(), 00433 a2.Size()+a3.Size() ? new T[a2.Size()+a3.Size()] : 0) 00434 { 00435 allocsize = size; 00436 ownmem = 1; 00437 for(int i = 0; i < a2.Size(); i++) 00438 (*this)[i] = a2[i]; 00439 for (int i = a2.Size(), j=0; i < size; i++,j++) 00440 (*this)[i] = a3[j]; 00441 } 00442 00444 ~Array() 00445 { 00446 if (ownmem) delete [] data; 00447 } 00448 00450 void SetSize(TSIZE nsize) 00451 { 00452 if (nsize > allocsize) ReSize (nsize); 00453 size = nsize; 00454 } 00455 00457 void SetAllocSize (int nallocsize) 00458 { 00459 if (nallocsize > allocsize) 00460 ReSize (nallocsize); 00461 } 00462 00464 int Append (const T & el) 00465 { 00466 if (size == allocsize) 00467 ReSize (size+1); 00468 data[size] = el; 00469 size++; 00470 return size; 00471 } 00472 00473 Array<T> & operator += (const T & el) 00474 { 00475 Append (el); 00476 return *this; 00477 } 00478 00479 00481 int Append (const Array<T> & source) 00482 { 00483 if(size + source.Size() >= allocsize) 00484 ReSize (size + source.Size() + 1); 00485 00486 int i,j; 00487 for(i = size, j=0; j<source.Size(); i++, j++) 00488 data[i] = source[j]; 00489 00490 size += source.Size(); 00491 return size; 00492 } 00493 00494 00495 00497 void DeleteElement (int i) 00498 { 00499 #ifdef CHECK_RANGE 00500 // RangeCheck (i); 00501 #endif 00502 00503 data[i] = data[size-1]; 00504 size--; 00505 } 00506 00507 00509 void RemoveElement (int i) 00510 { 00511 for(int j = i; j < this->size-1; j++) 00512 this->data[i] = this->data[i+1]; 00513 this->size--; 00514 } 00515 00516 00518 void DeleteLast () 00519 { 00520 #ifdef CHECK_RANGE 00521 // CheckNonEmpty(); 00522 #endif 00523 00524 size--; 00525 } 00526 00528 void DeleteAll () 00529 { 00530 if (ownmem) delete [] data; 00531 data = 0; 00532 size = allocsize = 0; 00533 } 00534 00536 Array & operator= (const T & val) 00537 { 00538 FlatArray<T,TSIZE>::operator= (val); 00539 return *this; 00540 } 00541 00543 Array & operator= (const Array & a2) 00544 { 00545 SetSize (a2.Size()); 00546 for (TSIZE i = 0; i < size; i++) 00547 (*this)[i] = a2[i]; 00548 return *this; 00549 } 00550 00552 Array & operator= (const FlatArray<T,TSIZE> & a2) 00553 { 00554 SetSize (a2.Size()); 00555 for (int i = 0; i < size; i++) 00556 (*this)[i] = a2[i]; 00557 return *this; 00558 } 00559 00560 /* 00562 Array & operator= (const IntRange & range) 00563 { 00564 SetSize (range.Size()); 00565 for (int i = 0; i < size; i++) 00566 (*this)[i] = range.First()+i; 00567 return *this; 00568 } 00569 */ 00570 template <typename T2, typename TA> 00571 Array & operator= (const BaseArrayObject<T2,TA> & a2) 00572 { 00573 SetSize (a2.Spec().Size()); 00574 for (int i = 0; i < size; i++) 00575 (*this)[i] = a2.Spec()[i]; 00576 return *this; 00577 } 00578 00579 void Swap (Array & b) 00580 { 00581 ngstd::Swap (size, b.size); 00582 ngstd::Swap (data, b.data); 00583 ngstd::Swap (allocsize, b.allocsize); 00584 ngstd::Swap (ownmem, b.ownmem); 00585 } 00586 00587 private: 00588 00590 void ReSize (TSIZE minsize) 00591 { 00592 TSIZE nsize = 2 * allocsize; 00593 if (nsize < minsize) nsize = minsize; 00594 00595 if (data) 00596 { 00597 T * p = new T[nsize]; 00598 00599 TSIZE mins = (nsize < size) ? nsize : size; 00600 memcpy (p, data, mins * sizeof(T)); 00601 00602 if (ownmem) delete [] data; 00603 ownmem = 1; 00604 data = p; 00605 } 00606 else 00607 { 00608 data = new T[nsize]; 00609 ownmem = 1; 00610 } 00611 00612 allocsize = nsize; 00613 } 00614 00615 }; 00616 00617 00618 00619 00626 template <class T, int S> 00627 class ArrayMem : public Array<T> 00628 { 00629 T mem[S]; // should be best, but calls trivial default constructor 00630 // now ok with major compilers ? 00631 00632 // char mem[S*sizeof(T)]; // avoids calling the array default-constructor (icc) 00633 // double mem[(S*sizeof(T)+7) / 8]; // alignment (on ia64 machines) 00634 00635 using Array<T>::size; 00636 using Array<T>::data; 00637 using Array<T>::ownmem; 00638 00639 public: 00641 explicit ArrayMem(int asize = 0) 00642 : Array<T> (S, static_cast<T*> (static_cast<void*>(&mem[0]))) 00643 { 00644 size = asize; 00645 if (asize > S) 00646 { 00647 data = new T[asize]; 00648 ownmem = 1; 00649 } 00650 // this->SetSize (asize); 00651 } 00652 00654 explicit ArrayMem(const Array<T> & a2) 00655 : Array<T> (S, (T*)mem) 00656 { 00657 Array<T>::operator= (a2); 00658 } 00659 00661 explicit ArrayMem(const ArrayMem & a2) 00662 : Array<T> (S, (T*)mem) 00663 { 00664 Array<T>::operator= (a2); 00665 } 00666 00667 00668 ArrayMem & operator= (const T & val) 00669 { 00670 FlatArray<T>::operator= (val); 00671 return *this; 00672 } 00673 00675 ArrayMem & operator= (const FlatArray<T> & a2) 00676 { 00677 this->SetSize (a2.Size()); 00678 for (int i = 0; i < size; i++) 00679 (*this)[i] = a2[i]; 00680 return *this; 00681 } 00682 00683 00684 template <typename T2, typename TA> 00685 ArrayMem & operator= (const BaseArrayObject<T2,TA> & a2) 00686 { 00687 this->SetSize (a2.Spec().Size()); 00688 for (int i = 0; i < size; i++) 00689 (*this)[i] = a2.Spec()[i]; 00690 return *this; 00691 } 00692 00693 }; 00694 00695 00696 00697 00698 00699 /* 00701 inline Array<int> & operator+= (Array<int> & array, const IntRange & range) 00702 { 00703 int oldsize = array.Size(); 00704 int s = range.Next() - range.First(); 00705 00706 array.SetSize (oldsize+s); 00707 00708 for (int i = 0; i < s; i++) 00709 array[oldsize+i] = range.First()+i; 00710 00711 return array; 00712 } 00713 */ 00714 00715 00716 template <typename T2, typename TA> 00717 inline Array<int> & operator+= (Array<int> & array, const BaseArrayObject<T2,TA> & a2) 00718 { 00719 int oldsize = array.Size(); 00720 int s = a2.Spec().Size(); 00721 00722 array.SetSize (oldsize+s); 00723 00724 for (int i = 0; i < s; i++) 00725 array[oldsize+i] = a2.Spec()[i]; 00726 00727 return array; 00728 } 00729 00730 00731 00732 00733 00734 00736 template <class T> 00737 inline void BubbleSort (const FlatArray<T> & data) 00738 { 00739 T hv; 00740 for (int i = 0; i < data.Size(); i++) 00741 for (int j = i+1; j < data.Size(); j++) 00742 if (data[i] > data[j]) 00743 { 00744 hv = data[i]; 00745 data[i] = data[j]; 00746 data[j] = hv; 00747 } 00748 } 00749 00751 template <class T, class S> 00752 inline void BubbleSort (FlatArray<T> & data, FlatArray<S> & slave) 00753 { 00754 for (int i = 0; i < data.Size(); i++) 00755 for (int j = i+1; j < data.Size(); j++) 00756 if (data[i] > data[j]) 00757 { 00758 T hv = data[i]; 00759 data[i] = data[j]; 00760 data[j] = hv; 00761 00762 S hvs = slave[i]; 00763 slave[i] = slave[j]; 00764 slave[j] = hvs; 00765 } 00766 } 00767 00768 00769 00770 00771 template <class T, typename TLESS> 00772 void QuickSort (FlatArray<T> data, TLESS less) 00773 { 00774 if (data.Size() <= 1) return; 00775 00776 int i = 0; 00777 int j = data.Size()-1; 00778 00779 T midval = data[ (i+j)/2 ]; 00780 00781 do 00782 { 00783 /* 00784 while (data[i] < midval) i++; 00785 while (midval < data[j]) j--; 00786 */ 00787 while (less (data[i], midval)) i++; 00788 while (less (midval, data[j])) j--; 00789 00790 if (i <= j) 00791 { 00792 Swap (data[i], data[j]); 00793 i++; j--; 00794 } 00795 } 00796 while (i <= j); 00797 00798 QuickSort (data.Range (0, j+1), less); 00799 QuickSort (data.Range (i, data.Size()), less); 00800 00801 // for (int i = 0; i < data.Size()-1; i++) 00802 // if (data[i+1] < data[i]) cerr << "quicksort is wrong !!" << endl; 00803 } 00804 00805 template <typename T> 00806 bool DefaultLess (const T & a, const T & b) 00807 { 00808 return a < b; 00809 } 00810 00811 template <class T> 00812 void QuickSort (FlatArray<T> data) 00813 { 00814 QuickSort (data, DefaultLess<T>); 00815 } 00816 00817 00818 00819 template <class T, typename TLESS> 00820 void QuickSortI (FlatArray<T> data, FlatArray<int> index, TLESS less) 00821 { 00822 if (index.Size() <= 1) return; 00823 00824 int i = 0; 00825 int j = index.Size()-1; 00826 00827 int midval = index[ (i+j)/2 ]; 00828 00829 do 00830 { 00831 /* 00832 while (data[index[i]] < data[midval]) i++; 00833 while (data[midval] < data[index[j]]) j--; 00834 */ 00835 while (less (data[index[i]],data[midval]) ) i++; 00836 while (less (data[midval], data[index[j]])) j--; 00837 00838 if (i <= j) 00839 { 00840 Swap (index[i], index[j]); 00841 i++; j--; 00842 } 00843 } 00844 while (i <= j); 00845 00846 QuickSortI (data, index.Range (0, j+1), less); 00847 QuickSortI (data, index.Range (i, index.Size()), less); 00848 } 00849 00850 00851 template <class T> 00852 void QuickSortI (FlatArray<T> data, FlatArray<int> index) 00853 { 00854 QuickSortI (data, index, DefaultLess<T>); 00855 } 00856 00857 00858 } 00859 00860 00861 #endif 00862