garray.cpp

一个非常有用的开源代码

/*
	Copyright (C) 2006, Mike Gashler

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	see http://www.gnu.org/copyleft/lesser.html
*/

#include "GArray.h"
#include "GMacros.h"

GDynamicArray::GDynamicArray(int nCellSize, int nGrowBy)
{
	GAssert(nCellSize > 0, "invalid cell size");
	if(nGrowBy < 8)
		nGrowBy = 8;
	m_nCellSize = nCellSize;
	m_nGrowBy = nGrowBy;
	m_nCellCount = 0;
	m_nAllocCount = 0;
	m_pData = NULL;
}

GDynamicArray::~GDynamicArray()
{
	delete[] (unsigned char*)m_pData;
}

void GDynamicArray::SetAllocSize(int n)
{
	if(m_nAllocCount == n)
		return;
	unsigned char* pOld = (unsigned char*)m_pData;
	m_pData = new unsigned char[n * m_nCellSize];
	GAssert(m_pData, "Out of Memory");
	if(m_nCellCount > n)
		m_nCellCount = n;
	memcpy(m_pData, pOld, m_nCellCount * m_nCellSize);
	m_nAllocCount = n;
	delete(pOld);
}

void GDynamicArray::Grow()
{
	if(m_nAllocCount == 0)
		SetAllocSize(m_nGrowBy);
	else
		SetAllocSize(m_nAllocCount * 2);
}

void GDynamicArray::_AddCellByRef(const void* pData)
{
	if(m_nCellCount >= m_nAllocCount)
		Grow();
	memcpy((char*)m_pData + (m_nCellCount * m_nCellSize), (char*)pData, m_nCellSize);
	m_nCellCount++;
}

void GDynamicArray::_SetCellByRef(int nCell, void* pData)
{
	GAssert(nCell >= 0 && nCell < m_nCellCount, "Out of range");
	memcpy((char*)m_pData + (nCell * m_nCellSize), (char*)pData, m_nCellSize);
}

inline void SmartMemCpy(void* pDest, void* pSrc, int nSize)
{
	int i;
	if(pDest < pSrc)
	{
		for(i = 0; i < nSize; i++)
			((unsigned char*)pDest)[i] = ((unsigned char*)pSrc)[i];
	}
	else
	{
		for(i = nSize - 1; i >= 0; i--)
			((unsigned char*)pDest)[i] = ((unsigned char*)pSrc)[i];
	}
}

void GDynamicArray::DeleteCell(int n)
{
	GAssert(n <= m_nCellCount, "Out of range");

	SmartMemCpy(
					(char*)m_pData + (n * m_nCellSize),
					(char*)m_pData + ((n + 1) * m_nCellSize),
					(m_nCellCount - n - 1) * m_nCellSize
					);
	m_nCellCount--;
}

void GDynamicArray::_InsertCellByRef(int n, void* pData)
{
	if(m_nCellCount >= m_nAllocCount)
		Grow();
	SmartMemCpy(
					(char*)m_pData + ((n + 1) * m_nCellSize),
					(char*)m_pData + (n * m_nCellSize),
					(m_nCellCount - n) * m_nCellSize
					);
	memcpy((char*)m_pData + (n * m_nCellSize), (char*)pData, m_nCellSize);
	m_nCellCount++;
}

void GDynamicArray::SetSize(int n)
{
	if(m_nAllocCount < m_nCellCount)
		SetAllocSize(n);
	m_nCellCount = n;
}

// -------------------------------------------------------------------------

// This uses merge sort.
void GPointerArray::Sort(PointerComparer pCompareFunc, void* pThis)
{
	int nCount = GetSize();
	void** pBuf = new void*[m_nAllocCount];
	void** pTmp;
	int nStep = 1;
	int n, i, j, k, end, cmp;
	while(nStep < nCount)
	{
		for(n = 0; n < nCount; n += (nStep + nStep))
		{
			i = nStep;
			if(n + nStep > nCount)
				i = nCount - n;
			j = nStep;
			if(n + nStep + j > nCount)
				j = MAX(nCount - (n + nStep), 0);
			end = i + j - 1;
			for(k = end; k >= 0; k--)
			{
				if(!i)
					cmp = -1;
				else if(!j)
					cmp = 1;
				else
					cmp = pCompareFunc(pThis, GetPointer(n + i - 1), GetPointer(n + nStep + j - 1));
				if(cmp <= 0)
				{
					pBuf[n + k] = GetPointer(n + nStep + j - 1);
					j--;
				}
				else
				{
					pBuf[n + k] = GetPointer(n + i - 1);
					i--;
				}
			}
		}
		pTmp = pBuf;
		pBuf = (void**)m_pData;
		m_pData = (void*)pTmp;
		nStep *= 2;
	}
	delete[] pBuf;
}

// -------------------------------------------------------------------------

// This uses merge sort.
void GIntArray::Sort(IntComparer pCompareFunc, void* pThis)
{
	int nCount = GetSize();
	int* pBuf = new int[m_nAllocCount];
	int* pTmp;
	int nStep = 1;
	int n, i, j, k, end, cmp;
	while(nStep < nCount)
	{
		for(n = 0; n < nCount; n += (nStep + nStep))
		{
			i = nStep;
			if(n + nStep > nCount)
				i = nCount - n;
			j = nStep;
			if(n + nStep + j > nCount)
				j = MAX(nCount - (n + nStep), 0);
			end = i + j - 1;
			for(k = end; k >= 0; k--)
			{
				if(!i)
					cmp = -1;
				else if(!j)
					cmp = 1;
				else
					cmp = pCompareFunc(pThis, GetInt(n + i - 1), GetInt(n + nStep + j - 1));
				if(cmp <= 0)
				{
					pBuf[n + k] = GetInt(n + nStep + j - 1);
					j--;
				}
				else
				{
					pBuf[n + k] = GetInt(n + i - 1);
					i--;
				}
			}
		}
		pTmp = pBuf;
		pBuf = (int*)m_pData;
		m_pData = (void*)pTmp;
		nStep *= 2;
	}
	delete[] pBuf;
}

int GIntArrayValueComparer(void* pThis, int a, int b)
{
	if(a < b)
		return -1;
	else if(a > b)
		return 1;
	else
		return 0;
}

void GIntArray::SortByValue()
{
	Sort(GIntArrayValueComparer, NULL);
}