Main Page Namespace List Class Hierarchy Compound List File List Namespace Members Compound Members File Members Related Pages

# SmartArray.h

Go to the documentation of this file.

    00001
    00042 #ifndef __SMART_ARRAY_H__
    00043 #define __SMART_ARRAY_H__
    00044
    00045 #include <memory.h>
    00046 #include <search.h>
    00047 #include "Debug.h"
    00048
    00049 using namespace std;
    00050
    00066 template<class T> class SmartArray
    00067 {
    00068         struct DATAREF {
    00069                 T* pData;
    00070                 int nLastItem;
    00071                 int nSize;
    00072                 int nRealSize;
    00073                 int nGrowFactor;
    00074                 int nLinks;
    00075
    00076                 DATAREF(int nGF)  { nLinks = 1; nGrowFactor = nGF; ASSERT(nGF > 0); }
    00077         };
    00078
    00079         DATAREF* ptr;
    00080
    00081 private:
    00082         void Unlink();
    00083
    00084 protected:
    00085         const T* GetData() const { return ptr->pData; }
    00086
    00087 public:
    00088
    00089         SmartArray(int nSize = 0, int nGrowFactor = 1) {
    00090                 ptr = new DATAREF(nGrowFactor);
    00091                 ptr->pData = (nSize > 0) ? new T[nSize]:NULL;
    00092                 ptr->nLastItem = 0;
    00093                 ptr->nSize = nSize;
    00094                 ptr->nRealSize = nSize;
    00095                 ASSERT(ptr->nSize == 0 || ptr->pData != NULL);
    00096         }
    00097
    00098         SmartArray(const SmartArray& x) {
    00099                 ptr = x.ptr;
    00100                 ptr->nLinks++;
    00101         }
    00102
    00103         ~SmartArray() {
    00104                 if (--ptr->nLinks == 0)
    00105                 {
    00106                         delete[] ptr->pData;
    00107                         delete ptr;
    00108                 }
    00109         }
    00110
    00111         const T& operator[](int i) const {
    00112                 ASSERT(i >= 0 && i < ptr->nSize);
    00113                 return ptr->pData[i];
    00114         }
    00115
    00116         operator const T*() const { return ptr->pData; }
    00117
    00118         int GetSize() const { return ptr->nSize; }
    00119         int GetTailIdx() const { return ptr->nLastItem - 1; }
    00120
    00121         ostream& Write(ostream& os) const
    00122         {
    00123                 os.write((char*)&(ptr->nSize), sizeof(ptr->nSize));
    00124
    00125                 if (ptr->nSize > 0)
    00126                         os.write((char*)(ptr->pData), sizeof(T) * ptr->nSize);
    00127                 //for (int i = 0; i < ptr->nSize; i++)
    00128                 //      os << operator[](i);
    00129
    00130                 return os;
    00131         }
    00132
    00133         void Print(ostream& os = cout, const char* pSep = NULL) const
    00134         {
    00135                 ASSERT(ptr->nSize >= 0);
    00136
    00137                 if (pSep == NULL)
    00138                         pSep = ", ";
    00139
    00140                 os << '[';
    00141                 for (int i = 0; i < ptr->nSize; i++) {
    00142                         os << operator[](i);
    00143                         if (i < ptr->nSize - 1)
    00144                                 os << pSep;
    00145                 }
    00146                 os << ']';
    00147         }
    00148
    00149         bool operator==(const SmartArray& rhs) const
    00150         {
    00151                 if (GetSize() != rhs.GetSize())
    00152                         return false;
    00153
    00154                 for (int i = 0; i < ptr->nSize; i++)
    00155                         if (operator[](i) != rhs.operator[](i))
    00156                                 return false;
    00157
    00158                 return true;
    00159         }
    00160
    00161         bool operator!=(const SmartArray& rhs) const
    00162         {
    00163                 return !operator==(rhs);
    00164         }
    00165
    00166         SmartArray Left(int nEnd) const
    00167         {
    00168                 ASSERT(nEnd >= 0 && nEnd < GetSize());
    00169
    00170                 SmartArray l(nEnd + 1);
    00171
    00172                 for (int i = 0; i <= nEnd; i++)
    00173                         l[i] = operator[](i);
    00174
    00175                 return l;
    00176         }
    00177
    00178         SmartArray Right(int nStart) const
    00179         {
    00180                 ASSERT(nStart >= 0 && nStart < GetSize());
    00181
    00182                 SmartArray r(GetSize() - nStart);
    00183
    00184                 for (int i = nStart; i < GetSize(); i++)
    00185                         r[i - nStart] = operator[](i);
    00186
    00187                 return r;
    00188         }
    00189
    00190         SmartArray Reverse() const
    00191         {
    00192                 int nSize = GetSize();
    00193                 SmartArray r(nSize);
    00194
    00195                 for (int i = 0; i < nSize; i++)
    00196                         r[nSize - i - 1] = (*this)[i];
    00197
    00198                 return r;
    00199         }
    00200
    00201         T operator*(const SmartArray& rhs) const
    00202         {
    00203                 ASSERT(GetSize() == rhs.GetSize());
    00204
    00205                 T n = 0;
    00206
    00207                 for (int i = 0; i < GetSize(); i++)
    00208                         n += operator[](i) * rhs[i];
    00209
    00210                 return n;
    00211         }
    00212
    00213         SmartArray operator-(const SmartArray& rhs) const
    00214         {
    00215                 ASSERT(GetSize() == rhs.GetSize());
    00216                 SmartArray v(GetSize());
    00217
    00218                 for (int i = 0; i < GetSize(); i++)
    00219                         v[i] = operator[](i) - rhs[i];
    00220
    00221                 return v;
    00222         }
    00223
    00224         T Sum() const
    00225         {
    00226                 T sum = 0;
    00227
    00228                 for (int i = 0; i < GetSize(); i++)
    00229                         sum += (*this)[i];
    00230
    00231                 return sum;
    00232         }
    00233
    00234 // Non-const functions. All these functions must unlink the data if necessary.
    00235
    00236         T& operator[](int i) {
    00237                 ASSERT(i >= 0 && i < ptr->nSize);
    00238
    00239                 if (ptr->nLinks > 1)
    00240                         Unlink();
    00241
    00242                 return ptr->pData[i];
    00243         }
    00244
    00245         const T& GetTail() const { return operator[](GetSize() - 1); }
    00246         const T& GetHead() const { return operator[](0); }
    00247
    00248         SmartArray& operator=(const SmartArray& rhs) {
    00249
    00250                 rhs.ptr->nLinks++;      // protect against 'x = x'
    00251
    00252                 if (--ptr->nLinks == 0)
    00253                 {
    00254                         delete[] ptr->pData;
    00255                         delete ptr;
    00256                 }
    00257
    00258                 ptr = rhs.ptr;
    00259                 return *this;
    00260         }
    00261
    00262         void Sort(int (*Compare)(const void *elem1, const void *elem2 ) )
    00263         {
    00264                 if (GetSize() > 0)
    00265                 {
    00266                   if (ptr->nLinks > 1)
    00267                         Unlink();
    00268
    00269                   qsort(ptr->pData, ptr->nSize, sizeof(T), Compare);
    00270                 }
    00271         }
    00272
    00274         void Set(const T& x)
    00275         {
    00276                 for (int i = 0; i < GetSize(); i++)
    00277                         (*this)[i] = x;
    00278         }
    00279
    00282         void Add(const T& x) {
    00283                 ASSERT(ptr->nLastItem < ptr->nSize);
    00284                 ptr->pData[ptr->nLastItem++] = x; // operator[]'ll handle the reference problem.
    00285         }
    00286
    00289         void AddTail(const T& x)
    00290         {
    00291                 if (ptr->nLastItem >= ptr->nSize)
    00292                 {
    00293                         if (ptr->nLastItem < ptr->nRealSize)
    00294                         {
    00295                                 if (ptr->nLinks > 1)
    00296                                         Unlink();
    00297
    00298                                 ptr->nSize++;
    00299                         }
    00300                         else
    00301                         {
    00302                                 ASSERT(ptr->nSize == ptr->nRealSize);
    00303
    00304                                 const SmartArray<T> a(*this);
    00305
    00306                                 ReSize(ptr->nRealSize + ptr->nGrowFactor);
    00307                                 memcpy(ptr->pData, a.GetData(), a.GetSize() * sizeof(T));
    00308
    00309                                 ptr->nSize = a.GetSize() + 1;
    00310                                 ptr->nLastItem = a.GetSize();
    00311                         }
    00312                 }
    00313
    00314                 Add(x);
    00315         }
    00316
    00317         void AddTail(const SmartArray<T>& tail)
    00318         {
    00319                 for (int i = 0; i < GetSize(); i++)
    00320                         AddTail(tail[i]);
    00321         }
    00322
    00323         void ReSize(int size, bool bInit = false)
    00324         {
    00325                 ASSERT(size >= 0);
    00326
    00327                 if (size != ptr->nSize || ptr->nLinks > 1)
    00328                 {
    00329                         if (ptr->nLinks > 1)
    00330                         {
    00331                                 ptr->nLinks--;
    00332                                 ptr = new DATAREF(ptr->nGrowFactor);
    00333                         }
    00334                         else if (ptr->pData)
    00335                                 delete[] ptr->pData;
    00336
    00337                         ptr->pData = (size > 0) ? new T[size]:NULL;
    00338                         ptr->nSize = size;
    00339                         ptr->nRealSize = size;
    00340                         ASSERT((size > 0 && ptr->pData != NULL) || size == 0);
    00341                 }
    00342
    00343                 ptr->nLastItem = 0;
    00344
    00345                 if (bInit && size > 0)
    00346                         memset(ptr->pData, 0, size * sizeof(T));
    00347         }
    00348
    00349         void Clear()
    00350         {
    00351                 ReSize(0);
    00352         }
    00353
    00354         istream& Read(istream& is)
    00355         {
    00356                 int size = 0; // set to zero in case read fails
    00357                 is.read((char*)&size, sizeof(size));
    00358
    00359                 ReSize(size);   // ReSize() will handle the multiple references issue.
    00360
    00361                 if (size > 0)
    00362                 {
    00363                         is.read((char*)(ptr->pData), sizeof(T) * size);
    00364                         //for (int i = 0; i < size; i++)
    00365                         //      is >> operator[](i);
    00366
    00367                         ptr->nLastItem = size;
    00368                 }
    00369
    00370                 return is;
    00371         }
    00372
    00373         friend ostream& operator<<(ostream& os, const SmartArray<T>& x) { return x.Write(os); }
    00374         friend istream& operator>>(istream& is, SmartArray<T>& x) { return x.Read(is); }
    00375 };
    00376
    00377 template<class T> void SmartArray<T>::Unlink()
    00378 {
    00379         ASSERT(ptr->nLinks > 1);
    00380
    00381         DATAREF* op = ptr;
    00382         ptr = new DATAREF(op->nGrowFactor);
    00383
    00384         ptr->pData = new T[op->nSize];
    00385         ptr->nLastItem = op->nLastItem;
    00386         ptr->nSize = op->nSize;
    00387         ptr->nRealSize = op->nSize;
    00388
    00389         //memcpy(ptr->pData, op->pData, op->nSize * sizeof(T));
    00390         for (int i = 0; i < op->nSize; i++)
    00391                 ptr->pData[i] = op->pData[i];
    00392
    00393         op->nLinks--;
    00394
    00395         //WARNING(true, "possible not desired copy of data");
    00396 }
    00397
    00398 template <class T> class SmartMatrix : public SmartArray< SmartArray<T> >
    00399 {
    00400
    00406     void ReSize(int size, bool bInit = false)
    00407     {
    00408                 SmartArray< SmartArray<T> >::ReSize(size, bInit);
    00409         }
    00410
    00411 public:
    00412         void ReSize(int rows, int cols, bool bInit = false)
    00413         {
    00414                 ReSize(rows, false);
    00415
    00416                 for (int i = 0; i < GetSize(); i++)
    00417                         operator[](i).ReSize(cols, bInit);
    00418         }
    00419
    00420         ostream& Write(ostream& os) const
    00421         {
    00422                 int nSize = GetSize();
    00423
    00424                 os.write((char*) &nSize, sizeof(nSize));
    00425
    00426                 if (nSize > 0)
    00427                   for (int i = 0; i < nSize; i++)
    00428                         operator[](i).Write(os);
    00429
    00430                 return os;
    00431         }
    00432
    00433         istream& Read(istream& is)
    00434         {
    00435                 int size = 0; // set to zero in case read fails
    00436                 is.read((char*)&size, sizeof(size));
    00437
    00438                 ReSize(size);
    00439
    00440                 if (size > 0)
    00441                   for (int i = 0; i < GetSize(); i++)
    00442                         operator[](i).Read(is);
    00443
    00444                 return is;
    00445         }
    00446
    00447         int NRows() const { return GetSize(); }
    00448         int NCols() const { return (GetSize() > 0) ? (*this)[0].GetSize():0; }
    00449
    00450         T RowSum(int nRow) const
    00451         {
    00452           const SmartArray<T>& row = operator[](nRow);
    00453           int size = row.GetSize();
    00454           T sum = 0;
    00455
    00456           for (int i = 0; i < size; i++)
    00457                 sum += row[i];
    00458
    00459           return sum;
    00460         }
    00461
    00462         const SmartMatrix& Transpose() const
    00463         {
    00464                 SmartMatrix t;
    00465                 int i, j;
    00466
    00467                 t.ReSize(NCols(), NRows(), false);
    00468
    00469                 for (i = 0; i < NRows(); i++)
    00470                         for (j = 0; j < NCols(); j++)
    00471                                 t[j][i] = (*this)[i][j];
    00472
    00473                 return t;
    00474         }
    00475
    00476         SmartArray<T> operator*(const SmartArray<T>& v) const
    00477         {
    00478                 ASSERT(NCols() == v.GetSize());
    00479
    00480                 SmartArray<T> r(v.GetSize());
    00481
    00482                 for (int i = 0; i < NRows(); i++)
    00483                         r[i] = (*this)[i] * v;
    00484
    00485                 return r;
    00486         }
    00487
    00488         /*SmartMatrix operator*(const SmartMatrix& rhs) const
    00489         {
    00490                 ASSERT(NCols() == rhs.NRows());
    00491
    00492                 SmartMatrix t;
    00493                 SmartMatrix m;
    00494                 int i, j;
    00495
    00496                 m.ReSize(NRows(), rhs.NCols(), false);
    00497                 t = rhs.Transpose();
    00498
    00499                 for (i = 0; i < NRows(); i++)
    00500                         for (j = 0; j < rhs.NCols(); j++)
    00501                                 m[i][j] = (*this)[i] * t[j];
    00502
    00503                 return m;
    00504         }*/
    00505
    00506         SmartMatrix operator-(const SmartMatrix& rhs) const
    00507         {
    00508                 ASSERT(NRows() == rhs.NRows() && NCols() == rhs.NCols());
    00509                 SmartMatrix m;
    00510
    00511                 m.ReSize(NRows(), false);
    00512
    00513                 for (int i = 0; i < NRows(); i++)
    00514                         m[i] = (*this)[i] - rhs[i];
    00515
    00516                 return m;
    00517         }
    00518
    00519         void Print(ostream& os = std::cout, int width = 3, int precision = 6, bool bShowLabels = true) const
    00520         {
    00521                 int i, j;
    00522
    00523                 os << setprecision(precision); // useful when T is double
    00524
    00525                 os << "[\n";
    00526
    00527                 if (bShowLabels)
    00528                 {
    00529                         os << setw(width) << '#';
    00530
    00531                         for (int j = 0; j < NCols(); j++)
    00532                                 os << setw(width) << j;
    00533
    00534                         os << "\n";
    00535                 }
    00536
    00537                 for (int i = 0; i < NRows(); i++)
    00538                 {
    00539                         if (bShowLabels)
    00540                                 os << setw(width) << i;
    00541
    00542                         for (int j = 0; j < NCols(); j++)
    00543                                 os << setw(width) << (*this)[i][j];
    00544
    00545                         os << "\n";
    00546                 }
    00547
    00548                 os << ']';
    00549
    00550                 os << setprecision(6); // back to default value
    00551         }
    00552 };
    00553
    00554 #endif //__SMART_ARRAY_H__