ds@1952: /**
ds@1952:  * vim: set ts=4 :
ds@1952:  * =============================================================================
ds@1952:  * SourceMod
ds@1952:  * Copyright (C) 2004-2008 AlliedModders LLC.  All rights reserved.
ds@1952:  * =============================================================================
ds@1952:  *
ds@1952:  * This program is free software; you can redistribute it and/or modify it under
ds@1952:  * the terms of the GNU General Public License, version 3.0, as published by the
ds@1952:  * Free Software Foundation.
ds@1952:  * 
ds@1952:  * This program is distributed in the hope that it will be useful, but WITHOUT
ds@1952:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
ds@1952:  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
ds@1952:  * details.
ds@1952:  *
ds@1952:  * You should have received a copy of the GNU General Public License along with
ds@1952:  * this program.  If not, see <http://www.gnu.org/licenses/>.
ds@1952:  *
ds@1952:  * As a special exception, AlliedModders LLC gives you permission to link the
ds@1952:  * code of this program (as well as its derivative works) to "Half-Life 2," the
ds@1952:  * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
ds@1952:  * by the Valve Corporation.  You must obey the GNU General Public License in
ds@1952:  * all respects for all other code used.  Additionally, AlliedModders LLC grants
ds@1952:  * this exception to all derivative works.  AlliedModders LLC defines further
ds@1952:  * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
ds@1952:  * or <http://www.sourcemod.net/license.php>.
ds@1952:  *
ds@1952:  * Version: $Id$
ds@1952:  */
ds@1952: 
ds@1952: #ifndef _INCLUDE_SM_QUEUE_H
ds@1952: #define _INCLUDE_SM_QUEUE_H
ds@1952: 
ds@1952: #include <new>
ds@1952: #include <malloc.h>
ds@1952: #include <sh_stack.h>
ds@1952: 
ds@1952: using namespace SourceHook;
ds@1952: 
ds@1952: /*
ds@1952: 	A circular, doubly-linked List with one sentinel node
ds@1952: 
ds@1952: 	Empty:
ds@1952: 	m_Head = sentinel
ds@1952: 	m_Head->next = m_Head;
ds@1952: 	m_Head->prev = m_Head;
ds@1952: 	One element:
ds@1952: 	m_Head = sentinel
ds@1952: 	m_Head->next = node1
ds@1952: 	m_Head->prev = node1
ds@1952: 	node1->next = m_Head
ds@1952: 	node1->prev = m_Head
ds@1952: 	Two elements:
ds@1952: 	m_Head = sentinel
ds@1952: 	m_Head->next = node1
ds@1952: 	m_Head->prev = node2
ds@1952: 	node1->next = node2
ds@1952: 	node1->prev = m_Head
ds@1952: 	node2->next = m_Head
ds@1952: 	node2->prev = node1
ds@1952: */
ds@1952: template <class T>
ds@1952: class Queue
ds@1952: {
ds@1952: public:
ds@1952: 	class iterator;
ds@1952: 	friend class iterator;
ds@1952: 	class QueueNode
ds@1952: 	{
ds@1952: 	public:
ds@1952: 		T obj;
ds@1952: 		QueueNode *next;
ds@1952: 		QueueNode *prev;
ds@1952: 	};
ds@1952: private:
ds@1952: 	// Initializes the sentinel node.
ds@1952: 	QueueNode *_Initialize()
ds@1952: 	{
ds@1952: 		QueueNode *n = (QueueNode *)malloc(sizeof(QueueNode));
ds@1952: 		n->next = n;
ds@1952: 		n->prev = n;
ds@1952: 		return n;
ds@1952: 	}
ds@1952: public:
ds@1952: 	Queue() : m_Head(_Initialize()), m_Size(0)
ds@1952: 	{
ds@1952: 	}
ds@1952: 
ds@1952: 	Queue(const Queue &src) : m_Head(_Initialize()), m_Size(0)
ds@1952: 	{
ds@1952: 		iterator iter;
ds@1952: 		for (iter=src.begin(); iter!=src.end(); iter++)
ds@1952: 		{
ds@1952: 			push_back( (*iter) );
ds@1952: 		}
ds@1952: 	}
ds@1952: 
ds@1952: 	~Queue()
ds@1952: 	{
ds@1952: 		clear();
ds@1952: 
ds@1952: 		// Don't forget to free the sentinel
ds@1952: 		if (m_Head)
ds@1952: 		{
ds@1952: 			free(m_Head);
ds@1952: 			m_Head = NULL;
ds@1952: 		}
ds@1952: 
ds@1952: 		while (!m_FreeNodes.empty())
ds@1952: 		{
ds@1952: 			free(m_FreeNodes.front());
ds@1952: 			m_FreeNodes.pop();
ds@1952: 		}
ds@1952: 	}
ds@1952: 
ds@1952: 	void push(const T &obj)
ds@1952: 	{
ds@1952: 		QueueNode *node;
ds@1952: 		
ds@1952: 		if (m_FreeNodes.empty())
ds@1952: 		{
ds@1952: 			node = (QueueNode *)malloc(sizeof(QueueNode));
ds@1952: 		} else {
ds@1952: 			node = m_FreeNodes.front();
ds@1952: 			m_FreeNodes.pop();
ds@1952: 		}
ds@1952: 
ds@1952: 		/* Copy the object */
ds@1952: 		new (&node->obj) T(obj);
ds@1952: 
ds@1952: 		/* Install into the Queue */
ds@1952: 		node->prev = m_Head->prev;
ds@1952: 		node->next = m_Head;
ds@1952: 		m_Head->prev->next = node;
ds@1952: 		m_Head->prev = node;
ds@1952: 
ds@1952: 		m_Size++;
ds@1952: 	}
ds@1952: 
ds@1952: 	size_t size() const
ds@1952: 	{
ds@1952: 		return m_Size;
ds@1952: 	}
ds@1952: 
ds@1952: 	void clear()
ds@1952: 	{
ds@1952: 		QueueNode *node = m_Head->next;
ds@1952: 		QueueNode *temp;
ds@1952: 		m_Head->next = m_Head;
ds@1952: 		m_Head->prev = m_Head;
ds@1952: 
ds@1952: 		// Iterate through the nodes until we find g_Head (the sentinel) again
ds@1952: 		while (node != m_Head)
ds@1952: 		{
ds@1952: 			temp = node->next;
ds@1952: 			node->obj.~T();
ds@1952: 			m_FreeNodes.push(node);
ds@1952: 			node = temp;
ds@1952: 		}
ds@1952: 		m_Size = 0;
ds@1952: 	}
ds@1952: 
ds@1952: 	bool empty() const
ds@1952: 	{
ds@1952: 		return (m_Size == 0);
ds@1952: 	}
ds@1952: 
ds@1952: private:
ds@1952: 	QueueNode *m_Head;
ds@1952: 	size_t m_Size;
ds@1952: 	CStack<QueueNode *> m_FreeNodes;
ds@1952: public:
ds@1952: 	class iterator
ds@1952: 	{
ds@1952: 		friend class Queue;
ds@1952: 	public:
ds@1952: 		iterator()
ds@1952: 		{
ds@1952: 			m_This = NULL;
ds@1952: 		}
ds@1952: 		iterator(const Queue &src)
ds@1952: 		{
ds@1952: 			m_This = src.m_Head;
ds@1952: 		}
ds@1952: 		iterator(QueueNode *n) : m_This(n)
ds@1952: 		{
ds@1952: 		}
ds@1952: 		iterator(const iterator &where)
ds@1952: 		{
ds@1952: 			m_This = where.m_This;
ds@1952: 		}
ds@1952: 		//pre decrement
ds@1952: 		iterator & operator--()
ds@1952: 		{
ds@1952: 			if (m_This)
ds@1952: 				m_This = m_This->prev;
ds@1952: 			return *this;
ds@1952: 		}
ds@1952: 		//post decrement
ds@1952: 		iterator operator--(int)
ds@1952: 		{
ds@1952: 			iterator old(*this);
ds@1952: 			if (m_This)
ds@1952: 				m_This = m_This->prev;
ds@1952: 			return old;
ds@1952: 		}	
ds@1952: 
ds@1952: 		//pre increment
ds@1952: 		iterator & operator++()
ds@1952: 		{
ds@1952: 			if (m_This)
ds@1952: 				m_This = m_This->next;
ds@1952: 			return *this;
ds@1952: 		}
ds@1952: 		//post increment
ds@1952: 		iterator operator++(int)
ds@1952: 		{
ds@1952: 			iterator old(*this);
ds@1952: 			if (m_This)
ds@1952: 				m_This = m_This->next;
ds@1952: 			return old;
ds@1952: 		}
ds@1952: 
ds@1952: 		const T & operator * () const
ds@1952: 		{
ds@1952: 			return m_This->obj;
ds@1952: 		}
ds@1952: 		T & operator * ()
ds@1952: 		{
ds@1952: 			return m_This->obj;
ds@1952: 		}
ds@1952: 
ds@1952: 		T * operator -> ()
ds@1952: 		{
ds@1952: 			return &(m_This->obj);
ds@1952: 		}
ds@1952: 		const T * operator -> () const
ds@1952: 		{
ds@1952: 			return &(m_This->obj);
ds@1952: 		}
ds@1952: 
ds@1952: 		bool operator != (const iterator &where) const
ds@1952: 		{
ds@1952: 			return (m_This != where.m_This);
ds@1952: 		}
ds@1952: 		bool operator ==(const iterator &where) const
ds@1952: 		{
ds@1952: 			return (m_This == where.m_This);
ds@1952: 		}
ds@1952: 	private:
ds@1952: 		QueueNode *m_This;
ds@1952: 	};
ds@1952: public:
ds@1952: 	iterator begin() const
ds@1952: 	{
ds@1952: 		return iterator(m_Head->next);
ds@1952: 	}
ds@1952: 
ds@1952: 	iterator end() const
ds@1952: 	{
ds@1952: 		return iterator(m_Head);
ds@1952: 	}
ds@1952: 
ds@1952: 	iterator erase(iterator &where)
ds@1952: 	{
ds@1952: 		QueueNode *pNode = where.m_This;
ds@1952: 		iterator iter(where);
ds@1952: 		iter++;
ds@1952: 
ds@1952: 
ds@1952: 		// Works for all cases: empty Queue, erasing first element, erasing tail, erasing in the middle...
ds@1952: 		pNode->prev->next = pNode->next;
ds@1952: 		pNode->next->prev = pNode->prev;
ds@1952: 
ds@1952: 		pNode->obj.~T();
ds@1952: 		m_FreeNodes.push(pNode);
ds@1952: 		m_Size--;
ds@1952: 
ds@1952: 		return iter;
ds@1952: 	}
ds@1952: public:
ds@1952: 	void remove(const T & obj)
ds@1952: 	{
ds@1952: 		iterator b;
ds@1952: 		for (b=begin(); b!=end(); b++)
ds@1952: 		{
ds@1952: 			if ( (*b) == obj )
ds@1952: 			{
ds@1952: 				erase( b );
ds@1952: 				break;
ds@1952: 			}
ds@1952: 		}
ds@1952: 	}
ds@1952: 	template <typename U>
ds@1952: 	iterator find(const U & equ) const
ds@1952: 	{
ds@1952: 		iterator iter;
ds@1952: 		for (iter=begin(); iter!=end(); iter++)
ds@1952: 		{
ds@1952: 			if ( (*iter) == equ )
ds@1952: 			{
ds@1952: 				return iter;
ds@1952: 			}
ds@1952: 		}
ds@1952: 		return end();
ds@1952: 	}
ds@1952: 	Queue & operator =(const Queue &src)
ds@1952: 	{
ds@1952: 		clear();
ds@1952: 		iterator iter;
ds@1952: 		for (iter=src.begin(); iter!=src.end(); iter++)
ds@1952: 		{
ds@1952: 			push_back( (*iter) );
ds@1952: 		}
ds@1952: 		return *this;
ds@1952: 	}
ds@1952: public:
ds@1952: 	T & first() const
ds@1952: 	{
ds@1952: 		iterator i = begin();
ds@1952: 
ds@1952: 		return (*i);
ds@1952: 	}
ds@1952: 
ds@1952: 	void pop()
ds@1952: 	{
ds@1952: 		iterator iter = begin();
ds@1952: 		erase(iter);
ds@1952: 	}
ds@1952: };
ds@1952: 
ds@1952: #endif //_INCLUDE_SM_QUEUE_H