ArrayEx.h

/************************************************************

  ArrayEx.h

  An improved array template class provides functionalities that are
  similar to the MFC "CArray" class except that:

  a) No need to link MFC libraries, can be used in any win32 applications.
  b) Implemented elements sorting and searching methods using the
     "qsort" and "bsearch" algorithms (requiring operators ">" and "=="
         being defined for stored element data type.
  c) The constant operator[] now returns "const TYPE&" instead of
     a "TYPE" instance, which was the case in "CArray".

  Written by: Abin (abinn32@yahoo.com)

  May 08, 2004		Initial release.
*************************************************************/

#ifndef __ARRAYEX_H__
#define __ARRAYEX_H__

#pragma warning(disable : 4311)

#define USE_MULTI_THREAD // uncomment this line if used in multi-thread application

#ifdef USE_MULTI_THREAD
#include "SyncObj.h"
#endif // USE_MULTI_THREAD

//////////////////////////////////////////////////////////////////////
// Necessary Definitions for Non-MFC applications
//////////////////////////////////////////////////////////////////////
#ifndef __AFXWIN_H__ // If non-MFC ...
#ifndef WIN32_LEAN_AND_MEAN
#define WIN32_LEAN_AND_MEAN
#endif
#include <windows.h>
#include <search.h>
#include <assert.h>
#ifndef ASSERT
#define ASSERT(x) assert(x)
#endif
#endif // __AFXWIN_H__

// Element sorting states
enum {
    AE_SORT_NONE = 0,  // Not sorted
    AE_SORT_ASCENDING, // Sorted in ascending order
    AE_SORT_DESCENDING
}; // Sorted in descending order

template <class TYPE, class ARG_TYPE>
class CArrayEx
#ifdef USE_MULTI_THREAD
    : public CSyncObj
#endif // USE_MULTI_THREAD
{
  public:
    // Constructions & Destructor
    CArrayEx();
    CArrayEx(const CArrayEx& src);
    virtual ~CArrayEx();

    // Sort & Search
    void Sort(BOOL bAscending = TRUE);
    int IsSorted() const {
        return m_nSort;
    }
    int Find(ARG_TYPE tData, int nStartAt = 0) const;
    int ReverseFind(ARG_TYPE tData) const;

    // General Access
    int GetSize() const {
        return m_nElementCount;
    }
    int GetUpperBound() const {
        return m_nElementCount - 1;
    }
    BOOL SetSize(int nNewSize);
    BOOL IsEmpty() const {
        return m_nElementCount == 0;
    }
    BOOL IsIndexValid(int nIndex) const {
        return nIndex >= 0 && nIndex < m_nElementCount;
    }
    BOOL FreeExtra();
    BOOL Copy(const CArrayEx& src);

    // Element Insertion & Removal
    int InsertAt(int nIndex, ARG_TYPE tData, int nCount = 1);
    int InsertAt(int nIndex, const CArrayEx* pNewArray);
    int Add(ARG_TYPE tData, int nCount = 1);
    int Append(const CArrayEx& src);
    int RemoveAt(int nIndex, int nCount = 1);
    BOOL RemoveLast() {
        return RemoveAt(m_nElementCount - 1, 1) > 0;
    }
    void RemoveAll() {
        m_nElementCount = 0;
    }

    // Element Access
    const TYPE& GetLast() const {
        return GetAt(m_nElementCount - 1);
    }
    TYPE& GetLast() {
        return ElementAt(m_nElementCount - 1);
    }
    const TYPE& GetAt(int nIndex) const;
    BOOL SetLast(ARG_TYPE tData) {
        return SetAt(m_nElementCount - 1, tData);
    }
    BOOL SetAt(int nIndex, ARG_TYPE tData);
    TYPE& ElementAt(int nIndex);
    const TYPE* GetData() const {
        return m_pData;
    }
    TYPE* GetData() {
        m_nSort = AE_SORT_NONE;
        return m_pData;
    }

    // Operators
    TYPE& operator[](int nIndex) {
        return ElementAt(nIndex);
    }
    const TYPE& operator[](int nIndex) const {
        return GetAt(nIndex);
    }
    const CArrayEx& operator=(const CArrayEx& src);

  protected:
    BOOL _MakeSpaces(int nIndex, int nCount = 1); // Make spaces for new elements
    BOOL _GrowSize(int nAdd);                     // dynamically grow array size
    void _AdjustIdx(int& nIndex, BOOL bAllowGrow) const;

    // call-back compare functions
    static int _CompareAscending(const void* p1, const void* p2);
    static int _CompareDescending(const void* p1, const void* p2);

    // member data
    int m_nSort;         // sort states
    int m_nElementCount; // element count
    int m_nAllocSize;    // allocated size
    TYPE* m_pData;       // data
};

template <class TYPE, class ARG_TYPE> int CArrayEx<TYPE, ARG_TYPE>::_CompareAscending(const void* p1, const void* p2) {
    TYPE* pElement1 = (TYPE*)p1;
    TYPE* pElement2 = (TYPE*)p2;
    ASSERT(pElement1 != NULL && pElement2 != NULL);

    if (*pElement1 == *pElement2)
        return 0;

    if (*pElement1 > *pElement2)
        return 1;

    return -1;
}

template <class TYPE, class ARG_TYPE> int CArrayEx<TYPE, ARG_TYPE>::_CompareDescending(const void* p1, const void* p2) {
    return _CompareAscending(p2, p1); // just reverse the order
}

template <class TYPE, class ARG_TYPE> void CArrayEx<TYPE, ARG_TYPE>::Sort(BOOL bAscending) {
    if (m_nElementCount < 2 || (bAscending && (m_nSort == AE_SORT_ASCENDING)) || (!bAscending && (m_nSort == AE_SORT_DESCENDING)))
        return; // no need to resort

    // use qsort
    if (bAscending)
        ::qsort(m_pData, m_nElementCount, sizeof(TYPE), _CompareAscending);
    else
        ::qsort(m_pData, m_nElementCount, sizeof(TYPE), _CompareDescending);

    m_nSort = bAscending ? AE_SORT_ASCENDING : AE_SORT_DESCENDING;
}

template <class TYPE, class ARG_TYPE> int CArrayEx<TYPE, ARG_TYPE>::Find(ARG_TYPE tData, int nStartAt /*=0*/) const {
    if (nStartAt < 0)
        nStartAt = 0;

    if (!IsIndexValid(nStartAt))
        return -1;

    if (m_nSort == AE_SORT_ASCENDING) // ascending
    {
        void* p = ::bsearch(&tData, &m_pData[nStartAt], m_nElementCount - nStartAt, sizeof(TYPE), _CompareAscending);
        int nIndex = (p == NULL) ? -1 : int(((long)p - (long)m_pData) / sizeof(TYPE));
        while (nIndex > 0 && m_pData[nIndex - 1] == tData)
            nIndex--;
        return nIndex;
    } else if (m_nSort == AE_SORT_DESCENDING) // descending
    {
        void* p = ::bsearch(&tData, &m_pData[nStartAt], m_nElementCount - nStartAt, sizeof(TYPE), _CompareDescending);
        int nIndex = (p == NULL) ? -1 : int(((long)p - (long)m_pData) / sizeof(TYPE));
        while (nIndex > 0 && m_pData[nIndex - 1] == tData)
            nIndex--;
        return nIndex;
    } else // not sorted
    {
        for (int i = nStartAt; i < m_nElementCount; i++) {
            if (m_pData[i] == tData)
                return i;
        }
        return -1;
    }
}

template <class TYPE, class ARG_TYPE> int CArrayEx<TYPE, ARG_TYPE>::ReverseFind(ARG_TYPE tData) const {
    if (m_nElementCount == 0)
        return -1;

    if (m_nSort == AE_SORT_ASCENDING) // ascending
    {
        void* p = ::bsearch(&tData, m_pData, m_nElementCount, sizeof(TYPE), _CompareAscending);
        int nIndex = (p == NULL) ? -1 : int(((long)p - (long)m_pData) / sizeof(TYPE));
        while (nIndex < m_nElementCount - 1 && m_pData[nIndex + 1] == tData)
            nIndex++;
        return nIndex;
    } else if (m_nSort == AE_SORT_DESCENDING) // descending
    {
        void* p = ::bsearch(&tData, m_pData, m_nElementCount, sizeof(TYPE), _CompareDescending);
        int nIndex = (p == NULL) ? -1 : int(((long)p - (long)m_pData) / sizeof(TYPE));
        while (nIndex < m_nElementCount - 1 && m_pData[nIndex + 1] == tData)
            nIndex++;
        return nIndex;
    } else // not sorted
    {
        for (int i = m_nElementCount - 1; i >= 0; i--) {
            if (m_pData[i] == tData)
                return i;
        }
        return -1;
    }
}

template <class TYPE, class ARG_TYPE> CArrayEx<TYPE, ARG_TYPE>::CArrayEx() {
    m_nSort = AE_SORT_NONE;
    m_nElementCount = 0;
    m_nAllocSize = 0;
    m_pData = NULL;
};

template <class TYPE, class ARG_TYPE> CArrayEx<TYPE, ARG_TYPE>::CArrayEx(const CArrayEx& src) {
    m_nSort = AE_SORT_NONE;
    m_nElementCount = 0;
    m_nAllocSize = 0;
    m_pData = NULL;
    if (!Copy(src))
        ASSERT(FALSE);
}

template <class TYPE, class ARG_TYPE> CArrayEx<TYPE, ARG_TYPE>::~CArrayEx() {
    if (m_pData != 0)
        delete[] m_pData;
};

template <class TYPE, class ARG_TYPE> BOOL CArrayEx<TYPE, ARG_TYPE>::SetSize(int nNewSize) {
    if (nNewSize < 0)
        return FALSE;

    if (!_GrowSize(nNewSize - m_nElementCount))
        return FALSE;

    m_nElementCount = nNewSize;
    return TRUE;
};

template <class TYPE, class ARG_TYPE> int CArrayEx<TYPE, ARG_TYPE>::Add(ARG_TYPE tData, int nCount) {
    // append at the end
    return InsertAt(m_nElementCount, tData, nCount);
}

// insert single element
template <class TYPE, class ARG_TYPE> int CArrayEx<TYPE, ARG_TYPE>::InsertAt(int nIndex, ARG_TYPE tData, int nCount) {
    if (nCount < 1)
        return -1;

    _AdjustIdx(nIndex, TRUE);
    if (!_MakeSpaces(nIndex, nCount))
        return -1;

    for (int i = 0; i < nCount; i++)
        m_pData[nIndex + i] = tData;

    m_nSort = AE_SORT_NONE;
    return nIndex;
}

// insert a whole array
template <class TYPE, class ARG_TYPE> int CArrayEx<TYPE, ARG_TYPE>::InsertAt(int nIndex, const CArrayEx* pNewArray) {
    if (pNewArray == NULL || pNewArray->GetSize() < 1)
        return -1;

    _AdjustIdx(nIndex, TRUE);
    if (!_MakeSpaces(nIndex, pNewArray->GetSize()))
        return -1;

    for (int i = 0; i < pNewArray->GetSize(); i++)
        m_pData[nIndex + i] = pNewArray->GetAt(i);

    m_nSort = AE_SORT_NONE;
    return nIndex;
}

template <class TYPE, class ARG_TYPE> int CArrayEx<TYPE, ARG_TYPE>::RemoveAt(int nIndex, int nCount) {
    if (nCount > m_nElementCount - nIndex)
        nCount = m_nElementCount - nIndex;

    if (!IsIndexValid(nIndex) || nCount < 1)
        return 0;

    const int SEG = m_nElementCount - nIndex - nCount;

    for (int i = 0; i < SEG; i++)
        m_pData[nIndex + i] = m_pData[nIndex + i + nCount];

    m_nElementCount -= nCount;
    return nCount;
}

template <class TYPE, class ARG_TYPE> BOOL CArrayEx<TYPE, ARG_TYPE>::FreeExtra() {
    if (m_pData == NULL || m_nAllocSize == m_nElementCount)
        return TRUE;

    // reallocate data array with optimized size
    m_nAllocSize = m_nElementCount;
    TYPE* p = new TYPE[m_nAllocSize];
    if (p == NULL)
        return FALSE;

    for (int i = 0; i < m_nElementCount; i++)
        p[i] = m_pData[i];

    delete[] m_pData;
    m_pData = p;
    return TRUE;
}

template <class TYPE, class ARG_TYPE> BOOL CArrayEx<TYPE, ARG_TYPE>::Copy(const CArrayEx& src) {
    if (!SetSize(src.m_nElementCount))
        return FALSE;

    for (int i = 0; i < m_nElementCount; i++)
        m_pData[i] = src.m_pData[i];
    m_nSort = src.m_nSort;
    return TRUE;
}

template <class TYPE, class ARG_TYPE> int CArrayEx<TYPE, ARG_TYPE>::Append(const CArrayEx& src) {
    int nAppenedeAt = src.m_nElementCount > 0 ? m_nElementCount : -1;
    if (!_GrowSize(src.m_nElementCount))
        return -1;

    // append at the end
    for (int i = 0; i < src.m_nElementCount; i++)
        m_pData[nAppenedeAt + i] = src.m_pData[i];

    m_nElementCount += src.m_nElementCount;
    m_nSort = AE_SORT_NONE;
    return nAppenedeAt;
}

template <class TYPE, class ARG_TYPE> void CArrayEx<TYPE, ARG_TYPE>::_AdjustIdx(int& nIndex, BOOL bAllowGrow) const {
    if (nIndex < 0)
        nIndex = 0;

    if (nIndex >= m_nElementCount)
        nIndex = bAllowGrow ? m_nElementCount : (m_nElementCount - 1);
}

template <class TYPE, class ARG_TYPE> BOOL CArrayEx<TYPE, ARG_TYPE>::_MakeSpaces(int nIndex, int nCount /*= 1*/) {
    if (nCount < 1)
        return TRUE;

    if (!_GrowSize(nCount))
        return FALSE;

    for (int i = m_nElementCount - 1; i >= nIndex; i--)
        m_pData[i + nCount] = m_pData[i];

    m_nElementCount += nCount;
    return TRUE;
}

template <class TYPE, class ARG_TYPE> BOOL CArrayEx<TYPE, ARG_TYPE>::_GrowSize(int nAdd) {
    if (nAdd < 1)
        return TRUE;

    if (m_nAllocSize <= 0)
        m_nAllocSize = 32;

    while (m_nAllocSize < m_nElementCount + nAdd)
        m_nAllocSize *= 2;

    TYPE* pNew = new TYPE[m_nAllocSize];
    if (pNew == NULL)
        return FALSE; // out of memory

    if (m_pData != NULL) {
        for (int i = 0; i < m_nElementCount; i++)
            pNew[i] = m_pData[i];
        delete[] m_pData;
    }
    m_pData = pNew;
    return TRUE;
}

template <class TYPE, class ARG_TYPE> BOOL CArrayEx<TYPE, ARG_TYPE>::SetAt(int nIndex, ARG_TYPE tData) {
    if (!IsIndexValid(nIndex))
        return FALSE;

    m_pData[nIndex] = tData;
    m_nSort = AE_SORT_NONE;
    return TRUE;
}

template <class TYPE, class ARG_TYPE> TYPE& CArrayEx<TYPE, ARG_TYPE>::ElementAt(int nIndex) {
    ASSERT(IsIndexValid(nIndex));
    m_nSort = AE_SORT_NONE;
    return m_pData[nIndex];
}

template <class TYPE, class ARG_TYPE> const TYPE& CArrayEx<TYPE, ARG_TYPE>::GetAt(int nIndex) const {
    ASSERT(IsIndexValid(nIndex));
    return m_pData[nIndex];
}

template <class TYPE, class ARG_TYPE> const CArrayEx<TYPE, ARG_TYPE>& CArrayEx<TYPE, ARG_TYPE>::operator=(const CArrayEx& src) {
    if (!Copy(src))
        ASSERT(FALSE);
    return *this;
}

#endif // __ARRAYEX_H__