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.






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

    dims = new 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 int[ndims];
    Utility::CheckPointer(dims);
    dims[0] = xdim;
    dims[1] = ydim;

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

    yDimStarts = new matrixCellStart<T>[ydim];
    Utility::CheckPointer(yDimStarts);
    for(int i=0; i<ydim; i++)
    {
        yDimStarts[i].listCount = 0;
        yDimStarts[i].first = new matrixCell<T>;
        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 matrixCell<T>;
    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;
}

CIMPL 0.1 Code Reference. Copyright © 2004, Baris Sumengen. All rights reserved.