NGSolve  4.9
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 
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