source-engine/public/list.h

//========= Copyright Valve Corporation, All rights reserved. ============//
//
// Purpose: 
//
// $NoKeywords: $
//
//=============================================================================//
#ifndef __LIST_H__
#define __LIST_H__

// TODO:
// GetPositionAtIndex needs to keep a cache of the previous call so 
// that it doesn't do a linear search every time.

#include <stdlib.h>

// FIXME: change the name of this to something more specific.
typedef struct
{
} _Position;
typedef _Position *Position;

template <class T> class GList;
template <class T> class GListIterator;

// GListNode: Class decleration and definition
template <class T> class GListNode
{
private:
	T data;
	GListNode<T> *next;
	GListNode<T> *prev;
	GListNode();
	GListNode( T item );
	friend class GList<T>;
	friend class GListIterator<T>;
};

template <class T>
GListNode<T>::GListNode()
{
	next = NULL;
	prev = NULL;
}

template <class T>
GListNode<T>::GListNode( T item )
{
	data = item;
	next = NULL;
	prev = NULL;
}

// GList: Class decleration and definition
template <class T> class GList
{
public:
	// Contructors/destructors
	GList();
	
	//
	Position InsertAtHead( T );
	Position InsertAtTail( T );
	T Remove( Position position );
	void RemoveAll( void (*DeleteItem)( T ) );
	void RemoveSelectedItems( bool (*NeedsRemovalFunc)( T ), void (*DeleteItemFunc)( T ) );	
	Position InsertAfter( T item, Position position );
	Position InsertBefore( T item, Position position );
	bool IsEmpty();
	int GetNumItems();
	T GetItemAtPosition( Position position );
	Position GetPositionAtIndex( int index );
	T GetItemAtIndex( int index );
	
protected:
	GListNode<T> *head;
	GListNode<T> *tail;
	int numItems;
	friend class GListIterator<T>;
};

template<class T> 
GList<T>::GList()
{
	// Set up a dummy head node and a dummy tail node.
	head = new GListNode<T>;
	tail = new GListNode<T>;
	head->next = tail;
	head->prev = head;
	tail->next = tail;
	tail->prev = head;
	numItems = 0;
}

template<class T> 
Position GList<T>::InsertAtHead( T item )
{
	GListNode<T> *newNode = new GListNode<T>( item );
	head->next->prev = newNode;
	newNode->next = head->next;
	newNode->prev = head;
	head->next = newNode;
	numItems++;
	return ( Position )( void * )newNode;
}

template<class T> 
Position GList<T>::InsertAtTail( T item )
{
	GListNode<T> *newNode = new GListNode<T>( item );
	tail->prev->next = newNode;
	newNode->prev = tail->prev;
	tail->prev = newNode;
	newNode->next = tail;
	numItems++;
	return ( Position )( void * )newNode;
}

template<class T>
T GList<T>::Remove( Position position )
{
	GListNode<T> *node = ( GListNode<T> * )( void * )position;
	node->prev->next = node->next;
	node->next->prev = node->prev;
	T data = node->data;
	numItems--;
	delete node;
	return data;
}

template<class T>
void GList<T>::RemoveAll( void (*DeleteItemFunc)( T ) )
{
	GListNode<T> *tmpNode;
	GListNode<T> *node = head->next;
	while( node != tail )
	{
		if( DeleteItemFunc )
		{
			DeleteItemFunc( node->data );
		}
		tmpNode = node->next;
		delete node;
		node = tmpNode;
	}
	head->next = tail;
	head->prev = head;
	tail->next = tail;
	tail->prev = head;
	numItems = 0;
}

template<class T>
void GList<T>::RemoveSelectedItems( bool (*NeedsRemovalFunc)( T ), void (*DeleteItemFunc)( T ) )
{
	GListNode<T> *tmpNode;
	GListNode<T> *node = head->next;
	while( node != tail )
	{
		if( NeedsRemovalFunc( node->data ) )
		{
			DeleteItemFunc( node->data );
			node->prev->next = node->next;
			node->next->prev = node->prev;
			tmpNode = node;
			node = node->next;
			delete tmpNode;
			numItems--;
		}
		else
		{
			node = node->next;
		}
	}
}

template<class T>
Position GList<T>::InsertAfter( T item, Position position )
{
	GListNode<T> *node = ( GListNode<T> * )( void * )position;
	GListNode<T> *newNode = new GListNode<T>( item );
	newNode->prev = node;
	newNode->next = node->next;
	node->next->prev = newNode;
	node->next = newNode;
	numItems++;
	return ( Position )( void * )newNode;
}

template<class T>
Position GList<T>::InsertBefore( T item, Position position )
{
	GListNode<T> *node = ( GListNode<T> * )( void * )position;
	GListNode<T> *newNode = new GListNode<T>( item );
	newNode->prev = node->prev;
	newNode->next = node;
	node->prev->next = newNode;
	node->prev = newNode;
	numItems++;
	return ( Position )( void * )newNode;
}

template<class T>
bool GList<T>::IsEmpty()
{
	return ( numItems == 0 );
}

template <class T>
int GList<T>::GetNumItems()
{
	return numItems;
}

template<class T>
T GList<T>::GetItemAtPosition( Position position )
{
	return ( ( GListNode<T> * )( void * )position )->data;
}

template<class T>
Position GList<T>::GetPositionAtIndex( int index )
{
	int i;
	GListNode<T> *node = head->next;
	for( i = 0; i < index; i++ )
    {
		node = node->next;
    }
	return ( Position )( void * )node;
}

template<class T>
T GList<T>::GetItemAtIndex( int index )
{
	return GetItemAtPosition( GetPositionAtIndex( index ) );
}

// GListIterator: Class decleration and definition
template<class T> class GListIterator
{
public:
	GListIterator( GList<T> *GList );
	void GotoHead( void );
	void GotoTail( void );
	void Goto( int index );
	void Increment();
	void Decrement();
	T GetCurrentAndIncrement();
	T GetCurrentAndDecrement();
	T IncrementAndGetCurrent();
	T DecrementAndGetCurrent();
	// postfix
	T operator++( int ) { return GetCurrentAndIncrement(); }
	T operator--( int ) { return GetCurrentAndDecrement(); }
	// prefix
	T operator++() { return IncrementAndGetCurrent(); }
	T operator--() { return DecrementAndGetCurrent(); }
	T GetCurrent();
	bool AtEnd( void );
	bool AtBeginning( void );
protected:
	GList<T> *list;
	GListNode<T> *currentNode;
};

template<class T>
GListIterator<T>::GListIterator( GList<T> *list )
{
	this->list = list;
	GotoHead();
}

template<class T>
void GListIterator<T>::GotoHead()
{
	this->currentNode = list->head->next;
}

template<class T>
void GListIterator<T>::GotoTail()
{
	this->currentNode = list->tail->prev;
}

template<class T>
void GListIterator<T>::Goto( int index )
{
	currentNode = ( GListNode<T> * )( void * )list->GetPositionAtIndex( index );
}

template<class T>
void GListIterator<T>::Increment()
{
	currentNode = currentNode->next;
}

template<class T>
void GListIterator<T>::Decrement()
{
	currentNode = currentNode->prev;
}

template<class T>
T GListIterator<T>::GetCurrentAndIncrement()
{
	T retval = currentNode->data;
	Increment();
	return retval;
}

template<class T>
T GListIterator<T>::GetCurrentAndDecrement()
{
	T retval = currentNode->data;
	Decrement();
	return retval;
}

template<class T>
T GListIterator<T>::IncrementAndGetCurrent()
{
	Increment();
	return GetCurrent();
}

template<class T>
T GListIterator<T>::DecrementAndGetCurrent()
{
	Decrement();
	return GetCurrent();
}

template<class T>
T GListIterator<T>::GetCurrent()
{
	return currentNode->data;
}

template<class T>
bool GListIterator<T>::AtEnd( void )
{
	return currentNode->next == currentNode;
}

template<class T>
bool GListIterator<T>::AtBeginning( void )
{
	return currentNode->prev == currentNode;
}

#endif /* __LIST_H__ */