tcsbl.cpp

并行TIN生成算法, 基于DeWall算法理论实现

// TcsBL.cpp
// 邓雪清, 2008/12/15

#include "TcsBL.h"

/////////////////////////////////////////////////////////////////////////////
// CTcsBL

CTcsBL::CTcsBL(void)
{
	m_nSize = 0;
	m_nNonc = -1;
	m_mLock = ::CreateMutex(0, 0, 0);
	m_pHead = m_pTail = m_pNonc = m_pFree = 0;
}

CTcsBL::~CTcsBL(void)
{
	if (m_mLock)
		::WaitForSingleObject(m_mLock, INFINITE);

	NODE *pNode;

	while (m_pHead)
	{
		pNode = m_pHead;
		m_pHead = pNode->next;
		delete pNode;
	}

	while (m_pFree)
	{
		pNode = m_pFree;
		m_pFree = pNode->next;
		delete pNode;
	}

	if (m_mLock)
		::CloseHandle(m_mLock);
}

CTcsBL::NODE *CTcsBL::NewNode(CTcsBL::NODE *pPrev, CTcsBL::NODE *pNext)
{
	CTcsBL::NODE* pNode;
	
	if (!m_pFree)
	{
		pNode = new CTcsBL::NODE;
		if (!pNode)
			return 0;
	}
	else
	{
		pNode = m_pFree;
		m_pFree = pNode->next;
	}

	pNode->data = 0;
	pNode->prev = pPrev;
	pNode->next = pNext;

	m_nSize++;

	return pNode;
}

void *CTcsBL::AddHead(void *pData)
{
	NODE *pNode = NewNode(0, m_pHead);

	if (!pNode)
		return 0;
	pNode->data = pData;
	
	if (m_pHead)
		m_pHead->prev = pNode;
	else
		m_pTail = pNode;

	m_pHead = pNode;
	// 设置当前节点
	m_pNonc = pNode;
	m_nNonc = 0;

	return pNode;
}

void *CTcsBL::AddTail(void *pData)
{
	NODE *pNode = NewNode(m_pTail, 0);

	if (!pNode)	return 0;
	pNode->data = pData;

	if (m_pTail)
		m_pTail->next = pNode;
	else
		m_pHead = pNode;

	m_pTail = pNode;
	// 设置当前节点
	m_pNonc = pNode;
	m_nNonc = m_nSize - 1;

	return pNode;
}

void *CTcsBL::AddAt(long idx, void *pData)
{
	if (idx < 0 || idx >= m_nSize)
		return 0;

	NODE *pPrev, *pNext;

	if		(idx == m_nNonc)
	{
		pPrev = m_pNonc;
		pNext = m_pNonc->next;
	}
	else if (idx < m_nNonc)
	{
		if (idx < m_nNonc - idx)
		{
			pPrev = m_pHead; // idx = 0;
			for (long i = 1; i <= idx; i++)
				pPrev = pPrev->next;
			pNext = pPrev->next;
		}
		else
		{
			pPrev = m_pNonc->prev; // idx = m_nNonc - 1;
			for (long i = m_nNonc - 2; i >= idx; i--)
				pPrev = pPrev->prev;
			pNext = pPrev->next;
		}
	}
	else
	{
		if (idx - m_nNonc < m_nSize - 1 - idx)
		{
			pPrev = m_pNonc->next; // idx = m_nNonc + 1;
			for (long i = m_nNonc + 2; i <= idx; i++)
				pPrev = pPrev->next;
			pNext = pPrev->next;
		}
		else
		{
			pPrev = m_pTail; // idx = m_nSize - 1;
			for (long i = m_nSize - 2; i >= idx; i--)
				pPrev = pPrev->prev;
			pNext = pPrev->next;
		}
	}

	NODE *pNode = NewNode(pPrev, pNext);

	if (!pNode)	return 0;
	pNode->data = pData;

	pPrev->next = pNode;
	if (pNext)
		pNext->prev = pNode;

	// 设置当前节点
	m_pNonc = pNode;
	m_nNonc = idx + 1;

	return pNode;
}

void *CTcsBL::GetAt(long idx)
{
	if (idx < 0 || idx >= m_nSize)
		return 0;

	if		(idx == m_nNonc)
		return m_pNonc->data;
	else if (idx  < m_nNonc)
	{
		if (idx < m_nNonc - idx)
		{
			NODE *pNode = m_pHead; // idx = 0;
			for (long i = 1; i <= idx; i++)
				pNode = pNode->next;
			// 设置当前节点
			m_pNonc = pNode;
			m_nNonc = idx;

			return pNode->data;
		}
		else
		{
			NODE *pNode = m_pNonc->prev; // idx = m_nNonc - 1;
			for (long i = m_nNonc - 2; i >= idx; i--)
				pNode = pNode->prev;
			// 设置当前节点
			m_pNonc = pNode;
			m_nNonc = idx;

			return pNode->data;
		}
	}
	else
	{
		if (idx - m_nNonc < m_nSize - 1 - idx)
		{
			NODE *pNode = m_pNonc->next; // idx = m_nNonc + 1;
			for (long i = m_nNonc + 2; i <= idx; i++)
				pNode = pNode->next;
			// 设置当前节点
			m_pNonc = pNode;
			m_nNonc = idx;

			return pNode->data;
		}
		else
		{
			NODE *pNode = m_pTail; // idx = m_nSize - 1;
			for (long i = m_nSize - 2; i >= idx; i--)
				pNode = pNode->prev;
			// 设置当前节点
			m_pNonc = pNode;
			m_nNonc = idx;

			return pNode->data;
		}
	}

	return 0;
}

long CTcsBL::SetAt(long idx, void *pData)
{
	if (idx < 0 || idx >= m_nSize)
		return 0;

	if		(idx == m_nNonc)
		m_pNonc->data = pData;
	else if (idx  < m_nNonc)
	{
		if (idx < m_nNonc - idx)
		{
			NODE *pNode = m_pHead; // idx = 0;
			for (long i = 1; i <= idx; i++)
				pNode = pNode->next;
			// 设置当前节点
			m_pNonc = pNode;
			m_nNonc = idx;

			pNode->data = pData;
		}
		else
		{
			NODE *pNode = m_pNonc->prev; // idx = m_nNonc - 1;
			for (long i = m_nNonc - 2; i >= idx; i--)
				pNode = pNode->prev;
			// 设置当前节点
			m_pNonc = pNode;
			m_nNonc = idx;

			pNode->data = pData;
		}
	}
	else
	{
		if (idx - m_nNonc < m_nSize - 1 - idx)
		{
			NODE *pNode = m_pNonc->next; // idx = m_nNonc + 1;
			for (long i = m_nNonc + 2; i <= idx; i++)
				pNode = pNode->next;
			// 设置当前节点
			m_pNonc = pNode;
			m_nNonc = idx;

			pNode->data = pData;
		}
		else
		{
			NODE *pNode = m_pTail; // idx = m_nSize - 1;
			for (long i = m_nSize - 2; i >= idx; i--)
				pNode = pNode->prev;
			// 设置当前节点
			m_pNonc = pNode;
			m_nNonc = idx;

			pNode->data = pData;
		}
	}

	return 1;
}

void *CTcsBL::RemoveHead(void)
{
	if (!m_pHead)	return 0;
	NODE *pNode = m_pHead;
	void *pData = pNode->data;

	m_pHead = m_pHead->next;
	if (m_pHead)
		m_pHead->prev = 0;
	else
		m_pTail = 0;

	m_nSize--;

	// 设置当前节点
	m_pNonc = m_pHead;
	if (m_pNonc)
		m_nNonc = 0;
	else
		m_nNonc = -1;

	// Insert Free List;
	if (m_pFree)
	{
		m_pFree->prev = pNode;
		pNode->prev = 0;
		pNode->next = m_pFree;
		pNode->data = 0;
		m_pFree = pNode;
	}
	else
	{
		m_pFree = pNode;
		m_pFree->prev = 0;
		m_pFree->next = 0;
		m_pFree->data = 0;
	}

	return pData;
}

void *CTcsBL::RemoveTail(void)
{
	if (!m_pTail)	return 0;
	NODE *pNode = m_pTail;
	void *pData = pNode->data;

	m_pTail = m_pTail->prev;
	if (m_pTail)
		m_pTail->next = 0;
	else
		m_pHead = 0;

	m_nSize--;

	// 设置当前节点
	m_pNonc = m_pTail;
	m_nNonc = m_nSize - 1;

	// Insert Free List;
	if (m_pFree)
	{
		m_pFree->prev = pNode;
		pNode->prev = 0;
		pNode->next = m_pFree;
		pNode->data = 0;
		m_pFree = pNode;
	}
	else
	{
		m_pFree = pNode;
		m_pFree->prev = 0;
		m_pFree->next = 0;
		m_pFree->data = 0;
	}

	return pData;
}

void *CTcsBL::RemoveAt(long idx)
{
	if (idx < 0 || idx >= m_nSize)
		return 0;

	NODE *pNode;

	if		(idx == m_nNonc)
		pNode = m_pNonc;
	else if (idx  < m_nNonc)
	{
		if (idx < m_nNonc - idx)
		{
			pNode = m_pHead; // idx = 0;
			for (long i = 1; i <= idx; i++)
				pNode = pNode->next;
		}
		else
		{
			pNode = m_pNonc->prev; // idx = m_nNonc - 1;
			for (long i = m_nNonc - 2; i >= idx; i--)
				pNode = pNode->prev;
		}
	}
	else
	{
		if (idx - m_nNonc < m_nSize - 1 - idx)
		{
			pNode = m_pNonc->next; // idx = m_nNonc + 1;
			for (long i = m_nNonc + 2; i <= idx; i++)
				pNode = pNode->next;
		}
		else
		{
			pNode = m_pTail; // idx = m_nSize - 1;
			for (long i = m_nSize - 2; i >= idx; i--)
				pNode = pNode->prev;
		}
	}
	void *pData = pNode->data;

	if (pNode->prev)
	{
		if (pNode->next)
		{
			pNode->prev->next = pNode->next;
			pNode->next->prev = pNode->prev;
		}
		else // At Tail
		{
			pNode->prev->next = 0;
			m_pTail = pNode->prev;
		}
	}
	if (pNode->next)
	{
		if (!pNode->prev) // At Head
		{
			pNode->next->prev = 0;
			m_pHead = pNode->next;
		}
	}
	else
	{
		if (!pNode->prev) // Only One
			m_pHead = m_pTail = 0;
	}

	m_nSize--;

	// 设置当前节点
	if (pNode->next)
	{
		m_pNonc = pNode->next;
		m_nNonc = idx;
	}
	else
	{
		m_pNonc = pNode->prev;
		if (!m_pNonc)
			m_nNonc = -1;
		else
			m_nNonc = idx - 1;
	}

	// Insert Free List;
	if (m_pFree)
	{
		m_pFree->prev = pNode;
		pNode->prev = 0;
		pNode->next = m_pFree;
		pNode->data = 0;
		m_pFree = pNode;
	}
	else
	{
		m_pFree = pNode;
		m_pFree->prev = 0;
		m_pFree->next = 0;
		m_pFree->data = 0;
	}

	return pData;
}

void *CTcsBL::RemoveAt(void *pNode)
{
	if (!pNode)	return 0;

	NODE *pTemp = (NODE*)pNode;
	NODE *pNext = pTemp->next;
	if (pNext && pNext->prev != pTemp)	return 0;
	NODE *pPrev = pTemp->prev;
	if (pPrev && pPrev->next != pTemp)	return 0;
	void *pData = pTemp->data;

	if (pTemp->prev)
	{
		if (pTemp->next)
		{
			pTemp->prev->next = pTemp->next;
			pTemp->next->prev = pTemp->prev;
		}
		else // At Tail
		{
			pTemp->prev->next = 0;
			m_pTail = pTemp->prev;
		}
	}
	if (pTemp->next)
	{
		if (!pTemp->prev) // At Head
		{
			pTemp->next->prev = 0;
			m_pHead = pTemp->next;
		}
	}
	else
	{
		if (!pTemp->prev) // Only One
			m_pHead = m_pTail = 0;
	}

	m_nSize--;

	// 设置当前节点
	m_pNonc = m_pHead;
	m_nNonc = 0;
	if (!m_pNonc)
		m_nNonc = -1;

	// Insert Free List;
	if (m_pFree)
	{
		m_pFree->prev = pTemp;
		pTemp->prev = 0;
		pTemp->next = m_pFree;
		pTemp->data = 0;
		m_pFree = pTemp;
	}
	else
	{
		m_pFree = pTemp;
		m_pFree->prev = 0;
		m_pFree->next = 0;
		m_pFree->data = 0;
	}

	return pData;
}