1.3 Добавляем поддержку связных списков (LinkedList.h)

//-----------------------------------------------------------------------------
//  File: LinkedList.h
//	Сборник функций и классов для работы со
//	связными списками (LinkedLists).
//
//	Original SourceCode:
//	Programming a Multiplayer First Person Shooter in DirectX
//	Copyright (c) 2004 Vaughan Young
//-----------------------------------------------------------------------------
#ifndef LINKED_LIST_H
#define LINKED_LIST_H

//----------------------------------------------------------------------------
// Macros
// Макросы безопасного удаления
//----------------------------------------------------------------------------
#define SAFE_DELETE( p )       { if( p ) { delete ( p );     ( p ) = NULL; } }
#define SAFE_DELETE_ARRAY( p ) { if( p ) { delete[] ( p );   ( p ) = NULL; } }
#define SAFE_RELEASE( p )      { if( p ) { ( p )->Release(); ( p ) = NULL; } }

//-----------------------------------------------------------------------------
// Linked List Class
//-----------------------------------------------------------------------------
template< class Type > class LinkedList
{
public:
	//-------------------------------------------------------------------------
	// Element Structure
	//-------------------------------------------------------------------------
	struct Element
	{
		Type *data; // Pointer to the data held in the element.
				// Указатель на данные, содержащиеся в элементе.
		Element *next; // Pointer to the next element in the list.
				// Указатель на следующий элемент в списке.
		Element *prev; // Pointer to the previous element in the list.
				// Указатель на предыдущий элемент в списке.

		//---------------------------------------------------------------------
		// The element structure constructor.
		//---------------------------------------------------------------------
		Element( Type *element )
		{
			data = element;
			next = prev = NULL;
		}

		//---------------------------------------------------------------------
		// The element structure destructor.
		//---------------------------------------------------------------------
		~Element()
		{
			SAFE_DELETE( data );

			if( next )
				next->prev = prev;
			if( prev )
				prev->next = next;
		}
	};

	//-------------------------------------------------------------------------
	// The linked list class constructor.
	//-------------------------------------------------------------------------
	LinkedList()
	{
		m_first = m_last = m_iterate = m_temp = NULL;
		m_totalElements = 0;
	}

	//-------------------------------------------------------------------------
	// The linked list class destructor.
	//-------------------------------------------------------------------------
	~LinkedList()
	{
		Empty();
	}

	//-------------------------------------------------------------------------
	// Adds the given element to the end of the linked list.
	// Добавляет (add) данный элемент в конец списка.
	//-------------------------------------------------------------------------
	Type *Add( Type *element )
	{
		if( element == NULL )
			return NULL;

		if( m_first == NULL )
		{
			m_first = new Element( element );
			m_last = m_first;
		}
		else
		{
			m_last->next = new Element( element );
			m_last->next->prev = m_last;
			m_last = m_last->next;
		}

		m_totalElements++;

		return m_last->data;
	}

	//-------------------------------------------------------------------------
	// Inserts the given element into the linked list just before nextElement.
	// Вставляет данный элемент в связный список сразу перед nextElement.
	//-------------------------------------------------------------------------
	Type *InsertBefore( Type *element, Element *nextElement )
	{
		m_temp = nextElement->prev;

		m_totalElements++;

		if( m_temp == NULL )
		{
			m_first = new Element( element );
			m_first->next = nextElement;
			nextElement->prev = m_first;

			return m_first->data;
		}
		else
		{
			m_temp->next = new Element( element );
			m_temp->next->prev = m_temp;
			m_temp->next->next = nextElement;
			nextElement->prev = m_temp->next;

			return m_temp->next->data;
		}
	}

	//-------------------------------------------------------------------------
	// Removes the given element from the linked list and destroys its data.
	// Удаляет данный элемент из списка и уничтожает его данные.
	//-------------------------------------------------------------------------
	void Remove( Type **element )
	{
		m_temp = m_first;
		while( m_temp != NULL )
		{
			if( m_temp->data == *element )
			{
				if( m_temp == m_first )
				{
					m_first = m_first->next;
					if( m_first )
						m_first->prev = NULL;
				}
				if( m_temp == m_last )
				{
					m_last = m_last->prev;
					if( m_last )
						m_last->next = NULL;
				}

				SAFE_DELETE( m_temp );

				*element = NULL;

				m_totalElements--;

				return;
			}

			m_temp = m_temp->next;
		}
	}

	//-------------------------------------------------------------------------
	// Destroys all the elements in the linked list as well as their data.
	// Убирает (удаляет) все элементы связного списка вместе с их данными.
	//-------------------------------------------------------------------------
	void Empty()
	{
		while( m_last != NULL )
		{
			m_temp = m_last;
			m_last = m_last->prev;
			SAFE_DELETE( m_temp );
		}
		m_first = m_last = m_iterate = m_temp = NULL;
		m_totalElements = 0;
	}

	//-------------------------------------------------------------------------
	// Removes all the elements and clears their data pointers.
	// Warning: This function does not destroy the data held be each element.
	// Убирает (удаляет) все элементы связного списка вместе с указателями.
	// Внимание: Эта функция не уничтожает данные, содерж. в элементах.
	//-------------------------------------------------------------------------
	void ClearPointers()
	{
		while( m_last != NULL )
		{
			m_temp = m_last;
			m_temp->data = NULL;
			m_last = m_last->prev;
			SAFE_DELETE( m_temp );
		}
		m_first = m_last = m_iterate = m_temp = NULL;
		m_totalElements = 0;
	}

	//-------------------------------------------------------------------------
	// Removes the given element and clears its data pointer.
	// Warning: This function does not destroy the data held by the element.
	// Убирает (удаляет) данный элемент списка и очищает указатель на него.
	// Внимание: Эта функция не уничтожает данные, содерж. в данном элементе.
	//-------------------------------------------------------------------------
	void ClearPointer( Type **element )
	{
		m_temp = m_first;
		while( m_temp != NULL )
		{
			if( m_temp->data == *element )
			{
				if( m_temp == m_first )
				{
					m_first = m_first->next;
					if( m_first )
						m_first->prev = NULL;
				}
				if( m_temp == m_last )
				{
					m_last = m_last->prev;
					if( m_last )
						m_last->next = NULL;
				}

				m_temp->data = NULL;

				SAFE_DELETE( m_temp );

				*element = NULL;

				m_totalElements--;

				return;
			}

			m_temp = m_temp->next;
		}
	}

	//-------------------------------------------------------------------------
	// Iterates through the elements in the linked list.
	// Итерация (сканирование) каждого элемента в списке
	//-------------------------------------------------------------------------
	Type *Iterate( bool restart = false )
	{
		if( restart )
			m_iterate = NULL;
		else
		{
			if( m_iterate == NULL )
				m_iterate = m_first;
			else
				m_iterate = m_iterate->next;
		}

		if( m_iterate == NULL )
			return NULL;
		else
			return m_iterate->data;
	}

	//-------------------------------------------------------------------------
	// Returns the currently iterated element in the linked list.
	// Возвращает элемент связного списка, итерируемый в данный момент.
	//-------------------------------------------------------------------------
	Type *GetCurrent()
	{
		if( m_iterate )
			return m_iterate->data;
		else
			return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the first element in the linked list.
	// Возвращает первый элемент связного списка.
	//-------------------------------------------------------------------------
	Type *GetFirst()
	{
		if( m_first )
			return m_first->data;
		else
			return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the last element in the linked list.
	// Возвращает последний элемент связного списка.
	//-------------------------------------------------------------------------
	Type *GetLast()
	{
		if( m_last )
			return m_last->data;
		else
			return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the next element in the linked list from the given element.
	// Возвращает элемент связного списка, следующий за данным.
	//-------------------------------------------------------------------------
	Type *GetNext( Type *element )
	{
		m_temp = m_first;
		while( m_temp != NULL )
		{
			if( m_temp->data == element )
			{
				if( m_temp->next == NULL )
					return NULL;
				else
					return m_temp->next->data;
			}

			m_temp = m_temp->next;
		}

		return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns a random element from the linked list.
	// Возвращает случайный элемент связного списка.
	//-------------------------------------------------------------------------
	Type *GetRandom()
	{
		if( m_totalElements == 0 )
			return NULL;
		else if( m_totalElements == 1 )
			return m_first->data;

		unsigned long element = rand() * m_totalElements / RAND_MAX;

		m_temp = m_first;
		for( unsigned long e = 0; e < element; e++ )
			m_temp = m_temp->next;

		return m_temp->data;
	}

	//-------------------------------------------------------------------------
	// Returns the complete element (including its next and previous pointers).
	// Возвращает полный элемент списка
	// (включая указатели на предыдущий и след. элементы).
	//-------------------------------------------------------------------------
	Element *GetCompleteElement( Type *element )
	{
		m_temp = m_first;
		while( m_temp != NULL )
		{
			if( m_temp->data == element )
					return m_temp;

			m_temp = m_temp->next;
		}

		return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the total number of elements in the linked list.
	// Возвращает число элементов в связном списке.
	//-------------------------------------------------------------------------
	unsigned long GetTotalElements()
	{
		return m_totalElements;
	}

private:
	Element *m_first; // Первый элемент связного списка.
	Element *m_last; // Последний элемент связного списка.
	Element *m_iterate; // Используется для итерации связного списка.
	Element *m_temp; // // Используется как временное хранилище при различных операциях.

	unsigned long m_totalElements; // Total number of elements in the linked list.
								// Общее количество элементов в связном списке.
};

#endif

...
//-----------------------------------------------------------------------------
// Linked List Class
//-----------------------------------------------------------------------------
template< class Type > class LinkedList
...

...
struct Element
	{
		Type *data; // Pointer to the data held in the element.
				// Указатель на данные, содержащиеся в элементе.
		Element *next; // Pointer to the next element in the list.
				// Указатель на следующий элемент в списке.
		Element *prev; // Pointer to the previous element in the list.
				// Указатель на предыдущий элемент в списке.

		//---------------------------------------------------------------------
		// The element structure constructor.
		//---------------------------------------------------------------------
		Element( Type *element )
		{
			data = element;
			next = prev = NULL;
		}

		//---------------------------------------------------------------------
		// The element structure destructor.
		//---------------------------------------------------------------------
		~Element()
		{
			SAFE_DELETE( data );

			if( next )
				next->prev = prev;
			if( prev )
				prev->next = next;
		}
	};
...

LinkedList<float> *list = new LinkedList<float>;

list->Add( new float(5.0f));
List->Add( new float(3.7f));

SAFE_DELETE(list;)

...
//-----------------
// DirectX Includes
//-----------------
#include <d3dx9.h>
#include <dinput.h>

//-----------------------------
// Engine Includes
//-----------------------------
#include "LinkedList.h"
...