|
//----------------------------------------------------------------------------
// CTArray.h: C++ template based class for dynamic arrays.
//
// 10/15/05 - Michael B. Comet, comet@comet-cartoons.com - Initial Rev
// 05/20/06 - tor - no ostream cout friends, renamed most of the members.
// 06/05/06 - tor - qsort wrapper with input sort callback
// 06/21/06 - tor - Find returning an index, not a boolean
// 08/23/06 - tor - Find with optional start index, to find duplicates
// 08/24/06 - tor - GetAll to a void ptr of specified size
// 08/25/06 - tor - some methods are now virtual for subclass overrides
// 08/26/06 - tor - swap
//----------------------------------------------------------------------------
#ifndef _CTARRAY_H_
#define _CTARRAY_H_
template<class TYPE> class CTArray
{
private:
UINT nSize; // actual size
UINT nGrow; // grow factor
protected:
UINT nItems; // number of elements (as it appears to the user)
TYPE* pData; // pointer to array of data
public:
// blank constructor
CTArray() { Init(); }
// copy constructor
CTArray(CTArray& Src) { Init(); Copy(Src); }
// typed copy constructor
CTArray(const TYPE* pSrc, UINT nCount = 1)
{
Init();
SetLength(nCount);
for (UINT u = 0; u < nItems; u++) pData[u] = pSrc[u];
}
// typed initializing constructor
CTArray(UINT nCount, TYPE Src)
{
Init();
SetLength(nCount);
for (UINT u = 0; u < nItems; u++) pData[u] = Src;
}
// operators
const TYPE& operator[](UINT nIndex) const { return pData[nIndex]; }
TYPE& operator[](UINT nIndex) { return pData[nIndex]; }
CTArray& operator=(CTArray& Src) { Copy(Src); return *this; }
// initialise
void Init() { pData = NULL; nSize = nItems = 0; nGrow = 8; }
// release data
virtual void Clear(void) { if (pData != NULL) delete [] pData; Init(); }
// copy from other
void Copy(CTArray& Src)
{
Clear();
SetLength(Src.Length());
for (UINT u = 0; u < nItems; u++) pData[u] = Src.pData[u];
}
// grow factor get/set
UINT GrowFactor(void) const { return nGrow; }
void SetGrowFactor(UINT nNewGrow) { nGrow = nNewGrow; if (nGrow == 0) nGrow = 1; }
// length (items) get
UINT Length(void) { return nItems; }
// set length regrow or shrink
virtual bool SetLength(UINT nLength, bool bForce = false)
{
if (nLength == 0)
{
Clear();
return true;
}
// alloc new storage
TYPE* pNewData = NULL;
UINT nNewSize = ((nLength / nGrow) + 1) * nGrow;
// grow only if either the amount we need is greater than what we have
// already or if the amount is <= 1/2, whatever's smaller
if (nNewSize > nSize || nNewSize <= nSize / 2 || bForce)
{
if ((pNewData = new TYPE[nNewSize]) == NULL)
return false;
// now copy the old elements into the new array, up to the old
// number of items or to the user-set new length, whichever's
// smaller
for (UINT u = 0; u < nItems && u < nLength; u++)
pNewData[u] = pData[u];
// update all the current info...
if (pData != NULL)
delete [] pData;
pData = pNewData;
nSize = nNewSize;
}
nItems = nLength;
return true;
}
// set w/bounds check but no grow
virtual bool Set(UINT nIndex, TYPE Src) const
{
if (nIndex >= nItems || pData == NULL)
return false;
pData[nIndex] = Src;
return true;
}
// get w/bounds check but no grow
virtual bool Get(TYPE& Dst, UINT nIndex) const
{
if (nIndex >= nItems || pData == NULL)
return false;
Dst = pData[nIndex];
return true;
}
// get all elements to a typed pointer; do not forget to delete
// such pointer after no longer needed
UINT GetAll(TYPE*& pDst)
{
pDst = new TYPE[nItems];
for (UINT u = 0; u < nItems; u++)
pDst[u] = pData[u];
return nItems;
}
// get all elements to an unknown size pointer of specified size; the
// pointer must be initialized by the caller...
UINT GetAll(void* pDst, int nSize)
{
for (UINT u = 0; u < nItems; u++)
memcpy((void*)((BYTE*)pDst + u * nSize), (void*)(&pData[u]), nSize);
return nItems;
}
// remove element at given position
virtual bool Remove(UINT nIndex)
{
if (nItems == 0 || pData == NULL)
return false;
// starting with the element we are removing, work up
// copying each next value down to the current spot...
for (UINT u = nIndex; u < nItems - 1 ; u++)
pData[u] = pData[u + 1];
// this will either simply change the nItems value or realloc and
// free some memory
SetLength(nItems - 1);
return true;
}
// insert element at given position
virtual void Insert(TYPE Src, UINT nIndex)
{
// first, make room
SetLength(nItems + 1);
// starting with the last element work back until we get to the one
// we are inserting at and copy forward
for (UINT u = nItems - 1; u > nIndex; u--)
pData[u] = pData[u - 1] ;
// finally insert new value
pData[nIndex] = Src;
}
// append element to the end of array
virtual int Append(TYPE Src)
{
// first, make room
SetLength(nItems + 1);
// insert new value
pData[nItems - 1] = Src;
return nItems;
}
// blank append
virtual int Append()
{
// just make room
SetLength(nItems + 1);
return nItems;
}
// finder with mem compare and optional start
int Find(TYPE Src, UINT nStart = 0)
{
for (UINT u = nStart; u < nItems; u++)
{
if (memcmp(&pData[u], &Src, sizeof(TYPE)) == 0)
return (int)u;
}
return -1;
}
// swap
void Swap(UINT i, UINT j)
{
if (i >= nItems || j >= nItems || i == j)
return;
TYPE Tmp = pData[i];
pData[i] = pData[j];
pData[j] = Tmp;
}
// sort wrapper with callback and method
void Sort(int (__cdecl* compare)(const void* p1, const void* p2), int nMethod = 0)
{
switch (nMethod)
{
case 1:
{
// sort the array with fixed starting items, by comparing neighbors
for (UINT i = 0; i < nItems - 1; i++)
{
// skip a neighbor that is in order (as determined by a non-zero
// return from the compare function)
if (compare((const void*)&pData[i], (const void*)&pData[i + 1]))
continue;
// search for an item matching the last starting item
UINT j = i + 1;
while (!compare((const void*)&pData[i], (const void*)&pData[j]) && j < nItems - 1)
j++;
// swap the matching item to be right below the starting item
if (j <= nItems - 1)
Swap(i + 1, j);
}
break;
}
default:
qsort(pData, nItems, sizeof(TYPE), compare);
break;
}
}
// destructor
~CTArray() { Clear(); }
};
typedef CTArray<DWORD> DWORDARRAY;
#endif // _CTARRAY_H_
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
Professional software engineer with 30+ years of experience delivering systems across diverse industries, looking for the next opportunity to deliver cutting edge end-to-end technology solutions.
Avid reader, disciplined writer and enthusiastic tinkerer with a background in electronics, looking inside and thinking outside the box, genuinely passionate about robust, extensible, reusable and performant code.
Framework developer leading, coaching and learning about best practices, code quality, DevOps and software and data lifecycle management with an agile mindset to create the most elegant and sustainable solutions.