---

SmartArray.h

Go to the documentation of this file.

#ifndef __SMART_ARRAY_H__
#define __SMART_ARRAY_H__

#include <memory.h>
#include <search.h>
#include "Debug.h"

using namespace std;

template<class T> class SmartArray
{
        struct DATAREF {
                T* pData;
                int nLastItem;
                int nSize;
                int nRealSize;
                int nGrowFactor;
                int nLinks;
                
                DATAREF(int nGF)  { nLinks = 1; nGrowFactor = nGF; ASSERT(nGF > 0); }
        };

        DATAREF* ptr;

private:
        void Unlink();

protected:
        const T* GetData() const { return ptr->pData; }

public:

        SmartArray(int nSize = 0, int nGrowFactor = 1) { 
                ptr = new DATAREF(nGrowFactor); 
                ptr->pData = (nSize > 0) ? new T[nSize]:NULL;
                ptr->nLastItem = 0;
                ptr->nSize = nSize;
                ptr->nRealSize = nSize;
                ASSERT(ptr->nSize == 0 || ptr->pData != NULL);
        }

        SmartArray(const SmartArray& x) { 
                ptr = x.ptr;
                ptr->nLinks++;
        }

        ~SmartArray() { 
                if (--ptr->nLinks == 0)
                {
                        delete[] ptr->pData;
                        delete ptr;
                }
        }       

        const T& operator[](int i) const { 
                ASSERT(i >= 0 && i < ptr->nSize);
                return ptr->pData[i]; 
        }

        operator const T*() const { return ptr->pData; }

        int GetSize() const { return ptr->nSize; }
        int GetTailIdx() const { return ptr->nLastItem - 1; }

        ostream& Write(ostream& os) const
        {
                os.write((char*)&(ptr->nSize), sizeof(ptr->nSize));     

                if (ptr->nSize > 0)
                        os.write((char*)(ptr->pData), sizeof(T) * ptr->nSize);
                //for (int i = 0; i < ptr->nSize; i++)
                //      os << operator[](i);

                return os;
        }

        void Print(ostream& os = cout, const char* pSep = NULL) const
        {
                ASSERT(ptr->nSize >= 0);
                
                if (pSep == NULL)
                        pSep = ", ";

                os << '[';
                for (int i = 0; i < ptr->nSize; i++) {
                        os << operator[](i);
                        if (i < ptr->nSize - 1)
                                os << pSep;
                }
                os << ']';
        }

        bool operator==(const SmartArray& rhs) const
        {
                if (GetSize() != rhs.GetSize())
                        return false;

                for (int i = 0; i < ptr->nSize; i++)
                        if (operator[](i) != rhs.operator[](i))
                                return false;
                
                return true;
        }

        bool operator!=(const SmartArray& rhs) const
        {
                return !operator==(rhs);
        }

        SmartArray Left(int nEnd) const
        {
                ASSERT(nEnd >= 0 && nEnd < GetSize());

                SmartArray l(nEnd + 1);

                for (int i = 0; i <= nEnd; i++)
                        l[i] = operator[](i);
                
                return l;
        }

        SmartArray Right(int nStart) const
        {
                ASSERT(nStart >= 0 && nStart < GetSize());

                SmartArray r(GetSize() - nStart);

                for (int i = nStart; i < GetSize(); i++)
                        r[i - nStart] = operator[](i);
                
                return r;
        }

        SmartArray Reverse() const
        {
                int nSize = GetSize();
                SmartArray r(nSize);

                for (int i = 0; i < nSize; i++)
                        r[nSize - i - 1] = (*this)[i];

                return r;
        }
        
        T operator*(const SmartArray& rhs) const
        {
                ASSERT(GetSize() == rhs.GetSize());
                
                T n = 0;
                
                for (int i = 0; i < GetSize(); i++)
                        n += operator[](i) * rhs[i];
                        
                return n;
        }
        
        SmartArray operator-(const SmartArray& rhs) const
        {
                ASSERT(GetSize() == rhs.GetSize());
                SmartArray v(GetSize());
                
                for (int i = 0; i < GetSize(); i++)
                        v[i] = operator[](i) - rhs[i];
                        
                return v;
        }
        
        T Sum() const
        {
                T sum = 0;
                
                for (int i = 0; i < GetSize(); i++)
                        sum += (*this)[i];
                        
                return sum;
        }

// Non-const functions. All these functions must unlink the data if necessary.

        T& operator[](int i) {
                ASSERT(i >= 0 && i < ptr->nSize);

                if (ptr->nLinks > 1)
                        Unlink();

                return ptr->pData[i]; 
        }

        const T& GetTail() const { return operator[](GetSize() - 1); }
        const T& GetHead() const { return operator[](0); }

        SmartArray& operator=(const SmartArray& rhs) {

                rhs.ptr->nLinks++;      // protect against 'x = x'
                
                if (--ptr->nLinks == 0)
                {
                        delete[] ptr->pData;
                        delete ptr;
                }

                ptr = rhs.ptr;
                return *this;
        }

        void Sort(int (*Compare)(const void *elem1, const void *elem2 ) )
        {
                if (GetSize() > 0)
                {         
                  if (ptr->nLinks > 1)
                        Unlink();
                
                  qsort(ptr->pData, ptr->nSize, sizeof(T), Compare);
                }
        }
        
        void Set(const T& x)
        {
                for (int i = 0; i < GetSize(); i++)
                        (*this)[i] = x;
        }

        void Add(const T& x) { 
                ASSERT(ptr->nLastItem < ptr->nSize); 
                ptr->pData[ptr->nLastItem++] = x; // operator[]'ll handle the reference problem.
        }

        void AddTail(const T& x) 
        {
                if (ptr->nLastItem >= ptr->nSize)
                {
                        if (ptr->nLastItem < ptr->nRealSize)
                        {
                                if (ptr->nLinks > 1)
                                        Unlink();

                                ptr->nSize++;
                        }
                        else
                        {
                                ASSERT(ptr->nSize == ptr->nRealSize);

                                const SmartArray<T> a(*this);

                                ReSize(ptr->nRealSize + ptr->nGrowFactor);
                                memcpy(ptr->pData, a.GetData(), a.GetSize() * sizeof(T));

                                ptr->nSize = a.GetSize() + 1;
                                ptr->nLastItem = a.GetSize();
                        }
                }

                Add(x);
        }
        
        void AddTail(const SmartArray<T>& tail)
        {
                for (int i = 0; i < GetSize(); i++)
                        AddTail(tail[i]);
        }

        void ReSize(int size, bool bInit = false)
        {
                ASSERT(size >= 0);

                if (size != ptr->nSize || ptr->nLinks > 1)
                {
                        if (ptr->nLinks > 1) 
                        {
                                ptr->nLinks--;
                                ptr = new DATAREF(ptr->nGrowFactor);
                        }
                        else if (ptr->pData) 
                                delete[] ptr->pData;

                        ptr->pData = (size > 0) ? new T[size]:NULL;
                        ptr->nSize = size;
                        ptr->nRealSize = size;
                        ASSERT((size > 0 && ptr->pData != NULL) || size == 0);
                }

                ptr->nLastItem = 0;

                if (bInit && size > 0)
                        memset(ptr->pData, 0, size * sizeof(T));
        }

        void Clear()
        {
                ReSize(0);
        }

        istream& Read(istream& is)
        {
                int size = 0; // set to zero in case read fails
                is.read((char*)&size, sizeof(size));

                ReSize(size);   // ReSize() will handle the multiple references issue.

                if (size > 0)
                {
                        is.read((char*)(ptr->pData), sizeof(T) * size);
                        //for (int i = 0; i < size; i++)
                        //      is >> operator[](i);

                        ptr->nLastItem = size;
                }

                return is;
        }

        friend ostream& operator<<(ostream& os, const SmartArray<T>& x) { return x.Write(os); }
        friend istream& operator>>(istream& is, SmartArray<T>& x) { return x.Read(is); }
};

template<class T> void SmartArray<T>::Unlink()
{
        ASSERT(ptr->nLinks > 1);

        DATAREF* op = ptr;
        ptr = new DATAREF(op->nGrowFactor);

        ptr->pData = new T[op->nSize];
        ptr->nLastItem = op->nLastItem;
        ptr->nSize = op->nSize;
        ptr->nRealSize = op->nSize;

        //memcpy(ptr->pData, op->pData, op->nSize * sizeof(T));
        for (int i = 0; i < op->nSize; i++)
                ptr->pData[i] = op->pData[i];

        op->nLinks--;

        //WARNING(true, "possible not desired copy of data");
}

template <class T> class SmartMatrix : public SmartArray< SmartArray<T> >
{

    void ReSize(int size, bool bInit = false) 
    { 
                SmartArray< SmartArray<T> >::ReSize(size, bInit);
        }

public:
        void ReSize(int rows, int cols, bool bInit = false)
        {
                ReSize(rows, false);

                for (int i = 0; i < GetSize(); i++)
                        operator[](i).ReSize(cols, bInit);
        }

        ostream& Write(ostream& os) const
        {
                int nSize = GetSize();

                os.write((char*) &nSize, sizeof(nSize));        

                if (nSize > 0)
                  for (int i = 0; i < nSize; i++)
                        operator[](i).Write(os);
                        
                return os;
        }

        istream& Read(istream& is)
        {
                int size = 0; // set to zero in case read fails
                is.read((char*)&size, sizeof(size));

                ReSize(size);

                if (size > 0)
                  for (int i = 0; i < GetSize(); i++)
                        operator[](i).Read(is);

                return is;
        }
        
        int NRows() const { return GetSize(); }
        int NCols() const { return (GetSize() > 0) ? (*this)[0].GetSize():0; }

        T RowSum(int nRow) const
        {
          const SmartArray<T>& row = operator[](nRow);
          int size = row.GetSize();
          T sum = 0;

          for (int i = 0; i < size; i++)
                sum += row[i];

          return sum;
        }
        
        const SmartMatrix& Transpose() const
        {
                SmartMatrix t;
                int i, j;
                
                t.ReSize(NCols(), NRows(), false);
                
                for (i = 0; i < NRows(); i++)
                        for (j = 0; j < NCols(); j++)
                                t[j][i] = (*this)[i][j];
                
                return t;
        }
        
        SmartArray<T> operator*(const SmartArray<T>& v) const
        {
                ASSERT(NCols() == v.GetSize());
                
                SmartArray<T> r(v.GetSize());
                
                for (int i = 0; i < NRows(); i++)
                        r[i] = (*this)[i] * v;
                        
                return r;
        }
        
        /*SmartMatrix operator*(const SmartMatrix& rhs) const
        {
                ASSERT(NCols() == rhs.NRows());
                
                SmartMatrix t;
                SmartMatrix m;
                int i, j;
                
                m.ReSize(NRows(), rhs.NCols(), false);
                t = rhs.Transpose();
                
                for (i = 0; i < NRows(); i++)
                        for (j = 0; j < rhs.NCols(); j++)
                                m[i][j] = (*this)[i] * t[j];
                        
                return m;
        }*/
        
        SmartMatrix operator-(const SmartMatrix& rhs) const
        {
                ASSERT(NRows() == rhs.NRows() && NCols() == rhs.NCols());
                SmartMatrix m;
                
                m.ReSize(NRows(), false);
                
                for (int i = 0; i < NRows(); i++)
                        m[i] = (*this)[i] - rhs[i];
                        
                return m;
        }
        
        void Print(ostream& os = std::cout, int width = 3, int precision = 6, bool bShowLabels = true) const
        {
                int i, j;
                
                os << setprecision(precision); // useful when T is double
                
                os << "[\n";
                
                if (bShowLabels)
                {
                        os << setw(width) << '#';
                        
                        for (int j = 0; j < NCols(); j++)
                                os << setw(width) << j;
                                
                        os << "\n";
                }
                
                for (int i = 0; i < NRows(); i++)
                {
                        if (bShowLabels)
                                os << setw(width) << i;
                                
                        for (int j = 0; j < NCols(); j++)
                                os << setw(width) << (*this)[i][j];
                                
                        os << "\n";
                }
                        
                os << ']';
                
                os << setprecision(6); // back to default value
        }
};

#endif //__SMART_ARRAY_H__

---