core/sourcehook/sh_list.h
changeset 539 db914129ae01
parent 523 6f1630519b81
child 684 8015336442cb
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/core/sourcehook/sh_list.h	Fri Nov 14 04:04:02 2008 -0600
     1.3 @@ -0,0 +1,321 @@
     1.4 +/* ======== SourceMM ========
     1.5 +* Copyright (C) 2004-2008 Metamod:Source Development Team
     1.6 +* No warranties of any kind
     1.7 +*
     1.8 +* License: zlib/libpng
     1.9 +*
    1.10 +* Author(s): David "BAILOPAN" Anderson
    1.11 +* ============================
    1.12 +*/
    1.13 +
    1.14 +#ifndef _INCLUDE_SMM_LIST_H
    1.15 +#define _INCLUDE_SMM_LIST_H
    1.16 +
    1.17 +#include <new>
    1.18 +#include <malloc.h>
    1.19 +
    1.20 +namespace SourceHook
    1.21 +{
    1.22 +
    1.23 +	//This class is from CSDM for AMX Mod X
    1.24 +	/*
    1.25 +		A circular, doubly-linked list with one sentinel node
    1.26 +
    1.27 +		Empty:
    1.28 +			m_Head = sentinel
    1.29 +			m_Head->next = m_Head;
    1.30 +			m_Head->prev = m_Head;
    1.31 +		One element:
    1.32 +			m_Head = sentinel
    1.33 +			m_Head->next = node1
    1.34 +			m_Head->prev = node1
    1.35 +			node1->next = m_Head
    1.36 +			node1->prev = m_Head
    1.37 +		Two elements:
    1.38 +			m_Head = sentinel
    1.39 +			m_Head->next = node1
    1.40 +			m_Head->prev = node2
    1.41 +			node1->next = node2
    1.42 +			node1->prev = m_Head
    1.43 +			node2->next = m_Head
    1.44 +			node2->prev = node1
    1.45 +	*/
    1.46 +	template <class T>
    1.47 +	class List
    1.48 +	{
    1.49 +	public:
    1.50 +		class iterator;
    1.51 +		friend class iterator;
    1.52 +		class ListNode
    1.53 +		{
    1.54 +		public:
    1.55 +			ListNode(const T & o) : obj(o) { };
    1.56 +			ListNode() { };
    1.57 +			T obj;
    1.58 +			ListNode *next;
    1.59 +			ListNode *prev;
    1.60 +		};
    1.61 +	private:
    1.62 +		// Initializes the sentinel node.
    1.63 +		// BAIL used malloc instead of new in order to bypass the need for a constructor.
    1.64 +		ListNode *_Initialize()
    1.65 +		{
    1.66 +			ListNode *n = (ListNode *)malloc(sizeof(ListNode));
    1.67 +			n->next = n;
    1.68 +			n->prev = n;
    1.69 +			return n;
    1.70 +		}
    1.71 +	public:
    1.72 +		List() : m_Head(_Initialize()), m_Size(0)
    1.73 +		{
    1.74 +		}
    1.75 +		List(const List &src) : m_Head(_Initialize()), m_Size(0)
    1.76 +		{
    1.77 +			iterator iter;
    1.78 +			for (iter=src.begin(); iter!=src.end(); iter++)
    1.79 +				push_back( (*iter) );
    1.80 +		}
    1.81 +		~List()
    1.82 +		{
    1.83 +			clear();
    1.84 +
    1.85 +			// Don't forget to free the sentinel
    1.86 +			if (m_Head)
    1.87 +			{
    1.88 +				free(m_Head);
    1.89 +				m_Head = NULL;
    1.90 +			}
    1.91 +		}
    1.92 +		void push_back(const T &obj)
    1.93 +		{
    1.94 +			ListNode *node = new ListNode(obj);
    1.95 +
    1.96 +			node->prev = m_Head->prev;
    1.97 +			node->next = m_Head;
    1.98 +			m_Head->prev->next = node;
    1.99 +			m_Head->prev = node;
   1.100 +
   1.101 +			m_Size++;
   1.102 +		}
   1.103 +
   1.104 +		void push_front(const T &obj)
   1.105 +		{
   1.106 +			insert(begin(), obj);
   1.107 +		}
   1.108 +
   1.109 +		void push_sorted(const T &obj)
   1.110 +		{
   1.111 +			iterator iter;
   1.112 +			for (iter = begin(); iter != end(); ++iter)
   1.113 +			{
   1.114 +				if (obj < *iter)
   1.115 +				{
   1.116 +					insert(iter, obj);
   1.117 +					return;
   1.118 +				}
   1.119 +			}
   1.120 +			push_back(obj);
   1.121 +		}
   1.122 +
   1.123 +		size_t size() const
   1.124 +		{
   1.125 +			return m_Size;
   1.126 +		}
   1.127 +
   1.128 +		void clear()
   1.129 +		{
   1.130 +			ListNode *node = m_Head->next;
   1.131 +			ListNode *temp;
   1.132 +			m_Head->next = m_Head;
   1.133 +			m_Head->prev = m_Head;
   1.134 +
   1.135 +			// Iterate through the nodes until we find g_Head (the sentinel) again
   1.136 +			while (node != m_Head)
   1.137 +			{
   1.138 +				temp = node->next;
   1.139 +				delete node;
   1.140 +				node = temp;
   1.141 +			}
   1.142 +			m_Size = 0;
   1.143 +		}
   1.144 +		bool empty() const
   1.145 +		{
   1.146 +			return (m_Size == 0);
   1.147 +		}
   1.148 +		T & front()
   1.149 +		{
   1.150 +			return m_Head->next->obj;
   1.151 +		}
   1.152 +		T & back()
   1.153 +		{
   1.154 +			return m_Head->prev->obj;
   1.155 +		}
   1.156 +	private:
   1.157 +		ListNode *m_Head;
   1.158 +		size_t m_Size;
   1.159 +	public:
   1.160 +		class iterator
   1.161 +		{
   1.162 +		friend class List;
   1.163 +		public:
   1.164 +			iterator()
   1.165 +			{
   1.166 +				m_This = NULL;
   1.167 +			}
   1.168 +			iterator(const List &src)
   1.169 +			{
   1.170 +				m_This = src.m_Head;
   1.171 +			}
   1.172 +			iterator(ListNode *n) : m_This(n)
   1.173 +			{
   1.174 +			}
   1.175 +			iterator(const iterator &where)
   1.176 +			{
   1.177 +				m_This = where.m_This;
   1.178 +			}
   1.179 +			//pre decrement
   1.180 +			iterator & operator--()
   1.181 +			{
   1.182 +				if (m_This)
   1.183 +					m_This = m_This->prev;
   1.184 +				return *this;
   1.185 +			}
   1.186 +			//post decrement
   1.187 +			iterator operator--(int)
   1.188 +			{
   1.189 +				iterator old(*this);
   1.190 +				if (m_This)
   1.191 +					m_This = m_This->prev;
   1.192 +				return old;
   1.193 +			}	
   1.194 +			
   1.195 +			//pre increment
   1.196 +			iterator & operator++()
   1.197 +			{
   1.198 +				if (m_This)
   1.199 +					m_This = m_This->next;
   1.200 +				return *this;
   1.201 +			}
   1.202 +			//post increment
   1.203 +			iterator operator++(int)
   1.204 +			{
   1.205 +				iterator old(*this);
   1.206 +				if (m_This)
   1.207 +					m_This = m_This->next;
   1.208 +				return old;
   1.209 +			}
   1.210 +			
   1.211 +			const T & operator * () const
   1.212 +			{
   1.213 +				return m_This->obj;
   1.214 +			}
   1.215 +			T & operator * ()
   1.216 +			{
   1.217 +				return m_This->obj;
   1.218 +			}
   1.219 +			
   1.220 +			T * operator -> ()
   1.221 +			{
   1.222 +				return &(m_This->obj);
   1.223 +			}
   1.224 +			const T * operator -> () const
   1.225 +			{
   1.226 +				return &(m_This->obj);
   1.227 +			}
   1.228 +			
   1.229 +			bool operator != (const iterator &where) const
   1.230 +			{
   1.231 +				return (m_This != where.m_This);
   1.232 +			}
   1.233 +			bool operator ==(const iterator &where) const
   1.234 +			{
   1.235 +				return (m_This == where.m_This);
   1.236 +			}
   1.237 +
   1.238 +			operator bool()
   1.239 +			{
   1.240 +				return m_This != NULL;
   1.241 +			}
   1.242 +		private:
   1.243 +			ListNode *m_This;
   1.244 +		};
   1.245 +	public:
   1.246 +		iterator begin() const
   1.247 +		{
   1.248 +			return iterator(m_Head->next);
   1.249 +		}
   1.250 +		iterator end() const
   1.251 +		{
   1.252 +			return iterator(m_Head);
   1.253 +		}
   1.254 +		iterator erase(iterator &where)
   1.255 +		{
   1.256 +			ListNode *pNode = where.m_This;
   1.257 +			iterator iter(where);
   1.258 +			iter++;
   1.259 +
   1.260 +
   1.261 +			// Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle...
   1.262 +			pNode->prev->next = pNode->next;
   1.263 +			pNode->next->prev = pNode->prev;
   1.264 +
   1.265 +			delete pNode;
   1.266 +			m_Size--;
   1.267 +
   1.268 +			return iter;
   1.269 +		}
   1.270 +
   1.271 +		iterator insert(iterator where, const T &obj)
   1.272 +		{
   1.273 +			// Insert obj right before where
   1.274 +
   1.275 +			ListNode *node = new ListNode(obj);
   1.276 +			ListNode *pWhereNode = where.m_This;
   1.277 +			
   1.278 +			pWhereNode->prev->next = node;
   1.279 +			node->prev = pWhereNode->prev;
   1.280 +			pWhereNode->prev = node;
   1.281 +			node->next = pWhereNode;
   1.282 +
   1.283 +			m_Size++;
   1.284 +
   1.285 +			return iterator(node);
   1.286 +		}
   1.287 +
   1.288 +	public:
   1.289 +		void remove(const T & obj)
   1.290 +		{
   1.291 +			iterator b;
   1.292 +			for (b=begin(); b!=end(); b++)
   1.293 +			{
   1.294 +				if ( (*b) == obj )
   1.295 +				{
   1.296 +					erase( b );
   1.297 +					break;
   1.298 +				}
   1.299 +			}
   1.300 +		}
   1.301 +		template <typename U>
   1.302 +		iterator find(const U & equ) const
   1.303 +		{
   1.304 +			iterator iter;
   1.305 +			for (iter=begin(); iter!=end(); iter++)
   1.306 +			{
   1.307 +				if ( (*iter) == equ )
   1.308 +					return iter;
   1.309 +			}
   1.310 +			return end();
   1.311 +		}
   1.312 +		List & operator =(const List &src)
   1.313 +		{
   1.314 +			clear();
   1.315 +			iterator iter;
   1.316 +			for (iter=src.begin(); iter!=src.end(); iter++)
   1.317 +				push_back( (*iter) );
   1.318 +			return *this;
   1.319 +		}
   1.320 +	};
   1.321 +
   1.322 +};	//NAMESPACE
   1.323 +
   1.324 +#endif //_INCLUDE_CSDM_LIST_H