garray.cpp

来自「一个由Mike Gashler完成的机器学习方面的includes neural」· C++ 代码 · 共 324 行

/*
	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 <= 0)
		nGrowBy = 1;
	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);
}

#ifndef NO_TEST_CODE
int PointerArrayComparer(void* pThis, void* pA, void* pB)
{
	if((int)pA > (int)pB)
		return 1;
	else if((int)pA < (int)pB)
		return -1;
	else
		return 0;
}

// static
void GDynamicArray::Test()
{
	class IntArray : public GDynamicArray
	{
	public:
		IntArray(int nGrowBy) : GDynamicArray(sizeof(int), nGrowBy) { }
		virtual ~IntArray() { }

		int GetInt(int nIndex) { return *(int*)_GetCellRef(nIndex); }
		void AddInt(int n) { _AddCellByRef(&n); }
		void SetInt(int nCell, int n) { _SetCellByRef(nCell, &n); }
	};
	
	IntArray arr(64);
	arr.SetAllocSize(7000);
	int n;
	for(n = 0; n < 10000; n++)
		arr.AddInt(n);
	if(arr.GetSize() != 10000)
		throw "failed";
	for(n = 0; n < 10000; n++)
	{
		if(arr.GetInt(n) != n)
			throw "failed";
	}
	for(n = 0; n < 3000; n++)
		arr.SetInt(n, 5);
	for(n = 0; n < 3000; n++)
	{
		if(arr.GetInt(n) != 5)
			throw "failed";
	}

	// Add, insert, and then check
	GDynamicArray sa(1, 17);
	for(n = 0; n < 1000; n++)
	{
		char cTmp = n + 50;
		sa._AddCellByRef(&cTmp);
	}
	for(n = 0; n < 50; n++)
	{
		char c = n;
		sa._InsertCellByRef(0, &c);
	}
	for(n = 0; n < 50; n++)
	{
		char* pData = (char*)sa._GetCellRef(n);
		if(*pData != (char)(49 - n))
			throw "wrong answer";
	}
	for(n = 50; n < 1050; n++)
	{
		if(*(char*)sa._GetCellRef(n) != (char)n)
			throw "wrong answer";
	}
	if(sa.GetSize() != 1050)
		throw "wrong answer";

	// Delete and then check again
	for(n = 0; n < 49; n++)
		sa.DeleteCell(1);
	if(sa.GetSize() != 1001)
		throw "wrong answer";
	sa.DeleteCell(0);
	for(n = 0; n < 1000; n++)
	{
		char cTmp = n + 50;
		if(*(char*)sa._GetCellRef(n) != cTmp)
			throw "wrong answer";
	}

	// Test GPointerArray::Sort
	GPointerArray arr2(64);
	for(n = 34; n >= 0; n--)
		arr2.AddPointer((void*)n);
	arr2.Sort(PointerArrayComparer, NULL);
	for(n = 0; n <= 34; n++)
	{
		if((int)arr2.GetPointer(n) != n)
			throw "wrong answer";
	}
}
#endif // NO_TEST_CODE