sourcehook/sh_list.h
author David Anderson <dvander@alliedmods.net>
Thu Sep 27 19:28:05 2007 +0000 (2007-09-27)
branchsourcemm-1.6.0
changeset 356 bbcf8dcb2aa7
parent 347 e82968c21606
permissions -rw-r--r--
removed unnecessary api call
dvander@347
     1
/* ======== SourceMM ========
dvander@347
     2
* Copyright (C) 2004-2007 Metamod:Source Development Team
dvander@347
     3
* No warranties of any kind
dvander@347
     4
*
dvander@347
     5
* License: zlib/libpng
dvander@347
     6
*
dvander@347
     7
* Author(s): David "BAILOPAN" Anderson
dvander@347
     8
* ============================
dvander@347
     9
*/
dvander@347
    10
dvander@347
    11
#ifndef _INCLUDE_SMM_LIST_H
dvander@347
    12
#define _INCLUDE_SMM_LIST_H
dvander@347
    13
dvander@347
    14
#include <new>
dvander@347
    15
#include <malloc.h>
dvander@347
    16
dvander@347
    17
namespace SourceHook
dvander@347
    18
{
dvander@347
    19
dvander@347
    20
	//This class is from CSDM for AMX Mod X
dvander@347
    21
	/*
dvander@347
    22
		A circular, doubly-linked list with one sentinel node
dvander@347
    23
dvander@347
    24
		Empty:
dvander@347
    25
			m_Head = sentinel
dvander@347
    26
			m_Head->next = m_Head;
dvander@347
    27
			m_Head->prev = m_Head;
dvander@347
    28
		One element:
dvander@347
    29
			m_Head = sentinel
dvander@347
    30
			m_Head->next = node1
dvander@347
    31
			m_Head->prev = node1
dvander@347
    32
			node1->next = m_Head
dvander@347
    33
			node1->prev = m_Head
dvander@347
    34
		Two elements:
dvander@347
    35
			m_Head = sentinel
dvander@347
    36
			m_Head->next = node1
dvander@347
    37
			m_Head->prev = node2
dvander@347
    38
			node1->next = node2
dvander@347
    39
			node1->prev = m_Head
dvander@347
    40
			node2->next = m_Head
dvander@347
    41
			node2->prev = node1
dvander@347
    42
	*/
dvander@347
    43
	template <class T>
dvander@347
    44
	class List
dvander@347
    45
	{
dvander@347
    46
	public:
dvander@347
    47
		class iterator;
dvander@347
    48
		friend class iterator;
dvander@347
    49
		class ListNode
dvander@347
    50
		{
dvander@347
    51
		public:
dvander@347
    52
			ListNode(const T & o) : obj(o) { };
dvander@347
    53
			ListNode() { };
dvander@347
    54
			T obj;
dvander@347
    55
			ListNode *next;
dvander@347
    56
			ListNode *prev;
dvander@347
    57
		};
dvander@347
    58
	private:
dvander@347
    59
		// Initializes the sentinel node.
dvander@347
    60
		// BAIL used malloc instead of new in order to bypass the need for a constructor.
dvander@347
    61
		ListNode *_Initialize()
dvander@347
    62
		{
dvander@347
    63
			ListNode *n = (ListNode *)malloc(sizeof(ListNode));
dvander@347
    64
			n->next = n;
dvander@347
    65
			n->prev = n;
dvander@347
    66
			return n;
dvander@347
    67
		}
dvander@347
    68
	public:
dvander@347
    69
		List() : m_Head(_Initialize()), m_Size(0)
dvander@347
    70
		{
dvander@347
    71
		}
dvander@347
    72
		List(const List &src) : m_Head(_Initialize()), m_Size(0)
dvander@347
    73
		{
dvander@347
    74
			iterator iter;
dvander@347
    75
			for (iter=src.begin(); iter!=src.end(); iter++)
dvander@347
    76
				push_back( (*iter) );
dvander@347
    77
		}
dvander@347
    78
		~List()
dvander@347
    79
		{
dvander@347
    80
			clear();
dvander@347
    81
dvander@347
    82
			// Don't forget to free the sentinel
dvander@347
    83
			if (m_Head)
dvander@347
    84
			{
dvander@347
    85
				free(m_Head);
dvander@347
    86
				m_Head = NULL;
dvander@347
    87
			}
dvander@347
    88
		}
dvander@347
    89
		void push_back(const T &obj)
dvander@347
    90
		{
dvander@347
    91
			ListNode *node = new ListNode(obj);
dvander@347
    92
dvander@347
    93
			node->prev = m_Head->prev;
dvander@347
    94
			node->next = m_Head;
dvander@347
    95
			m_Head->prev->next = node;
dvander@347
    96
			m_Head->prev = node;
dvander@347
    97
dvander@347
    98
			m_Size++;
dvander@347
    99
		}
dvander@347
   100
		size_t size() const
dvander@347
   101
		{
dvander@347
   102
			return m_Size;
dvander@347
   103
		}
dvander@347
   104
dvander@347
   105
		void clear()
dvander@347
   106
		{
dvander@347
   107
			ListNode *node = m_Head->next;
dvander@347
   108
			ListNode *temp;
dvander@347
   109
			m_Head->next = m_Head;
dvander@347
   110
			m_Head->prev = m_Head;
dvander@347
   111
dvander@347
   112
			// Iterate through the nodes until we find g_Head (the sentinel) again
dvander@347
   113
			while (node != m_Head)
dvander@347
   114
			{
dvander@347
   115
				temp = node->next;
dvander@347
   116
				delete node;
dvander@347
   117
				node = temp;
dvander@347
   118
			}
dvander@347
   119
			m_Size = 0;
dvander@347
   120
		}
dvander@347
   121
		bool empty() const
dvander@347
   122
		{
dvander@347
   123
			return (m_Size == 0);
dvander@347
   124
		}
dvander@347
   125
		T & back()
dvander@347
   126
		{
dvander@347
   127
			return m_Head->prev->obj;
dvander@347
   128
		}
dvander@347
   129
	private:
dvander@347
   130
		ListNode *m_Head;
dvander@347
   131
		size_t m_Size;
dvander@347
   132
	public:
dvander@347
   133
		class iterator
dvander@347
   134
		{
dvander@347
   135
		friend class List;
dvander@347
   136
		public:
dvander@347
   137
			iterator()
dvander@347
   138
			{
dvander@347
   139
				m_This = NULL;
dvander@347
   140
			}
dvander@347
   141
			iterator(const List &src)
dvander@347
   142
			{
dvander@347
   143
				m_This = src.m_Head;
dvander@347
   144
			}
dvander@347
   145
			iterator(ListNode *n) : m_This(n)
dvander@347
   146
			{
dvander@347
   147
			}
dvander@347
   148
			iterator(const iterator &where)
dvander@347
   149
			{
dvander@347
   150
				m_This = where.m_This;
dvander@347
   151
			}
dvander@347
   152
			//pre decrement
dvander@347
   153
			iterator & operator--()
dvander@347
   154
			{
dvander@347
   155
				if (m_This)
dvander@347
   156
					m_This = m_This->prev;
dvander@347
   157
				return *this;
dvander@347
   158
			}
dvander@347
   159
			//post decrement
dvander@347
   160
			iterator operator--(int)
dvander@347
   161
			{
dvander@347
   162
				iterator old(*this);
dvander@347
   163
				if (m_This)
dvander@347
   164
					m_This = m_This->prev;
dvander@347
   165
				return old;
dvander@347
   166
			}	
dvander@347
   167
			
dvander@347
   168
			//pre increment
dvander@347
   169
			iterator & operator++()
dvander@347
   170
			{
dvander@347
   171
				if (m_This)
dvander@347
   172
					m_This = m_This->next;
dvander@347
   173
				return *this;
dvander@347
   174
			}
dvander@347
   175
			//post increment
dvander@347
   176
			iterator operator++(int)
dvander@347
   177
			{
dvander@347
   178
				iterator old(*this);
dvander@347
   179
				if (m_This)
dvander@347
   180
					m_This = m_This->next;
dvander@347
   181
				return old;
dvander@347
   182
			}
dvander@347
   183
			
dvander@347
   184
			const T & operator * () const
dvander@347
   185
			{
dvander@347
   186
				return m_This->obj;
dvander@347
   187
			}
dvander@347
   188
			T & operator * ()
dvander@347
   189
			{
dvander@347
   190
				return m_This->obj;
dvander@347
   191
			}
dvander@347
   192
			
dvander@347
   193
			T * operator -> ()
dvander@347
   194
			{
dvander@347
   195
				return &(m_This->obj);
dvander@347
   196
			}
dvander@347
   197
			const T * operator -> () const
dvander@347
   198
			{
dvander@347
   199
				return &(m_This->obj);
dvander@347
   200
			}
dvander@347
   201
			
dvander@347
   202
			bool operator != (const iterator &where) const
dvander@347
   203
			{
dvander@347
   204
				return (m_This != where.m_This);
dvander@347
   205
			}
dvander@347
   206
			bool operator ==(const iterator &where) const
dvander@347
   207
			{
dvander@347
   208
				return (m_This == where.m_This);
dvander@347
   209
			}
dvander@347
   210
		private:
dvander@347
   211
			ListNode *m_This;
dvander@347
   212
		};
dvander@347
   213
	public:
dvander@347
   214
		iterator begin() const
dvander@347
   215
		{
dvander@347
   216
			return iterator(m_Head->next);
dvander@347
   217
		}
dvander@347
   218
		iterator end() const
dvander@347
   219
		{
dvander@347
   220
			return iterator(m_Head);
dvander@347
   221
		}
dvander@347
   222
		iterator erase(iterator &where)
dvander@347
   223
		{
dvander@347
   224
			ListNode *pNode = where.m_This;
dvander@347
   225
			iterator iter(where);
dvander@347
   226
			iter++;
dvander@347
   227
dvander@347
   228
dvander@347
   229
			// Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle...
dvander@347
   230
			pNode->prev->next = pNode->next;
dvander@347
   231
			pNode->next->prev = pNode->prev;
dvander@347
   232
dvander@347
   233
			delete pNode;
dvander@347
   234
			m_Size--;
dvander@347
   235
dvander@347
   236
			return iter;
dvander@347
   237
		}
dvander@347
   238
dvander@347
   239
		iterator insert(iterator where, const T &obj)
dvander@347
   240
		{
dvander@347
   241
			// Insert obj right before where
dvander@347
   242
dvander@347
   243
			ListNode *node = new ListNode(obj);
dvander@347
   244
			ListNode *pWhereNode = where.m_This;
dvander@347
   245
			
dvander@347
   246
			pWhereNode->prev->next = node;
dvander@347
   247
			node->prev = pWhereNode->prev;
dvander@347
   248
			pWhereNode->prev = node;
dvander@347
   249
			node->next = pWhereNode;
dvander@347
   250
dvander@347
   251
			m_Size++;
dvander@347
   252
dvander@347
   253
			return iterator(node);
dvander@347
   254
		}
dvander@347
   255
dvander@347
   256
	public:
dvander@347
   257
		void remove(const T & obj)
dvander@347
   258
		{
dvander@347
   259
			iterator b;
dvander@347
   260
			for (b=begin(); b!=end(); b++)
dvander@347
   261
			{
dvander@347
   262
				if ( (*b) == obj )
dvander@347
   263
				{
dvander@347
   264
					erase( b );
dvander@347
   265
					break;
dvander@347
   266
				}
dvander@347
   267
			}
dvander@347
   268
		}
dvander@347
   269
		template <typename U>
dvander@347
   270
		iterator find(const U & equ) const
dvander@347
   271
		{
dvander@347
   272
			iterator iter;
dvander@347
   273
			for (iter=begin(); iter!=end(); iter++)
dvander@347
   274
			{
dvander@347
   275
				if ( (*iter) == equ )
dvander@347
   276
					return iter;
dvander@347
   277
			}
dvander@347
   278
			return end();
dvander@347
   279
		}
dvander@347
   280
		List & operator =(const List &src)
dvander@347
   281
		{
dvander@347
   282
			clear();
dvander@347
   283
			iterator iter;
dvander@347
   284
			for (iter=src.begin(); iter!=src.end(); iter++)
dvander@347
   285
				push_back( (*iter) );
dvander@347
   286
			return *this;
dvander@347
   287
		}
dvander@347
   288
	};
dvander@347
   289
};	//NAMESPACE
dvander@347
   290
dvander@347
   291
#endif //_INCLUDE_CSDM_LIST_H