sourcehook/sh_list.h
changeset 163 377bdd31c28d
parent 150 22fbddfa0209
child 279 4836de1350c5
     1.1 --- a/sourcehook/sh_list.h	Fri Dec 23 11:58:11 2005 +0000
     1.2 +++ b/sourcehook/sh_list.h	Fri Dec 23 23:00:55 2005 +0000
     1.3 @@ -16,253 +16,276 @@
     1.4  
     1.5  namespace SourceHook
     1.6  {
     1.7 -//This class is from CSDM for AMX Mod X
     1.8 -template <class T>
     1.9 -class List
    1.10 -{
    1.11 -public:
    1.12 -	class iterator;
    1.13 -	friend class iterator;
    1.14 -	class ListNode
    1.15 +
    1.16 +	//This class is from CSDM for AMX Mod X
    1.17 +	/*
    1.18 +		A circular, doubly-linked list with one sentinel node
    1.19 +
    1.20 +		Empty:
    1.21 +			m_Head = sentinel
    1.22 +			m_Head->next = m_Head;
    1.23 +			m_Head->prev = m_Head;
    1.24 +		One element:
    1.25 +			m_Head = sentinel
    1.26 +			m_Head->next = node1
    1.27 +			m_Head->prev = node1
    1.28 +			node1->next = m_Head
    1.29 +			node1->prev = m_Head
    1.30 +		Two elements:
    1.31 +			m_Head = sentinel
    1.32 +			m_Head->next = node1
    1.33 +			m_Head->prev = node2
    1.34 +			node1->next = node2
    1.35 +			node1->prev = m_Head
    1.36 +			node2->next = m_Head
    1.37 +			node2->prev = node1
    1.38 +	*/
    1.39 +	template <class T>
    1.40 +	class List
    1.41  	{
    1.42  	public:
    1.43 -		ListNode(const T & o) : obj(o) { };
    1.44 -		ListNode() { };
    1.45 -		T obj;
    1.46 -		ListNode *next;
    1.47 -		ListNode *prev;
    1.48 -	};
    1.49 -private:
    1.50 -	ListNode *_Initialize()
    1.51 -	{
    1.52 -		ListNode *n = (ListNode *)malloc(sizeof(ListNode));
    1.53 -		n->next = NULL;
    1.54 -		n->prev = NULL;
    1.55 -		return n;
    1.56 -	}
    1.57 -public:
    1.58 -	List() : m_Head(_Initialize()), m_Size(0)
    1.59 -	{
    1.60 -	}
    1.61 -	List(const List &src) : m_Head(_Initialize()), m_Size(0)
    1.62 -	{
    1.63 -		iterator iter;
    1.64 -		for (iter=src.begin(); iter!=src.end(); iter++)
    1.65 -			push_back( (*iter) );
    1.66 -	}
    1.67 -	~List()
    1.68 -	{
    1.69 -		clear();
    1.70 -		if (m_Head)
    1.71 +		class iterator;
    1.72 +		friend class iterator;
    1.73 +		class ListNode
    1.74 +		{
    1.75 +		public:
    1.76 +			ListNode(const T & o) : obj(o) { };
    1.77 +			ListNode() { };
    1.78 +			T obj;
    1.79 +			ListNode *next;
    1.80 +			ListNode *prev;
    1.81 +		};
    1.82 +	private:
    1.83 +		// Initializes the sentinel node.
    1.84 +		// BAIL used malloc instead of new in order to bypass the need for a constructor.
    1.85 +		ListNode *_Initialize()
    1.86  		{
    1.87 -			free(m_Head);
    1.88 -			m_Head = NULL;
    1.89 +			ListNode *n = (ListNode *)malloc(sizeof(ListNode));
    1.90 +			n->next = n;
    1.91 +			n->prev = n;
    1.92 +			return n;
    1.93 +		}
    1.94 +	public:
    1.95 +		List() : m_Head(_Initialize()), m_Size(0)
    1.96 +		{
    1.97  		}
    1.98 -	}
    1.99 -	void push_back(const T &obj)
   1.100 -	{
   1.101 -		ListNode *node = new ListNode(obj);
   1.102 +		List(const List &src) : m_Head(_Initialize()), m_Size(0)
   1.103 +		{
   1.104 +			iterator iter;
   1.105 +			for (iter=src.begin(); iter!=src.end(); iter++)
   1.106 +				push_back( (*iter) );
   1.107 +		}
   1.108 +		~List()
   1.109 +		{
   1.110 +			clear();
   1.111  
   1.112 -		if (!m_Head->prev)
   1.113 +			// Don't forget to free the sentinel
   1.114 +			if (m_Head)
   1.115 +			{
   1.116 +				free(m_Head);
   1.117 +				m_Head = NULL;
   1.118 +			}
   1.119 +		}
   1.120 +		void push_back(const T &obj)
   1.121  		{
   1.122 -			//link in the node as the first item 
   1.123 -			node->next = m_Head;
   1.124 -			node->prev = m_Head;
   1.125 -			m_Head->prev = node;
   1.126 -			m_Head->next = node;
   1.127 -		} else {
   1.128 +			ListNode *node = new ListNode(obj);
   1.129 +
   1.130  			node->prev = m_Head->prev;
   1.131  			node->next = m_Head;
   1.132  			m_Head->prev->next = node;
   1.133  			m_Head->prev = node;
   1.134 +
   1.135 +			m_Size++;
   1.136  		}
   1.137 -		m_Size++;
   1.138 -	}
   1.139 -	size_t size()
   1.140 -	{
   1.141 -		return m_Size;
   1.142 -	}
   1.143 -	void clear()
   1.144 -	{
   1.145 -		ListNode *node = m_Head->next;
   1.146 -		ListNode *temp;
   1.147 -		m_Head->next = NULL;
   1.148 -		m_Head->prev = NULL;
   1.149 -		while (node && node != m_Head)
   1.150 +		size_t size()
   1.151 +		{
   1.152 +			return m_Size;
   1.153 +		}
   1.154 +
   1.155 +		void clear()
   1.156  		{
   1.157 -			temp = node->next;
   1.158 -			delete node;
   1.159 -			node = temp;
   1.160 +			ListNode *node = m_Head->next;
   1.161 +			ListNode *temp;
   1.162 +			m_Head->next = m_Head;
   1.163 +			m_Head->prev = m_Head;
   1.164 +
   1.165 +			// Iterate through the nodes until we find g_Head (the sentinel) again
   1.166 +			while (node != m_Head)
   1.167 +			{
   1.168 +				temp = node->next;
   1.169 +				delete node;
   1.170 +				node = temp;
   1.171 +			}
   1.172 +			m_Size = 0;
   1.173  		}
   1.174 -		m_Size = 0;
   1.175 -	}
   1.176 -	bool empty()
   1.177 -	{
   1.178 -		return (m_Head->next == NULL);
   1.179 -	}
   1.180 -	T & back()
   1.181 -	{
   1.182 -		return m_Head->prev->obj;
   1.183 -	}
   1.184 -private:
   1.185 -	ListNode *m_Head;
   1.186 -	size_t m_Size;
   1.187 -public:
   1.188 -	class iterator
   1.189 -	{
   1.190 -	friend class List;
   1.191 +		bool empty()
   1.192 +		{
   1.193 +			return (m_Size == 0);
   1.194 +		}
   1.195 +		T & back()
   1.196 +		{
   1.197 +			return m_Head->prev->obj;
   1.198 +		}
   1.199 +	private:
   1.200 +		ListNode *m_Head;
   1.201 +		size_t m_Size;
   1.202  	public:
   1.203 -		iterator()
   1.204 -		{
   1.205 -			m_This = NULL;
   1.206 -		}
   1.207 -		iterator(const List &src)
   1.208 -		{
   1.209 -			m_This = src.m_Head;
   1.210 -		}
   1.211 -		iterator(ListNode *n) : m_This(n)
   1.212 -		{
   1.213 -		}
   1.214 -		iterator(const iterator &where)
   1.215 -		{
   1.216 -			m_This = where.m_This;
   1.217 -		}
   1.218 -		//pre decrement
   1.219 -		iterator & operator--()
   1.220 +		class iterator
   1.221  		{
   1.222 -			if (m_This)
   1.223 -				m_This = m_This->prev;
   1.224 -			return *this;
   1.225 -		}
   1.226 -		//post decrement
   1.227 -		iterator operator--(int)
   1.228 +		friend class List;
   1.229 +		public:
   1.230 +			iterator()
   1.231 +			{
   1.232 +				m_This = NULL;
   1.233 +			}
   1.234 +			iterator(const List &src)
   1.235 +			{
   1.236 +				m_This = src.m_Head;
   1.237 +			}
   1.238 +			iterator(ListNode *n) : m_This(n)
   1.239 +			{
   1.240 +			}
   1.241 +			iterator(const iterator &where)
   1.242 +			{
   1.243 +				m_This = where.m_This;
   1.244 +			}
   1.245 +			//pre decrement
   1.246 +			iterator & operator--()
   1.247 +			{
   1.248 +				if (m_This)
   1.249 +					m_This = m_This->prev;
   1.250 +				return *this;
   1.251 +			}
   1.252 +			//post decrement
   1.253 +			iterator operator--(int)
   1.254 +			{
   1.255 +				iterator old(*this);
   1.256 +				if (m_This)
   1.257 +					m_This = m_This->prev;
   1.258 +				return old;
   1.259 +			}	
   1.260 +			
   1.261 +			//pre increment
   1.262 +			iterator & operator++()
   1.263 +			{
   1.264 +				if (m_This)
   1.265 +					m_This = m_This->next;
   1.266 +				return *this;
   1.267 +			}
   1.268 +			//post increment
   1.269 +			iterator operator++(int)
   1.270 +			{
   1.271 +				iterator old(*this);
   1.272 +				if (m_This)
   1.273 +					m_This = m_This->next;
   1.274 +				return old;
   1.275 +			}
   1.276 +			
   1.277 +			const T & operator * () const
   1.278 +			{
   1.279 +				return m_This->obj;
   1.280 +			}
   1.281 +			T & operator * ()
   1.282 +			{
   1.283 +				return m_This->obj;
   1.284 +			}
   1.285 +			
   1.286 +			T * operator -> ()
   1.287 +			{
   1.288 +				return &(m_This->obj);
   1.289 +			}
   1.290 +			const T * operator -> () const
   1.291 +			{
   1.292 +				return &(m_This->obj);
   1.293 +			}
   1.294 +			
   1.295 +			bool operator != (const iterator &where) const
   1.296 +			{
   1.297 +				return (m_This != where.m_This);
   1.298 +			}
   1.299 +			bool operator ==(const iterator &where) const
   1.300 +			{
   1.301 +				return (m_This == where.m_This);
   1.302 +			}
   1.303 +		private:
   1.304 +			ListNode *m_This;
   1.305 +		};
   1.306 +	public:
   1.307 +		iterator begin() const
   1.308  		{
   1.309 -			iterator old(*this);
   1.310 -			if (m_This)
   1.311 -				m_This = m_This->prev;
   1.312 -			return old;
   1.313 -		}	
   1.314 -		
   1.315 -		//pre increment
   1.316 -		iterator & operator++()
   1.317 +			return iterator(m_Head->next);
   1.318 +		}
   1.319 +		iterator end() const
   1.320 +		{
   1.321 +			return iterator(m_Head);
   1.322 +		}
   1.323 +		iterator erase(iterator &where)
   1.324 +		{
   1.325 +			ListNode *pNode = where.m_This;
   1.326 +			iterator iter(where);
   1.327 +			iter++;
   1.328 +
   1.329 +
   1.330 +			// Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle...
   1.331 +			pNode->prev->next = pNode->next;
   1.332 +			pNode->next->prev = pNode->prev;
   1.333 +
   1.334 +			delete pNode;
   1.335 +			m_Size--;
   1.336 +
   1.337 +			return iter;
   1.338 +		}
   1.339 +
   1.340 +		iterator insert(iterator where, const T &obj)
   1.341  		{
   1.342 -			if (m_This)
   1.343 -				m_This = m_This->next;
   1.344 +			// Insert obj right before where
   1.345 +
   1.346 +			ListNode *node = new ListNode(obj);
   1.347 +			ListNode *pWhereNode = where.m_This;
   1.348 +			
   1.349 +			pWhereNode->prev->next = node;
   1.350 +			node->prev = pWhereNode->prev;
   1.351 +			pWhereNode->prev = node;
   1.352 +			node->next = pWhereNode;
   1.353 +
   1.354 +			m_Size++;
   1.355 +
   1.356 +			return iterator(node);
   1.357 +		}
   1.358 +
   1.359 +	public:
   1.360 +		void remove(const T & obj)
   1.361 +		{
   1.362 +			iterator b;
   1.363 +			for (b=begin(); b!=end(); b++)
   1.364 +			{
   1.365 +				if ( (*b) == obj )
   1.366 +				{
   1.367 +					erase( b );
   1.368 +					break;
   1.369 +				}
   1.370 +			}
   1.371 +		}
   1.372 +		template <typename U>
   1.373 +		iterator find(const U & equ)
   1.374 +		{
   1.375 +			iterator iter;
   1.376 +			for (iter=begin(); iter!=end(); iter++)
   1.377 +			{
   1.378 +				if ( (*iter) == equ )
   1.379 +					return iter;
   1.380 +			}
   1.381 +			return end();
   1.382 +		}
   1.383 +		List & operator =(const List &src)
   1.384 +		{
   1.385 +			clear();
   1.386 +			iterator iter;
   1.387 +			for (iter=src.begin(); iter!=src.end(); iter++)
   1.388 +				push_back( (*iter) );
   1.389  			return *this;
   1.390  		}
   1.391 -		//post increment
   1.392 -		iterator operator++(int)
   1.393 -		{
   1.394 -			iterator old(*this);
   1.395 -			if (m_This)
   1.396 -				m_This = m_This->next;
   1.397 -			return old;
   1.398 -		}
   1.399 -		
   1.400 -		const T & operator * () const
   1.401 -		{
   1.402 -			return m_This->obj;
   1.403 -		}
   1.404 -		T & operator * ()
   1.405 -		{
   1.406 -			return m_This->obj;
   1.407 -		}
   1.408 -		
   1.409 -		T * operator -> ()
   1.410 -		{
   1.411 -			return &(m_This->obj);
   1.412 -		}
   1.413 -		const T * operator -> () const
   1.414 -		{
   1.415 -			return &(m_This->obj);
   1.416 -		}
   1.417 -		
   1.418 -		bool operator != (const iterator &where) const
   1.419 -		{
   1.420 -			return (m_This != where.m_This);
   1.421 -		}
   1.422 -		bool operator ==(const iterator &where) const
   1.423 -		{
   1.424 -			return (m_This == where.m_This);
   1.425 -		}
   1.426 -	private:
   1.427 -		ListNode *m_This;
   1.428  	};
   1.429 -public:
   1.430 -	iterator begin() const
   1.431 -	{
   1.432 -		if (m_Size)
   1.433 -			return iterator(m_Head->next);
   1.434 -		else
   1.435 -			return iterator(m_Head);
   1.436 -	}
   1.437 -	iterator end() const
   1.438 -	{
   1.439 -		return iterator(m_Head);
   1.440 -	}
   1.441 -	iterator erase(iterator &where)
   1.442 -	{
   1.443 -		ListNode *pNode = where.m_This;
   1.444 -		iterator iter(where);
   1.445 -		iter++;
   1.446 -
   1.447 -		//If we are both the head and tail...
   1.448 -		if (m_Head->next == pNode && m_Head->prev == pNode)
   1.449 -		{
   1.450 -			m_Head->next = NULL;
   1.451 -			m_Head->prev = NULL;
   1.452 -		} else if (m_Head->next == pNode) {
   1.453 -			//we are only the first
   1.454 -			pNode->next->prev = m_Head;
   1.455 -			m_Head->next = pNode->next;
   1.456 -		} else if (m_Head->prev == pNode) {
   1.457 -			//we are the tail
   1.458 -			pNode->prev->next = m_Head;
   1.459 -			m_Head->prev = pNode->prev;
   1.460 -		} else {
   1.461 -			//middle unlink
   1.462 -			pNode->prev->next = pNode->next;
   1.463 -			pNode->next->prev = pNode->prev;
   1.464 -		}
   1.465 -
   1.466 -		delete pNode;
   1.467 -		m_Size--;
   1.468 -
   1.469 -		return iter;
   1.470 -	}
   1.471 -public:
   1.472 -	void remove(const T & obj)
   1.473 -	{
   1.474 -		iterator b;
   1.475 -		for (b=begin(); b!=end(); b++)
   1.476 -		{
   1.477 -			if ( (*b) == obj )
   1.478 -			{
   1.479 -				erase( b );
   1.480 -				break;
   1.481 -			}
   1.482 -		}
   1.483 -	}
   1.484 -	template <typename U>
   1.485 -	iterator find(const U & equ)
   1.486 -	{
   1.487 -		iterator iter;
   1.488 -		for (iter=begin(); iter!=end(); iter++)
   1.489 -		{
   1.490 -			if ( (*iter) == equ )
   1.491 -				return iter;
   1.492 -		}
   1.493 -		return end();
   1.494 -	}
   1.495 -	List & operator =(const List &src)
   1.496 -	{
   1.497 -		clear();
   1.498 -		iterator iter;
   1.499 -		for (iter=src.begin(); iter!=src.end(); iter++)
   1.500 -			push_back( (*iter) );
   1.501 -		return *this;
   1.502 -	}
   1.503 -};
   1.504  };	//NAMESPACE
   1.505  
   1.506  #endif //_INCLUDE_CSDM_LIST_H