NGSolve  5.3
ngstd/array.hpp
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