tomslib.h

游戏编程精华02－含有几十个游戏编程例子

	void Check ( void )
	{
#if CHECK_HEAP
#ifdef DEBUG
		for ( int iCurPos = iCurrentSize-1; iCurPos >= 2; iCurPos-- )
		{
			ASSERT ( pBlobArray[iCurPos].Sort <= pBlobArray[iCurPos>>1].Sort );
			ASSERT ( pBlobArray[iCurPos].pThing != NULL );
		}
#endif
#endif
	}

	void Add ( THING *pThisThing, SORT ThisSort )
	{
		Check();

#ifdef DEBUG
		bFindNextValid = FALSE;
#endif
		iCurrentPos = 0;

		if ( iCurrentSize <= 1 )
		{
			iCurrentSize = 1;
		}

		// Make sure it's big enough.
		if ( iAllocatedSize <= iCurrentSize )
		{
			// Add 50% to the allocated size.
			iAllocatedSize = ( iAllocatedSize >> 1 ) + iAllocatedSize;
			// And then a bit more.
			iAllocatedSize += 32;
			// And round up to 1k array size.
			iAllocatedSize = ( iAllocatedSize + 1023 ) & ~1023;

			Blob *pOldBlobArray = pBlobArray;
			pBlobArray = new Blob[iAllocatedSize];
			ASSERT ( pBlobArray != NULL );
			if ( pOldBlobArray != NULL )
			{
				memcpy ( pBlobArray, pOldBlobArray, ( iCurrentSize + 1 ) * sizeof ( Blob ) );
				delete[] pOldBlobArray;
			}
			Check();
		}

		// And add the item.
		iCurrentPos = iCurrentSize;
		while ( ( iCurrentPos > 1 ) && ( pBlobArray[iCurrentPos >> 1].Sort < ThisSort ) )
		{
			pBlobArray[iCurrentPos] = pBlobArray[iCurrentPos >> 1];
			iCurrentPos >>= 1;
		}
		pBlobArray[iCurrentPos].Sort = ThisSort;
		pBlobArray[iCurrentPos].pThing = pThisThing;

		iCurrentSize++;

		Check();
	}


	THING *FindFirst ( void )
	{
		if ( iCurrentSize > 1 )
		{
			ASSERT ( pBlobArray != NULL );
#ifdef DEBUG
			bFindNextValid = TRUE;
#endif
			iCurrentPos = 1;
			return pBlobArray[1].pThing;
		}
		else
		{
#ifdef DEBUG
			bFindNextValid = FALSE;
#endif
			iCurrentPos = 0;
			return NULL;
		}
	}

	// Must have called FindFirst first.
	// THIS DOES NOT TRAVERSE IN SORTED ORDER!
	THING *FindNextUnsorted ( void )
	{
#ifdef DEBUG
		ASSERT ( bFindNextValid );
#endif
		if ( iCurrentPos >= iCurrentSize - 1 )
		{
			// Reached the end.
			return NULL;
		}
		else
		{
			iCurrentPos++;

			return pBlobArray[iCurrentPos].pThing;
		}
	}

	// Must have called FindFirst/FindNext first.
	SORT GetCurrentSort ( void )
	{
#ifdef DEBUG
		ASSERT ( bFindNextValid );
#endif
		ASSERT ( iCurrentPos < iCurrentSize );
		ASSERT ( pBlobArray != NULL );
		return pBlobArray[iCurrentPos].Sort;
	}

	// Must have called FindFirst/FindNext first.
	THING *RemoveCurrent ( void )
	{
#ifdef DEBUG
		ASSERT ( bFindNextValid );
		bFindNextValid = FALSE;
#endif
		if ( iCurrentPos < ( iCurrentSize - 1 ) )
		{
			ASSERT ( pBlobArray != NULL );
			THING *pThing = pBlobArray[iCurrentPos].pThing;

			SORT MovedSort = pBlobArray[iCurrentSize-1].Sort;


			// First bubble this item up the list until
			// the parent is greater or equal to the last item in the heap.
			while ( ( iCurrentPos > 1 ) &&
					( pBlobArray[iCurrentPos>>1].Sort < MovedSort ) )
			{
				pBlobArray[iCurrentPos] = pBlobArray[iCurrentPos>>1];
				iCurrentPos = iCurrentPos >> 1;
			}



			// Then delete it, and replace it by the last in the heap,
			// then bubble that item down the heap again.
			iCurrentSize--;

			// And bubble the last item back down the tree.
			while ( (iCurrentPos<<1) < iCurrentSize )
			{
				if ( ( MovedSort >= pBlobArray[(iCurrentPos<<1)+0].Sort ) &&
					 ( ( ((iCurrentPos<<1)+1) >= iCurrentSize ) ||
					   ( MovedSort >= pBlobArray[(iCurrentPos<<1)+1].Sort ) ) )
				{
					// Yep - fits here.
					break;
				}
				else
				{
					// Find the bigger of the two, and move it up.
					if ( ( ((iCurrentPos<<1)+1) < iCurrentSize ) &&
						 ( pBlobArray[(iCurrentPos<<1)+0].Sort < pBlobArray[(iCurrentPos<<1)+1].Sort ) )
					{
						pBlobArray[iCurrentPos] = pBlobArray[(iCurrentPos<<1)+1];
						iCurrentPos = (iCurrentPos<<1)+1;
					}
					else
					{
						pBlobArray[iCurrentPos] = pBlobArray[(iCurrentPos<<1)+0];
						iCurrentPos = (iCurrentPos<<1)+0;
					}
				}
			}

			// Fits here.
			pBlobArray[iCurrentPos] = pBlobArray[iCurrentSize];
			pBlobArray[iCurrentSize].pThing = NULL;

			Check();

			return pThing;
		}
		else if ( iCurrentPos == iCurrentSize - 1 )
		{
			// This is already the last item - that was easy!
			iCurrentSize--;
			THING *pThing = pBlobArray[iCurrentPos].pThing;
			return pThing;
		}
		else
		{
			return NULL;
		}
	}

	// Must have called FindFirst first.
	THING *RemoveNext ( void )
	{
#ifdef DEBUG
		ASSERT ( bFindNextValid );
#endif
		iCurrentPos++;
		return RemoveCurrent();
	}

	THING *RemoveFirst ( void )
	{
#ifdef DEBUG
		// Keep the assert happy.
		bFindNextValid = TRUE;
#endif
		iCurrentPos = 1;
		return RemoveCurrent();
	}

	// Number of items in the heap.
	int SizeOfHeap ( void )
	{
		return ( iCurrentSize - 1 );
	}

};





// An arbitrary-sized list template class.
// Designed to hold _unsorted_ data, but only RemoveItem()
// actually disturbs the order, so you can use it for general arrays
// if you don't use that function.
template <class T>
class ArbitraryList
{
	T		*pT;				// The list.
	int		iSize;				// The current size of the list.
	int		iReservedSize;		// The current reserved size of the list.


public:

	// Constructor, with optional initial size setting.
	ArbitraryList ( int iInitialSize = 0 )
	{
		pT = NULL;
		iSize = 0;
		iReservedSize = 0;
		if ( iInitialSize > 0 )
		{
			SizeTo ( iInitialSize );
		}
	}

	// Destructor.
	~ArbitraryList ( void )
	{
		if ( pT == NULL )
		{
			ASSERT ( iReservedSize == 0 );
			ASSERT ( iSize == 0 );
		}
		else
		{
			ASSERT ( iReservedSize > 0 );
			ASSERT ( iSize > 0 );
			delete[] pT;
			pT = NULL;
		}
	}

	// Returns the pointer to the given item.
	T *Item ( int iItem )
	{
		ASSERT ( iItem < iSize );
		return ( &pT[iItem] );
	}

	// Returns the pointer to the first item.
	T *Ptr ( void )
	{
		return ( pT );
	}

	// Returns the size of the list
	int Size ( void )
	{
		return iSize;
	}

	// Grows or shrinks the list to this number of items.
	// Preserves existing items.
	// Items that fall off the end of a shrink may vanish.
	// Returns the pointer to the first item.
	T *SizeTo ( int iNum )
	{
		ASSERT ( iNum >= 0 );
		iSize = iNum;
		if ( iNum <= iReservedSize )
		{
			if ( iNum == 0 )
			{
				// Shrunk to 0 - bin the memory.
				delete[] pT;
				pT = NULL;
				iReservedSize = 0;
			}
			else
			{
				ASSERT ( pT != NULL );
			}
			return ( pT );
		}
		else
		{
			// Need to grow. Grow by 50% more than
			// needed to avoid constant regrows.
			int iNewSize = ( iNum * 3 ) >> 1;
			if ( pT == NULL )
			{
				ASSERT ( iReservedSize == 0 );
				pT = new T [iNewSize];
			}
			else
			{
				ASSERT ( iReservedSize != 0 );

				T *pOldT = pT;
				pT = new T[iNewSize];
				for ( int i = 0; i < iReservedSize; i++ )
				{
					pT[i] = pOldT[i];
				}
				delete[] pOldT;
			}
			ASSERT ( pT != NULL );
			iReservedSize = iNewSize;
			return ( pT );
		}
	}

	// Adds one item to the list and returns a pointer to that new item.
	T *AddItem ( void )
	{
		SizeTo ( iSize + 1 );
		return ( &pT[iSize-1] );
	}

	// Removes the given item number by copying the last item
	// to that position and shrinking the list.
	void RemoveItem ( int iItemNumber )
	{
		ASSERT ( iItemNumber < iSize );
		pT[iItemNumber] = pT[iSize-1];
		SizeTo ( iSize - 1 );
	}

	// Copy the specified data into the list.
	void CopyFrom ( int iFirstItem, T *p, int iNumItems )
	{
		for ( int i = 0; i < iNumItems; i++ )
		{
			*(Item ( i + iFirstItem ) ) = p[i];
		}
	}

	// A copy from another arbitrary list of the same type.
	void CopyFrom ( int iFirstItem, ArbitraryList<T> &other, int iFirstOtherItem, int iNumItems )
	{
		for ( int i = 0; i < iNumItems; i++ )
		{
			*(Item ( i + iFirstItem ) ) = *(other.Item ( i + iFirstOtherItem ) );
		}
	}


	// Copy constructor.
	ArbitraryList ( const ArbitraryList<T> &other )
	{
		int iNumItems = other.Size();

		pT = NULL;
		iSize = 0;
		iReservedSize = 0;
		if ( iInitialSize > 0 )
		{
			SizeTo ( iNumItems );
		}
		for ( int i = 0; i < iNumItems; i++ )
		{
			*(Item(i) ) = *(other.Item(i) );
		}
	}


};






#define MIN(a,b) ( (a) > (b) ? (b) : (a) )
#define MAX(a,b) ( (a) < (b) ? (b) : (a) )



#endif //#ifndef TOMSLIB_INCLUDED