SparseArray.h

Go to the documentation of this file.

/*  Copyright (C) 2003-2021 Free Electron Organization
    Any use of this software requires a license.  If a valid license
    was not distributed with this file, visit freeelectron.org. */

/** @file */

#ifndef __solve_SparseArray_h__
#define __solve_SparseArray_h__

#define FE_SA_PREALLOC  8
#define FE_SA_GROW      1.5f

namespace fe
{
namespace ext
{

/**************************************************************************//**
    @brief Row-Compressed Sparse Container

    @ingroup solve
*//***************************************************************************/
template<class T>
class SparseArray
{
    public:
                    SparseArray(U32 prealloc=FE_SA_PREALLOC);
                    SparseArray(const SparseArray<T> &other);
                    ~SparseArray(void);

        SparseArray<T>& operator=(const SparseArray<T> &other);

                    /// @brief Remove all existing values
        void        reset(U32 prealloc=FE_SA_PREALLOC);

                    /// @brief Zero existing values, but do not remove
        void        clear(void);

                    /// @brief Return the largest index
        U32         size(void) const { return m_used? m_maxIndex+1: 0; }

                    /// @brief Return the entry at the particular index
        T&          operator[](U32 index);

                    /// @brief Return the const entry at the particular index
        T           operator[](U32 index) const;

                    /** @brief Return the number of actual stored entries

                        This can be less than the size.
                        Using entry() instead of operator[] can be helpful
                        to limit an iteration to only the values that
                        are actually set, instead of reading lots of zeros.
                        */
        U32         entries(void) const         { return m_used; }

                    /// @brief Return the index at a storage location
        U32         index(U32 location) const   { return m_pIndex[location]; }

                    /// @brief Return the entry at a storage location
        T&          entry(U32 location)         { return m_pData[location]; }

                    /// @brief Return the const entry at a storage location
        T           entry(U32 location) const   { return m_pData[location]; }


    private:
        void        grow(void);
        void        initialize(U32 prealloc);

        U32     m_allocated;
        U32     m_used;
        U32     m_maxIndex;
        U32     m_cacheLocation;
        U32*    m_pIndex;
        T*      m_pData;
};


template<class T>
inline SparseArray<T>::SparseArray(U32 prealloc):
        m_pIndex(NULL),
        m_pData(NULL)
{
    initialize(prealloc);
}

template<class T>
inline void SparseArray<T>::initialize(U32 prealloc)
{
    if(prealloc)
    {
        m_pIndex=new U32[prealloc];
        m_pData=new T[prealloc];
    }

    m_allocated=prealloc;
    m_used=0;
    m_maxIndex=0;
    m_cacheLocation=0;
}

template<class T>
inline SparseArray<T>::SparseArray(const SparseArray<T> &other):
        m_used(0),
        m_pIndex(NULL),
        m_pData(NULL)
{
    operator=(other);
}

template<class T>
inline SparseArray<T>::~SparseArray(void)
{
    delete[] m_pIndex;
    delete[] m_pData;
}

template<class T>
inline void SparseArray<T>::reset(U32 prealloc)
{
    delete[] m_pIndex;
    delete[] m_pData;
    initialize(prealloc);
}

template<class T>
inline void SparseArray<T>::clear(void)
{
    for(U32 m=0;m<m_used;m++)
    {
        m_pData[m]=defaultByType(m_pData[0]);
    }
}

template<class T>
inline T& SparseArray<T>::operator[](U32 index)
{
    while(m_cacheLocation &&
            (m_cacheLocation>=m_used || m_pIndex[m_cacheLocation]>index))
        m_cacheLocation--;
    while(m_cacheLocation<m_used && m_pIndex[m_cacheLocation]<index)
        m_cacheLocation++;

    if(m_cacheLocation>=m_used || m_pIndex[m_cacheLocation]!=index)
    {
        if(m_used==m_allocated)
        {
            grow();
        }
        for(U32 m=m_used;m>m_cacheLocation;m--)
        {
            m_pIndex[m]=m_pIndex[m-1];
            m_pData[m]=m_pData[m-1];
        }
        m_pIndex[m_cacheLocation]=index;
        m_pData[m_cacheLocation]=defaultByType(m_pData[0]);
        m_used++;

        if(m_maxIndex<index)
        {
            m_maxIndex=index;
        }
    }

    return m_pData[m_cacheLocation];
}

template<class T>
inline T SparseArray<T>::operator[](U32 index) const
{
    U32 location=0;
    while(location<m_used && m_pIndex[location]<index)
        location++;

    if(location<m_used && m_pIndex[location]==index)
    {
        return m_pData[location];
    }

    return defaultByType(m_pData[0]);
}

template<class T>
inline SparseArray<T> &SparseArray<T>::operator=(const SparseArray<T> &other)
{
    if(this != &other)
    {
        clear();

        U32 count=other.m_used;
        for(U32 i = 0; i < count; i++)
        {
            operator[](other.m_pIndex[i])=other.m_pData[i];
        }
    }
    m_cacheLocation=0;
    return *this;
}

template<class T>
inline void SparseArray<T>::grow(void)
{
    U32 newsize=U32(m_allocated*FE_SA_GROW);
    U32* pNewIndex=new U32[newsize];
    T* pNewData=new T[newsize];

    //* TODO we could do the insertion shift here instead of copying some twice
    for(U32 m=0;m<m_used;m++)
    {
        pNewIndex[m]=m_pIndex[m];
        pNewData[m]=m_pData[m];
    }

    delete[] m_pIndex;
    delete[] m_pData;

    m_allocated=newsize;
    m_pIndex=pNewIndex;
    m_pData=pNewData;
}

/** Print to a string
    @relates SparseArray
    */
template<class T>
inline String print(const SparseArray<T> &rhs,BWORD sparse=FALSE)
{
    U32 size=sparse? rhs.entries(): rhs.size();

    String s = "";
    for(U32 i = 0; i < size; i++)
    {
        if(i)
        {
            s.cat(" ");
        }
        if(sparse)
        {
            s.catf("%d:%.6G", rhs.index(i), rhs.entry(i));
        }
        else
        {
            s.catf("%.6G", rhs[i]);
        }
    }
    return s;
}

} /* namespace ext */
} /* namespace fe */

#endif /* __solve_SparseArray_h__ */