dvander@767: /**
dvander@767:  * vim: set ts=4 :
ds@1330:  * =============================================================================
dvander@1231:  * SourceMod
ds@1947:  * Copyright (C) 2004-2008 AlliedModders LLC.  All rights reserved.
ds@1330:  * =============================================================================
dvander@767:  *
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@767:  *
dvander@767:  * Version: $Id$
dvander@767:  */
dvander@767: 
dvander@767: #ifndef _INCLUDE_SOURCEMOD_FASTLINK_H_
dvander@767: #define _INCLUDE_SOURCEMOD_FASTLINK_H_
dvander@767: 
dvander@854: #include <assert.h>
dvander@854: 
dvander@767: template <typename T>
dvander@767: class FastLink
dvander@767: {
dvander@767: public:
dvander@767: 	struct FastLinkNode
dvander@767: 	{
dvander@767: 		unsigned int prev;
dvander@767: 		unsigned int next;
dvander@767: 		unsigned int freeNode;
dvander@767: 		T obj;
dvander@767: 	};
dvander@767: public:
dvander@1131: 	FastLink(unsigned int maxsize) : m_Size(0), m_FirstLink(0), m_FreeNodes(0), m_LastLink(0), m_UsableIndex(0)
dvander@767: 	{
dvander@767: 		m_MaxSize = maxsize;
dvander@767: 		m_Nodes = new FastLinkNode[m_MaxSize+1];
dvander@767: 	}
dvander@767: public:
dvander@767: 	bool push_back(const T & obj)
dvander@767: 	{
dvander@767: 		unsigned int new_node = GetFreeIndex();
dvander@767: 		if (!new_node)
dvander@767: 		{
dvander@767: 			return false;
dvander@767: 		}
dvander@767: 		m_Nodes[new_node].obj = obj;
dvander@767: 		m_Nodes[new_node].next = 0;
dvander@767: 		if (!m_FirstLink)
dvander@767: 		{
dvander@767: 			m_Nodes[new_node].prev = 0;
dvander@767: 			m_FirstLink = new_node;
dvander@767: 			m_LastLink = new_node;
dvander@767: 		} else {
dvander@767: 			m_Nodes[new_node].prev = m_LastLink;
dvander@767: 			m_Nodes[m_LastLink].next = new_node;
dvander@767: 			m_LastLink = new_node;
dvander@767: 		}
dvander@767: 		m_Size++;
dvander@767: 		return true;
dvander@767: 	}
dvander@767: 	size_t size() const
dvander@767: 	{
dvander@767: 		return m_Size;
dvander@767: 	}
dvander@767: private:
dvander@767: 	unsigned int GetFreeIndex()
dvander@767: 	{
dvander@767: 		if (m_FreeNodes)
dvander@767: 		{
dvander@767: 			return m_Nodes[m_FreeNodes--].freeNode;
dvander@767: 		} else {
dvander@1131: 			if (m_UsableIndex >= m_MaxSize)
dvander@767: 			{
dvander@767: 				return 0;
dvander@767: 			}
dvander@1131: 			m_UsableIndex++;
dvander@1131: 			return m_UsableIndex;
dvander@767: 		}
dvander@767: 	}
dvander@767: public:
dvander@767: 	class iterator
dvander@767: 	{
dvander@767: 		friend class FastLink;
dvander@767: 	public:
dvander@767: 		iterator()
dvander@767: 		{
dvander@767: 			link = NULL;
dvander@767: 			position = 0;
dvander@767: 		}
dvander@767: 		iterator(const FastLink *_link, unsigned int _position)
dvander@767: 		{
dvander@767: 			link = _link;
dvander@767: 			position = _position;
dvander@767: 		}
dvander@767: 	public:
dvander@767: 		bool operator ==(const iterator &where) const
dvander@767: 		{
dvander@772: 			return (link == where.link && position == where.position);
dvander@767: 		}
dvander@767: 		bool operator !=(const iterator &where) const
dvander@767: 		{
dvander@772: 			return (link != where.link || position != where.position);
dvander@767: 		}
dvander@767: 		T & operator *()
dvander@767: 		{
dvander@767: 			return link->m_Nodes[position].obj;
dvander@767: 		}
dvander@767: 		const T & operator *() const
dvander@767: 		{
dvander@767: 			return link->m_Nodes[position].obj;
dvander@767: 		}
dvander@767: 		iterator & operator++()
dvander@767: 		{
dvander@767: 			position = link->m_Nodes[position].next;
dvander@767: 			return *this;
dvander@767: 		}
dvander@767: 	private:
dvander@767: 		const FastLink *link;
dvander@767: 		unsigned int position;
dvander@767: 	};
dvander@767: public:
dvander@767: 	iterator begin() const
dvander@767: 	{
dvander@767: 		return iterator(this, m_FirstLink);
dvander@767: 	}
dvander@767: 	iterator end() const
dvander@767: 	{
dvander@767: 		return iterator(this, 0);
dvander@767: 	}
dvander@767: 	void remove(const T & obj)
dvander@767: 	{
dvander@767: 		for (iterator iter=begin(); iter!=end(); ++iter)
dvander@767: 		{
dvander@767: 			if ((*iter) == obj)
dvander@767: 			{
dvander@767: 				erase(iter);
dvander@767: 				return;
dvander@767: 			}
dvander@767: 		}
dvander@767: 	}
dvander@767: 	iterator erase(const iterator &where)
dvander@767: 	{
dvander@767: 		/* Whoa, this better be right! */
dvander@767: 		assert(where.link == this);
dvander@767: 
dvander@767: 		iterator iter(where.link, where.position);
dvander@767: 		++iter;
dvander@767: 
dvander@767: 		unsigned int index = where.position;
dvander@767: 
dvander@767: 		/* Each case is different, we have no sentinel.
dvander@767: 		 * CASE: We're the HEAD AND the TAIL */
dvander@767: 		if (index == m_FirstLink
dvander@767: 			&& index == m_LastLink)
dvander@767: 		{
dvander@767: 			m_FirstLink = 0;
dvander@767: 			m_LastLink = 0;
dvander@767: 		}
dvander@767: 		/* We're the HEAD */
dvander@767: 		else if (index == m_FirstLink)
dvander@767: 		{
dvander@767: 			m_FirstLink = m_Nodes[index].next;
dvander@854: 			m_Nodes[m_FirstLink].prev = 0;
dvander@767: 		}
dvander@767: 		/* We're the TAIL */
dvander@767: 		else if (index == m_LastLink)
dvander@767: 		{
dvander@767: 			m_LastLink = m_Nodes[index].prev;
dvander@854: 			m_Nodes[m_LastLink].next = 0;
dvander@767: 		}
dvander@767: 		/* We're in the middle! */
dvander@767: 		else
dvander@767: 		{
dvander@767: 			/* Patch forward reference */
dvander@767: 			m_Nodes[m_Nodes[index].next].prev = m_Nodes[index].prev;
dvander@767: 			/* Patch backward reference */
dvander@767: 			m_Nodes[m_Nodes[index].prev].next = m_Nodes[index].next;
dvander@767: 		}
dvander@767: 
dvander@767: 		/* Add us to the free list */
dvander@767: 		m_Nodes[++m_FreeNodes].freeNode = index;
dvander@767: 
dvander@854: 		m_Size--;
dvander@854: 
dvander@767: 		return iter;
dvander@767: 	}
dvander@1131: #if defined MENU_DEBUG
dvander@1131: public:
dvander@1131: #else
dvander@767: private:
dvander@1131: #endif
dvander@767: 	size_t m_Size;
dvander@767: 	unsigned int m_FirstLink;
dvander@778: 	unsigned int m_FreeNodes;
dvander@767: 	unsigned int m_LastLink;
dvander@767: 	unsigned int m_MaxSize;
dvander@1131: 	unsigned int m_UsableIndex;
dvander@767: 	FastLinkNode *m_Nodes;
dvander@767: };
dvander@767: 
dvander@767: #endif //_INCLUDE_SOURCEMOD_FASTLINK_H_