SparseMatrix.inl

Go to the documentation of this file.

//Copyright (c) 2004-2005, Baris Sumengen
//All rights reserved.
//
// CIMPL Matrix Performance Library
//
//Redistribution and use in source and binary
//forms, with or without modification, are
//permitted provided that the following
//conditions are met:
//
//    * No commercial use is allowed. 
//    This software can only be used
//    for non-commercial purposes. This 
//    distribution is mainly intended for
//    academic research and teaching.
//    * Redistributions of source code must
//    retain the above copyright notice, this
//    list of conditions and the following
//    disclaimer.
//    * Redistributions of binary form must
//    mention the above copyright notice, this
//    list of conditions and the following
//    disclaimer in a clearly visible part 
//    in associated product manual, 
//    readme, and web site of the redistributed 
//    software.
//    * Redistributions in binary form must
//    reproduce the above copyright notice,
//    this list of conditions and the
//    following disclaimer in the
//    documentation and/or other materials
//    provided with the distribution.
//    * The name of Baris Sumengen may not be
//    used to endorse or promote products
//    derived from this software without
//    specific prior written permission.
//
//THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT
//HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
//EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT
//NOT LIMITED TO, THE IMPLIED WARRANTIES OF
//MERCHANTABILITY AND FITNESS FOR A PARTICULAR
//PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
//CONTRIBUTORS BE LIABLE FOR ANY
//DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
//EXEMPLARY, OR CONSEQUENTIAL DAMAGES
//(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
//OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
//DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
//HOWEVER CAUSED AND ON ANY THEORY OF
//LIABILITY, WHETHER IN CONTRACT, STRICT
//LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
//OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
//OF THIS SOFTWARE, EVEN IF ADVISED OF THE
//POSSIBILITY OF SUCH DAMAGE.



namespace CIMPL
{



template< class T >
SparseMatrix<T>::SparseMatrix()
        : ndims(2), count(0)
{
        xDimStarts = 0;
        yDimStarts = 0;

        dims = new (std::nothrow) int[ndims];
        Utility::CheckPointer(dims);
        for(int j=0;j<ndims;j++)
        {
                dims[j] = 0;
        }
        
}




template< class T >
SparseMatrix<T>::SparseMatrix(const int xdim, const int ydim)
{
        if(xdim < 1 || ydim < 1)
        {
                cerr << "Line: " << __LINE__ << " File: " << __FILE__ << endl;
                Utility::RunTimeError("All array dimensions should be larger than 1!");
        }

        ndims = 2;
        count = 0;
        dims = new (std::nothrow) int[ndims];
        Utility::CheckPointer(dims);
        dims[0] = xdim;
        dims[1] = ydim;

        xDimStarts = new (std::nothrow) matrixCellStart<T>[xdim];
        Utility::CheckPointer(xDimStarts);
        for(int i=0; i<xdim; i++)
        {
                xDimStarts[i].listCount = 0;
                xDimStarts[i].first = new (std::nothrow) matrixCell<T>;
                Utility::CheckPointer(xDimStarts[i].first);
                xDimStarts[i].first->xNext = 0;
                xDimStarts[i].first->yNext = 0;
        }

        yDimStarts = new (std::nothrow) matrixCellStart<T>[ydim];
        Utility::CheckPointer(yDimStarts);
        for(int i=0; i<ydim; i++)
        {
                yDimStarts[i].listCount = 0;
                yDimStarts[i].first = new (std::nothrow) matrixCell<T>;
                Utility::CheckPointer(yDimStarts[i].first);
                yDimStarts[i].first->xNext = 0;
                yDimStarts[i].first->yNext = 0;
        }
        
        
}






template< class T >
SparseMatrix<T>::~SparseMatrix()
{

        

        for(int i=0; i<XDim(); i++)
        {
                matrixCell<T> *temp = xDimStarts[i].first;
                while(temp != 0)
                {
                        matrixCell<T> *c = temp->yNext;
                        delete temp;
                        temp = c;
                }
        }
        delete [] xDimStarts;
        
        for(int i=0; i<YDim(); i++)
        {
                delete yDimStarts[i].first;
        }
        delete [] yDimStarts;
        delete [] dims;

        
}





template< class T >
inline const int SparseMatrix<T>::Columns() const
{
        return dims[0];
}

template< class T >
inline const int SparseMatrix<T>::Rows() const
{
        return dims[1];
}


template< class T >
inline const int SparseMatrix<T>::XDim() const
{
        return dims[0];
}

template< class T >
inline const int SparseMatrix<T>::YDim() const
{
        if(ndims < 2)
        {
                cerr << "Line: " << __LINE__ << " File: " << __FILE__ << endl;
                Utility::RunTimeError("YDim(): Number of dimensions is less than 2!");
        }
        return dims[1];
}



template< class T >
inline const int SparseMatrix<T>::NNZ(void) const
{
        return count;
}


template< class T >
inline void SparseMatrix<T>::SetValue(const int x, const int y, const T value)
{
        if(x<0 || x>=dims[0] || y<0 || y>=dims[1])
        {
                cerr << "Line: " << __LINE__ << " File: " << __FILE__ << endl;
                Utility::RunTimeError("Index outside bounds!");
        }

        if(value == 0)
        {
                bool deleted = DeleteCell(x, y);
                if(deleted)
                {
                        xDimStarts[x].listCount--;
                        yDimStarts[y].listCount--;
                        count--;
                }
                return;
        }


        matrixCell<T> *c = new (std::nothrow) matrixCell<T>;
        Utility::CheckPointer(c);
        c->value = value;
        c->x = x;
        c->y = y;
        c->xNext = 0;
        c->yNext = 0;

        if( xDimStarts[x].listCount > yDimStarts[y].listCount )  // less elements for row scan
        {
                bool exists = AddCellYStart(c);
                if(!exists)
                {
                        AddCellXStart(c);
                        xDimStarts[x].listCount++;
                        yDimStarts[y].listCount++;
                        count++;
                }
        }
        else // less elements for column scan
        {
                bool exists = AddCellXStart(c);
                if(!exists)
                {
                        AddCellYStart(c);
                        xDimStarts[x].listCount++;
                        yDimStarts[y].listCount++;
                        count++;
                }
        }
}

template< class T >
inline T SparseMatrix<T>::GetValue(const int x, const int y)
{
        if(x<0 || x>=dims[0] || y<0 || y>=dims[1])
        {
                cerr << "Line: " << __LINE__ << " File: " << __FILE__ << endl;
                Utility::RunTimeError("Index outside bounds!");
        }

        if( xDimStarts[x].listCount > yDimStarts[y].listCount )  // less elements for row scan
        {
                return GetCellYStart(x, y);
        }
        else // less elements for column scan
        {
                return GetCellXStart(x, y);
        }
}





// OPERATORS

template< class T >
inline T SparseMatrix<T>::operator() (const int i, const int j)
{
        return GetValue(i, j);
}















// PRIVATE




template< class T >
bool SparseMatrix<T>::AddCellYStart(matrixCell<T> *c)
{
        matrixCell<T> *temp = yDimStarts[c->y].first;
        while(temp->xNext != 0)
        {
                if(temp->xNext->x == c->x)
                {
                        temp->xNext->value = c->value;
                        delete c;
                        return true;
                }
                else if(temp->xNext->x > c->x)
                {
                        c->xNext = temp->xNext;
                        temp->xNext = c;
                        return false;
                }
                
                temp = temp->xNext;
        }
        
        c->xNext = 0;
        temp->xNext = c;
        return false;
}



template< class T >
bool SparseMatrix<T>::AddCellXStart(matrixCell<T> *c)
{
        matrixCell<T> *temp = xDimStarts[c->x].first;
        while(temp->yNext != 0)
        {
                if(temp->yNext->y == c->y)
                {
                        temp->yNext->value = c->value;
                        delete c;
                        return true;
                }
                else if(temp->yNext->y > c->y)
                {
                        c->yNext = temp->yNext;
                        temp->yNext = c;
                        return false;
                }
                
                temp = temp->yNext;
        }
        
        c->yNext = 0;
        temp->yNext = c;
        return false;
}


template< class T >
T SparseMatrix<T>::GetCellYStart(const int x, const int y)
{
        matrixCell<T> *temp = yDimStarts[y].first;
        while(temp->xNext != 0)
        {
                if(temp->xNext->x == x)
                {
                        return temp->xNext->value;
                }
                else if(temp->xNext->x > x)
                {
                        return 0;
                }
                
                temp = temp->xNext;
        }
        
        return 0;
}

template< class T >
T SparseMatrix<T>::GetCellXStart(const int x, const int y)
{
        matrixCell<T> *temp = xDimStarts[x].first;
        while(temp->yNext != 0)
        {
                if(temp->yNext->y == y)
                {
                        return temp->yNext->value;
                }
                else if(temp->yNext->y > y)
                {
                        return 0;
                }

                temp = temp->yNext;
        }
        
        return 0;
}


template< class T >
bool SparseMatrix<T>::DeleteCell(const int x, const int y)
{
        matrixCell<T> *c = 0;
        bool deleted = false;
        
        matrixCell<T> *temp = yDimStarts[y].first;
        while(temp->xNext != 0)
        {
                if(temp->xNext->x == x)
                {
                        c = temp->xNext;
                        temp->xNext = c->xNext;
                        deleted = true;
                        break;
                }
                else if(temp->xNext->x > c->x)
                {
                        return false;
                }

                temp = temp->xNext;
        }

        if(deleted == false)
        {
                return false;
        }

        temp = xDimStarts[x].first;
        while(temp->yNext != 0)
        {
                if(temp->yNext->y == y)
                {
                        c = temp->yNext;
                        temp->yNext = c->yNext;
                        deleted = true;
                        break;
                }
                else if(temp->yNext->y > c->y)
                {
                        return false;
                }
                
                temp = temp->yNext;
        }
        if(deleted == false)
        {
                return false;
        }

        delete c;
        return true;
}




}; //namespace

---