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